/*
 Calculator for OEIS A106372
 Copyright (C) 2017 Michael Gottlieb
*/

#include <fstream>
#include <iostream>
#include <time.h>

// define BASE to n to compute a106372(n)
#ifndef BASE
#define BASE 30
#endif

// does the base-b representation of number contain a 0?
int hasZeroInBase(long long number, int b) {
	long long copy = number;
	while (copy >= b) {
		if (copy % b == 0) {
			return 1;
		}
		copy /= b;
	}
	return 0;
}

// does the base-b representation of number contain a 0 (except at the end)?
int hasZeroInBaseExceptEnd(long long number, int b) {
	return hasZeroInBase(number/b, b);
}

// get the next base-b representation of number with a 0
long long getNextWithZero(long long number, int b) {
	// if number contains a zero except at the end, add 1
	if (hasZeroInBaseExceptEnd(number, b)) {
		return number + 1;
	// else, add enough to end in a zero
	} else {
		return number + (b - (number % b));
	}	
}

// g++ a106372.cpp -o a106372.exe -Wall -O3
int main(int argc, char *argv[]) {
	std::cout << "Base is " << BASE << "\n";
	clock_t startTime = clock();
	
	// set iterator_0 and iterator_1 to a larger value to start there
	long long iterator_0 = 0LL;
	long long iterator_1 = 0LL;
	iterator_1 = getNextWithZero(iterator_1, BASE - 2);
	
	// output a progress indicator every interval of this length
	long long progressAmount = 10000000000LL;
	long long nextProgress = 0LL;
	while (nextProgress > progressAmount) {
		nextProgress += progressAmount;
	}
	
	while (1) {
		while (iterator_0 < iterator_1) {
			iterator_0 = getNextWithZero(iterator_0, BASE-1);
		}
		while (iterator_1 < iterator_0) {
			iterator_1 = getNextWithZero(iterator_1, BASE-2);
		}
		if (iterator_0 == iterator_1) {
			// output progress
			if (iterator_0 > nextProgress) {
				std::cout << "Progress: " << nextProgress << "\n" << std::flush;
				nextProgress += progressAmount;
			}
			// check that this number has zeros in bases < BASE-2
			for (int i=BASE-3; i>=2; i--) {
				if (!hasZeroInBase(iterator_0, i)) {
					iterator_1 = getNextWithZero(iterator_1, BASE-2);
					break;
				}
			}
			if (iterator_0 == iterator_1) {
				iterator_1 = getNextWithZero(iterator_1, BASE-2);
				if (hasZeroInBase(iterator_0, BASE)) {
					// not a value for a(BASE), since it has a 0 in that base, but a possible value for a(BASE+k) (if it is the smallest such)
					int nextNonZeroBase = BASE;
					for (int i=BASE; i<=1000; i++) {
						if (!hasZeroInBase(iterator_0, i)) {
							nextNonZeroBase = i;
							break;
						}
					}
					std::cout << "Almost: " << iterator_0 << " (Possible value for a(" << nextNonZeroBase << "). Time: " << (double(clock() - startTime) / (double)CLOCKS_PER_SEC) << "s)\n" << std::flush;
				} else {
					// Found a(BASE)
					std::cout << "a(" << BASE << ") = " << iterator_0 << ". Time: " << (double(clock() - startTime) / (double)CLOCKS_PER_SEC) << "s.\n" << std::flush;
					break;
				}
			}
		}
	}
	
	return 0;
}