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 lengthk; for example, R(6) = 111111.

Given thatnis 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 byn, and let A(n) be the least such value ofk; for example, A(7) = 6 and A(41) = 5.

You are given that for all primes,p> 5, thatp– 1 is divisible by A(p). For example, whenp= 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 ofnfor which

GCD(n, 10) = 1 andn– 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.