## 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

*Project Euler 130 Solution last updated*

## Discussion

## No comments yet.