Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

project euler
repunit
python
communitycreator

How to solve the Project Euler large repunit factors problem

Irzum Jafri

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 2200002 - 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)
Code to produce list of primes from 2 - 20000

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
Project Euler Problem 132 Solution

RELATED TAGS

project euler
repunit
python
communitycreator
RELATED COURSES

View all Courses

Keep Exploring