PairWise Digit Sum
[English text published on SeqFans, on 6/15/2012 at 10:57 AM]:
Hello Seqfans (I hope this
idea is not old hat),
We change integer abcde...mn (with a,b,c,d,e,..m,n being digits) into integer a+b|b+c|c+d|d+e|e+...+m|m+n
(where the symbol < | means <
concatenate with . Then we iterate.
So 2012 gives 2+0|0+1|1+2 which is 213.
213 gives 2+1|1+3 which is 34.
And 34 gives 3+4 = 7 (which we call "end result")
1) What integers are divisible by their end result?
2) 991 loops -- as 992, 993, 994, 995, 996, 997, 998, 999 (ex. 991-1810-991...); which integers > 999 also
enter in a loop?
3) Which is the smallest integer growing for ever (if
such an integer exists)? I don't know the fate of 1891, for example:
1891-91710-10881-18169-99715-181686-9971414...
Besides, is
there an end pattern here: 1991
101810
11991
2101810
311991
42101810
6311991
942101810
Best, ...
É.
---------------------------------------------------
[Jack Brennen on Seqfans]:
After just 46 iterations, 1891 ends up with a number
with 115236 digits; I think it's a safe conjecture that it grows forever. There
is a pattern to it. At the 19th iteration, the number begins with:
18168554419171361118161213169411181614106781186648741118161412106774461411111055
And at the 20th iteration, the number begins with:
99714131098510108849722997733447151352299775516131592914121012151152299775533161
Afterward, the first digits cycle through those two
strings apparently ad infinitum.
I believe the
smallest starting number which seems to grow forever is 1496, which ends up at 1891 after four
iterations:
1496 -> 51315 -> 6446 -> 10810 -> 1891
-> ...
---------------------------------------------------
[Texte français
publié sur Fr.Sci.Maths quelques jours plus tard] :
Bonjour à tous,
Transformons l’entier N
composé des chiffres {abcde... mn} en l’entier M
ainsi:
M = {a+b|b+c|c+d|d+e|...
|m+n} où le symbole < | > veut dire < concaténé avec >.
On itère ensuite M en O,
puis O en P, etc.
Ainsi 178 devient-il 1+7|7+8
soit 815, lequel devient 8+1|1+5 soit 96, lequel produit 9+6 soit 15, qui fait
1+5 = 6, fin.
1) quel
est le plus petit entier qui générera une suite de nombres infinie ?
2)
quels autres entiers que 991, 992, 993, 994, 995, 996, 997, 998 et 999 bouclent
? On voit p.ex. que 991 produit 1810 qui reproduit
991.
Voici, pour le point (1) un motif intéressant à
croissance infinie trouvé par Jack
Brennen, que je cite :
For an interesting pattern which is obviously provable to be infinite,
start with 4949:
4949
131313
44444
8888
161616
77777
14141414
5555555
101010101010
11111111111
2222222222
444444444
88888888
etc.
à+
É.
---------------------------------------------------
[Acetonik] sur Fr.Sci.Maths :
[..]
de 1 à 1495 toutes les suites générées sont finies
ou infinies périodiques.
Les périodiques sont celles générées par les nombres
consécutifs :
de 991 à 999
de 1082 à 1089
de 1256 à 1259
de 1491 à 1495
Une étude exhaustive est facile et rapide jusqu’à 1495,
il faut calculer peu de termes pour chaque nombre.
Le plus petit nombre qui pourrait générer un une suite
non périodique infinie est 1496... Reste à le prouver !
(pour info, après 30
"concaténations" on obtient un nombre de 701 chiffres)
Donc :
1) quel est le plus petit entier qui générera une suite
de nombres infinie?
1496 (très forte probabilité)
2) quels autres entiers que 991, 992, 993, 994, 995,
996, 997, 998 et 999 bouclent?
Liste exhaustive des 249 nombres inférieurs à 10000
qui génèrent une "concaténation" périodique:
[ils ne se raréfient pas:
123/5000 ; 249/10000]
991, 992, 993, 994, 995, 996, 997, 998, 999, 1082,
1083, 1084, 1085, 1086, 1087, 1088, 1089, 1256, 1257, 1258, 1259, 1491, 1492,
1493, 1494, 1495, 1537, 1538, 1539, 1810, 1811, 1812, 1813, 1814, 1815, 1816,
1817, 1818, 2165, 2166, 2167, 2168, 2169, 2446, 2447, 2448, 2449, 2720, 2721, 2722,
2723, 2724, 2725, 2726, 2727, 2802, 2803, 2804, 2805, 2806, 2807, 2808, 2809,
2935, 2936, 3074, 3075, 3076, 3077, 3078, 3079, 3355, 3356, 3357, 3358, 3359,
3630, 3631, 3632, 3633, 3634, 3635, 3636, 3711, 3712, 3713, 3714, 3715, 3716, 3717,
3718, 3844, 3845, 3937, 3938, 3939, 3950, 4264, 4265, 4266, 4267, 4268, 4540,
4541, 4542, 4543, 4544, 4545, 4620, 4621, 4622, 4623, 4624, 4625, 4626, 4627,
4753, 4754, 4846, 4847, 4848, 4849, 4927, 5173, 5174, 5175, 5176, 5177, 5450, 5451,
5452, 5453, 5454, 5530, 5531, 5532, 5533, 5534, 5535, 5536, 5662, 5663, 5755,
5756, 5757, 5758, 5759, 5836, 5901, 5902, 5903, 5904, 5905, 5930, 5931, 6082,
6083, 6084, 6085, 6086, 6360, 6361, 6362, 6363, 6440, 6441, 6442, 6443, 6444, 6445,
6571, 6572, 6664, 6665, 6666, 6667, 6668, 6669, 6745, 6810, 6811, 6812, 6813,
6814, 6840, 7270, 7271, 7272, 7350, 7351, 7352, 7353, 7354, 7480, 7481, 7506,
7507, 7508, 7509, 7573, 7574, 7575, 7576, 7577, 7578, 7654, 7720, 7721, 7722, 7723,
7920, 8180, 8181, 8260, 8261, 8262, 8263, 8390, 8415, 8416, 8417, 8418, 8482,
8483, 8484, 8485, 8486, 8487, 8563, 8630, 8631, 8632, 9090, 9170, 9171, 9172,
9324, 9325, 9326, 9327, 9391, 9392, 9393, 9394, 9395, 9396, 9472, 9540, 9541.
---------------------------------------------------
[Éric A] :
Un autre aspect "boucle" qui me plaît est
celui des demi-lignes infinies (à droite) composées d’entiers K identiques.
Ainsi 3333... fait-il 6666... puis 121212... puis
3333...
[Acetonik] :
Par exemple comme celles qui débutent par
99999 .....
puis
1818181818.......
etc., générées en
particulier par les nombres suivants:
5980 ; 5981 ; 6890 ; 9990 à 9999.
Le seul intérêt que je vois ici ; c’est qu’il est
facile de démontrer que les suites sont infinies.
---------------------------------------------------
[Acetonik] :
Un nombre génère par cette
concaténation l’un des 3 types de suite :
F-> une suite finie (le
dernier terme a un seul chiffre)
P-> une suite périodique
(boucle)
i-> une suite infinie non
périodique (pas de boucle)
Les nombres avec de grands
chiffres génèrent plutôt des suites infinies.
Les nombres avec de petits
chiffres génèrent plutôt des suites finies.
Les nombres générant des
suites périodiques sont peu nombreux (123/5000)
Voici une classification
donnant le type de suite associée aux entiers inférieurs à 5000.
0 à 990
-> F
991 à 999 -> P
1000 à 1081 -> F
1082 à 1089 -> P
1090 à 1255 -> F
1256 à 1259 -> P
1260 à 1490 -> F
1491 à 1495 -> P
1496 à 1499 -> i
1537 à 1539 -> P
1540 à 1586 -> F
1587 à 1589 -> i
1590 à 1690 -> F
1691 à 1699 -> i
1700 à 1718 -> F
1719 -> i
1720 à 1728 -> F
1729 -> i
1730 à 1782 -> F
1783 à 1789 -> i
1789 à 1809 -> F
1810 à 1818 -> P
1819 -> i
1820 à 1866 -> F
1867 à 1869 -> i
1870 à 1954 -> F
1955 à 1959 -> i
1960 à 1963 -> F
1964 à 1989 -> i
1990 -> F
1991 à 1999 -> i
2000 à 2164 -> F
2165 à 2169 -> i
2170 à 2445 -> F
2446 à 2449 -> P
2450 à 2495 -> F
2496 à 2499 -> i
2500 à 2627 -> F
2628 à 2629 -> i
2630 à 2636 -> F
2637 à 2639 -> i
2640 à 2691 -> F
2692 à 2699 -> i
2700 à 2718 -> F
2719 -> i
2720 à 2727 -> P
2728 à 2729 -> i
2730 à 2768 -> F
2769 -> i
2770 à 2775 -> F
2776 à 2779 -> i
2780 à 2782 -> F
2783 à 2799 -> i
2800 à 2801 -> F
2802 à 2809 -> P
2810 à 2863 -> F
2864 à 2869 -> i
2870 à 2872 -> F
2873 à 2899 -> i
2900 à 2934 -> F
2935 à 2936 -> P
2937 à 2945 -> F
2946 à 2949 -> i
2950 à 2953 -> F
2954 à 2979 -> i
2980 à 2981 -> F
2982 à 2999 -> i
3000 à 3073 -> F
3074 à 3079 -> P
3080 à 3354 -> F
3355 à 3359 -> P
3360 à 3536 -> F
3537 à 3539 -> i
3540 à 3545 -> F
3546 à 3549 -> i
3550 à 3578 -> F
3579 -> i
3580 à 3627 -> F
3628 à 3629 -> i
3630 à 3636 -> P
3637 à 3639 -> i
3640 à 3677 -> F
3678 -> i
3679 à 3684 -> F
3685 à 3689 -> i
3690 à 3691 -> F
3692 à 3699 -> i
3700 à 3710 -> F
3711 à 3718 -> P
3719 -> i
3720 à 3768 -> F
3769 -> i
3770 à 3772 -> F
3773 à 3779 -> i
3780 à 3781 -> F
3782 à 3799 -> i
3800 à 3843 -> F
3844 à 3845 -> P
3846 à 3854 -> F
3855 à 3859 -> i
3860 à 3862 -> F
3863 à 3889 -> i
3890 -> F
3891 à 3899 -> i
3900 à 3936 -> F
3937 à 3939 -> P
3940 à 3945 -> F
3946 à 3949 -> i
3950 -> P
3951 à 3979 -> i
3980 -> P
3981 à 3999 -> i
4000 à 4263 -> F
4264 à 4268 -> P
4269 -> i
4270 à 4445 -> F
4446 à 4449 -> i
4450 à 4454 -> F
4455 à 4459 -> i
4460 à 4487 -> F
4488 à 4489 -> I
4490 à 4536 -> F
4537 à 4539 -> i
4540 à 4545 -> P
4546 à 4549 -> i
4550 à 4578 -> F
4579 -> i
4580 à 4586 -> F
4587 -> i
4588 à 4593 -> F
4594 à 4599 -> i
4600 à 4619 -> F
4620 à 4627 -> P
4628 à 4629 -> i
4630 à 4677 -> F
4678 à 4679 -> i
4680 à 4681 -> F
4682 à 4689 -> i
4690 -> F
4691 à 4699 -> i
4700 à 4718 -> F
4719 -> i
4720 à 4748 -> F
4749 -> i
4750 à 4752 -> F
4753 à 4754 -> P
4755 à 4763 -> F
4764 à 4769 -> i
4770 à 4471 -> F
4772 à 4799 -> i
4800 à 4845 -> F
4846 à 4849 -> P
4850 à 4854 -> F
4855 à 4899 -> i
4900 à 4936 -> F
4937 à 4999 -> i
---------------------------------------------------
[Philippe 92]
Un nombre génère par cette
concaténation l’un des 3 types de suite :
F-> une suite finie (le
dernier terme a un seul chiffre)
P -> une suite périodique
(boucle)
i -> une suite infinie non
périodique (pas de boucle)
... peut-être faut-il distinguer ici deux sortes de
suites infinies :
a) les "réplicateurs"
M qui au bout d’un nombre fini d’étapes produisent M|M
ou éventuellement un M|M|...|M fini
b) les autres, "chaotiques"...
Tout ce phénomène ressemble étrangement aux diverses
variantes de "jeu de la vie"
---------------------------------------------------
[Acetonik] :
Petite précision : si l’on ne considère que des
suites périodiques (strictement, et non à partir d’un certain rang) on ne
trouve pour les nombres inférieurs à 10 000 que 15 nombres générateurs !!!
9 suites de période 2:
991, 992, 993, 994, 995, 996, 997, 998, 999, 1810,
1811, 1812, 1813, 1814, 1815, 1816, 1817, 1818.
6 suites de période 3:
6664, 6665, 6666, 6667, 6668, 6669,
121210, 121211, 121212, 121213, 121214, 121215, 33331, 33332, 33333,
33334, 33335, 33336.
---------------------------------------------------
[Olivier
Miakinen] :
Bonjour,
Le 17/06/2012 21:20, Philippe 92 a écrit :
[...]
Un nombre génère par cette concaténation l’un des 3
types de suite :
F -> une suite finie ( le
dernier terme a un seul chiffre)
P -> une suite périodique (boucle)
i -> une suite infinie non périodique (pas de
boucle)
> peut être faut-il distinguer ici deux sortes de
suites infinies :
>
> les "réplicateurs" M qui au bout d’un nombre fini d’étapes
> produisent M|M ou
éventuellement un M|M|...|M fini
>
> les autres,
"chaotiques" ...
Crois-tu qu’il soit possible de prouver qu’il existe
vraiment des suites chaotiques ici ? Qui sait si, au contraire, on ne pourrait
pas montrer que chaque suite infinie, même si elle semble longtemps chaotique,
ne serait pas au bout du compte un « multi-réplicateur
» (du style M -> M|M|M|M|...|M) ?
---------------------------------------------------
[Acetonik] :
Un peu d’ordre quand même
dans ce chaos...
Voici les effectifs des
différents types par classes de 1000.
F -> suite finie (le dernier terme a un seul chiffre)
P -> suite
périodique (ou partir d’un certain rang) ->
boucle
i -> suite infinie
non périodique -> pas de boucle
classes | F |
i | P |
------------------------------
0 à 999
| 991 | 0 | 9
|
| |
| |
1000 à 1999 |
866 | 105 | 29 |
| |
| |
2000 à 2999 |
850 | 123 | 27 |
| |
| |
3000 à 3999 |
821 | 147 | 32 |
| |
| |
4000 à 4999 |
783 | 191 | 26 |
| |
| |
5000 à 5999 |
733 | 235 | 32 |
| |
| |
6000 à 6999 |
701 | 269 | 30 |
| |
| |
7000 à 7999 |
650 | 324 | 26 |
| |
| |
8000 à 8999 |
591 | 388 | 21 |
| |
| |
9000 à 9999 |
537 | 446 | 17 |
------------------------------
0 à 9999
| 7523 | 2228 | 249 |
------------------------------
------------------------------
10000 à 10999| 510 | 479 | 10 |
------------------------------
... et plus exactement, pour les nombres inférieurs à
10 000 on ne trouve que :
9 suites de période 2:
991, 992, 993, 994, 995, 996, 997, 998, 999, 1810,
1811, 1812, 1813, 1814, 1815, 1816, 1817, 1818.
6 suites de période 3:
6664, 6665, 6666, 6667, 6668, 6669,
121210, 121211, 121212, 121213, 121214, 121215, 33331, 33332, 33333,
33334, 33335, 33336.
Soit 24 nombres
générateurs de suites périodiques:
991, 992, 993, 994, 995, 996, 997, 998, 999, 1810,
1811, 1812, 1813, 1814, 1815, 1816, 1817, 1818, 6664, 6665, 6666, 6667, 6668,
6669.
---------------------------------------------------
[Lars Blomberg] :
Hello Eric,
Is this not the same problem as described in
http://www2.stetson.edu/~efriedma/mathmagic/0200.html
?
When investigating it, I recognized some of the results.
:-)
I found some
documentation that I made almost a year ago concerning this problem.
___________________________________________________________________________________________________________________
7 Pairwise Digit Sums and Concatenate
7.1 Problem definition
Erich Friedmann
introduces a "Problem of the Month" in February 2000 which Eric
Angelini revived recently in SeqFan, defined as
follows.
For integer n, let f(n) be the concatenation of the sums of every pair of
consecutive digits of n. For example, f(82671)=108138,
since 8+2=10, 2+6=8, 6+7=13, and 7+1=8. If n is a single digit, define f(n)=0.
See http://www2.stetson.edu/~efriedma/mathmagic/0200.html
for more information.
Several interesting questions can be
asked regarding this problem, some of which are answered on the above Web site.
Additional investigations are
presented in the following.
7.2 Some basics
Pairwise summing of
digits gives 1-digit sums in 55 cases (45 cases for the first pair in a number
since numbers do not start with 0):
00
01 10
02 11 20
03 12 21 30
04 13 22 31 40
05 14 23 32 41 50
06 15 24 33 42 51 60
07 16 25 34 43 52 61
70
08 17 26 35 44 53 62
71 80
09 18 27 36 45 54 63
72 81 90
And 2-digit sums in 45 cases
(first digit is always 1):
19 28 37 46 55 64 73
82 91
29 38 47 56 65 74 83
92
39 48 57 66 75 84 93
49 58 67 76 85 94
59 68 77 86 95
69 78 87 96
79 88 97
89 98
99
For a n-digit
number there are n-1 pairs to be summed. Each pair results in 1 or 2 digits.
Therefore the resulting number will have m digits, n-1≤m≤2(n-1).
For a number to become shorter,
all the pairwise sums need to be 1 digit. Obviously
the chance of this happening diminishes with the number of digits in the
number.
Given m, what is the range of n?
n-1≤m and m≤2(n-1)
n≤m+1
and floor(m/2)+1≤n so
floor(m/2)+1≤n≤m+1
If an n-digit number is
transformed into a m-digit number then there
have been t=m-n+1 pairs that have yielded a 2-digit result, 0≤t≤n-1.
When f(2056)
= 2511, we say that 2511 is the successor of 2056, and
conversely, 2056 is the predecessor of 2511.
All numbers have a successor.
Sometimes the successor iteration
leads to one value being repeated indefinitely as a fixed point, for example 0.
Other iterations lead to a set of
values being repeated in a cycle, for example 991 --> 1810 --> 991.
Yet other iterations lead to
numbers that grow in size indefinitely.
Some numbers have no predecessors,
for example 110.
Numbers can have many predecessors,
for example 9 <-- {18, 27, 36, 45, 54, 63, 72, 81, 90}.
7.3 Cycles
Some successor sequences lead into
cycles.
The following cycles have been
found by Joseph DeVincentis and others:
99(a+1) --> 181a
--> 99(a+1) [where 0≤a≤8]
3333(a+1) -->
666(a+4) --> 12121a --> 3333(a+1) [where 0≤a≤5]
or, more
explicitly:
L1 1810 --> 991
-->
L2 1811 --> 992
-->
L3 1812 --> 993
-->
L4 1813 --> 994
-->
L5 1814 --> 995
-->
L6 1815 --> 996
-->
L7 1816 --> 997
-->
L8 1817 --> 998
-->
L9 1818 --> 999
-->
M1 121210 --> 33331
--> 6664 -->
M2 121211 -->
33332 --> 6665 -->
M3 121212 -->
33333 --> 6666 -->
M4 121213 -->
33334 --> 6667 -->
M5 121214 -->
33335 --> 6668 -->
M6 121215 -->
33336 --> 6669 -->
There are 15 cycles containing a
total of 36 values.
7.4 Expanding cycles
Some iterations
do not terminate with 0 or one of the cycles, they go on forever.
Such iterations of course lead to
numbers that grow beyond limit.
Some (all?)
of these infinite iterations exhibit a cyclic pattern in the first few digits. When a cycle
is completed, at least one more digit has been added to the right, otherwise we
would have a proper cycle.
The additional digits for each
cycle make it an expanding cycle.
Of course, there might be more
digits to the right of the cycling numbers which may or may not expand by
themselves.
The following 24 expanding cycles
have been found, each has been given a name.
The information inside () are the
extra digits generated with each cycle. When the count of these digits exceeds
9, the count is instead given inside (<>).
A1 18141 -->
9955 --> 18141(0)
A2 18146 -->
9951(0) --> 18146(1)
A3 18151 -->
9966 --> 18151(2)
A4 18157 -->
9961(2) --> 18157(3)
A5 18161 -->
9977 --> 18161(4)
A6 18168 -->
9971(4) --> 18168(5)
A7 18171 -->
9988 --> 18171(6)
A8 18179 -->
9981(6) --> 18179(7)
A9 18181 -->
9999 --> 18181(8)
B1 66661 -->
1212127 --> 333339 --> 66661(2)
B2 66666 -->
1212121(2) --> 333333(3) --> 66666(6)
B3 66678 -->
1212131(5) --> 333344(6) --> 66678(10)
B4 66691 -->
1212151(0) --> 333366(1) --> 66691(27)
C1 18121 -->
9933 --> 18126 --> 9938 --> 18121(1)
C2 18124 -->
9936 --> 18129 --> 9931(1) --> 18124(2)
D1 18111 -->
9922 --> 18114 --> 9925 --> 18117 --> 9928 --> 18111(0)
D2 18113 -->
9924 --> 18116 --> 9927 --> 18119 --> 9921(0) --> 18113(1)
D3 18131 -->
9944 --> 18138 --> 9941(1) --> 18135(2) --> 9948(7) -->
18131(215)
E1 66642 -->
1212106 --> 333316 --> 66647 --> 1212101(1) --> 333311(2) -->
66642(3)
E2 66681 --> 1212149 --> 333351(3) --> 66686(4)
--> 1212141(410) --> 333355(551) --> 66681(010106)
F 222222 --> 44444 --> 8888 --> 161616 -->
77777 --> 14141414 --> 5555555 --> 101010101010 --> 11111111111
--> 222222(2222)
G 66651 --> 1212116 --> 333327 --> 66659
--> 1212111(4) --> 333322(5) --> 66654(7) --> 1212119(11) -->
333321(0102) --> 66653(1112) --> 1212118(4223) --> 333329(12645)
--> 66651(11038109)
H 18101 --> 9911 --> 18102 --> 9912 -->
18103 --> 9913 --> 18104 --> 9914 --> 18105 --> 9915 -->
18106 --> 9916 --> 18107 --> 9917 --> 18108 --> 9918 -->
18109 --> 9919 --> 18101(0)
I 101088 --> 111816 --> 22997 --> 411181(6)
--> 52299(7) --> 741118(16) --> 115229(97) --> 26741(11816) -->
813115(22997) --> 94426(74111816) --> 13868(<10>) -->
411141(<14>) --> 52255(<18>) --> 74710(<25>) --> 111181(<30>)
--> 22299(<40>) --> 441118(<50>) --> 85229(<68>)
--> 137411(<82>) --> 4101152(<112>) -->
511267(<141>) --> 62381(<188>) --> 85119(<241>) -->
13621(<318>) --> 4983(<403>) --> 13171(<532>) -->
4488(<680>) --> 81216(<881>) --> 9337(<1123>) -->
12610(<1453>) --> 3871(<1865>) --> 11158(<2407>) -->
22613(<3078>) --> 4874(<3961>) --> 121511(<5108>)
--> 33662(<6540>) --> 69128(<8454>) -->
151031(<10813>) --> 66134(<14019>) --> 12747(<17945>)
--> 391111(<23196>) --> 1210222(<29697>) -->
331244(<38401>) --> 64368(<49279>) --> 10791(<63825>)
--> 17161(<81773>) --> 8877(<105797>) -->
16151(<135743>) --> 7766(<175542>) --> 141312(<225282>)
--> 55443(<291102>) --> 10987(<373857>) -->
19171(<483295>) --> 101088(<620681>)
The number of iterations until the
cycle is closed is
A1 |
2 |
A2 |
2 |
A3 |
2 |
A4 |
2 |
A5 |
2 |
A6 |
2 |
A7 |
2 |
A8 |
2 |
A9 |
2 |
B1 |
3 |
B2 |
3 |
B3 |
3 |
B4 |
3 |
C1 |
4 |
C2 |
4 |
D1 |
6 |
D2 |
6 |
D3 |
6 |
E1 |
6 |
E2 |
6 |
F |
9 |
G |
12 |
H |
18 |
I |
53 |
Berend Jan van der Zwaag states 23 expanding cycles, he forgot to mention A3
(the value 9966 in his enumeration).
7.5 Successor statistics
Given a number, the successor
iteration ends up in 0, one of the cycles (LM), or one of the expanding cycles
(A-I).
For all numbers up to 10^6 the
outcome has been determined for the 10 intervals of size 10^5 resulting in the
following table:
Interval |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
ZERO |
20822 |
1475 |
1288 |
1064 |
918 |
781 |
637 |
548 |
447 |
320 |
L1 |
23 |
1 |
0 |
2 |
0 |
1 |
1 |
1 |
1 |
0 |
L2 |
27 |
1 |
0 |
2 |
0 |
1 |
1 |
0 |
1 |
1 |
L3 |
33 |
1 |
0 |
2 |
0 |
1 |
1 |
0 |
1 |
1 |
L4 |
60 |
3 |
1 |
3 |
0 |
3 |
2 |
0 |
2 |
1 |
L5 |
71 |
4 |
5 |
2 |
1 |
3 |
0 |
0 |
2 |
2 |
L6 |
81 |
4 |
4 |
4 |
2 |
4 |
0 |
0 |
2 |
2 |
L7 |
106 |
8 |
8 |
7 |
7 |
5 |
1 |
0 |
4 |
2 |
L8 |
79 |
4 |
6 |
3 |
4 |
4 |
1 |
1 |
0 |
1 |
L9 |
19 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
M1 |
19 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
M2 |
20 |
1 |
2 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
M3 |
21 |
2 |
2 |
2 |
1 |
0 |
1 |
0 |
1 |
0 |
M4 |
22 |
2 |
3 |
2 |
2 |
0 |
1 |
0 |
1 |
0 |
M5 |
30 |
3 |
4 |
2 |
2 |
2 |
1 |
0 |
1 |
0 |
M6 |
29 |
3 |
2 |
3 |
2 |
2 |
2 |
0 |
1 |
0 |
A1 |
9753 |
12964 |
11447 |
11849 |
10948 |
10176 |
11331 |
12278 |
13125 |
12828 |
A2 |
293 |
390 |
455 |
480 |
457 |
398 |
305 |
230 |
123 |
602 |
A3 |
858 |
1288 |
1247 |
1208 |
970 |
962 |
1221 |
882 |
873 |
1466 |
A4 |
2633 |
3438 |
3403 |
3901 |
4248 |
4740 |
3408 |
2693 |
2901 |
2668 |
A5 |
13599 |
17598 |
15508 |
16018 |
14980 |
16854 |
16515 |
18464 |
19115 |
16617 |
A6 |
735 |
833 |
612 |
747 |
901 |
1109 |
916 |
896 |
750 |
1038 |
A7 |
1785 |
3214 |
1907 |
2478 |
3243 |
2410 |
2138 |
1861 |
1955 |
2712 |
A8 |
59 |
94 |
64 |
58 |
43 |
43 |
30 |
31 |
20 |
210 |
A9 |
968 |
1306 |
1420 |
1185 |
1235 |
1331 |
1042 |
1085 |
1055 |
1661 |
B1 |
464 |
591 |
526 |
540 |
533 |
582 |
684 |
807 |
705 |
588 |
B2 |
561 |
279 |
299 |
401 |
403 |
349 |
901 |
985 |
1127 |
1086 |
B3 |
70 |
41 |
48 |
66 |
144 |
124 |
121 |
120 |
120 |
120 |
B4 |
115 |
112 |
135 |
146 |
193 |
168 |
232 |
286 |
240 |
202 |
C1 |
12112 |
15739 |
16582 |
14827 |
14048 |
14516 |
15655 |
15793 |
17271 |
16787 |
C2 |
100 |
162 |
147 |
122 |
26 |
34 |
43 |
30 |
41 |
445 |
D1 |
172 |
213 |
245 |
172 |
107 |
85 |
12 |
75 |
69 |
759 |
D2 |
103 |
198 |
159 |
107 |
58 |
69 |
41 |
55 |
51 |
362 |
D3 |
2145 |
1989 |
2233 |
2730 |
2475 |
2634 |
3272 |
3753 |
1731 |
2549 |
E1 |
130 |
124 |
131 |
205 |
125 |
129 |
218 |
206 |
189 |
195 |
E2 |
50 |
30 |
40 |
30 |
30 |
140 |
142 |
133 |
110 |
100 |
F |
2609 |
2092 |
2765 |
3385 |
3919 |
2963 |
2782 |
3265 |
4431 |
4794 |
G |
70 |
20 |
20 |
120 |
120 |
120 |
120 |
110 |
100 |
100 |
H |
842 |
622 |
608 |
729 |
703 |
692 |
750 |
898 |
960 |
2162 |
I |
28311 |
35149 |
38672 |
37396 |
39149 |
38563 |
37469 |
34514 |
32474 |
29619 |
The count of numbers ending in
each cycle and expanding cycle varies greatly.
Zeros decrease as numbers
increase.
Cycles are scarce overall and seem
to get scarcer as the numbers increase.
All iterations that go off to
infinity are one of the expanding cycles. No iteration with "random"
digit pattern has been found for numbers < 10^6.
This suggests a few challenges:
1) Prove that the cycles L-M are the only possible
ones.
2) Prove that the expanding cycles A-I are the only
possible ones.
3) Is there a number above which no number goes to 0?
7.6 Predecessor statistics
There are 165 numbers < 10^3
with no predecessor:
110
120
121
130
131
132
...
The requirement is that the middle
digit is at least as big as the sum of the other two (Berend
Jan van der Zwaag).
Using an algorithm that determines
all predecessors to a given number, we get the following table.
Up to -> |
10^3 |
10^4 |
10^5 |
10^6 |
10^7 |
10^8 |
10^9 |
10^10 |
0 |
165 |
2867 |
42907 |
548144 |
6520193 |
73543012 |
801726786 |
8528432789 |
1 |
164 |
1915 |
19359 |
181374 |
1595745 |
13495392 |
110380431 |
881047611 |
2 |
164 |
1668 |
14622 |
122298 |
961085 |
7283293 |
53447981 |
383324517 |
3 |
158 |
1378 |
10570 |
76789 |
528707 |
3527594 |
22879751 |
145514909 |
4 |
121 |
929 |
6269 |
40189 |
243655 |
1432601 |
8187936 |
45923129 |
5 |
89 |
591 |
3446 |
19090 |
100242 |
511013 |
2536968 |
12372762 |
6 |
62 |
348 |
1716 |
8081 |
36128 |
157222 |
667483 |
2789252 |
7 |
40 |
184 |
748 |
2929 |
10946 |
40031 |
143455 |
508212 |
8 |
23 |
83 |
271 |
866 |
2683 |
8229 |
24994 |
75694 |
9 |
11 |
29 |
76 |
199 |
525 |
1390 |
3701 |
9892 |
10 |
2 |
7 |
15 |
40 |
90 |
222 |
513 |
1233 |
Sum |
999 |
9999 |
99999 |
999999 |
9999999 |
99999999 |
999999999 |
9999999999 |
(ex. “Up to 10^4 there are 1668 integers with 2 predecessors”)
Numbers with no predecessors
become more frequent as numbers grow larger, whereas ones with 1..10 predecessors seem to reach a maximum and then recede as
illustrated graphically below.
What is surprising is that no
number (below 10^10) has more than 10 predecessors. (The reverse algorithm used
here is more complicated but requires less time and memory than using the
forward algorithm for this purpose. The data in the above diagram up to 10^8
has been verified by using the forward algorithm.)
More predecessors maybe will appear
for numbers larger than 10^10.
Using 10^7 random samples each of
numbers up to 30 digits, the following graph was obtained.
This diagram is similar to the
previous one.
No number with more that 10 predecessors was found, but it may be that 11 or
more is extremely rare and needs a very large number of digits.
So there are two more challenges:
4) Find a number that has 11 or more predecessors, or
5) Prove that no number can have more than 10
predecessors.
7.7 Numbers with 10 predecessors
Numbers with 10 predecessors has
been calculated for all numbers < 10^10 (see previous section).
The count of occurrences numbers
less than different powers of 10 is:
10^3 |
10^4 |
10^5 |
10^6 |
10^7 |
10^8 |
10^9 |
10^10 |
2 |
7 |
15 |
40 |
90 |
222 |
513 |
1233 |
A few of the first entries are
Number ... Predecessors ...
10 |
100 |
19 |
28 |
37 |
46 |
55 |
64 |
73 |
82 |
91 |
109 |
1009 |
190 |
281 |
372 |
463 |
554 |
645 |
736 |
827 |
918 |
1010 |
191 |
282 |
373 |
464 |
555 |
646 |
737 |
828 |
9100 |
919 |
1011 |
10010 |
192 |
283 |
374 |
465 |
556 |
647 |
738 |
829 |
9101 |
1099 |
10090 |
1909 |
2818 |
3727 |
4636 |
5545 |
6454 |
7363 |
8272 |
9181 |
1110 |
10100 |
1019 |
291 |
382 |
473 |
564 |
655 |
746 |
837 |
928 |
9910 |
18100 |
1819 |
2728 |
3637 |
4546 |
5455 |
6364 |
7273 |
8182 |
9091 |
10109 |
1918 |
2827 |
3736 |
4645 |
5554 |
6463 |
7372 |
8281 |
91009 |
9190 |
10119 |
100109 |
1927 |
2836 |
3745 |
4654 |
5563 |
6472 |
7381 |
8290 |
91018 |
10910 |
10091 |
28100 |
2819 |
3728 |
4637 |
5546 |
6455 |
7364 |
8273 |
9182 |
10911 |
10092 |
19010 |
28101 |
3729 |
4638 |
5547 |
6456 |
7365 |
8274 |
9183 |
10999 |
100909 |
19090 |
28181 |
37272 |
46363 |
55454 |
64545 |
73636 |
82727 |
91818 |
11109 |
101009 |
10190 |
2918 |
3827 |
4736 |
5645 |
6554 |
7463 |
8372 |
9281 |
98910 |
18091 |
27182 |
36273 |
45364 |
54455 |
63546 |
72637 |
81728 |
908100 |
90819 |
99109 |
181009 |
18190 |
27281 |
36372 |
45463 |
54554 |
63645 |
72736 |
81827 |
90918 |
From this and from the complete
data set in the file Pred10.txt one can see some recurring patterns.
Maybe these patterns are a clue to
solving the 10-predecessor problem.
A few more observations:
o Numbers start with 1 or 9.
o Numbers contain only digits 0, 1,
2, 8, 9, therefore no number contains any of the digits 3-7.
o Last digit is 0, 1 or 9.
o Last two digits are 09, 10, 11, 19
or 99.
(c) Lars Blomberg
___________________________________________________________________________________________________________________
Thanks to all, merci à tous !