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.

  1. Faites une liste de nombres premiers en utilisant mymath.  mymath.py  http://qiita.com/cof/items/45d3823c3d71e7e22920
  2. 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.
  3. 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.
  4. 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.
  5. 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,

  1. Faites une liste pour chaque numéro. "" "," ", ..."
  2. 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.
  3. 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],...]
  4. 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.

Recommended Posts

Projecet Euler 12 Trouvez le nombre de fractions sans diviser.
Comment connaître le nombre de processeurs sans utiliser la commande sar
Trouvez le nombre de jours dans un mois
10. Compter le nombre de lignes
Obtenez le nombre de chiffres
Calculez le nombre de changements
Maya | Découvrez le nombre de polygones dans l'objet sélectionné
Python --Trouvez le nombre de groupes dans l'expression regex
Obtenez le nombre de vues de Qiita
Découvrez l'âge et le nombre de gains des gouverneurs de préfecture dans tout le pays
Calcul du nombre d'associations de Klamer
Obtenez le nombre d'abonnés Youtube
Trouvez l'aire de l'ensemble somme des rectangles qui se chevauchent
Compter / vérifier le nombre d'appels de méthode.
Version Migemo de la commande: find ,: mfind
Projet Euler # 17 "Nombre de caractères" en Python
Trouvez le coefficient du polypole le moins carré
Compter le nombre de caractères avec écho
Sortie du nombre de cœurs de processeur en Python
Comment trouver la zone du diagramme de Boronoi
Trouver la main de "Millijan" par l'optimisation des combinaisons
Calculez le nombre total de combinaisons avec python
Divisez la chaîne de caractères en le nombre de caractères spécifié
Découvrez la fraction de la valeur saisie en python
Minimisez le nombre de polissages en optimisant la combinaison
Trouvez la solution de l'équation d'ordre n avec python
Découvrez le jour par date / heure
Déterminez le nombre de classes à l'aide de la formule Starges
Découvrez le nombre maximum de caractères dans un texte multiligne stocké dans un bloc de données
Trouvez une ligne directrice pour le nombre de processus / threads à définir sur le serveur d'applications