This was a tough one mathematics wise. R(10^9) is way way way too large for any computer to handle (it’s a billion digits long). So, I had to think more creatively.
I found on Wolfram MathWorld that the formul for a base 10 repunit is (10^n - 1)/ (10 - 1) where n is the number of concatenated 1’s. This means, R(10^9)’s factors must be the factors of (10^(a billion) - 1).
After doing a little more research, and from just looking at the lists of prime factors of small values of R(n), I discovered that all R(k) are divisors of R(n) where k’s are all the divisors of n. I used this to make a list of all the divisors of R(10^9).
from itertools import *
def R(k):
n = '1'*k
return int(n)
def isprime(n):
if n == 2:
return True
elif n < 2 or n%2 == 0:
return False
else:
for i in range(3, int(n**0.5 + 1), 2):
if n%i == 0: return False
return True
def nextprime(n):
if n < 2:
return 2
elif n == 2:
return 3
else:
while True:
n += 2
if isprime(n) == True:
return n
def primefactors(n):
num = n
fact = []
p = 1
while n != 1:
p = nextprime(p)
while n%p == 0:
fact.append(p)
n /= p
if p > (2*10**5) and n != 1:
break
return sorted(fact)
def factors(n):
factorss = primefactors(n)
fact = set()
for length in range(1, len(factorss)):
for num in combinations(factorss, length):
number = 1
for n in num:
number *= n
fact.add(number)
return sorted(list(fact))
n = 10**9
fact = set()
humbug = False
for r in factors(n):
if humbug == True or len(fact) > 40:
break
try:
fact |= set(primefactors(R(r)))
except:
humbug = True
print r, len(fact)
fact = sorted(list(fact))
print fact
print sum(fact[:40])