So I am working on this problem… which states:
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).
My general strategy was to find the prime factorization of the highest repunit below 100,000^2 which I assumed if a factor was less than 100,000 it would become a factor of a repunit by 100,000 squared… which apparently isn't true, as that list is: (3,
7,
11,
13,
37,
41,
73,
101,
137,
239,
271,
4649,
9091)
and going as far as I can in 64 bit ints the list is: (3,
7,
11,
13,
17,
19,
31,
37,
41,
53,
73,
79,
101,
137,
239,
271,
4649,
9091,
9901,
21649,
52579)
So most interesting is the numbers are 17 and 19… which leads me to believe that I need to find a very different way around this problem… but I am not sure where to go next.
PS I haven't unit tested my algorithms to verify that the lists are complete and correct… but they look right when checking against the factorizations listed on wikipedia.
Best Answer
Not sure that your statement is right. Did you mean $R(10^n)$ and not R(10n) Note that $$R(k)= \frac{10^k-1}{9}$$
So for $p \neq 3$, $p | R(k)$ if and only if $$10^k \equiv 1 \mod p$$
This says that for $p$ to divide $R(k)$, $p-1$ and $k$ must have some non-trivial common factor and $10$ to the power of this factor should be $1 \mod p$.
For example, if you set $p=19$ then $10 n$ and $18$ must have a nontrivial factor. Thus repunit with 180 ones is $$9 \, R(180) = 10^{180}-1 = \left(10^{18}\right)^{10} - 1 \equiv 1^{10} -1 = 0 \mod 19$$
In fact every $p$ divides $R(10n)$ where $n = p-1$.
If what you meant was $R(10^n)$ then the above logic says that $p-1$ must have a common factor with $10^n$, i.e. $p-1$ must be divisible by $2$ or $5$ or both. Now argue that if $p-1$ is a power of 2, or power of 2 times a power of 5 then we can always find a $n$. If in addition $p-1$ is a multiple of a power of $3$ then use the fact that $10\equiv 1 \mod 3$ to argue the case.