// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (9 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 49 Solution

Project Euler 49 Solution

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


Problem Description

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?

Analysis

Start with the known solution plus 2 (1489) and find the next set checking only odd numbers.

Project Euler 49 Solution

Runs < 0.005 seconds in Python 2.7.

download arrowUse this link to get the Project Euler 49 Solution Python 2.7 source.

Comments

  • Functions is_prime, is_perm are listed in Common Functions and Routines for Project Euler
  • It wasn’t clear, perhaps intentionally, that the terms in the sequence would increase by the same amount (3330) as the example.
  • only 494 iterations to find an answer.
Project Euler 49 Solution last updated

Discussion

2 Responses to “Project Euler 49 Solution”

  1. I thought 3330 was the intended space between 4-digit primes when I first wrote this solution and never gave it much thought. It’s been years since I solved this one and never really looked back.

    It did make sense that the spacing would be consistent with the example.

    Posted by Mike | May 12, 2011, 4:12 PM
  2. incr = 0[2], clearly, and
    incr = 0[9], for same sum of digits,
    =>
    incr = 0[18], like 3330=18*5*37

    but why suppose incr == 3330 ?

    [code]
    def test(n): # test for n prime
    chif=list(str(n))
    chif.sort()
    maxi=int(chif[0])+10*int(chif[1])+100*int(chif[2])+1000*int(chif[3])
    decTot=maxi-n
    for c in range(1, decTot//18):
    if isPrime(n+18*c) and isPrime(n+36*c):
    chif2=list(str(n+18*c))
    chif2.sort()
    if chif==chif2:
    chif3=list(str(n+36*c))
    chif3.sort()
    if chif2==chif3:
    return c # give a correct incr !=0
    return 0

    [\code]

    Posted by Francky | April 28, 2011, 4:33 AM

Post a comment