Project Euler 49: Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other

Problem 49 of Project Euler asks us to find three numbers with the following properties

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

When I first read the description I misread the description and interpreted it as I had to find a sequence which was 3330 apart. So I solved that problem and arrived with a correct solution. However, I realise this was not what was meant with the problem.  So the solution I will present here is one that looks for any three number sequence with equal distance among two neighbouring terms and having properties (i) and (ii).

Main Algorithm

I think there are many ways to approach this problem since we need to find a triplet which are permutations, prime numbers and equal distance apart. We could start with generating permutations of a candidate number and then check the other properties afterwards as one example. I chose another path.

Avid readers of the blog knows how fond I am of prime number lists by now, so I took that approach instead. I took the following approach.

  1. Generate a list of primes below between 1000 and 10000.
  2. Take two primes i and j with i < jand calculate k = j + (j-i).
  3. Check if k < 10000 and check if k is a prime, if not go to 2.
  4. Check if i and j are permutations of each other and check if i and k are permutations of each other. If not go to 2.
  5. Found the triple, so exit.

This can be implemented in C# as

const int limit = 10000;
long result = 0;
int[] primes = ESieve(1489,limit);

for (int i = 0; i < primes.Length; i++) {
    for (int j = i + 1; j < primes.Length; j++) {
        int k = primes[j] + (primes[j] - primes[i]);
        if (k < limit && Array.BinarySearch(primes, k) >= 0) {
            if (isPerm(primes[i], primes[j]) && isPerm(primes[i], k)) {
                result = concat(concat(primes[i], primes[j]), k);
                break;
            }
        }
    }
    if(result > 0){
        break;
    }
}

A few things to note. I have modified the Sieve algorithm to take a lower bound as well, this was really easy, but made it more flexible. Second thins is that we need a method to check if two numbers are permutations of each other.

Checking Permutations

I have checked several places to get inspiration for how to check if two numbers are permutations of each other. Every time I find a method where they convert the number to a char array. My experience tells me that the operation of conversion is rather costly, so I have made a method that counts the number of each type of digit from 0 to 9 and compares the two arrays. The C# method looks like

private bool isPerm(int m, int n) {
    int[] arr = new int[10];

    int temp = n;
    while(temp > 0){
        arr[temp % 10]++;
        temp /= 10;
    }

    temp = m;
    while(temp > 0){
        arr[temp % 10]--;
        temp /= 10;
    }

    for(int i = 0; i< 10; i++){
        if(arr[i] != 0){
            return false;
        }
    }
    return true;
}

It is my standard way to chop digits off a number. First I chop up the first number and increase the array accordingly. After that I chop up the other number and decrease the array according. Last I check if all indices of the array is 0, otherwise the two numbers weren’t permutations.

Wrapping up

I have presented you with one way to solve this problem out of several. I get the result

The 12 digit number is 296962999629
Solution took 11 ms

My first attempt of this approach took me 17ms, but with a few rewrites I pushed the time to 11ms. I am pretty satisfied. As usual you can find the whole source code for download, including the left out parts.

Did you solve it another way, have comments or questions? I would like to hear from you.

The three stone picture illustrating the arithmetic sequence of three numbers is taken by Alun Stone. I have shared my version of it under the creative commons license just as the original photo.

Posted by Kristian

28 comments

I have often wondered if there is a better way to check if a number is a permutation of another number. It seems so naive to me to create a new array every time. But this is the best way I’ve found so far…

Hey, the link to the source code isn’t working.

Ooops, thanks for noticing. I just updated the path.

Hi SuprDewd

It bugs me as well to use an array for checking if a number is a permutation of another, but the only other solution I have found for it is based on converting it to a string and a char array – and that doesn’t really help with the whole issue of creating an array to check for permutations. My first version of the method involved two arrays, which I managed to cut down to one. So at least there is some sort of thought in the algorithm.

/Kristian

