How to solve the Project Euler large repunit factors problem

Project Euler is a set of mathematical problems that focus not only on your mathematical insights, but also put your problem-solving and programming skills to the test.

The problem

Project Euler Large Repunit Factors is Problem 132 which presents us with the following problem:

“A number consisting entirely of ones is called a repunit. We shall define R(k)R(k) to be a repunit of length kk. For example, R(10)=1111111111R(10) = 1111111111 =11×41×271×9091=11 × 41 × 271 × 9091, and the sum of these prime factors is 94149414. Find the sum of the first forty prime factors of R(109)R(10^9).”

Please refer to this link for the source of Problem 132.

Approach to solution

Repunit numbers are numbers comprised of multiple ones and can be represented as shown in diagram below:

To solve the given problem, we would need to think of a method to represent R(K)R(K) in terms of a factor of a prime number.

This can be done by assuming XX as a prime number. Now, we can simply take the modulo of R(K)R(K). If the resultant value is 00, XX is a prime factor.

For this problem, we run a loop to find the first 4040 prime factors that are possible of our repunit number (i.e. R(109)R(10^9)) and add them up to find the sum.

Code

Firstly, we can make a list to filter out prime numbers from a simple function. This can also be done through inbuilt python libraries. Some of these libraries include primepy and sympy.

The code below produces prime numbers from 2−200002 - 20000:

primes = []
# for loop to create a prime number list for numbers 2 - 20000
for n in range (2, 20000 + 1):
    for i in range (2, n):
        if (n % i) == 0:
                break
    else:
        primes.append(n)
print(primes)

Once the list of prime numbers is ready, you can simply run the list in a function to check if it is a factor of our repunit number.

The code below executes the following and adds up the first 40 factors to output the results:

sum = 0

n = 0

k = 10**9 # repunit number for which the problem needs to be solved.

count = 0



# loops for the first 40 factors

while count < 40:

    # mod to check if the prime number is a factor and sum up in the result

    if (10 ** k % (9 * primes[n]) == 1):

        sum = sum + primes[n]

        count += 1



    n = n + 1
Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
YouTubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)