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.
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 to be a repunit of length . For example, , and the sum of these prime factors is . Find the sum of the first forty prime factors of .”
Please refer to this link for the source of Problem 132.
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 in terms of a factor of a prime number.
This can be done by assuming as a prime number. Now, we can simply take the modulo of . If the resultant value is , is a prime factor.
For this problem, we run a loop to find the first prime factors that are possible of our repunit number (i.e. ) and add them up to find the sum.
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
The code below produces prime numbers from :
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
View all Courses