My method is pretty much the same as yours. The only thing that differs is that I usually do:

if ((int)Math.Log10(a) != (int)Math.Log10(b)) return false;

But this is not needed in this problem because they are both 4 digit numbers.

Hi SuprDewd

Do you perform that as an extra test? Because I am not sure why it is needed. The method I have posted should return false whenever there is a different number of digits. Maybe I have just missed something.

/Kristian

No no, it’s an extra test.
I *think* it’s faster to include it if the numbers vary in length.
For a number to be a permutation of another number, they must have the same amount of digits (log10(a) == log10(b)).
This will return false immediately if they don’t.

Okay, so the benefit is dependent if you encounter lots of instances of different number length or not.

But good thinking, I like the idea.

/Kristian

I solved it this way in Java. Basicly I sweep linearly throgh the array of primes. For each of these it finds the next (lexicographically) permutation. If that is a prime, then start permute that one. If one matches print that and move on to the next prime. At most there are d! permutations for a d digit number, so it should do at most d! n check for a list of n primes. Furthermore I do some checking of the candidates before consulting the list if they are prime.

On my system my method uses 16 ms where your method uses 200 ms, for checking all between 1000 and 10000.

Implementation of both methods
http://pastebin.com/tPKiFmmp

Btw. nice blog have gotten some nice inspiration for optimization from this.

	public static void byPermutation(int max) {
		List<Integer> primes = util.Prime.getPrimesBelow(1000, max);
		
		for (int i = 0; i < primes.size(); i++) {
			int first = primes.get(i);
			int[] firstArray = buildIntArray(first);

			boolean found = false;
			while (nextPermutation(firstArray)) {
				int middle = arrayToInt(firstArray);
				int target = 2 * middle - first;

				if (target < max && middle % 2 != 0 && target % 2 != 0
						&& binarySearch(primes, middle) >= 0
						&& binarySearch(primes, target) >= 0) {

					while (nextPermutation(firstArray)) {
						int last = arrayToInt(firstArray);
						if (last == target) {
							System.out.println(first + " " + middle + " " + last);
							found = true;
							break;
						}
					}
				}
				if (found)
					break;
			}
		}
	}

Hi Michael

Thanks for the compliment and thanks for the solution method you have constructed. It seems like a really good solution you have made.

So the basic difference is that you generate permutations and check if they are primes. I find primes and check if they are permutations. Apparently that solution is much faster.

Thanks for enlightening us all
/Kristian

Hi Kristian!

Thank you for your blog, I like to read mathematical underground to each problem, about ESieve and some other algorithms I knew from you.
I found solution for the problem that takes 1-2 ms.

After I got primes using ESieve method, I filter out numbers containing zeros and append to others a key that is made of sorted digits of the number. I put all such numbers in other array and sort them. All permutative numbers are near each other.

        public void OtherForce() {
            Stopwatch clock = Stopwatch.StartNew();
            int[] primes = ESieve(1234, 9998);	        
	        int[] grouped = new int[primes.Length];	
	        int z = 0;
	        for (int i=0; i<primes.Length; ++i) {
		        int r = convert(primes[i]);
		        if (r > 0) 
			        grouped[z++] = r;			
	        }            
            Array.Sort(grouped, 0, z);
	        for(int i=0; i<z-2; ++i) {        
		        int key1 = grouped[i]/10000;		
		        int val1 = grouped[i]%10000;		
		        for (int j=i+1; j<z; ++j) {
			        int key2 = grouped[j]/10000;
                    if (key2 != key1) 
                        break;                    
			        int val2 = grouped[j]%10000;
			        int diff = val2-val1;									
			        int end = (z-j > 24) ? 23 : z-j-1; // 24  = 4! - we should find only in a group of unique key, but as we handle only primes it can be /2=12 I think.  					
                    if (Array.IndexOf(grouped, grouped[j] + diff, j + 1, end) > 0) { 			
				        Console.WriteLine("The 12 digit number is {0}", val1.ToString() + (val1+diff).ToString() + (val1+(diff<<1)).ToString());
				        break;
			        }			
		        }
            }
	        clock.Stop();            
            Console.WriteLine("Solution took {0} ms", clock.ElapsedMilliseconds);		
        }

        private int convert(int number) {
	        int num = number;
	        int res = 0;	
	        int[] digits = new int[4];
	        for (int i=0; i<4; ++i) {
		        int n = num%10;
		        if ( n == 0 ) 
			        return 0;
		        num = num/10;	
		        digits[i] = n;
	        }
            Array.Sort(digits, 0, digits.Length);
	        for (int i=0; i<4; ++i) {
                res += digits[i] * (int)Math.Pow(10, 3 - i);
	        }
	        return res*10000 + number;
        }

