# 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>
```

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

2. Succinct!

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

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

Blog at WordPress.com.