Problem #132 says:

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k.

For example, R(10) = 1111111111 = 11×41×271×9091, and the sum of these prime factors is 9414.

Find the sum of the first forty prime factors of R(10^(9)).

To solve this problem we take the number and rearrange it a bit, then check for primes that fit the formula runs in about 12 seconds.

Solution in Python. Requires the RabinMiller.py file.

Problem132.py

from RabinMiller import *
from time import *

t0 = time()
def GeoSum (a,  n,  c):
    if (n == 1):
        return 1
    if (n==2):
        return (1+a)%c
    ret = ((GeoSum(a, n/2, c)%c)*((1+pow(a, n/2, c))%c))%c
    if (n&1):
        ret = (ret+pow(a, n-1, c))%c
    return ret

sum = 0
count = 0
i = 3
while (count <40):
    if (MillerRabin(i) and not GeoSum(10, 10**9,  i)):
        count = count + 1
        sum = sum + i
        print count, " divids by ", i
    i = i + 2
print sum
print time() - t0

RabinMiller.py

import sys
import random

def toBinary(n):
  r = []
  while (n > 0):
    r.append(n % 2)
    n = n / 2
  return r

def test(a, n):
  """
  test(a, n) -> bool Tests whether n is complex.

  Returns:
    - True, if n is complex.
    - False, if n is probably prime.
  """
  b = toBinary(n - 1)
  d = 1
  for i in xrange(len(b) - 1, -1, -1):
    x = d
    d = (d * d) % n
    if d == 1 and x != 1 and x != n - 1:
      return True # Complex
    if b[i] == 1:
      d = (d * a) % n
  if d != 1:
    return True # Complex
  return False # Prime

def MillerRabin(n, s = 3):
  """
    MillerRabin(n, s = 1000) -> bool Checks whether n is prime or not

    Returns:
      - True, if n is probably prime.
      - False, if n is complex.
  """
  for j in xrange(1, s + 1):
    a = random.randint(1, n - 1)
    if (test(a, n)):
      return False # n is complex
  return True # n is prime