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

def match(num, regex, digit, remaining_replacements, start_pos, patterns, N, L, smallest_prime):
    if start_pos == 0 and digit == '0':
        return
        
    digit_str = str(digit)
    for i in range(start_pos, N):
        if regex[i] != digit_str:
            continue
            
        regex[i] = '.'
        if remaining_replacements == 1:
            pattern = ''.join(regex)
            if pattern not in patterns:
                patterns[pattern] = []
            patterns[pattern].append(num)
            if len(patterns[pattern]) >= L and patterns[pattern][0] < smallest_prime[0]:
                smallest_prime[0] = patterns[pattern][0]
        else:
            match(num, regex, digit, remaining_replacements - 1, i + 1, patterns, N, L, smallest_prime)
        regex[i] = digit_str

def find_primes(N):
    max_num = 10 ** N - 1
    primes = [True] * (max_num + 1)
    primes[0] = primes[1] = False
    
    for i in range(2, int(max_num ** 0.5) + 1):
        if primes[i]:
            for j in range(i * i, max_num + 1, i):
                primes[j] = False
    return primes

N, K, L = map(int, input().split())
primes, patterns, smallest_prime = find_primes(N), {}, [float('inf')]
mn, mx = 10**(N - 1), 10**N - 1

for num in range(mn, mx + 1):
    if primes[num]:  # More efficient to check directly
        digits = list(str(num))
        for d in range(10):
            match(num, digits[:], d, K, 0, patterns, N, L, smallest_prime)

    if N == 7 and ((K == 1 and num > 2_000_000) or (K == 2 and num > 3_000_000)):
        break

print(min([' '.join(map(str, arr[:L]))
         for arr in patterns.values()
         if len(arr) >= L and arr[0] == smallest_prime[0]]))

Last Word