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

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

Written by on 25 June 2011

Topics: Project Euler

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.

26 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    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…

  2. SuprDewd says:

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

  3. Kristian says:

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

  4. Kristian says:

    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

  5. SuprDewd says:

    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.

  6. Kristian says:

    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

  7. SuprDewd says:

    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.

  8. Kristian says:

    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

  9. Michael says:

    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;
    			}
    		}
    	}
  10. Kristian says:

    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

  11. Alexey says:

    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;
            }
    
  12. Kristian says:

    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

  13. SuprDewd says:

    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.

  14. Kristian says:

    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

  15. Satya says:

    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.

  16. Kristian says:

    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.

  17. Keith says:

    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.

  18. Kristian says:

    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.

  19. Vlad says:

    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
  20. hongtengyin says:

    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
    
  21. Eqbal says:

    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

  22. mrb says:

    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;
    }
    
  23. Daniel Roberts says:

    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.

  24. Metafity says:

    4597 4759 9547 this satisfies the two conditions..

  25. Henrik says:

    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.

  26. Apara says:

    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!

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.