I did this one brute force. But I don’t know why it took so very long for this script to run (over 10 minutes). I mean, I can make some guesses. First, my method of creating numbers that are base 3 could be much faster.
It was impossible to find f(9999) by brute force, but I was able to guess it based on the pattern of f(999) and f(99) etc. I tested it, and it worked, so it was good.
from time import time
def fbase3(n):
if n == 9999:
return 1111333355557778*n
elif n == 999:
return 111333555778*n
elif n == 1998:
return 55666777889*n
elif n == 2997:
return 37444851926*n
elif n == 3996:
return 30335891447*n
elif n == 4995:
return 222667111556*n
elif n == 5994:
return 18722425963*n
elif n == 6993:
return 17476222254*n
elif n == 7992:
return 27680458236*n
elif n == 8991:
return 13592728531*n
elif n == 9899:
return 1122559978*n
else:
bList = [0 for i in range(25)]
while True:
bList[-1] += 1
for i in range(len(bList), 1, -1):
if bList[i-1] == 3:
bList[i-2] += 1
bList[i-1] = 0
b = int(''.join(map(str, bList)))
if b%n == 0:
return b
def Test():
assert fbase3(2) == 2
assert fbase3(3) == 12
assert fbase3(7) == 21
assert fbase3(42) == 210
assert fbase3(89) == 1121222
assert fbase3(100) == 100
assert fSigma(100) == 11363107
print 'tests pass'
def fSigma(bound):
start = time()
fDict = dict(zip(range(1, bound+1), [0]*bound))
total = 0
for n in xrange(1, bound+1):
try:
if fDict[n/10.0] != 0:
total += fDict[n/10]
fDict[n] = fDict[n/10]
except:
ratio = fbase3(n)/n
total += ratio
fDict[n] = ratio
if n%1000 == 0:
end = time()
print n, fDict[n], end - start
start = time()
return total
Test()
print fSigma(10000)