Repunit Nonfactors

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$.
Let us consider repunits of the form $R(10^n)$.
Although $R(10)$, $R(100)$, or $R(1000)$ are not divisible by $17$, $R(10000)$ is divisible by $17$. Yet there is no value of $n$ for which $R(10^n)$ will divide by $19$. In fact, it is remarkable that $11$, $17$, $41$, and $73$ are the only four primes below one-hundred that can be a factor of $R(10^n)$.
Find the sum of all the primes below one-hundred thousand that will never be a factor of $R(10^n)$.

This is a tough problem, but you can approach it in three steps.

Step 1: Understand the Problem

A repunit is a number that consists entirely of ones. We define a repunit $R(k)$ to be a repunit of length $k$. For example, $R(6)$ would be 111111. We are looking to find the sum of all the primes less than 100000 that will never be a factor of the repunit $R(10^n)$ for any $n$.

Step 2: A property of Repunits

Notice something interesting about the series of repunits: they form a geometrical series with ratio 10. So if you have a repunit $R(a)$ and another repunit $R(b)$, if $b$ is a multiple of $a$, the repunit $R(a)$ is a factor of the repunit $R(b)$.

This means that if a prime divides any member of this geometric series, it will divide $R(10^n)$ at some $n$.

Step 3: Finding Primes and Checking Divisibility

Using the above properties, we can conclude that to find a prime $p$ such that it will constitute a divisor for none of the numbers $R(10^n)$ means that the prime $p$ cannot divide any repunit $R(ns)$ (where $1 \leq n < 10$ and s is any positive integer). Now, list all the primes below 100000, and find out how many of them divide a repunit $R(ns)$ (where $1 \leq n < 10$ and s is any positive integer). Again, you can use the geometric series property, and do this for just enough $s$ to cover all the primes. This means that if $R(ns) \equiv 0 \mod p$, then $p$ divides some $R(10^n)$. Once you have done this, the primes left over are the ones that will never divide $R(10^n)$ for any $n$. Just add these primes up, and you have your answer. Summing up all the primes under 100000 and then subtracting the sum of primes that divide a repunit $R(ns)$ where $1 \leq n < 10$ and s is any integer will give you the answer. Detecting the primes under 100000 can be efficiently done using the Sieve of Eratosthenes algorithm. Generating the repunits and checking for divisibility will take some programming work. The program will likely work faster if it calculates the $R(ns)$ values up to the largest prime (less than 100000) only. The formatted output includes the total number of primes in the range, the number of primes that divide some $R(10^n)$, and the sum of primes that never divide a $R(10^n)$. Finally, print out the sum of primes that never divide a $R(10^n)$ as this is the answer we are looking for.

More Answers: