Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Equation Diophantienne

Difficulté : Moyenne (25%) Origine : Projet Euler n°66

COnsidérons l'équation Diophantienne quadratique de la forme : x2Dy2=1.

Par exemple, quand D=13, la solution minimale en x est 649213×1802=1.

On admettra qu'il n'y a pas de solutions pour les entiers strictement positifs quand D est un carré.

En trouvant les solutions minimales en x pour D dans l'ensemble {2, 3, 5, 6, 7}, on obtient :

322×22=1
223×12=1
925×42=1
526×22=1
827×32=1

Donc, en considérant les solutions minimales en x pour D ≤ 7, le plus grand x est obtenu pour D=5.

Trouver la valeur de D ≤ 1000 pour laquelle la valeur de x est maximale parmi les solutions minimale en x de l'équation considérée.

On affichera le résultat avec print.

Equation Diophantienne

Chemin de somme maximum II

Difficulté : Facile Origine : Projet Euler n°67

A partir d'un nombre dans les triangles ci-dessous, on peut se déplacer uniquement vers le bas soit vers le nombre juste en dessous, soit vers le nombre à droite de celui qui est en dessous. Par exemple, à partir du 6, on peut descendre uniquement vers le 9 ou le 3 mais pas vers le 5.

En partant du sommet du triangle ci-dessous, le chemin dont le total en additionnant les nombres du chemin est le plus grand est 23.

3
7 4
2 4 6
8 5 9 3

En effet, 3 + 7 + 4 + 9 = 23.

Trouver le chemin de somme maximum dans le triangle donné. (Le triangle est donné sous forme de chaine de caractère).

Note : L'énoncé est le même que le problème 18 à la différence près que cette fois ci le triangle a 100 lignes ce qui fait un total de 2^99 chemins. Même avec un ordinateur qui calcule 1000 milliard de chemins par seconde, il faudrait 20 milliard d'années pour tous les tester. Il vaut donc mieux refléchir à des stratégies plus efficaces.

On affichera le résultat avec print.

Chemin de somme maximum II

Pentagone magique

Difficulté : Moyen(25%) Origine : Projet Euler n°68

Considérons le triangle magique suivant, rempli avec les nombres de 1 à 6 tel que chaque ligne a une somme qui vaut neuf.

Triangle magique

En tournant dans le sens des aiguilles d'une montre et en commençant par le groupe de trois qui a le noeud externe dont la valeur est la plus petite (4,3,2 dans cet exemple), chaque solution peut être décrite de manière unique. Par exemple, la solution ci-dessus peut être décrite par l'ensemble : 4,3,2; 6,2,1; 5,1,3 .

Il est possible de completer ce triangle avec quatre sommes différentes : 9, 10, 11 et 12. Il y a en tout huit solutions :

Total Ensemble solution
9 4,2,3; 5,3,1; 6,1,2
9 4,3,2; 6,2,1; 5,1,3
10 2,3,5; 4,5,1; 6,1,3
10 2,5,3; 6,3,1; 4,1,5
11 1,4,6; 3,6,2; 5,2,4
11 1,6,4; 5,4,2; 3,2,6
12 1,5,6; 2,6,4; 3,4,5
12 1,6,5; 3,5,4; 2,4,6

En concaténant chaque groupe, il est possible de former une chaine de caractère de 9 chiffres. La chaine maximum pour ce triangle magique est 432621513.

En utilisant des nombres de 1 à 10, selon l'arrangement, il est possible de former ainsi des chaines de 16 ou 17 chiffres. Quelle est la chaine de caractère maximum formée de 16 chiffres pour un pentagone magique ?

Pentagone magique

On affichera le résultat avec print.

Pentagone magique

Fonction phi d'Euler et maximum

Difficulté : Moyen(10%) Origine : Projet Euler n°69

La fonction phi d'Euler, φ(n) est utilisée pour déterminer le nombre d'entiers inférieurs à n qui sont premiers avec n. Par exemple, comme les entiers 1, 2, 4, 5, 7, et 8 sont tous inférieurs à 9 et premiers avec 9, on a φ(9)=6.

npremiers avec nφ(n)n/φ(n)
2112
31,221.5
41,322
51,2,3,441.25
61,523
71,2,3,4,5,661.1666...
81,3,5,742
91,2,4,5,7,861.5
101,3,7,942.5

On peut voir que pour n=6, la valeur de n/φ(n) est maximum pour n ≤ 10.

Trouver la valeur de n ≤ 1,000,000 pour laquelle n/φ(n) est maximum.

On affichera le résultat avec print.

Fonction phi d'Euler et maximum

Fonction phi d'Euler et permutations

Difficulté : Moyen(20%) Origine : Projet Euler n°70

La fonction phi d'Euler, φ(n) est utilisée pour déterminer le nombre d'entiers inférieurs à n qui sont premiers avec n. Par exemple, comme les entiers 1, 2, 4, 5, 7, et 8 sont tous inférieurs à 9 et premiers avec 9, on a φ(9)=6.

le nombre 1 est considéré comme premier avec tout entier strictement positif donc φ(1)=1.

Il est interessant de noter que φ(87109)=79180, en remarquant que 87109 est une permutation de 79180.

Trouver la valeur de n inférieure à 107 pour laquelle φ(n) est une permutation de n et le ratio n/φ(n) est un minimum.

On affichera le résultat avec print.

Fonction phi d'Euler et permutations

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content