prime permutations 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 ii each of the 4digit numbers are permutations of one another there are no arithmetic sequences made up of three 1 2 or 3digit primes exhibiting this property but there is one other 4digit increasing sequence what 12digit number do you form by concatenating the three terms in this sequence solution first we need to generate all 4 digits prime numbers then greedy all of them and use permutation to form new numbers use binary search to check if the permutated numbers is in our prime list and include them in a candidate list after that bruteforce all passed candidates sequences using 3 nested loops since we know the answer will be 12 digits the bruteforce of this solution will be about 1 sec checks to see if a number is a prime in osqrtn a number is prime if it has exactly two factors 1 and itself isprime0 false isprime1 false isprime2 true isprime3 true isprime27 false isprime87 false isprime563 true isprime2999 true isprime67483 false 2 and 3 are primes negatives 0 1 all even numbers all multiples of 3 are not primes all primes number are in format of 6k 1 function to search a number in a list using binary search search3 1 2 3 true search4 1 2 3 false search101 listrange100 100 false return the solution of the problem solution 296962999629 checks to see if a number is a prime in o sqrt n a number is prime if it has exactly two factors 1 and itself is_prime 0 false is_prime 1 false is_prime 2 true is_prime 3 true is_prime 27 false is_prime 87 false is_prime 563 true is_prime 2999 true is_prime 67483 false 2 and 3 are primes negatives 0 1 all even numbers all multiples of 3 are not primes all primes number are in format of 6k 1 function to search a number in a list using binary search search 3 1 2 3 true search 4 1 2 3 false search 101 list range 100 100 false return the solution of the problem solution 296962999629
import math
from itertools import permutations


def is_prime(number: int) -> bool:
    

    if 1 < number < 4:
        
        return True
    elif number < 2 or number % 2 == 0 or number % 3 == 0:
        
        return False

    
    for i in range(5, int(math.sqrt(number) + 1), 6):
        if number % i == 0 or number % (i + 2) == 0:
            return False
    return True


def search(target: int, prime_list: list) -> bool:
    

    left, right = 0, len(prime_list) - 1
    while left <= right:
        middle = (left + right) // 2
        if prime_list[middle] == target:
            return True
        elif prime_list[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return False


def solution():
    
    prime_list = [n for n in range(1001, 10000, 2) if is_prime(n)]
    candidates = []

    for number in prime_list:
        tmp_numbers = []

        for prime_member in permutations(list(str(number))):
            prime = int("".join(prime_member))

            if prime % 2 == 0:
                continue

            if search(prime, prime_list):
                tmp_numbers.append(prime)

        tmp_numbers.sort()
        if len(tmp_numbers) >= 3:
            candidates.append(tmp_numbers)

    passed = []
    for candidate in candidates:
        length = len(candidate)
        found = False

        for i in range(length):
            for j in range(i + 1, length):
                for k in range(j + 1, length):
                    if (
                        abs(candidate[i] - candidate[j])
                        == abs(candidate[j] - candidate[k])
                        and len({candidate[i], candidate[j], candidate[k]}) == 3
                    ):
                        passed.append(
                            sorted([candidate[i], candidate[j], candidate[k]])
                        )
                        found = True

                    if found:
                        break
                if found:
                    break
            if found:
                break

    answer = set()
    for seq in passed:
        answer.add("".join([str(i) for i in seq]))

    return max(int(x) for x in answer)


if __name__ == "__main__":
    print(solution())