Project Euler 130: Composites with prime repunit property

Problem Description

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 minus 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).

Analysis

Asking if n-1 is divisible by A(n) is the same as asking if R(n-1) is divisible by n. We use the Python pow() function to create a rep unit of n-1 digits by dividing 10**(n-1) by 9 and then by n. In this case we use just one step and mod it by 9*n and check for a 1 remainder.

Project Euler 130 Solution

Runs < 0.03 seconds in Python.

from Euler import is_prime

dnp = set()    # set of deceptive non-primes
L = 25
n = 91    # start with first valid n given in the problem description

while len(dnp) < L:
    if not is_prime(n) and pow(10, n-1, 9*n) == 1:
        dnp.add(n)
    n += 2

print "Project Euler 130 Solution =", sum(dnp)

Comments

• Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A000864: Deceptive nonprimes: composite numbers n such that n divides the repunit R_{n-1}.
• Function is_prime is listed in Common Functions and Routines for Project Euler