Project Euler Problem 49 Solution

Project Euler Problem 49 Solution

Prime Permutations

by {BetaProjects} | Project Euler & HackerRank

Project Euler Problem 49 Statement

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?

Solution

HackerRank version

HackerRank logo

Solves all test cases for Hackerrank Project Euler Problem 49

HackerRank Project Euler 49: You are given $N$ and $K$, find all $K$ size sequences where first element is less than $N$ and $K$ elements are permutations of each other, are prime and are in Arithmetic Progression.

Python Source Code

from collections import defaultdict
import math, Euler

digit_prime_product = lambda n: math.prod(primes[int(d)] for d in str(n))

N, K = map(int, input().split())
primes = Euler.prime_sieve(1_000_000)
pPrimes = defaultdict(list) 
seq = defaultdict(lambda: defaultdict(list))

for p in primes:
    if p < N: seq[p]
    prod = digit_prime_product(p)
    for prev in pPrimes[prod]:
        if prev in seq:
            d = p - prev
            [seq[prev][s].append(d//s) for s in seq[prev] if d%s==0]
            seq[prev][d].append(1)
    pPrimes[prod].append(p)

for start_prime, steps in seq.items():
    if len(steps) >= K - 1:
        for step, counts in sorted(steps.items()):
            if len(counts) > K - 2 and counts[K - 2] == K - 1:
                print(''.join(str(start_prime + step * x) for x in range(K)))

Last Word