/* equations.c
 *
 * compilation:
 * 	gcc -o equations equations.c
 * usage:
 * 	equations base n_digits
 * example:
 * 	equations 5 4
 * 	...
 * 	124 a_0 + 23 a_1 + 3 a_2 - 1 a_3 = 0
 * 	123 a_0 + 22 a_1 + 1 a_2 - 3 a_3 = 0
 * 	121 a_0 + 19 a_1 - 2 a_2 - 7 a_3 = 0
 * 	117 a_0 + 13 a_1 - 9 a_2 - 14 a_3 = 0
 * 	110 a_0 + 2 a_1 - 22 a_2 - 28 a_3 = 0
 * 	96 a_0 - 19 a_1 - 47 a_2 - 55 a_3 = 0
 * 	69 a_0 - 60 a_1 - 95 a_2 - 107 a_3 = 0
 * 	17 a_0 - 139 a_1 - 188 a_2 - 207 a_3 = 0
 *
 * 	les solutions (4 chiffres en base 5) sont :
 * 	18      154      is a 5_Keith number  [ 9 ] 1104_5
 * 	19      221      is a 5_Keith number  [ 9 ] 1341_5
 * 	20      483      is a 5_Keith number  [ 10 ] 3413_5
 *
 * 	en effet on les obtient ainsi :
 * 	110 a_0 + 2 a_1 - 22 a_2 - 28 a_3 = 0
 * 	110*1 + 2*1 - 22*0 -28*4 = 0    correspond à  1104_b5
 * 	110*1 + 2*3 - 22*4 -28*1 = 0    correspond à  1341_b5
 *
 * 	96 a_0 - 19 a_1 - 47 a_2 - 55 a_3 = 0
 * 	96*3 - 19*4 - 47*1 - 55*3 = 0   correspond à  3413_5
 * 	
 * */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXI 1000

main (int argc, char *argv[]) {
	int i,j,n, b;
	long long p[MAXI], tab[MAXI][MAXI];
	if(argc<3) {
		printf("usage : %s base n_digits\n"
			"exemple : %s 10 3\n",argv[0],argv[0]);
		return 0;
	}
	n = atoi(argv[2]);
	b = atoi(argv[1]);
	printf("b=%d n=%d\n\n",b, n);

	for(i=1,p[0]=1LL;i<=n;i++) p[i] = p[i-1]*b;
	for(i=0;i<n;i++) {
		for(j=0;j<n;j++) 
			tab[i][j]=0LL;
		tab[i][i]=1ULL;
		tab[i][n]=1ULL;
		for(j=n+1;j<MAXI && tab[i][j-1]<p[n];j++) 
			tab[i][j]=2*tab[i][j-1]-tab[i][j-n-1];
	}
	for(i=0;i<n;i++) {
		for(j=0;j<MAXI && tab[i][j]<p[n];j++)
			printf("%Ld ",tab[i][j]);
		printf("\n");
	}
	printf("\n");
        for(j=n+1;j<MAXI && tab[n-1][j] < p[n] && p[n-1]>=tab[0][j];j++) {
	  for(i=0;i<n;i++) {
		  printf("(%Ld - %Ld) a_%d ",p[n-1-i],tab[i][j],i);
		  if(i<n-1) printf("+ ");
		  else printf("= 0\n");
	  }
	}
	printf("\n");
	/* p[n-1]-tab[0][j] + 1 - tab[n-1][j] */
	/* p[n-1]-tab[0][j] - (p[n-2]-tab[1][j])*/
	/* && (b-1)*(p[n-1]-tab[0][j]) + (p[n-2]-tab[1][j])>=0 */
	for(j=n+1;      j<MAXI 
			&& tab[n-1][j] < p[n] 
			&& p[n-1]-tab[0][j]>0 
			&& (b-1)*(p[n-1]-tab[0][j]) + (p[n-2]-tab[1][j])>=0
			;j++) {
#ifdef REDUIT
		// if(p[n-1]-tab[0][j] + (b-1)*(1 - tab[n-1][j])<=0) {
#endif
		for(i=0;i<n;i++) {
			if(p[n-1-i]-tab[i][j]>0) {
			  if(i>0) printf("+ ");
			  printf("%Ld a_%d ",p[n-1-i]-tab[i][j],i);
			} else {
			  printf("- %Ld a_%d ",-p[n-1-i]+tab[i][j],i);
			}
			if(i==n-1)
			  printf("= 0\n");
		}
#ifdef REDUIT
	//	}
#endif
	}
	return 0;
	
}