Hi Alexey

That seems like a pretty interesting solution with some interesting ideas. So far there have been several good alternative inputs on how to solve this problem. Yours is definitely among those. I have some problems following your code 100% but I think it will help once I get it into visual studio, so I can mess around with it.

Thanks for the comment, and thanks for the valuable input.

/Kristian

Does the problem statement say whether the final arithmetic sequence is incremented by 3330, like the other sequence, or not?

If it does:

#include <iostream>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;

bool isPrime(int n)
{
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    if (n <= 13) return true;

    for (int i = 5; i * i <= n; i += 6)
    {
        if (n % i == 0) return false;
        if (n % (i + 2) == 0) return false;
    }

    return true;
}

int dCnt[10] = {0};

bool isPermutation(int a, int b)
{
    while (a > 0) dCnt[a % 10]++, a /= 10;
    while (b > 0) dCnt[b % 10]--, b /= 10;
    for (int i = 0; i < 10; i++)
    {
        if (dCnt[i] != 0)
        {
            memset(dCnt, 0, 4 * 10);
            return false;
        }
    }

    return true;
}

int main()
{
	clock_t start = clock(), end;

    int n = 9999,
    	max = (n - 3) / 2;

    bool primes[4999];
    memset(primes, true, 4999);

    // Prime sieve
    int ms = (static_cast<int>(sqrt(static_cast<double>(n))) - 3) / 2;
    for (int i = 0; i <= ms; i++)
    {
        if (primes[i])
        {
            int i2 = 2 * i,
                s = i2 * i + i2 * 3 + 3,
                cur = i2 + 3;

            for (int j = s; j <= max; j += cur)
            {
                primes[j] = false;
            }
        }
    }

    for (int i = 499; i <= 4998; i++)
    {
    	if (primes[i])
    	{
           int cur = 2 * i + 3;
           if (cur == 1487) continue;

           // Prime / Permutation checks can be switched to tweak performance
           if (isPrime(cur + 3330) && isPrime(cur + 6660))
           {
                if (isPermutation(cur, cur + 3330) && isPermutation(cur, cur + 6660))
                {
                    cout << cur << (cur + 3330) << (cur + 6660) << endl;
                    break;
                }
           }
    	}
    }

    end = clock();
    cout << (end - start) << " ms" << endl;

	return 0;
}

The program runs in 0-2 ms.

Hi Bjarki

Personally I haven’t read the problem description as the difference have to be 3330, especially since they state that there are no 1,2 or 3 digit sequences. Which is a trivial statement if the difference have to be 3330.

However, I have read many who has read and solved the problem that way. And honestly, if the assumptions you make for the solution holds, such that you find the solution, then I guess they are valid 🙂

Nice solution
/Kristian

Hi…first of all,awesome job sir….I too am trying to solve all problems from project euler.I’ve gotten to problem 50.And I use your site to check my answers…and compare my times to yours since I write my code in C(Yeah..I am a noob and I like C more than C++..dont know why).I just want to add that you dont need an array to check if two numbers are permutations of each other.
Initially flag var =1;
You first check if the first digit of the first number is present in second number.
If yes,remove that digit from both numbers and then check for the new numbers.
If its a no at any iteration,you break the loop and set flag variable =0.

