/* Keith.c (Brute force) Determination of Keith Numbers in every base
 *          Version GMP (great integers)
 *          
 * 18 juillet 2004 Jean-Paul Davalan jpdvl@wanadoo.fr
 * 
 * Copyright (C) 2004  Jean-Paul Davalan
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * LINKS:
 * ======
 * 
 * GPL at GNU.ORG
 * --------------
 * http://www.gnu.org/copyleft/gpl.html
 * 
 * The On-Line Encyclopedia of Integer Sequences
 * ---------------------------------------------
 * http://www.research.att.com/~njas/sequences/index_b.html
 * http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A007629
 * 
 * Mike Keith's World of Words & Numbers
 * -------------------------------------
 * http://users.aol.com/s6sj7gt/mikehome.htm#toc
 * Keith Numbers
 * http://users.aol.com/s6sj7gt/mikekeit.htm
 * Determination of all Keith Numbers up to 10^19
 * http://users.aol.com/s6sj7gt/keithnum.htm
 * 
 * Ken Shirrif homepage
 * --------------------
 * http://www.righto.com/
 * http://www.righto.com/papers/
 * K. Shirriff, ``Computing Replicating Fibonacci Digits,'' 
 * Journal of Recreational Mathematics, 26(3), July 1994, 191-193.
 * http://www.righto.com/papers/fib.ps
 * 
 * compilation:
 * ============
 *   gcc -O2 -o keith keith.c -lgmp
 *
 * usage:
 * ======
 *   keith [ base [ n0 ]]
 *   
 * example:  hexadecimals
 * ========
 * keith 16
 * 1       23       is a 16_Keith number  [ 4 ] 17_16
 * 2       31       is a 16_Keith number  [ 3 ] 1f_16
 * 
 * 31(base 10) = 1f(base 16) where f(base 16) = 15(base 10)
 * a0=1 a1=15 a2=16 a3=31       [ 3 ] means a3=1f_16
 *
 * 10      250      is a 16_Keith number  [ 7 ] fa_16
 * 
 * a0='f'=15 a1='a'=10, 25, 35, 60, 95, 155, a7='fa'=250
 * 
 * */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>

#define MAX 1000

int main(int argc, char *argv[])
{
    int base = 10, pos, pos0, cnt = 0, cur, i, l, k;
    //char st[MAX], *p;
    mpz_t a, n, n0, m, tot, tab[MAX];
    for (i = 0; i < MAX; i++)
	mpz_init_set_ui(tab[i], 0);
    mpz_init(n0);
    mpz_init(tot);
    mpz_init(a);
    mpz_init(n);
    mpz_init(m);
    if (argc == 1) {		// base 10 
	mpz_set_ui(n0, 10);
    } else if (argc > 1) {	//  base 
	base = atoi(argv[1]);
	if (argc == 2)
	    mpz_set_ui(n0, base);
	else
	    mpz_set_str(n0, argv[2], 10);
    }
    mpz_init_set(n, n0);
    for (;; mpz_add_ui(n, n, 1)) {
	mpz_set_ui(tot, 0);
	p = mpz_get_str(st, base, n);
	l = strlen(st);
	l = strlen(p);
	//mpz_set(m,n);
	//for(l=0; mpz_cmp_ui(m, 0) != 0; l++) mpz_fdiv_q_ui(m,m,base);    
	mpz_set(m, n);
	for (k = l - 1; mpz_cmp_ui(m, 0) != 0; k--) {
	    mpz_fdiv_qr_ui(m, tab[k], m, base);
	    mpz_add(tot, tot, tab[k]);
	}
	mpz_set(tab[l], tot);
	for (pos0 = 0, pos = l, cur = l + 1;
	     mpz_cmp(tab[pos], n) < 0;
	     cur = (cur++) % MAX, pos = (pos++) % MAX, pos0 =
	     (pos0++) % MAX) {
	    mpz_mul_2exp(tab[cur], tab[pos], 1);
	    mpz_sub(tab[cur], tab[cur], tab[pos0]);
	}
	if (mpz_cmp(tab[(cur - 1 + MAX) % MAX], n) == 0) {
	    cnt++;
	    printf("%d\t", cnt);
	    mpz_out_str(stdout, 10, n);
	    printf("\t is a %d_Keith number ", base);
	    printf(" [ %d ] ", pos);
	    if (base != 10) {
		mpz_out_str(stdout, base, n);
		printf("_%d", base);
	    }
	    printf("\n");
	    fflush(stdout);
	}
    }
    return 0;
}