Projet Euler 37

problème

3797 a une propriété intéressante: d'abord, c'est un nombre premier, et quand les chiffres sont enlevés de gauche à droite, ce sont tous des nombres premiers (3797, 797, 97, 7). De même, les chiffres de droite à gauche. Tous sont des nombres premiers sauf pour (3797, 379, 37, 3).

Il n'y a que 11 nombres premiers qui peuvent être tronqués à partir de la droite ou de la gauche. Trouvez la somme.

Remarque: nous ne considérons pas que 2, 3, 5, 7 sont tronqués. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2037

Considération mathématique

Ces nombres ont un premier chiffre de 3 ou 7. Si le premier chiffre est 1,4,6,8,9, le nombre lui-même n'est pas un nombre premier, et si le premier chiffre de deux chiffres ou plus est 2,5, c'est un multiple de 2 ou un multiple de 5. De plus, vous n'avez pas besoin de 2,4,5,6,8 dans les chiffres du milieu. En effet, si 2,4,5,6,8 est entré au milieu lorsqu'il est arrondi à partir de la droite, le nombre n'est plus un nombre premier. De plus, il n'y a pas de nombre de 3 chiffres ou plus dont le chiffre maximum est de 2,5. D'après la considération ci-dessus, il est de 1,3,7,9 sauf pour les chiffres, mais si le chiffre le plus significatif est 2 ou 5 et qu'il y a un ou plusieurs 1, 7 au milieu, ce sera toujours un multiple de 3 au milieu. De plus, si le chiffre le plus significatif est 2 ou 5 et le reste est 3 ou 9, il sera un multiple de 3 lorsqu'il est arrondi à partir de la gauche. Pour les nombres à deux chiffres, 23 et 53 sont des nombres premiers qui satisfont à la condition. Pour les nombres autres que ceux-ci, on peut voir que les nombres dans lesquels chaque chiffre se compose de 1,3,5,7 doivent être considérés.

Répondre

  1. Pour n chiffres, le nombre qui est un nombre premier parmi les nombres combinés de 1, 3, 5 et 7 à partir de la droite est considéré comme un objet de type ensemble nr.
  2. Pour n chiffres, le nombre qui est un nombre premier parmi les nombres combinés de 1, 3, 5 et 7 à partir de la droite est considéré comme un objet de type ensemble nl.
  3. Ajoutez l'ensemble de produits nr et nl à l'ensemble de réponses s.
  4. Ensuite, pour n + 1 chiffres, attachez l'un des 1,3,7,9 au nombre premier susmentionné tronqué à partir de la droite ou de la gauche dans une direction appropriée pour déterminer s'il s'agit d'un nombre premier ou non. Ce faisant, les deux ensembles de nombres premiers des étapes 1 et 2 ci-dessus sont créés.

Il se termine lorsque le nombre de colonnes de réponses atteint 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()

J'ai écrit le code que 23,53 demande également. Dans ce cas, le nombre à combiner comprend non seulement 1,3,7,9 mais aussi 2,5. De plus, l'ensemble nr (N est le nombre de répétitions + 1) de nombres à N chiffres de nombres premiers joints par la droite est vide, ou l'ensemble nr (N est) de nombres à N chiffres de nombres premiers joints par la gauche. Il se termine lorsque le nombre de répétitions + 1) devient vide. Ce code a également confirmé que le nombre ci-dessus n'était que de 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

Projet Euler 37
Projet Euler 7
Projet Euler 47
Projet Euler 31
Projet Euler 4
Projet Euler 38
Projet Euler 17
Projet Euler 26
Projet Euler 8
Projet Euler 23
Projet Euler 22
Projet Euler 19
Projet Euler 50
Projet Euler 42
Projet Euler 33
Projet Euler 32
Projet Euler 43
Projet Euler 35
Projet Euler 36
Projet Euler 24
Projet Euler 46
Projet Euler 48
Projet Euler 45
Projet Euler 6
Projet Euler 44
Projet Euler 39
Projet Euler 40
Projet Euler 49
Projet Euler 29
Projet Euler 27
Projet Euler 41
Projet Euler 18
Projet Euler 13
Projet Euler 30
Projet Euler 16
Projet Euler 14
Projet Euler 34
Projet Euler 25
[Projet Euler] problème1
Projet Euler15 "Chemin du treillis"
Project Euler 2 Acceleration 2.21 Économisez des microsecondes.
Projet Euler Original Method Group 1
Qu'est-ce que Project Euler 3 Acceleration?
Programmation fonctionnelle dans Python Project Euler 1
Projet Euler 10 "Somme des nombres premiers"
[Note] Projet Euler en Python (problème 1-22)
Programmation fonctionnelle dans Python Project Euler 3
Projet Euler # 5 "Minimum Multiple" en Python
Projet Euler 4 Tentative d'accélération
Programmation fonctionnelle dans Python Project Euler 2
Projet Euler 11 "Produit maximum dans la grille"
Projet Euler # 15 "Lattice Path" en Python
Projet Euler # 4 "Calligraphie maximum" en Python
Projet Euler 9 Conservation des résultats des calculs
Projet Euler # 3 "Maximum Prime Factors" en Python
Projet Euler # 11 "Produit maximum dans la grille" en Python
Projet Euler # 7 "1000 1er nombre premier" en Python
Projet Euler # 16 "Somme des pouvoirs" en Python
Projet Euler # 9 "Numéro spécial Pitagolas" en Python
Projet Euler # 14 "Colonne de nombre de collats la plus longue" en Python
J'ai écrit Project Euler 1 en une seule ligne.