Another problem I came across while browsing the EIS for sequences that needed more terms, is a problem with balanced bases A049364. What is the smallest number that is digitally balanced in all bases 2, 3, ... n?
I wrote a routine that tested whether a number was balanced, and most importantly if it is not it increments the number to a point where it is closer to one that is! I found a base 5 balanced number in seconds, but then discovered subsequent solutions must be EXTREMELY large! Here are all the known solutions so far:
#include <math.h>
BOOL IsBalanced(int b, ZZ &n) {
double ln = log(n); // natural log
// log_b(n) = ln(n)/ln(b)
int lb = (int)(ln / log(b));
// Since it must be balanced, base b digits should be
// multiples of base...
if(lb % b != (b-1)) {
while( (lb % b) != (b-1) ) lb++;
// set n = b^lb;
power(n, b, lb);
// could improve this by adding 0,0,0,1,1,1,etc...
return FALSE;
}
ZZ nCopy = n;
int *hit = new int [b];
memset(hit, 0, b * sizeof(int));
// Early break-out...
ZZ x;
power(x, b, lb);
for(int z=lb; z>1; z--) {
int r = Long(nCopy/x) % b;
hit[r]++;
if(hit[r] > (lb+1)/b) {
n -= n%x;
n += x;
delete [] hit;
return FALSE;
}
nCopy %= x;
x /= b;
}
nCopy = n;
memset(hit, 0, b * sizeof(int));
while(nCopy > 0) {
hit[nCopy%b]++;
nCopy /= b;
}
int target = (lb+1)/b;
for(int i=0; i<b; i++)
if(hit[i] != target)
break;
delete [] hit;
if(i<b) return FALSE;
return TRUE;
}
void BalanceTest(void) {
ZZ i;
i = 500; // starting point
int targetBal = 6; // target balance base...
for(;;) {
cout << "i=" << i << " \r" << flush;
if(kbhit()) break;
int gotit = 1;
if(i%2 ==0) {
for(int c=2; c<=targetBal; c++) {
if(!IsBalanced(c, i)) {
gotit = 0;
break;
}
}
}
else {
for(int c=targetBal; c>=2; c--) {
if(!IsBalanced(c, i)) {
gotit = 0;
break;
}
}
}
if(gotit) {
cout << targetBal << "bal=" << i << " \n" << flush;
break;
}
// Every now and then check to make sure i
// is possible for middle bases and adjust
// accordingly...
if(rand()%10 == 0) {
IsBalanced(3+rand()%(targetBal-3), i);
}
i++;
}
cout << "Last i = " << i << " \n" << flush;
}