Problème de codage quotidien : nombres triangulaires et grands diviseurs

Bienvenue à tous avec un autre problème à résoudre ! Aujourd'hui, nous allons parler des nombres triangulaires et de leurs diviseurs : surtout les plus grands !

Alors que nous pouvons admirer ma fabuleuse représentation artistique des nombres triangulaires dans la nature, ayons nos avertissements habituels :

1. Ce problème est fourni par le merveilleux site Web ProjetEuler.net , auquel vous pouvez vous abonner ici ! Il y a plus de 800 problèmes de mathématiques et de codage à résoudre et une vaste archive de discussions à leur sujet. C'est littéralement l'outil parfait pour se gratter la tête et apprendre quelque chose de nouveau ! Allez le vérifier et essayez également de résoudre vos défis !

   
   

2. Je ne suis pas un programmeur expert : juste un gars qui aime écrire sur ce genre de choses et aime partager ses clichés. Je suis sûr que ce ne sera pas la solution optimale, donc si vous en avez une meilleure ou une idée sur la façon de l'optimiser, vous êtes plus que bienvenu si vous souhaitez partager !

Assez parlé, voyons ce que le problème d'aujourd'hui a à offrir :

La séquence de nombres triangulaires est générée en ajoutant les nombres naturels. Ainsi, le numéro du 7e triangle serait 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Les dix premiers termes seraient : 1,3,6,10,15,21,28,36,45,55,…

Énumérons les facteurs des sept premiers nombres triangulaires :

Nous pouvons voir que 28 est le premier nombre de triangles à avoir plus de cinq diviseurs.

Quelle est la valeur du premier nombre de triangles ayant plus de cinq cents diviseurs ?

Le problème est assez simple : on nous demande de comprendre quel est le premier nombre triangulaire qui a plus de 500 diviseurs . Tout d'abord, regardons mieux ce qu'est un nombre triangulaire et ce qu'est un diviseur.

Nombres triangulaires

Les nombres triangulaires sont un sous-ensemble particulier de nombres qui sont formés par la somme de tous les nombres naturels jusqu'à un certain. Ils sont appelés triangulaires car vous pouvez toujours les disposer en triangle . Voici quelques exemples:

Dans l'image ci-dessus, il s'agit des 3e, 4e et 5e nombres triangulaires. Ainsi, par exemple, le 3ème nombre est formé comme 1+2+3 = 6, le 4ème comme 1+2+3+4 = 10, et ainsi de suite. D'une manière générale, le nombre triangulaire nᵗʰ, Tₙ, est égal à

C'est, bien sûr, l'une des séries les plus célèbres en mathématiques, présentée également par Gauss , qui a déclaré que la somme d'entiers consécutifs est égale à :

Donc, fondamentalement, si nous voulons calculer le 3ème nombre triangulaire, par exemple, nous calculons simplement 3*4/2 = 6. Cela sera très utile une fois que nous commencerons à écrire notre solution !

Les diviseurs

Pour donner une définition du diviseur (ou facteur ) d'un nombre n, c'est très simple : c'est un nombre j qui peut être multiplié par un autre entier k pour donner à nouveau n . Par exemple, 3 est un diviseur de 18, car on peut multiplier 3 et 6 pour obtenir à nouveau 18.

Cependant, 5 n'est pas un diviseur de 18, car il n'y a pas de nombre k qui multiplié par 5 donne 18.

Par la définition, on obtient aussi une propriété importante : si j est un diviseur de n car il peut être multiplié par k pour obtenir n, alors aussi k est un diviseur de n car il peut être multiplié par j pour obtenir n.

De cette façon, nous pouvons être sûrs qu'un nombre n a toujours au moins deux diviseurs j et k ( en fait, j peut toujours être 1 et k être n ).

Aussi, pour le dire autrement, un nombre j est un diviseur du nombre n si le reste de n / j est égal à 0 . Ainsi, par exemple, 18/3 = 6, et le reste est 0.

On peut mieux formaliser ce concept avec l'arithmétique modulaire en disant que j est un diviseur de n si n % j = 0. En d'autres termes, on obtient cette seconde propriété :

La troisième et dernière propriété qui nous intéresse est qu'il ne peut y avoir de diviseur d'un nombre n supérieur à n/2, plutôt que n lui-même. C'est assez simple à comprendre. D'après la première propriété, nous savons que les facteurs sont en quelque sorte « liés » entre eux dans l'intervalle 1,…,n.

C'est parce que encore une fois, si j \ n, c'est parce que j * k = n. Par conséquent, également k \ n. Reprenons 18 comme exemple, trouvons ses diviseurs et colorons-les pour refléter cette propriété.

Ainsi, par exemple, si j = 3, k = 6, et inversement si j = 6, k = 3, cela signifie que le plus petit j que nous pouvons utiliser, en plus de 1, est 2, ce qui nous donne le plus grand k possible, n/2 (9 dans notre cas) . Cela marche:

• pour les nombres pairs, auquel cas le plus grand facteur sera exactement égal à la moitié de n ;

• pour les nombres impairs : si on ne peut pas diviser n par 2 (car être impair nous donnera un nombre rationnel) ; cela signifie que nous ne pouvons utiliser que j > 2, ce qui nous donnera toujours des résultats k < n/2.

  
  

Enfin, il n'y a qu'un seul cas où j et k peuvent être égaux : lorsque n est un nombre carré. Par exemple, lorsque n = 36, un facteur possible j = 6 produira un autre facteur k = 6. Nous discuterons plus en détail de ce cas plus tard dans la partie code.

Ces concepts sont assez triviaux, bien sûr, mais ils seront très importants dans notre solution !

Le code

