Project Euler 130: Finding composite values, n, for which n−1 is divisible by the length of the smallest repunits that divide it.

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.

Posted by Kristian

3 comments

Jean-Marie Hachey
January 10, 2013

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

jeras
August 12, 2014

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:

#! /usr/bin/env python

import itertools as it
from primes import primes

def deceptive_nonprimes():
    # See: http://oeis.org/A000864
    p = 7
    for q in it.dropwhile(lambda n: n &lt; 11, primes()):
        for n in xrange(p+2, q-1, 2):
            if n%5 and pow(10, n-1, 9*n) == 1:
                yield n
        p = q

def solve(n=25):
    return sum(it.islice(deceptive_nonprimes(), n))

if __name__ == '__main__':
    print solve()

On the other hand, if you only have a good is_prime() method (Miller-Rabin or similar), then the generator could look like this:

def deceptive_nonprimes():
    # See: http://oeis.org/A000864
    for n in it.count(9, 2):
        if n%5 and not is_prime(n) and pow(10, n-1, 9*n) == 1:
            yield n

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.

Carl Appellof
August 18, 2018

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.

Leave a Reply