Project Euler 41

problem

N-digit pandigital means that each digit has a number from 1 to n.

Different from the mathematical definition as shown in the link below

For example, 2143 is a 4-digit Pandigital number and a prime number. N-digit (9 digits or less in the definition of this problem) Answer the largest number among Pandigital prime numbers. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2041

Mathematical consideration

If the sum of the numbers of each digit is a multiple of 3, the number itself will be a multiple of 3, but for 9-digit, 8-digit, 6-digit, 5-digit, 3-digit, and 2-digit Pandigital, the sum of each digit is Since it is a multiple of 3, it cannot be a prime number. Therefore, 7 digits and 4 digits should be checked.

Answer

Create a Pandigital number using the Pandigital number generator you created earlier. Whether it is a prime number or not is determined from a large Pandigital number.

# coding: utf-8
# Here your code !
import copy
import math
def pandigital(digit,seq1,seq2=[]):
  iter1 = map(str,seq1)
  if seq2:
    iter2 = map(str,seq2)
  else:
    iter2 = copy.deepcopy(iter1)
  for d in range(digit-1):
    iter1 = (x+y for x in iter1 for y in iter2 if not (y in x))
  return iter1

def get_prime_boolean(max):
    bool = [False,False]+[True]*(max-1)
    #Multiples of 2 to False
    bool[4::2] = [False] * (len(bool[4::2]))
    p = 3
    p_max = int(math.sqrt(max))+1
    while p<=p_max:
        if bool[p]:
          bool[p**2::p] = [False] * (len(bool[p**2::p]))
        p+=2
    return bool

def get_prime_list(bool):
    length = len(bool)
    return [i for i in range(2,length) if bool[i]]

def get_primes(max):
    bool = get_prime_boolean(max)
    list = get_prime_list(bool)
    return {'bool':bool,'list':list}

def is_prime(num,pri):
  num = int(num)
  if num < len(pri['bool']):
    return pri['bool'][num]

  M = (num**0.5)+1
  #print num
  for p in pri['list']:
    if p > M:
      return True
    if (num % p) == 0:
      return False

  p = pri['list'][-1]+2
  while p<M:
    if (num % p) == 0:
      return False
    p += 2
  return True


def main():
    MAX=10**7
    pri = get_primes(MAX)
    ans = 0
    for i in [7, 4]:
        for pdg in pandigital(i,range(i,0,-1)):
            if is_prime(pdg,pri):
                ans = pdg
                break
        if ans:
            break
    print ans    

main()

Recommended Posts

Project Euler 37
Project Euler 7
Project Euler 31
Project Euler 4
Project Euler 38
Project Euler 17
Project Euler 26
Project Euler 8
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 32
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
[Project Euler] problem1
Project Euler15 "Lattice Path"
Project Euler 2 Acceleration 2.21 Save microseconds.
Project Euler Original Method Group 1
What is Project Euler 3 Acceleration?
Functional programming in Python Project Euler 1
Project Euler 10 "Sum of Prime Numbers"
Functional programming in Python Project Euler 3
Project Euler # 5 "Minimum Multiples" in Python
Project Euler 4 Attempt to speed up
Functional programming in Python Project Euler 2
Project Euler 11 "Maximum product in grid"
Project Euler # 15 "Lattice Path" in Python
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler 9 Retention of calculation results
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 9 "Special Pythagorean Triple" in Python
Project Euler # 14 "Longest Collatz Sequence" in Python
I wrote Project Euler 1 in one liner.
Project Euler # 2 "Even Fibonacci Numbers" in Python
Project Euler # 17 "Number of Characters" in Python
Project Euler # 1 "Multiples of 3 and 5" in Python
Project Euler # 8 "Maximum Product in Number String" in Python
Project Euler # 10 "sum of prime numbers" in Python
Project Euler 28 Inefficient Answer Proposal Create "Spiral Numbers"