Projecet Euler 12 Trouvez le nombre de fractions sans diviser.

problème

La séquence des triangles est représentée par la somme des nombres naturels, et le septième triangle est 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Les 10 premiers termes du triangle sont:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Sera.

Voici une liste des réductions pour les sept premiers trimestres.

1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28

De là, on peut voir que le septième triangle, 28, est le premier triangle avec plus de cinq réductions.

Alors, quels sont les premiers triangles avec plus de 500 réductions? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2012

Considération mathématique

Il est difficile de dire un nombre triangulaire, mais le fait est qu'un nombre triangulaire est un nombre représenté par la somme des nombres naturels de 1 à n. La somme des nombres naturels de 1 à n est exprimée par la formule suivante.

n * (n+1) /2

Et puisque n et (n + 1) sont premiers l'un par rapport à l'autre (n'ont pas de facteur premier commun), n / 2 et n + 1 ou n et (n + 1) / 2 sont également premiers l'un par rapport à l'autre. Que ce soit n / 2 et n + 1 ou n et (n + 1) / 2 dépend de ce qui est pair. Le nombre de fractions obtenu en multipliant les nombres naturels n1 et n2, qui sont mutuellement premiers, est égal au nombre obtenu en multipliant le nombre de fractions de n1 et le nombre de fractions de n2.

Politique de réponse 1

Sur la base des considérations mathématiques ci-dessus, nous répondrons à cette question en utilisant l'algorithme suivant.

Faites une liste de nombres premiers en utilisant mymath. 　mymath.py 　http://qiita.com/cof/items/45d3823c3d71e7e22920
Tant que le nombre de fractions est inférieur à 500, la variable n est incrémentée dans l'ordre à partir de 1 dans la boucle de boucle.
Après avoir déterminé si n + 1 est pair ou non, effectuez une factorisation n + 1 ou (n + 1) / 2 premiers en utilisant la liste des nombres premiers.
Obtenez le nombre de fractions de n + 1 en dessous des facteurs premiers obtenus et multipliez-le par le nombre de fractions de n précédemment mémorisées.
Mémorisez le nombre multiplié sous la forme d'un nombre d'environ et revenez à 2.

code

import mymath

def cof():
  pri = mymath.get_primes(10**4)
  n = 1
  num_fac = 1
  lim = 500
  n1_fac =  mymath.get_number_of_factor(n,pri)
  while num_fac < lim:
    n += 1
    if (n+1)%2:
      n2_fac =  mymath.get_number_of_factor(n+1,pri)
    else:
      n2_fac =  mymath.get_number_of_factor((n+1)/2,pri)
    num_fac = n1_fac * n2_fac
    n1_fac = n2_fac
  print n * (n+1) / 2

Découverte des problèmes et nouvelle prise de conscience

Quand j'ai essayé de l'exécuter, c'était 1,62 seconde par exécution, ce qui est lent au niveau de la merde. Quand je me suis demandé si je pouvais l'accélérer d'une manière ou d'une autre, j'ai réalisé que la factorisation était la cause de la lenteur en premier lieu. J'ai remarqué que la même méthode que Eratostenes peut être utilisée pour obtenir la fraction de chaque nombre sans division.

Politique de réponse 2

Pour plus de détails,

Faites une liste pour chaque numéro. "" "," ", ..."
Faites une boucle de 1 à un nombre approprié et ajoutez le nombre de cibles en tant qu'élément à une position qui est un multiple du nombre de cibles. Par exemple, si 2 est le nombre cible [[]. [1], [1], [1], [1] ← Ajouter 2 à la liste correspondant au multiple 4, le même que 6,8,10 ci-dessous.
Répétez 2 et, étrangement, vous aurez une liste de vraies fractions des nombres correspondants. [[].[1],[1],[1],[1,2],[1],[1,2,3],[1],[1,2,4],[1,3],[1,2,5],...]
Sur la base de cette liste de réductions, trouvez le nombre de réductions de n dans la politique de réponse 1.

code

Ajout des fonctions suivantes à mymath.

def factor_seq(max):
  ret = [[0]]
  for i in range(max):
    ret += [[1]]
  seq = range(max+1)
  for i in seq[2:max//2+1]:
    for j in seq[i*2::i]:
      ret[j] += [i]
  return ret

Codé en utilisant ce qui précède

def cof2():
  fq = mymath2.factor_seq(10**5)
  n = 1
  num_fac = 1
  lim = 500
  n1_fac = len(fq[n])
  while num_fac < lim:
    n += 1
    if (n+1)%2:
      n2_fac =  len(fq[n+1])
    else:
      n2_fac =  len(fq[(n+1)/2])
    num_fac = n1_fac * n2_fac
    n1_fac = n2_fac
  print n * (n+1) / 2

En conséquence, c'était 640ms, ce qui était un niveau que je pouvais supporter. Probablement, si vous changez ret [j] + = [i] en ret [j] + = 1 dans factor_seq, vous pouvez trouver le nombre de fractions, donc je pense que ce sera plus rapide si vous l'utilisez.