Python pour le collège et le lycée. Exercices, Cours, TP, Projets.

Nombres polygonaux cycliques

Difficulté : Moyenne (20%) Origine : Projet Euler n°61

Les nombres triangulaires, carrés, pentagonaux, hexagonaux, heptagonaux et octogonaux sont des nombres polygonaux donnés par les formules suivantes :

• Triangulaires : $$ P_{3,n}={\displaystyle \frac{n(n+1)}{2}}$$
  1, 3, 6, 10, 15, ...
• Carrés : $$ P_{4,n}=n^2$$
  1, 4, 9, 16, 25, ...
• Pentagonaux : $$ P_{5,n}={\displaystyle \frac{n(3n-1)}{2}}$$
  1, 5, 12, 22, 35, ...
• Hexagonaux : $$ P_{6,n}=n(2n-1)$$
  1, 6, 15, 28, 45, ...
• Heptagonaux : $$ P_{7,n}={\displaystyle \frac{n(5n-3)}{2}}$$
  1, 7, 18, 34, 55, ...
• Octogonaux : $$ P_{8,n}=n(3n-2)$$
  1, 8, 21, 40, 65, ...

Les 3 nombres de quatre chiffres 8128, 2882 et 8281 possède trois propriétés intéressantes :

1. Ils sont cycliques au sens suivant : les deux derniers chiffres de chaque nombre sont les deux premiers du nombre suivant ( y compris le dernier avec le premier)
2. Chaque nombre polygonal est représenté par un nombre différent : Triangulaire ($$ P_{3,127}=8128$$), Carré ($$ P_{4,91}=8281$$) et Pentagonal ($$ P_{5,44}=2882$$).
3. C'est le seul ensemble de nombre à quatre chiffres qui a cette propriété.

Trouver la somme de l'unique ensemble de six nombres de quatre chiffres qui forment un ensemble cyclique (comme présenté dans l'exemple) et tel que chaque type de polygone soit représenté une et une seule fois (Triangulaire, carré,..., Octogonal)

On affichera le résultat avec print.

Permutations cubiques

Difficulté : Moyenne (15%) Origine : Projet Euler n°62

Le cube 41063625 ($$ {3453}^3$$) peut être permuté pour produire deux autres cubes 56623104 ($$ {384}^3$$) and 66430125 ($$ {405}^3$$). En fait, 41063625 est le plus petit cube ayant exactement trois permutations de ses chiffres qui sont des cubes.

Trouver le plus petit cube qui a exactement cinq permutations de ses chiffres qui sont des cubes.

On affichera le résultat avec print.

Puissances et nombre de chiffres

Difficulté : Facile Origine : Projet Euler n°63

Le nombre de cinq chiffres $$ 16807=7^5$$ est aussi une puissance 5-ième. De même, le nombre de 9 chiffres $$ 134217728=8^9$$ est une puissance 9-ième.

Combien existe-t-il de nombres entiers strictement positifs de n-chiffres qui sont aussi des puissances n-ième ?

On affichera le résultat avec print.

Racines carrées de période impaire

Difficulté : Moyenne(20%) Origine : Projet Euler n°64

Toutes les racines carrées sont périodiques quand elles sont écrites sous forme de fractions continues c'est à dire sous la forme :

$$ \sqrt{N}=a_0+{\displaystyle \frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\dots }}}}$$

Par exemple :

$$ \sqrt{23}=4+\sqrt{23}-4=4+{\displaystyle \frac{1}{\frac{1}{\sqrt{23}-4}}}=4+{\displaystyle \frac{1}{1+\frac{\sqrt{23}-3}{7}}}$$

Si on continue, on obtiendrait le développement suivant :
$$ \sqrt{23}=1+{\displaystyle \frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{8+\dots }}}}}$$

Le processus peut être résumé comme suit :