I have not tried it yet…but it should work because my permutator functions works this way.But I donno for sure.

Hi and thanks for the comment.

I think you are right about not needing the array when you represent it like that. But you still need to be able to access the individual digits of the number and remove it. That operation is as far as I know easiest if you make an array of the number, whether it be a string (which is a char array in C) or an int array is not that important.

Second thing is the speed of the operation (which for this purpose is probably not important). The method I suggest here walks through each number 1 time and then once to compare the two arrays. Your method walks through the first number once and the second number n times, where n is the number of digits. So mine is linear in time and yours is squared.

That being said, I think both solutions would work perfectly for this application. Regarding the language of choice. I don’t like c myself, but that is mostly because I can’t keep my pointer references straight so I always end up segfaulting. So I need a language that can help me sort those things out. If you can wrap your head around c, you will certainly get faster programs.

Thanks for the blog. I really like coming here and seeing how I could have done much better on my solutions if I had just looked at them in a different light. It’s been a great help.

Mine is much slower than yours, due to the brute force method I used. I’m coming in at a whopping average of 90ms.

However, I did try to speed mine up by using your Permutation code and it wasn’t actually faster than my code that uses a char.

Basically I’m first making sure they are the same length. Then I loop through all the characters of one of them and make sure they appear the same number of times in both submitted values.

The functions I’m using in C# is:

private bool matchDigits(int x, int p)
{
string s1 = Convert.ToString(x);
string s2 = Convert.ToString(p);
if (s1.Length != s2.Length ){return false;}
foreach (char c in s1)
{
if (s1.numberOfInstances(c.ToString()) != s2.numberOfInstances(c.ToString())) { return false; }
}
return true;
}
public static int numberOfInstances(this string fullVal, string piece)
{
int cnt = 0;
foreach (char c in fullVal)
{
if (c.ToString() == piece) { cnt++; }
}
return cnt;
}

When I swapped out my matchDigits function for your isPerm function I actually run about the same number. I have only run a handful of runs so I can’t quantify a difference, but just running a handful and watching the numbers they are about the same.

I also attempted running a .Substring() instead of looping through char’s and doing .toString()…but that didn’t have any real effect on the speed either.

Of course, my implementation is brute force and much slower than your solution overall.

Thanks for the compliment. I always had a feeling that working with strings and chars would be slower then working with arrays of numbers. But I am glad you can prove me wrong.

I took a slightly different approach than what you did.

First I generated the primes below 10000, and I grouped them based on a sorted permutation of their digits (ex 1487: [1487, 4817, 8147])

perms = {}
for i in range(10001):
    perms[i] = []

for prime in get_primes(10001):
    pkey = int(''.join(sorted(list(str(prime)))))
    if pkey < 1000:
        continue
    perms[pkey].append(prime)

Once I got these, i just iterated through the prime permutations we have to find a sequence of 3.

for i in perms:
    differences = {}
    for a, b, c in combinations(perms[i], 3):
        diffs = set([abs(a - b), abs(b - c), abs(c - a)])
        if len(diffs) != 3:
            print a, b, c

Runs in 15ms, but definitely can be optimized.

PS: Using a fairly inefficient prime generation algorithm I made myself

