Duncan's blog

November 10, 2008

Project Euler: problem 49

Problem 49:

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?

There are three aspects to this:

  • Work out how to loop through the numbers
  • Work out if the digits are the same in each case
  • Work out if each number is prime

So, each number has to be 4 digits. The largest 4 digit number is 9999. If we add 3330 each time, the largest number can’t be any more than 9999 – 3330 – 3330. On re-reading the brief, it says “there is one other 4-digit increasing sequence“, and I had a nasty thought that it maybe wasn’t one that increased by 3330, but some other number. However that’s not the case thankfully.

If we know 1487 is the other number that this works for, we can exclude that. I made the assumption that the second number would be larger than 1487. However this could have been a wrong assumption, and my code should have started at 1001, and deliberately stepped over 1487. But my assumption turned out be correct, so the code worked as it was.

All primes apart from 2 are odd, so I started at the next odd number greater than 1487. Also setting the loop increment to +2, so we can exclude the even numbers.

To work out if the numbers are the same each time, I put two sets of numbers each into an array, sort the arrays, then compare them. If the numbers in the arrays differ, then the digits must be different.

I’m reusing my IsPrime() function from earlier problems.

<cfset end = 9999 - (3330 * 2)>

<cfscript>
function sameDigits(x, y)
{
	var i = 0; 
	var arrX = ArrayNew(1);
	var arrY = ArrayNew(1);
	
	for (i = 1; i LTE Len(x); i = i + 1)
	{
		ArrayAppend(arrX, Mid(x, i, 1));
	}
	for (i = 1; i LTE Len(y); i = i + 1)
	{
		ArrayAppend(arrY, Mid(y, i, 1));
	}
	ArraySort(arrX, "numeric");
	ArraySort(arrY, "numeric");
	
	for (i = 1; i LTE ArrayLen(arrX); i = i + 1)
	{
		if (arrX[i] NEQ arrY[i])
			return false;
	}
	
	return true;
}

function isPrime(x)
{
	var isPrime = true;
	var i = 0; 
	
	if (x LT 2)
	{
		return false;
	}
	
	if ((NOT x MOD 2) AND (x GT 2))
	{	// a multiple of 2, but not 2 itself
		return false;
	}
	
	for (i = 3; i LTE SQR(x); i = i + 2)
	{
		if (NOT x MOD i)
		{	// found a factor of x
			return false;
		}
	}
	
	return isPrime;
}
</cfscript>

<cfloop index="i" from="1489" to="#end#" step="2">
	<cfset num2 = i + 3330>
	<cfset num3 = num2 + 3330>
	
	<cfif 	sameDigits(i, num2) 
	AND 	sameDigits(i, num3) 
	AND 	IsPrime(i)
	AND 	IsPrime(num2)
	AND 	IsPrime(num3)>
		<cfoutput>#i##num2##num3#</cfoutput>
		<cfbreak>
	</cfif>
</cfloop>

3 Comments »

  1. Thanks for this; from the wording of the problem I too wasn’t sure if the offset was 3330 or something else; after various failed attempts (because there exist more than three prime permutations of the answer), your blog entry helped me find the answer.

    In case you care, here’s what a Ruby solution looks like:

    
    require 'prime'
    
    Prime.instance.each( 10000-3330*2 ) do |prime|
      next unless prime >= 1000 # needs to be 4 digits
      next if prime == 1487     # skip over this answer
      nums = [prime, prime+3330, prime+3330*2 ]
      next unless nums.all?{ |n| n.prime? }
      digits = nums.map{ |n| n.to_s.split(//).sort }
      next unless digits[0]==digits[1] && digits[1]==digits[2]
      puts nums.join
      exit
    end
    #=> [Finished in 0.202 seconds]
    

    Comment by Gavin Kistner — March 17, 2010 @ 4:31 pm | Reply

  2. Succinct!

    Comment by duncan — March 18, 2010 @ 12:01 am | Reply

  3. […] previously blogged about this Project Euler puzzle nearly 6 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and […]

    Pingback by Project Euler: problem 49 (PHP) – Prime permutations | Duncan's blog — October 16, 2014 @ 8:01 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: