PGCD & PPCM

(deux idées d’algorithmes pour Alain Zalmanski)

__________

Idée PGCD

... on choisit un nombre quelconque (par exemple 41) et on le considère un instant comme la concaténation de deux chaînes, « a » et « b » (ainsi 41 --> 4 et 1)

On cherche le PGCD(a,b) et on l’ajoute au nombre initial [ici PGCD(4,1)= 1 ; lequel 1, ajouté à 41, donne 42].

Et on recommence à partir du résultat.

Ainsi aura-t-on dans notre exemple :

41+1=42

42+2=44

44+4=48

48+4=52

52+1=53

53+1=54

54+1=55

55+5=60 FIN [un nombre meurt dès qu’il se termine par zéro -- et ce même si l’on peut trouver deux chaînes « a » et « b » valides (ainsi le nombre 1020 meurt-il même si on peut le voir comme 10 et 20 avec PGCD=10 ; c’est injuste mais c’est comme ça !)]

Quel est le plus petit nombre qui ne meurt pas ?

[si plusieurs chaînes « a » et « b » sont possibles, on choisit celle qu’on veut ; ainsi 324 pourra-t-il être vu comme 3 et 24 (PGCD=3) ou 32 et 4 (PGCD=4) : dans le premier cas on continue avec 324+3=327, dans le second avec 324+4=328.]

__________

Idée PPCM

... c’est un peu la même, on ajoute le PPCM au nombre de départ, la FIN étant la même [ceci pour éviter que la suite des résultats n’entre dans un schéma répétitif -- 26, par exemple, donnerait :

26+6=32

32+6=38

38+24=62

62+6=68

68+24=92

92+18=110

110+10=120

120+20=140

140+40=180

180+80=260

et 260 produit 320,380,620,680,920,1100,1200,1400,1800,2600, etc.]

Même remarque que supra sur la décomposition en chaînes « a » et « b » –> on fait comme on veut ! Quel est, ici aussi, le plus petit nombre qui ne meurt pas ?

à+

É.