Nombres de Keith.

On appelle nombre de Keith un nombre K de n chiffres ayant la propriété suivante:
en partant des nombres composés chacun d'un des n chiffres de K, on compose une sorte de suite de Fibonacci en calculant la somme des n derniers nombres de la suite pour déterminer le suivant. Si cette suite fournit à un moment le nombre K, ce nombre est dit nombre de Keith.

Exemple: K=197
1,9,7,17(=1+9+7),33(=9+7+17),57(=7+17+33),107(=17+33+57),197(=33+57+107)

Note: les calculs peuvent être accélérés par ak = 2ak-1 - ak-n-1

Vous pouvez charger une version Delphi de la recherche des nombres de Keith en cliquant ici


No. chiffres

 Nombres de Keith

2

 14, 19, 28, 47, 61, 75

3

 197, 742

4

 1104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909

5

 31331, 34285, 34348, 55604, 62662, 86935, 93993

6

 120284, 129106, 147640, 156146, 174680, 183186, 298320, 355419, 694280, 925993

7

 1084051, 7913837

8

 11436171, 33445755, 44121607

9

 129572008, 251133297

10

 aucun

11

 24769286411, 96189170155

12

 171570159070, 202366307758, 239143607789, 296658839738

13

 1934197506555, 8756963649152

14

 43520999798747, 74596893730427, 97295849958669

15

 120984833091531, 270585509032586, 754788753590897

16

 3621344088074041, 3756915124022254, 4362827422508274

17

 11812665388886672, 14508137312404344, 16402582054271374, 69953250322018194, 73583709853303061

18

 119115440241433462, 166308721919462318, 301273478581322148

19

 1362353777290081176, 3389041747878384662, 5710594497265802190, 5776750370944624064, 6195637556095764016 
entier i,N,K,j,S,Sav
tableau Ti i=1,..,4 de entier
pour i de 10 à 1000 faire
  N ß 1+[log10i]
  K ß i
  S ß 0
  pour j de 1 à N faire
     TN-j+1ß K mod 10
     S ß S+TN-j+1K ß K\10
  fpour
  K ß N+1
  Sav ß T1+(K-1) mod N
  T1+(K-1) mod N ß S
  tant que NOT (S³ i) faire
    S ß 2*S-Sav
    K ß K+1
    Sav ß T1+(K-1) mod N
    T1+(K-1) mod N ß S
ftant
si S=i alors écrire i,"est un nombre de Keith"
fsi
fpour
ou dans une version moins optimisée 
entier i,K,j,N,S
tableau Ti i=1,..,4 de entier
pour i de 10 à 1000 faire
  K ß i
  N ß 0
  tant que NOT (K=0) faire
    N ß N +1
    TN ß K mod 10
    K ß K\10
  ftant
  pour j de 1 à N\2 faire
    Tmp ß Tj
    Tj ß TN-j+1
    TN-j+1 ß Tj
  fpour
  S ß 0
  pour j de 1 à N faire
    S ß S+Tj
  fpour
  tant que NOT (S³ i) faire
  pour j de 1 à N\2 faire
    Tmp ß Tj
    Tj ß TN-j+1
    TN-j+1 ß Tj
  fpour
  TN ß S
  S ß 0
  pour j de 1 à N faire
    S ß S+Tj
  fpour
ftant
si S=i alors écrire i,"est un nombre de Keith"
fsi
fpour
ou dans une version avec procédures/fonctions 
type tabl=tableaui i=1,..,4 de entier

procédure Chiffres(¯ i,­ T,­ N) ¡Stocke les chiffres de i dans T¡
  paramètres: i,N:entier
                      T: Tabl
N ß 0
tant que NOT (i=0) faire
  N ß N +1
  TN ß i mod 10
  i ß i\10
ftant
fproc

fonction Somme(T,N) ¡Calcule la somme des N éléménts de T¡
  paramètres: T: Tabl
                      N: entier
  à valeur: entier
entier: S,i
S ß 0
pour i de 1 à N faire
  S ß S+Ti
fpour
résultat(S)

procédure Inverse(¯­T,¯ N) ¡Inverse l'ordre des éléménts de T¡
  paramètres: T: Tabl
                       N: entier
entier: i,j,Tmp
pour i de 1 à N\2 faire
  Tmp ß Ti
  Ti ß TN-i+1 
  TN-i+1 ß Ti
fpour
fproc

procédure ShiftGauche(¯­T,¯ N,¯ k) ¡Déplace tous les éléménts de T de k cases¡
  paramètres: T: Tabl
                      N,k: entier
entier: i,j,Tmp
pour i de 1 à k faire
  Tmp ß T1
  pour j de 1 à N-1 faire
    Tj ß Tj+1 
  fpour
  TN ß T1
fpour
fproc

entier i,S
tabl: T
pour i de 10 à 1000 faire
  Chiffres(i,T,N)
  Inverse(T,N)
  S ß Somme(T,N)
  tant que NOT (S³ i) faire
    ShiftGauche(T,N,1)
    TN ß S
    S ß Somme(T,N)
  ftant
  si S=i alors écrire i,"est un nombre de Keith"
  fsi
fpour

Page précédente.
Page d'accueil.