Problem 130 of Project Euler is a continuation of problem 129, so if you have already solved that this one should be pretty easy. It reads
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(6) = 111111.
Given that n is a positive integer and GCD(n, 10) = 1, it can be shown that there always exists a value, k, for which R(k) is divisible by n, and let A(n) be the least such value of k; for example, A(7) = 6 and A(41) = 5.
You are given that for all primes, p > 5, that p – 1 is divisible by A(p). For example, when p = 41, A(41) = 5, and 40 is divisible by 5.
However, there are rare composite values for which this is also true; the first five examples being 91, 259, 451, 481, and 703.
Find the sum of the first twenty-five composite values of n for which
GCD(n, 10) = 1 and n – 1 is divisible by A(n).
If you have already solved Problem 129 as we have, this one can be solved pretty easily. We already have a function that will give us A(n), so we can just brute force our way through the problem calculating check if n-1 is divisible by A(n) and n is not a prime. We can do this with the following code
int limit = 25; int found = 0; int n = 1; int result = 0; while (found < limit) { n++; if (IsPrime(n)) continue; int a = A(n); if (a != 0 && ((n - 1) % a == 0)) { result += n; found++; } }
This gives me the following solution in less than 50ms
The sum of the first 25 of these composite numbers is 149253
I know this is a short post. I think the majority of the ideas and insight you need to solve this problem comes from Problem 129. From the discussion on the solution forum, I can see that there is much more to this problem than what I have used in the solution. However, I have not used those ideas. I will suggest that you check them out though.
You can download the full source code here.
Project Euler Problem 130:
Results and comments
___
Table 1
Project Euler 130:
Finding composite values, n, for which n−1 is divisible by the length of the smallest repunits that divide it.
___
Table 1 shows the first 25 composite values, n, for which n−1 is divisible by the length of the smallest repunits that divide it.
http://img35.imageshack.us/img35/4307/pe130table1v2.jpg
As predicted, the sum of the composite values equals 149253.
All these repunits are included between [(10^1 – 1)/9] and [(10^100 -1)/9] with two exceptions : R(330) : [(10^330 – 1)/9] and R(198) : [(10^198 – 1)/9] (Entries 15 and 20).
Numerous sequences of factors of « a » are present in many repunits
with the exceptions of Entries 15, 20, 23 and 25.
___
Figure 1 shows the evolution of the composite values, n, with the increase in the sequence of natural numbers.
http://img19.imageshack.us/img19/2016/pe130figone.jpg
______
Sources :
PE130: algorithm
http://www.mathblog.dk/files/euler/Problem130.cs
Microsoft Visual C# 2010 Express
Factorizations of 11…11 (Repunit)
http://homepage2.nifty.com/m_kamada/math/11111.htm
I originally implemented a solution in python similar to yours, but it took about 1.3 seconds. There is actually a much faster implementation based on the idea that if n-1 is divisible by A(n), then R(n-1) is divisible by n.
Entering “91, 259, 451, 481, 703” into the On-line Encylopedia of Integer Sequences, reveals the Deceptive nonprimes sequence, A000864.
If you have a good infinite prime generator [mine is called primes()], then translating the PARI/GP code for generating sequence A000864 yields something like:
On the other hand, if you only have a good is_prime() method (Miller-Rabin or similar), then the generator could look like this:
The first implementation runs in 20ms, and the is_prime() based version in 31ms, as opposed to 1.3s for a solution similar to the one you gave.
Wow! In C++, my implementation using A(n) took 63ms to come up with the result. Not bad.
The implementation using a modular exponentiation function took only 2.25 ms !
Great insight.