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)$ 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)$.”

### 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)$ in terms of a factor of a prime number.

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

For this problem, we run a loop to find the first $40$ prime factors that are possible of our repunit number (i.e. $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 - 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

CONTRIBUTOR

Irzum Jafri
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time