Il est très simple de démontrer : Théorème : ========== Soit l'application dans l'ensemble |N* des entiers strictements positifs N = (abc...x_i...d) |--> T(N) = somme_n (x_i^n) (abc...x_i...d) étant le développement décimal à n chiffres de N. a) il n'existe qu'un nombre fini de points fixes et de cycles b) tout système N, T(N), T^2(N)=T(T(N)), T^3(N), ..., T^k(N), ... finit par aboutir à un point fixe ou par entrer dans un cycle. Démonstration : =============== T est l'application "somme digitale" N --> T(N) = somme x_i^n des puissances n-ièmes des n chiffres décimaux x_i de N. T(N) est majoré par T(999...9)=n*9^n = M. Pour déterminer le nombre de chiffres de M, on le compare à 10^(n-k). On étudie alors les variations de f(x)=x*9^x / 10^(x-k) de variable x et de paramètre k. La dérivée f'(x) = 10^k * (0,9)^x (1 + x ln(0.9)) s'annule et change de signe en x = -1/ln(0,9) = 9.49... f'(x) est négative et f(x) décroît strictement lorsque x > 9,49... x | 0 x0=1/ln(10/9) +oo --------------------------------------------------- f'(x) | + 0 - --------------------------------------------------- f(x) | 10^k/(e*ln(10/9)) | / \ | / \ | 0 / \ 0 10^k/(e*ln(10/9)) = 10^k * 3.49162 k >=0 entraîne f(x0) = 10^k/(e*ln(10/9)) > 1 et donc l'équation f(x) = 1 a une solution (unique) dans l'intervalle ]1/ln(10/9), +oo[ ce qui prouve ceci : Si pour n=n0 (n0>= 10), T(N) a k chiffres (ou plus) de moins que N, alors c'est encore vrai pour tout n supérieur à n0. Il suffit ensuite de calculer le nombre de chiffres de M en fonction de n=1 jusqu'à n=61 pour conclure. (ou un peu plus de 61 pour voir !). nb de chiffres de M=T(999...9) suivant n = 1, 2, 3... : l= | 1 2 3 4 5 6 7 8 9 10 ------------------------------------- 1 | 1 3 4 5 6 7 8 9 10 11 11 | 12 13 14 15 16 17 18 19 20 21 21 | 22 23 24 25 26 27 28 29 30 31 31 | 32 33 34 34 35 36 37 38 39 40 nb chiffres 41 | 41 42 43 44 45 46 47 48 49 50 maxi de T(N) 51 | 51 52 53 54 55 56 57 58 59 60 (chif. de n9^n) 61 | 60 61 62 63 64 65 66 67 68 69 71 | 70 71 72 73 74 ... \_______ _________________________/ \/ moins que n = 61 62 ... --- Si N a 60 chiffres ou moins de 60 chiffres, alors M a 60 chiffres ou moins et donc T(N) aussi. --- Si N a 61 chiffres ou plus, alors M et T(N) ont strictement moins de chiffres que N. On en déduit que tout système N, T(N),...,T^r(N)... débouche sur un point fixe ou un cycle dont les éléments ont 60 chiffres au plus. Démo en version longue : ======================== 1) Si un nombre N a plus de 60 chiffres, alors T(N) a moins de chiffres que N. (voir 4)) 2) Si N a 60 chiffres ou moins de 60 chiffres, alors T(N) a au plus 60 chiffres. Calculer T(N) seulement lorsque tous les chiffres sont des 9 et voir ci-après pour compléter. 3) De tous les nombres N de n chiffres, c'est lorsque tous les chiffres de N sont des 9 que T(N) est le plus grand : pour tout c de 0 à 9, c < 9 => c^n < 9^n (et égalité si c=9) ce qui nous donne un majorant de T(N), qu'il suffit de calculer pour n=1, 2, ..., 61 et éventuellement plus. Écrire ici pour différentes valeurs de n, le nombre de chiffres de T(N) lorsque N = 99999...999 n'a que des chiffres 9. export BC_LINE_LENGTH=1000; echo 'for(n=1; n<=75; n++) print length(n*9^n)," "'|bc -q 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 notez le passage 60 60 de la dernière ligne ainsi que 1 3 et 34 34 auparavant qui montrent ceci : un nombre N de n=2...34 chiffres peut conduire à un successeur T(N) de n+1 chiffres un nombre N de n=34...60 chiffres a un successeur de n chiffres au plus ensuite, du moins pour les valeurs de ce tableau, T(N) a moins de chiffres que N 4) Si N = 999...9 = 10^n - 1, alors T(N) = n*9^n. Pour comparer les nombres de chiffres de N et de T(N) on peut comparer à 1 le quotient T(N)/10^(n-k) = n*9^n/10^(n-k) pour k fixé et étudier les variations la fonction numérique suivante de la variable réelle x. partie analytique : - - - - - - - - - - voir le détail dans la première partie. f(x)=x*9^x / 10^(x-k) = 10^k * x * (0,9)^x a pour dérivée f'(x) = 10^k * (0,9)^x (1 + x ln(0.9)) qui s'annule et change de signe en x = -1/ln(0,9) = 9.49... elle est négative lorsque x > 9.49... f(x) décroît strictement lorsque x > 9,49... - - - - - - - - - - Donc pour si pour n>= 10 on a T(N)/10^(n-k) < 1, ce sera vrai aussi pour tout N ayant encore plus de chiffres (et à fortiori que ces chiffres soient tous des 9 ou non). Comme pour (k=1, n=61), T(999...9) a n-k=61-1=60 chiffres, alors pour tout n supérieur ou égal à 61, T(N) aura n-k = n-1 chiffres ou plus. 5) fin de l'explication et conclusion : Après vérification pour chaque n <= 60 que T(N) a au plus 60 chiffres, on peut affirmer pour tout N : Au bout d'un nombre fini r d'étapes, le système N, T(N), T^2(N)=T(T(N)), T^3(N), ..., T^r(N), ... est tel que T^r(N) a 60 chiffres ou moins de 60 chiffres ainsi que tous les suivants qui sont éléments de l'ensemble fini des nombres entiers naturels de 60 chiffres ou de moins de 60 chiffres. Le système finit donc par aboutir à un point fixe ou par entrer dans un cycle (car d'une part T^p(N) ne peut prendre un nombre infini de valeurs toutes différentes dans un ensemble fini et que d'autre part si T^q(N) est le premier à égal à une valeur précédente T^p(N), on a précisément abouti à un cycle de période q-p qui est T^p(N)...T^(q-1)(N) ou à un point fixe si q=p+1). Complément : ================ les n des changements : export BC_LINE_LENGTH=10000 echo 'for(n=1; n<=1000; n++) print length(n*9^n)," "'|bc -q| \ gawk '{for(i=1;i<=NF;i++){d[i]=$i-i;if(d[i]!=d[i-1])printf("%d, ",i)}}'; \ echo "" 2, 34, 61, 86, 111, 134, 158, 181, 204, 227, 250, 272, 295, 317, 340, 362, 385, 407, 430, 452, 474, 496, 519, 541, 563, 585, 608, 630, 652, 674, 696, 719, 741, 763, 785, 807, 829, 851, 873, 895, 918, 940, 962, 984, chiffres de N et T(N) : echo 'for(n=1; n<=1000; n++) print length(n*9^n)," "'|bc -q| \ gawk '{for(i=1;i<=NF;i++){d[i]=$i-i;if(d[i]!=d[i-1])print i " "$i}}' 2 3 34 34 61 60 86 84 111 108 134 130 158 153 181 175 204 197 227 219 250 241 272 262 295 284 317 305 340 327 362 348 385 370 407 391 430 413 452 434 474 455 496 476 519 498 541 519 563 540 585 561 608 583 630 604 652 625 674 646 696 667 719 689 741 710 763 731 785 752 807 773 829 794 851 815 873 836 895 857 918 879 940 900 962 921 984 942 j-p mars 2009