$$ a_0=4$$, $$ {\displaystyle \frac{1}{\sqrt{23}-4}}={\displaystyle \frac{\sqrt{23}+4}{7}}=1+{\displaystyle \frac{\sqrt{23}-3}{7}}$$
$$ a_1=1$$, $$ {\displaystyle \frac{7}{\sqrt{23}-3}}={\displaystyle \frac{7(\sqrt{23}+3)}{14}}=3+{\displaystyle \frac{\sqrt{23}-3}{2}}$$
$$ a_2=3$$, $$ {\displaystyle \frac{7}{2}}\sqrt{23}-3={\displaystyle \frac{2(\sqrt{23}+3)}{14}}=1+{\displaystyle \frac{\sqrt{23}-4}{7}}$$
$$ a_3=1$$, $$ {\displaystyle \frac{7}{\sqrt{23}-4}}={\displaystyle \frac{7(\sqrt{23}+4)}{7}}=8+\sqrt{23}-4$$
$$ a_4=8$$, $$ {\displaystyle \frac{1}{\sqrt{23}-4}}={\displaystyle \frac{\sqrt{23}+4}{7}}=1+{\displaystyle \frac{\sqrt{23}-3}{7}}$$
$$ a_5=1$$, $$ {\displaystyle \frac{7}{\sqrt{23}-3}}={\displaystyle \frac{7(\sqrt{23}+3)}{14}}=3+{\displaystyle \frac{\sqrt{23}-3}{2}}$$
$$ a_6=3$$, $$ {\displaystyle \frac{7}{2}}\sqrt{23}-3={\displaystyle \frac{2(\sqrt{23}+3)}{14}}=1+{\displaystyle \frac{\sqrt{23}-4}{7}}$$
$$ a_7=1$$, $$ {\displaystyle \frac{7}{\sqrt{23}-4}}={\displaystyle \frac{7(\sqrt{23}+4)}{7}}=8+\sqrt{23}-4$$

Les dix premieres représentations en fraction continue des racines carrées (irrationnelles) sont :

$$ \sqrt{2}=[1;(2)]$$, periode=1
$$ \sqrt{3}=[1;(1,2)]$$, periode=2
$$ \sqrt{5}=[2;(4)]$$, periode=1
$$ \sqrt{6}=[2;(2,4)]$$, periode=2
$$ \sqrt{7}=[2;(1,1,1,4)]$$, periode=4
$$ \sqrt{8}=[2;(1,4)]$$, periode=2
$$ \sqrt{10}=[3;(6)]$$, periode=1
$$ \sqrt{11}=[3;(3,6)]$$, periode=2
$$ \sqrt{12}=[3;(2,6)]$$, periode=2
$$ \sqrt{13}=[3;(1,1,1,1,6)]$$, periode=5

Exactement quatre fractions continues pour N ≤ 13 ont une période impaire.

Combien de fractions continues pour N ≤ 10000 ont une période impaire ?

On affichera le résultat avec print.

Convergence de e

Difficulté : Moyenne(15%) Origine : Projet Euler n°65

La racine carrée de 2 peut être écrite en fraction continue infinie sous la forme :
$$ \sqrt{2}=1+{\displaystyle \frac{1}{2+\frac{1}{2+\frac{1}{2+\dots }}}}$$

Cette fraction continue infinie peut s'écrire $$ \sqrt{2}=[1;(2)]$$ où $$ (2)$$ indique que 2 se répète ad infinitum. De la même manière, on a $$ \sqrt{23}=[4;(1,3,1,8)]$$ (voir le problème précédent).

La suite des valeurs des fractions continues partielles qu'on obtient en s'arretant donne pour une racine carrée la meilleurs approximation rationnelle. Considérons les fractions obtenues pour $$ \sqrt{2}$$ :

$$ 1+{\displaystyle \frac{1}{2}}={\displaystyle \frac{3}{2}}$$
$$ 1+{\displaystyle \frac{1}{2+\frac{1}{2}}}={\displaystyle \frac{7}{5}}$$
$$ 1+{\displaystyle \frac{1}{2+\frac{1}{2+\frac{1}{2}}}}={\displaystyle \frac{17}{12}}$$
$$ 1+{\displaystyle \frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2}}}}}={\displaystyle \frac{41}{29}}$$

On obtient ainsi la suite des dix premieres fractions continues partielles de $$ \sqrt{2}$$ :
$$ 1,{\displaystyle \frac{3}{2}},{\displaystyle \frac{7}{5}},{\displaystyle \frac{17}{12}},{\displaystyle \frac{41}{29}},{\displaystyle \frac{99}{70}},{\displaystyle \frac{239}{169}},{\displaystyle \frac{577}{408}},{\displaystyle \frac{1393}{985}},{\displaystyle \frac{3363}{2378}},...$$

La constant e a un développement remarquable :

$$ e=[2;1,2,1,1,4,1,1,6,1,...,1,2k,1,...]$$.

Les dix premiers termes de la suite des fractions continues partielles de e sont : $$ 2,3,{\displaystyle \frac{8}{3}},{\displaystyle \frac{11}{4}},{\displaystyle \frac{19}{7}},{\displaystyle \frac{87}{32}},{\displaystyle \frac{106}{39}},{\displaystyle \frac{193}{71}},{\displaystyle \frac{1264}{465}},{\displaystyle \frac{1457}{536}},...$$

La somme des chiffres du numérateur de la dixième fraction est 1+4+5+7=17.

Trouver la somme des chiffres du numérateur de la 100e fraction continue partielle de e.

On affichera le résultat avec print.