def get_primes(n):
    """
    Get all the primes smaller than n
    """
    primes = [0] * n
    for i in xrange(2, n):
        if primes[i] == 0:
            yield i
        else:
            continue
        for j in xrange(1, n // i):
            primes[j * i] = 1
hongtengyin

I use the bit shift to see if the two numbers are permutations.
here is the approach:(python)

def is_Permutations(base,check):
    bit_base, bit_check = 0, 0
    while True:
        bit_base = bit_base | 1 << (base % 10)
        base /= 10
        bit_check = bit_check | 1 << (check % 10)
        check /= 10
        if base < 1 and check < 1:
            break
    if bit_base == bit_check:
        return True
    return False

I’m not sure if I’m using the same approach or not but at least I’m getting the same results with simpler ruby code:


def perm?(a,b,c)
a_s = a.to_s.chars.sort.join().to_i
b_s = b.to_s.chars.sort.join().to_i
c_s = c.to_s.chars.sort.join().to_i
(a_s == b_s) && (b_s== c_s)
end

def prime?(n)
return true if (n==2)
return false if (n % 2 == 0 || n == 1)
limit = Math.sqrt(n)

for i in (3..limit).step(2)
return false if (n%i==0)
end
true
end

for a in (1000..9999)
next if a ==1487
b = a + 3330
c = b + 3330

next unless (prime?(a) && prime?(b) && prime?(c))
next unless perm?(a,b,c)
puts a,b,c
end

This program is not fast, but it shows a different method to check whether the numbers are premutations or not. I compare the sums of the powers of 2 to the digits. (don’t know how to write that sentence correctly)

long long power(int number, int p){
    int i;
    long long x = 1;
    for(i=0;i&lt;p;i++){
        x *= number;
    }
    return x;
}

int same_digits(int n1, int n2, int n3){
    int v1=0,v2=0,v3=0;
    while(n1&gt;0){
        v1 += power(2,n1%10);
        n1 /= 10;
    }
    while(n2&gt;0){
        v2 += power(2,n2%10);
        n2 /= 10;
    }
    while(n3&gt;0){
        v3 += power(2,n3%10);
        n3 /= 10;
    }
    if(v1==v2 &amp;&amp; v1==v3){
        return 1;
    }
    return 0;
}

int main()
{
    int i,inc;

    for(inc=1;inc&lt;5000;inc++){
        for(i=1000;i&lt;9999-2*inc;i++){
            if(is_prime(i)&amp;&amp;is_prime(i+inc)&amp;&amp;is_prime(i+2*inc)){
                if(same_digits(i,i+inc,i+2*inc)==1){
                    printf(&quot;answer: %d%d%d\n&quot;,i,i+inc,i+2*inc);
                }
            }
        }
    }
    return 0;
}
Daniel Roberts

Nice solution.

I went with picking the subsets of length four 6561(9^4) = s. Then finding all permutations of these 4^4 = p. s * p = 1679616. Then filtering down to just the primes. Then checking pairs on that list to see if p2 – p1 = p3.

4597 4759 9547 this satisfies the two conditions..

Where did you get the number 1489 from? You said you wanted to check numbers between 1000 and 1000000 the you jumped up to 1489.

I used a method similar to finding a pandigital number to check for permutation. I think this is much faster than storing in arrays.


bool isPermutation(int n, int m) {
int A = 0, B = 0, temp;
while (n > 0) {
temp = A;
A |= (1 << static_cast((n % 10) - 1));
n /= 10;
}
while (m > 0) {
temp = B;
B |= (1 << static_cast((m % 10) - 1));
m /= 10;
}
return A == B;
}

By the way, a fan of your blog!

I did this pretty earlier in my learning of python. Like some other posters here It was not clear what the delta must be 3330 or not… 😀

My solution is in python and goes about it probably in a round a bout way. It takes just under 2 seconds to run.

I’ve shared the Jupyter Notebook here:

https://github.com/modulusmath/primes/blob/master/Prime%2BEuler%2BNet%2BNumber%2B49.ipynb

this is my solution with python, it took 3.18ms on my computer:

https://github.com/sorrowise/euler/blob/master/049.py

from sympy import sieve

def main():
primes = list(sieve.primerange(1488,10000))
for p in primes:
a = p + 3330
b = p + 6660
if a in primes and b in primes and set(str(p))==set(str(a))==set(str(b)):
return str(p) + str(a) + str(b)

Leave a Reply