Project Euler 37

problem

3797 has an interesting property. First, it is a prime number, and when the digits are removed from left to right, it is all prime numbers (3797, 797, 97, 7). Similarly, the digits from right to left. All are prime numbers except for (3797, 379, 37, 3).

There are only 11 prime numbers that can be truncated from the right or from the left. Find the sum.

Note: We do not consider 2, 3, 5, 7 to be truncated prime numbers. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2037

Mathematical consideration

Such numbers have a first digit of 3 or 7. If the first digit is 1,4,6,8,9, the number itself is not a prime number, and if the first digit of two or more digits is 2,5, it is a multiple of 2 or a multiple of 5. Also, you don't need 2,4,5,6,8 in the middle digits. This is because if 2,4,5,6,8 is entered in the middle when rounded down from the right, the number is no longer a prime number. In addition, there is no number with 3 or more digits that has a maximum digit of 2.5. From the above consideration, it is 1,3,7,9 except for that digit, but if the most significant digit is 2 or 5 and there is one or more 1, 7 in the middle, it will always be a multiple of 3 in the middle. Also, if the most significant digit is 2 or 5 and the rest is 3 or 9, it will be a multiple of 3 when rounded down from the left. For two-digit numbers, 23 and 53 are prime numbers that satisfy the condition. For numbers other than these, it can be seen that numbers with each digit consisting of 1,3,5,7 should be considered.

Answer

  1. For n digits, the number that is a prime number among the combined numbers of 1, 3, 5, and 7 from the right is held as a set type object nr.
  2. For n digits, the number that is a prime number among the combined numbers of 1, 3, 5, and 7 from the right is held as a set type object nl.
  3. Add the intersection of nr and nl to the answer set s.
  4. Next, for n + 1 digits, attach any of 1,3,7,9 to the prime number truncated from the right or left from the appropriate direction to determine whether it is a prime number or not. By doing so, the two prime number sets in steps 1 and 2 above are created.

It ends when the number of answer columns reaches 11.

def conjoin(f, iter1, iter2):
  return set(f(e1,e2) for e1 in iter1 for e2 in iter2)

def connect_num(e1,e2):
  return str(e1)+str(e2)

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
    

import mymath

def get_pri(iter1, pri):
  ret = []
  for n in iter1:
    if is_prime(n,pri):
      ret.append(n)
  return set(ret)

def main():
  MAX = 10**7
  pri = mymath.get_primes(MAX)
  nr = [3,7]
  nl = [3,7]
  n2 = [1,3,7,9]
  s = set(['23', '53'])
  MAX_LEN = 11
  while len(s)<MAX_LEN:
    if len(nr) == 0:
      break
    nr = set(get_pri(conjoin(connect_num,nr,n2),pri))
    nl = set(get_pri(conjoin(connect_num,n2,nl),pri))
    s = s | (nr & nl)
  ans = 0
  for n in s:
    ans += int(n)
  print s
  print ans
main()

I wrote the code for 23,53 as well. In this case, the number to be combined includes not only 1,3,7,9 but also 2,5. Also, the set nr (N is the number of repetitions + 1) of N-digit numbers of prime numbers joined from the right is empty, or the set nr (N is) of N-digit numbers of prime numbers joined from the left. It ends when the number of repetitions + 1) becomes empty. This code also confirmed that the number above was only 11.

import copy
import mymath
def main():
  MAX = 10**7
  pri = mymath.get_primes(MAX)
  nr = set(get_pri(range(1,10),pri))
  nl = copy.deepcopy(nr)
  ns = [1,2,3,5,7,9]
  s = set([])
  while len(nr)>0 and len(ns)>0:
    nr = set(get_pri(conjoin(connect_num,nr,ns),pri))
    nl = set(get_pri(conjoin(connect_num,ns,nl),pri))
    s = s | (nr & nl)
  ans = 0
  for n in s:
    ans += int(n)
  print s
  print ans

Recommended Posts

Project Euler 37
Project Euler 7
Project Euler 47
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 48
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
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"
[Note] Project Euler in Python (Problem 1-22)
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 # 3 "Maximum Prime Factors" in Python
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 16 "Sum of Powers" 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.