Le code sera écrit en Go , car c'est vraiment un langage rapide qui maintient toujours un bon niveau de lisibilité. Nous allons diviser la solution en deux : d'abord, nous allons créer une fonction pour trouver les diviseurs d'un nombre, puis nous l'appliquerons aux nombres triangulaires .

Voyons d'abord la fonction :

Nous créons notre fonction qui accepte un entier n et renvoie un tableau d'entiers out , qui contiendra nos diviseurs. Après cela, nous out aux facteurs triviaux, à savoir 1 et n lui-même.

Ensuite, nous commençons à boucler j de 2 à n/2 (à partir de la deuxième propriété ; notez également que nous ne sommes pas intéressés par n/2 lui-même car dans le cas où n est pair, k = n/2 sera ajouté aux diviseurs par le j = 2 itération : c'est pourquoi on s'arrête à j<n/2 et non j≤ n/2 ).

De cette façon, nous ne pouvons vérifier les diviseurs que dans la première moitié de n , accélérant un peu le processus.

A chaque boucle, on vérifie 3 choses :

• La troisième instruction if vérifie en fait si n%j==0 , en d'autres termes, si 0 ≡ n (mod j). Si oui, nous avons trouvé un facteur, et nous ajoutons j à la liste. On peut aussi ajouter son homologue k à la liste, en calculant n/j puis en passant au j suivant ;

• La deuxième instruction if vérifie si n est un carré, et donc j est la racine de n . Si tel est le cas, un seul diviseur j sera ajouté à out , afin d'éviter les doublons, puis l'algorithme continue.

  
  

  Supposons n = 36 : si ce petit bloc manquait, la troisième instruction if serait déclenchée, out la réception j = 6 et k = n/j = 36/6 = 6 , créant ainsi un doublon.

• La première instruction if est la plus complexe : son but est de vérifier si nous commençons à avoir des paires jk répétitives. Si tel est le cas, nous pouvons instantanément rompre la boucle, car notre facteur sera déjà présent dans out .

  
  

Plus précisément sur ce troisième point, il y a deux cas à vérifier : si out[len(out)-1] == j ou out[len(out)-2] == j .

Le premier cas est le plus classique : prenons le nombre T₇ = 28 par exemple :

Lorsque j = 7 , il sera égal à la dernière valeur insérée. Par conséquent, nous pouvons rompre la boucle.

Le deuxième cas ne se produit que lorsque nous avons trouvé un carré n . Reprenez 36, par exemple :

Lorsque j = 9 , il sera égal à la dernière valeur ajoutée avant la racine carrée de n , qui n'apparaît qu'une seule fois. Par conséquent, à ce stade, nous pouvons rompre la boucle.

Enfin, nous pouvons simplement return out pour avoir nos diviseurs.

Application des résultats

Maintenant que nous avons notre fonction, nous pouvons l'appliquer à chaque nombre triangulaire. Nous allons créer un compteur c qui servira de générateur pour nos nombres triangulaires. Nous calculons le nombre triangulaire associé tn avec l'équation de Gauss et vérifions combien de diviseurs il a.

S'il est supérieur à 500, nous renvoyons ce tn comme résultat.

Mais… il y a un hic !

ProjectEuler.net est vraiment un beau projet : en plus de présenter des énigmes et des problèmes mathématiques, leur objectif principal est de fournir un outil pour commencer à apprendre, à réfléchir et à raisonner sur les mathématiques .

Et j'adore ça : ils sont tellement engagés qu'il est en fait interdit de publier des résultats et des guides pour leurs problèmes (c'est l'un des 100 premiers problèmes, donc je comprends que c'est autorisé).

Compte tenu de cela, je ne pense pas qu'il serait juste de donner simplement la solution pour copier-coller et obtenir le succès . Pour cette raison, je ne vous donne pas la vraie solution : essayez-la par vous-même et essayez de trouver un meilleur algorithme que le mien (il y en a beaucoup). Désolé les gars! 😅

Complexité temporelle

Je suis convaincu qu'il existe de nombreuses meilleures solutions car je pense que celle-ci est un coup assez terrible!

La fonction FindDivisor s'exécute en temps linéaire : puisqu'elle dépend de la taille de l'instance n et qu'elle exécute également au plus n/2 boucles ; on peut le considérer comme un O(n).

Cependant, nous devons d'abord calculer chaque nombre triangulaire, ce qui prend également un temps O(tn), où tn est le résultat (le dernier que nous calculons réellement). Compte tenu de cela, approximativement la complexité temporelle de l'ensemble de l'algorithme devrait être O(tn*n).

Puisque tn devient l'argument ou notre fonction, et que nous exécutons au plus n/2 boucles à l'intérieur, nous pouvons réécrire la complexité temporelle comme O(tn*tn/2) = O(tn²/2) = O(tn²). Donc une solution en temps quadratique , malheureusement !

J'ai été surpris que même si l'algorithme est d'environ ce genre de complexité, il fonctionne néanmoins assez rapidement. Pour donner un résultat sur ma machine (AMD Ryzen 5, moy. ck. 2700 MHz), il a fallu 322,564227 ms.

Essayer de trouver le premier nombre triangulaire dépassant 1000 diviseurs a cependant pris 3,827144472 secondes, il est donc clairement visible que la consommation de temps augmente rapidement.

Conclusion

Nous l'avons finalement fait! J'espère que vous avez apprécié l'article, et j'espère que vous pourrez en tirer quelque chose d'intéressant : si c'est le cas, veuillez laisser un applaudissement ou deux et partager l'article avec quelqu'un qui pourrait être intéressé par ce sujet !

Un grand bravo à ProjectEuler encore une fois pour le travail fantastique : je veux vraiment vous suggérer d'aller voir ce qu'ils peuvent offrir ; Je suis sûr que vous le trouverez super intéressant !

Et comme toujours, merci d'avoir lu.

Nicolas