Project Euler 134: Prime pair connection

With a little help from Wikipedia I found Problem 134 of Project Euler rather easy to solve.  Well it was easy after solving some issues I had with integer overflows and several other bugs. But anyway, the problem reads

Consider the consecutive primes p1 = 19 and p2 = 23. It can be verified that 1219 is the smallest number such that the last digits are formed by p1 whilst also being divisible by p2.

In fact, with the exception of p1 = 3 and p2 = 5, for every pair of consecutive primes, p2 > p1, there exist values of n for which the last digits are formed by p1 and n is divisible by p2. Let S be the smallest of these values of n.

Find ΣS for every pair of consecutive primes with 5 ≤ p1 ≤ 1000000.

Based on the problem description we can read that we need to solve the equation

where the function d(x), is a function that counts the digits of x. So now we have a more mathematical formulation of what we need. The above formulation is also known as a linear congruence, which we can find on Wikipedia, including instructions on how to solve.

Wikipedia uses the formulation

So we have to rewrite the equation a bit, lets start with that

Now we have a negative value of b, which we do not really like. However, you can always add 0 to both sides, and since we are dealing with a problem modulo adding  is equivalent to adding 0, so we get

So now we have a positive term on the right side, since we are given that in the problem description. So we have

In order to solve this now, we need to build a few functions. You can see all the code in the source file. I have built a function which returns the a, and I have built an extended Euclidian algorithm which we also need, using the Wikipedia description of the algorithm. As a side note to that, I can see that the blog Problematic sets has derived the exact same solution, but written it in Python, which gives a much nicer expression for the extended Euclidian Algorithm compared to C#.

My implementation of the two functions look like

private long DigitCountFactor(long number) {
long factor = 1;

while (number > 0) {
factor *= 10;
number /= 10;
}

return factor;
}

private long[] extended_gcd(long a, long b) {
long x = 0;
long lastx = 1;
long y = 1;
long lasty = 0;
while (b != 0) {
long quotient = a / b;

long temp = b;
b = a % b;
a = temp;

temp = x;
x = lastx - quotient * x;
lastx = temp;

temp = y;
y = lasty - quotient * y;
lasty = temp;
}

return new long[] { lastx, lasty, a };
}


Not much to say about them, you can see the description on Wikipedia for the latter algorithm, and the first algorithm should be self explanatory if you have come this far in the problems. We of course also need a prime number generator, but this is just copy paste of my good old Prime Sieve.

Our extended euclidian algorithm returns r, s and d based on the input a and n, such that {r,s,d} = gcd(a,n). Where we have the relationship that ra + sn = d and d is the greatest common divisor of the input a and b. Based on that we have a solution to our linear congruence which is

There are a few notes here and a caveat with using c# as implementation language. First of all d = 1 in our case, since the input n is a prime. So we can leave that division out of the implementation. Second note is that we get a solution not necessarily the minimum solution, and the solution might very well be negative. However, we can make it minimal by taking the modulo of the solution. And here comes the caveat of C#. The modulo operator does not always return a positive number. So where some languages (e.g. Python) gives us that -4 % 7 = 3, C# gives us that -4 % 7 = -4. In this case we need to make it positive, which we can do by adding , this will give us the minimum positive solution instead of the minimal negative solution.

All in all we get he following implementation

int limit = 1000000;
int[] primes = Sieve(5, limit + 100);
long result = 0;
int i = 0;

while (primes[i] <= limit) {

//solve the linear congruence
// 10^d(p1)*x + p1 == 0 (mod p2)
// 10^d(p1)*x == -p1 (mod p2)
// 10^d(p1)*x == p2-p1 (mod p2)
// ax == b mod n
long p1 = primes[i];
long p2 = primes[i + 1];

long a = DigitCountFactor(p1);
long b = p2 - p1;
long n = p2;

long[] rs = extended_gcd(a,n);
long x  = rs[0] * b % n;

if (x < 0)
x = n + x;

result += x * a + p1;
i++;
}


This gives us the result

Sum of S: 18613426663617118


In 35ms. I also tried bruteforcing a solution by just increasing x until we hit something which is correct, but that solutions takes about 5 minutes to finish. So that wasn’t pretty. However, it was okay to have running in the background while reading about linear congruence solving.

You can find the complete source code here.

Posted by Kristian

Jean-Marie Hachey

Some results for p1 < 100

___

Table 1
Project Euler 134: Prime pair connection
(For p1 < 100)

http://img690.imageshack.us/img690/4429/pe134figone.jpg

Jean-Marie Hachey

In relation to a reference to Wikipedia…

Linear congruence theorem

http://en.wikipedia.org/wiki/Linear_congruence_theorem

Citation from Wikipedia:

This link appearing in the above article contains a lot of references and sources:

Chinese remainder theorem
http://en.wikipedia.org/wiki/Chinese_remainder_theorem

Another general reference may be added:

Number Theory for Computing
By Song Y. Yan
(2nd edition)

Springer, Jun 10, 2002 – Computers – 435 pages

ISBN 978-3-540-43072-8

Quote :
« This book provides a good introduction to the classical elementary number theory and the modern algorithmic number theory, and their applications in computing and information technology, including computer systems design, cryptography and network security. In this second edition proofs of many theorems have been provided, further additions and corrections were made ».

Bjarki Ágúst

This is one of my favorite problems. I solved it very similarly. Given $p_1$ and $p_2$, I wanted to find an integer $x$ such that

$\displaystyle x \equiv 0 \pmod{p_2}$
$\displaystyle x \equiv p_1 \pmod{10^{d(p_1)}}$

Now I had two linear congruences with one variable. When I was solving the problem, I had read about The Chinese Remainder Theorem some months ago, but didn’t fully understand it nor see any uses for it. But having written these two equations down, I immediately saw that the CRT could be used to solve this. Also note that this is possible since $p_2$ and $10^{d(p_2)}$ are coprime ($p_2$ is some prime other than 2 or 5). Then I just implemented the algorithm given on the CRT Wikipedia page, and the rest was pretty much the same as you did.

Also, one little tip. To cope with negative numbers when doing the modulo operation in C# (or any language where % is the remainder operation), I usually do the following:

public static int Mod(int a, int b) {
return (a % b + b) % b;
}


I think it’s a little more neat than having an extra check for negative remainders, but this is also slower.

Tamas

I just have a side note for the DigitCount method; I think it is unnecessary, you can easily get the required number using Math.pow, Math.ceil and Math.log base 10.

Keep up the good work!

Kristian

Yes indeed I can. When I first wrote the function I didn’t think about that, and apparantly I haven’t changed it later. It would be interesting to see which one is faster though.