Problem 133 of Project Euler is a continuation of Problem 132 and Problem 129 in which we are supposed to find the some prime numbers which are not factors of R(10^{n}) for any n. In fact the problem reads

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of lengthk; 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 ofnfor 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}).

I have found two methods for solving this. Both build upon the same principle. From previous problems we know that a repunit can be written on the form

We will use this in our solution. The next thing we need is to know that if we have a number k = am, where k, a and m are positive integers, then R(a) divides R(k). We can show that since we have

and

Therefore if we divide the two we get

Then for a little trick since the first part can be rewritten as an expression of R(a), since we have that (simple rewrite of the definition of R(a). Using this we get that . This can be inserted into the previous equation

The upper part where we have that can be expanded such that it will yield a whole lot of terms containing some power and multiplum of 9R(a) and then one term which will be a one. As an example if m = 2 we get . Thus if we expand the power the ones will cancel out and we can divide all the terms by 9, such that we are left with terms which contains R(a), therefore R(a) is divisible by this numbers.

What this means is that if p divides for some n then p also divides if n < m, since divides as we have just shown since we can write where a = m – n.

## Choosing n large enough

With the previous deduction, if we make n large enough then it should divide every prime we want to test it up against. Of course this method means that we must make a guess of the size of n. I started out with n = 100 and got the result in 218ms.

Sum of the primes not divisible not a factor of R(10^n): 453647705

After that I tried to lower n and check that the result was the same. The smallest n for which it works i n= 16, and then I can get the result in 38ms.

The code for doing this is rather simple and can be written in C# reusing a large chunk of the code from Problem 132

int result = 0; int[] primes = Sieve(2, 100000); BigInteger k = BigInteger.Pow(10, 16); for(int i = 0; i < primes.Length; i++){ if (BigInteger.ModPow(10, k, 9 * primes[i]) != 1) result += primes[i]; }

## Factoring A(n)

In Problem 129 we found a way to calculate the smallest A(n) which is the smallest p such that R(k) is divisible by n. We will reuse that function (or at least most of it).

If we look at then this will have the prime factorization , for a given n. Thus if we calculate A(p) for a given prime and we can factor this A(p) into a prime factorization on the form for some integers c and d, then we know that there will exist a number where e = m – c, and f = m – d for a large enough m. and thus we can use the result that if we can write m = bA(p) then we know from the beginning of the post that since A(p) is divisible by p then R(m) will be divisible by p as well.

This reuses the A(n) function from Problem 129, with the exception that for p > 6 we don’t need to check if gcd(p,10) = 1, since p is prime. However, for 2 and 5 this does not hold. However, we can rather easily show that 2,3 and 5 will not be divisible by any .

First of all 2, this will not be divible by any repunit since a repunit is an odd number. For 3 we can use the digit root test. If the digit root of a number is divisible by 3 then the number will also be divisible by 3. However, the digit root of any will be 1, since the there are ones which then summed up will be a one with n zeros following. And lastly 5 is only divisible with numbers which ends on 0 or 5, so that will not work either.

Thus we can make the main loop as

int result = 10; int[] primes = Sieve(6, 100000); for (int i = 0; i < primes.Length; i++) { if (OtherFactor(A(primes[i]))) { result += primes[i]; } }

with the Otherfactor function as

private bool OtherFactor(int k) { int[] factors = new int[]{2,5}; int i = 0; while (i < factors.Length && k > 1) { if (k % factors[i] == 0) { k = k / factors[i]; } else { i++; } } return k > 1; }

This will give us the answer in 1822ms, which is a whole lot slower then the first solution, but we don’t have to guess the size of a number.

## Wrapping up

I have now presented you with 2 different solutions. One is fast, but needs a guess on an upper bound, the other one is slower. I am sure you can make the slow one faster though, but having sorted out the math in this problem, I think suffices for me.

You can find all the code for the problem here.

Guessing n, I love this part.

I still feel lucky when I got the answer by guessing.

My guess was n = 20. 🙂

Basically I guessed as well, just a tad higher 🙂

Table 1

Primes (p): nonfactors and factors of [R(10^n)]

(p<100)

http://img407.imageshack.us/img407/6451/pe133table1.jpg

Concerning the occurence of 19 as a factor of repunits, one can

observe that it first appears in repunit R(18) and the

multiples of 18.

Thanks to Kristian for the article and the code

🙂

great… and cool..

I’m not sure I follow (or would trust in general) your first approach. It seems like you are suggesting that if p does not divide R(10^{“sufficiently large N”}), then it does not divide R(10^n) for any n. Your argument is that factors of R(10^n) are also factors of R(10^m) for m>n. However, this argument says nothing about the possibility of introducing a new small factor for some very very large power of ten. Higher powers R(10^M) can result in unique factors not present in lower powers R(10^N) M>N. You can never be certain you actually chose a sufficiently large N.

With your second approach, you can be certain. You don’t need to actually compute A(p) for any prime. Since A(p) divides totient(p)=p-1, all you need to do is check powers of the factors 2 and 5 of p-1. If 10^(2^a*5^b) = 1 mod p, where p-1=2^a*5^b*c and c not divisible by 2 or 5, then p will divide some R(10^n) for some n. This takes about 2ms to compute for all primes below 100000.

Re : My comment above (January 28, 2013 at 13:40))

The non-functional link : (Error : 404 Not Found)

http://img407.imageshack.us/img407/6451/pe133table1.jpg

has been replaced by hostingpics.net

http://hpics.li/ea90f22