Colorless green ideas

(I hope this is not old hat)

Let N be an integer

Let S be the sum of N’s digits

--> make M=N+S if S is even

--> make M=N-S if S is odd

Iterate.

Example:

71(+8)=79

79(+16)=95

95(+14)=109

109(+10)=119

119(-11)=108

108(-9)=99

99(+18)=117

117(-9)=108

Thus 71 enters in the loop 99.117.108.99

---

Here is the fate of the first 245 integers below (computed by hand);

- colorless integers end on zero;

- yellow integers are attracted in the loop 99.117.108.99;

- grey integers are attracted in the loop 198.216.207.198:

1, 2, 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, 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, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 243, 245, ...

---

The next attractor is 297.315.306.297, I guess (considering the arising pattern). Will there be a change in the attractor’s behaviour when we’ll jump to 4-digit integers? Could someone provide a list of the successive attractors?

I guess that all integers end in a loop, at some point. Which integer < 1000000 performs the longest “flight”? Are there interesting sequences for the OEIS, here?

Best,

É.

(sleeping now furiously)

__________

Update, February 23rd, 2011.

I’ve received this yesterday, from an anonymous (Dutch?) member of SeqFans, < Aai >:

Here are some answers obtained with progr. lang. J (http://www.jsoftware.com/index.html)

Mind line wrapping!

First different attractors N < 500

~. ,. ([: (({:=}:) ];. 1 }:) (,(+ ([: (* (_1 ^ 2&|))

+/@:(,.&.":)))@{:)^:({:-.@e.}:)^:_ )&. 0+i.500

┌───────────┐

│0

├───────────┤

│108 99 117 │

├───────────┤

│99 117 108 │

├───────────┤

│117 108 99 │

├───────────┤

│207 198 216│

├───────────┤

│198 216 207│

├───────────┤

│216 207 198│

├───────────┤

│297 315 306│

├───────────┤

│306 297 315│

├───────────┤

│315 306 297│

├───────────┤

│405 396 414│

├───────────┤

│396 414 405│

├───────────┤

│414 405 396│

├───────────┤

│495 513 504│

├───────────┤

│504 495 513│

├───────────┤

│513 504 495│

└───────────┘

for 600000 <= N < 600200

~. ,. ([: (({:=}:) ];. 1 }:) (,(+ ([: (* (_1 ^ 2&|))

+/@:(,.&.":)))@{:)^:({:-.@e.}:)^:_ )&. 600000+i.200

┌──────────────────────────────────────────────────────────────┐

│599949 599904 599940 599976 599931 599967 599922 599958 599913│

├──────────────────────────────────────────────────────────────┤

│600093 600111 600102

├──────────────────────────────────────────────────────────────┤

│600102 600093 600111

├──────────────────────────────────────────────────────────────┤

│600111 600102 600093

├──────────────────────────────────────────────────────────────┤

│600201 600192 600210

├──────────────────────────────────────────────────────────────┤

│600192 600210 600201

├──────────────────────────────────────────────────────────────┤

│600462 600480 600498 600471 600489

├──────────────────────────────────────────────────────────────┤

│600210 600201 600192

└──────────────────────────────────────────────────────────────┘

I assumed the longest ones will be found somewhere between 100000 < N < 1000000 :-)

(O o, assumption is the mother of all...)

length 698869 = 52

The whole sequence:

_13 ]\(,(+ ([: (* (_1 ^ 2&|)) +/@:(,.&.":)))@{:)^:({:-.@e.}:)^:_

[698869, 698869, 698915, 698953, 698993, 699037, 699071, 699103, 699131, 699102, 699075, 699111, 699084, 699120, 699093, 699129, 699165, 699201, 699174, 699210, 699183, 699219, 699255, 699291, 699327, 699363, 699399, 699354, 699390, 699426, 699462, 699498, 699453, 699489, 699444, 699480, 699516, 699552, 699588, 699543, 699579, 699534, 699570, 699606, 699642, 699678, 699633, 699669, 699624, 699660, 699696, 699651, 699687, 699642] <-- first repeater.

Met vriendelijke groet,

=@@i

Good job, thank you Aai!

__________

Harvey P. Dale:

Here is a simple Mathematica program to compute this sequence. By changing the second term in the second line of the program, you can change the initial seed number. In most cases, the resulting sequence fairly quickly devolves into a string of zeroes. If you seed it with 71, however, it produces a sequence that, after the first five initial terms, consists of a repetitive cycle of 108, 99, 117.

nxt[n_]:=Module[{tidn=Total[IntegerDigits[n]]},If[EvenQ[tidn],n+tidn, n-tidn]]

NestList[nxt,71,100]

Charles Greathouse :

Is there a good way to find the final cycles in Mathematica? I know of bad ways (say, hardcode Floyd’s algorithm) and of course it could be done manually, something like

Final[0] := {0}

Final[99] := {99, 117, 108}

Final[6732] := {6732, 6750, 6768, 6741, 6759}

Final[6642] := {6642, 6660, 6678, 6651, 6669}

. . .

Final[n_] := Final[n] = Final[nxt[n]]

but I was wondering if there’s a built-in way, something like FixedPointList[nxt, 71] but stopping at a fixed cycle rather than fixed element.

Neil Sloane:

Start at n, let a(n) be the smallest number in the cycle if it goes into a cycle, or -1 if it diverges. Is this sequence in the OEIS? And if not, you know what to do!

William Keith :

Looks like none of them diverge, none go to 0 after 98, and all of them wind up in a cycle that is fairly close by. Cycles appear to be exclusively rooted on multiples of 9: {99, 117, 108, 99}, {198, 216, 207, 198}, {6732, 6750, 6768, 6741, 6759, 6732}, {6822, 6840, 6858, 6831, 6849, 6822}, etc. Makes sense, as sums of digits will be closed under that property, and I’d suspect that there’s a digital criterion that will tell you where a number goes.

Maximilian Hasler:

[Neil]:

> Start at n, let a(n) be the smallest number in the cycle if it goes into a cycle, or -1 if it diverges.

That sequence is a bit boring, and in particular its first 3 lines...

Here are the first 1000 terms:

/* return the first number seen twice when starting with n */

{ EAI = (n,S=[])->while(!setsearch(S,n),S=setunion(S,Set(n));n+=(-1)^(s=digsum(n))*s);n

}

/* return the loop, starting (and ending) with the least element.

assumes that n is part of the loop */

{EAL = (n)->n=[n];until(!n[#n]|n[#n]==n[1],n=concat(n,n[#n]+=(-1)^(s=digsum(n[#n]))*s));while(n[1]>vecmin(n),n=concat(vecextract(n,"2.."),n[2]));n

}

for(n=0,999,print1(EAL(EAI(n))[1]", "))

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 99, 0, 0, 0, 0, 0, 99, 0, 99, 99, 0, 0, 0, 0, 0, 99, 0, 99, 0, 0, 99, 0, 99, 0, 99, 0, 99, 0, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 198, 99, 99, 99, 99, 99, 198, 99, 198, 99, 99, 99, 99, 99, 99, 99, 99, 198, 99, 198, 198, 99, 198, 99, 198, 99, 198, 99, 198, 99, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 198, 297, 198, 198, 198, 198, 198, 297, 198, 297, 198, 198, 198, 198, 198, 198, 198, 198, 297, 198, 297, 297, 198, 297, 198, 297, 198, 297, 198, 297, 198, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 297, 396, 297, 297, 297, 297, 297, 396, 297, 396, 297, 297, 297, 297, 297, 297, 297, 297, 396, 297, 396, 396, 297, 396, 297, 396, 297, 396, 297, 396, 297, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 396, 495, 396, 396, 396, 396, 396, 495, 396, 495, 396, 396, 396, 396, 396, 396, 396, 396, 495, 396, 495, 495, 396, 495, 396, 495, 396, 495, 396, 495, 396, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 495, 594, 495, 495, 495, 495, 495, 594, 495, 594, 495, 495, 495, 495, 495, 495, 495, 495, 594, 495, 594, 594, 495, 594, 495, 594, 495, 594, 495, 594, 495, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 693, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 693, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 594, 693, 594, 594, 594, 594, 594, 693, 594, 693, 594, 594, 594, 594, 594, 594, 594, 594, 693, 594, 693, 693, 594, 693, 594, 693, 594, 693, 594, 693, 594, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 792, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 792, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 693, 792, 693, 693, 693, 693, 693, 792, 693, 792, 693, 693, 693, 693, 693, 693, 693, 693, 792, 693, 792, 792, 693, 792, 693, 792, 693, 792, 693, 792, 693, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 972, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 972, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 792, 972, 792, 792, 792, 792, 792, 792, 792, 972, 792, 972, 792, 792, 792, 792, 792, 972, 792, 972, 792, 792, 792, 792, 792, 792, 792, 792, 972, 792, 972, 972, 792, 972, 792, 972, 792, 972, 792, 972, 792, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, 972, ...

Maybe more / also interesting:

b(n) = list of these values

c(n) = least integer to hit b(n)

d(n) = largest integer to hit b(n)

e(n) = number of steps for n to go to a(n)

f(n) = number of steps until one element is seen twice

g(n) = number of steps until / before n reaches it’s "ending loop"

h(n) = length of the loop containing b(n)

Maximilian again:

The loops and the minimal element going into that loop:

L=[]; for(n=0,9999,T=EAL(EAI(n)); setsearch(L,T) & next; print(n"

"T","); L=setunion(L,Set([T])))

0 [0, 0],

71 [99, 117, 108, 99],

170 [198, 216, 207, 198],

260 [297, 315, 306, 297],

350 [396, 414, 405, 396],

440 [495, 513, 504, 495],

530 [594, 612, 603, 594],

578 [693, 711, 702, 693],

668 [792, 810, 801, 792],

758 [972, 990, 1008, 999, 972],

1070 [1098, 1116, 1107, 1098],

1160 [1197, 1215, 1206, 1197],

1250 [1296, 1314, 1305, 1296],

1340 [1395, 1413, 1404, 1395],

1430 [1494, 1512, 1503, 1494],

1478 [1593, 1611, 1602, 1593],

1568 [1692, 1710, 1701, 1692],

1658 [1962, 1980, 1998, 1971, 1989, 1962],

2060 [2097, 2115, 2106, 2097],

2150 [2196, 2214, 2205, 2196],

2240 [2295, 2313, 2304, 2295],

2330 [2394, 2412, 2403, 2394],

2378 [2493, 2511, 2502, 2493],

2468 [2592, 2610, 2601, 2592],

2558 [2862, 2880, 2898, 2871, 2889, 2862],

2837 [2952, 2970, 2988, 2961, 2979, 2952],

3050 [3096, 3114, 3105, 3096],

3140 [3195, 3213, 3204, 3195],

3230 [3294, 3312, 3303, 3294],

3278 [3393, 3411, 3402, 3393],

3368 [3492, 3510, 3501, 3492],

3458 [3762, 3780, 3798, 3771, 3789, 3762],

3737 [3852, 3870, 3888, 3861, 3879, 3852],

3836 [3942, 3960, 3978, 3951, 3969, 3942],

4040 [4095, 4113, 4104, 4095],

4130 [4194, 4212, 4203, 4194],

4178 [4293, 4311, 4302, 4293],

4268 [4392, 4410, 4401, 4392],

4358 [4662, 4680, 4698, 4671, 4689, 4662],

4637 [4752, 4770, 4788, 4761, 4779, 4752],

4736 [4842, 4860, 4878, 4851, 4869, 4842],

4844 [4932, 4950, 4968, 4941, 4959, 4932],

5030 [5094, 5112, 5103, 5094],

5078 [5193, 5211, 5202, 5193],

5168 [5292, 5310, 5301, 5292],

5258 [5562, 5580, 5598, 5571, 5589, 5562],

5537 [5652, 5670, 5688, 5661, 5679, 5652],

5636 [5742, 5760, 5778, 5751, 5769, 5742],

5744 [5832, 5850, 5868, 5841, 5859, 5832],

5843 [5922, 5940, 5958, 5931, 5949, 5922],

6020 [6093, 6111, 6102, 6093],

6068 [6192, 6210, 6201, 6192],

6158 [6462, 6480, 6498, 6471, 6489, 6462],

6437 [6552, 6570, 6588, 6561, 6579, 6552],

6536 [6642, 6660, 6678, 6651, 6669, 6642],

6644 [6732, 6750, 6768, 6741, 6759, 6732],

6743 [6822, 6840, 6858, 6831, 6849, 6822],

6842 [6912, 6930, 6948, 6921, 6939, 6912],

6950 [7092, 7110, 7101, 7092],

7058 [7362, 7380, 7398, 7371, 7389, 7362],

7337 [7452, 7470, 7488, 7461, 7479, 7452],

7436 [7542, 7560, 7578, 7551, 7569, 7542],

7544 [7632, 7650, 7668, 7641, 7659, 7632],

7643 [7722, 7740, 7758, 7731, 7749, 7722],

7742 [7812, 7830, 7848, 7821, 7839, 7812],

7854 [7902, 7920, 7938, 7911, 7929, 7902],

7931 [8262, 8280, 8298, 8271, 8289, 8262],

8237 [8352, 8370, 8388, 8361, 8379, 8352],

8336 [8442, 8460, 8478, 8451, 8469, 8442],

8444 [8532, 8550, 8568, 8541, 8559, 8532],

8543 [8622, 8640, 8658, 8631, 8649, 8622],

8642 [8712, 8730, 8748, 8721, 8739, 8712],

8754 [8802, 8820, 8838, 8811, 8829, 8802],

8893 [9162, 9180, 9198, 9171, 9189, 9162],

9137 [9252, 9270, 9288, 9261, 9279, 9252],

9236 [9342, 9360, 9378, 9351, 9369, 9342],

9344 [9432, 9450, 9468, 9441, 9459, 9432],

9443 [9522, 9540, 9558, 9531, 9549, 9522],

9542 [9612, 9630, 9648, 9621, 9639, 9612],

9654 [9702, 9720, 9738, 9711, 9729, 9702],

9883 [9999, 10035, 10026, 10017, 10008, 9999],

>>> f(n) = number of steps until one element is seen twice

{ EAC = (n,S=[])->for(i=1,1e9,

S=setunion(S,Set(n));setsearch(S,n+=(-1)^(s=digsum(n))*s) & return(i))

}

for(n=0,299, print1(EAC(n)", "))

1, 2, 6, 2, 5, 2, 4, 2, 4, 2, 3, 7, 3, 6, 3, 5, 3, 5, 3, 5, 8, 4, 7, 4, 6, 4, 6, 4, 6, 4, 5, 8, 5, 12, 5, 7, 5, 7, 5, 11, 9, 6, 13, 6, 8, 6, 8, 6, 12, 6, 7, 10, 7, 9, 7, 9, 7, 9, 7, 12, 11, 8, 10, 8, 10, 8, 10, 8, 13, 8, 9, 8, 9, 11, 9, 11, 9, 9, 9, 7, 6, 10, 12, 10, 12, 10, 5, 10, 5, 10, 11, 8, 11, 6, 11, 6, 11, 5, 11, 3, 4, 7, 4, 6, 4, 5, 4, 5, 3, 5, 7, 4, 6, 4, 5, 4, 5, 3, 5, 4, 4, 7, 4, 11, 4, 6, 4, 6, 4, 10, 8, 5, 12, 5, 7, 5, 7, 5, 11, 5, 6, 9, 6, 8, 6, 8, 6, 8, 6, 11, 10, 7, 9, 7, 9,

>>> Records:

m=0; for(n=0,999999, m<EAC(n)|next; print1(m=EAC(n) ", "))

1, 2, 6, 7, 8, 12, 13, 14, 20, 27, 28, 31, 36, 37, 38, 39, 40, 41, 45, 46, 48, 49, 52

>>> Indices of records:

0, 1, 2, 11, 20, 33, 42, 161, 758, 1658, 7931, 29773, 29782, 79811, 289474, 289511, 299374, 299411, 389374, 389411, 399274, 399311, 698869 (answer to Eric’s question: record holder below 10^6)

>>> Indices with yet unseen run length:

u=0; for(n=0,999999, bittest(u,EAC(n)) & next; print1([n, m=EAC(n)] ",

"); u+=1<<m)

[0, 1], [1, 2], [2, 6], [4, 5], [6, 4], [10, 3], [11, 7], [20, 8], [33, 12], [39, 11], [40, 9], [42, 13], [51, 10], [161, 14], [758, 20], [778, 19], [790, 18], [798, 17], [820, 16], [828, 15], [1658, 27], [1678, 26], [1690, 25], [1698, 24], [1719, 21], [1720, 23], [1728, 22], [7931, 28], [29773, 31], [29782, 36], [29801, 30], [29810, 35], [29821, 29], [29830, 34], [29852, 33], [29878, 32], [79811, 37], [289474, 38], [289511, 39], [299374, 40], [299411, 41], [389374, 45], [389408, 44], [389411, 46], [389419, 42], [389440, 43], [399274, 48], [399308, 47], [399311, 49], [698869, 52], [698896, 50], [698915, 51]

>>> Least k such that f(k)=n, [or -1 if n never occurs in f: will this happen?]

apply(x->x[1], vecsort(%,2));

0, 1, 10, 6, 4, 2, 11, 20, 40, 51, 39, 33, 42, 161, 828, 820, 798, 790, 778, 758, 1719, 1728, 1720, 1698, 1690, 1678, 1658, 7931, 29821, 29801, 29773, 29878, 29852, 29830, 29810, 29782, 79811, 289474, 289511, 299374, 299411, 389419, 389440, 389408, 389374, 389411, 399308, 399274, 399311, 698896, 698915, 698869

Robert Gerbicz:

[Neil]:

> Start at n, let a(n) be the smallest number in the cycle if it goes into a cycle, or -1 if it diverges.

My conjecture is that for every n in O(log(n)^2) iteration the sequence goes to a cycle. The idea behind this that by O(1/log(n)) probability F(F(n))=n is true. Computations up to n=10^5 supports my conjecture.

Robert Gerbicz, again:

> The idea behind this that by O(1/log(n)) probability F(F(n))=n is true.

Need another idea, up to n=10^7 there is no solution of F(F(n))=n, other than the trivial n=0.

Does it have a loop of length two?

Hans Havermann:

[Robert Gerbicz]:

> Does it have a loop of length two?

No. Let {a,b} represent such a loop with a<b.

b=a+s(a)

a=b-s(b) => b=a+s(b) => s(a)=s(b)

but s(a) is even and s(b) is odd, a contradiction

Jack Brennen:

[Neil]:

> Start at n, let a(n) be the smallest number in the cycle if it goes into a cycle, or -1 if it diverges.

Cycles must consist exclusively of multiples of 9.

Any time that a number’s successor is smaller than the first number, the successor will be a multiple of 9. Any multiple of 9 has a successor which is a multiple of 9. Every cycle will have a downward step in the cycle. Put all that together, it’s easy to see that all cycles are entirely multiples of 9.

Jack Brennen:

[Robert Gerbicz]:

> Need another idea, up to n=10^7 there is no solution of F(F(n))=n, other than the trivial n=0.

> Does it have a loop of length two?

There is no other solution of F(F(n))=n, other than the trivial 0.

The sequence can only go up by an even delta, and only down by an odd delta. So no two-step cycles, since one would have to be an up delta, and the other a down delta.

A three-step cycle would have to be UP, DOWN, DOWN. For instance, 99->117->108->99.

I wrote a little program to find invariants for loops... Basically, the idea being that there should be invariants of the form:

N*10^a + b always ends up in the same loop as long as the sum of digits of N is equal to some value C.

The first such invariant that the program found was C=16, a=2, b=2.

The first such integer example under this invariant is the number 7902:

7902->7920->7938->7911->7929->7902.

Note that since the additions and subtractions never carry or borrow beyond the tens column, all that matters is the digit sum of the prefix (in this case "79" has digit sum 16). So the following numbers all enter similar loops:

7902, 8802, 9702, 16902, 17802, 18702, 19602, 25902, 26802, 27702, 28602, 29502, ...

Another example, with a large prefix digit sum, is C=100, a=3, b=332.

If N has digit sum 100, the following loop is possible:

N*10^3 + 332

N*10^3 + 440

N*10^3 + 548

N*10^3 + 431

N*10^3 + 539

N*10^3 + 422

N*10^3 + 530

N*10^3 + 638

N*10^3 + 521

N*10^3 + 629

N*10^3 + 512

N*10^3 + 620

N*10^3 + 728

N*10^3 + 611

N*10^3 + 719

N*10^3 + 602

N*10^3 + 710

N*10^3 + 818

N*10^3 + 701

N*10^3 + 809

N*10^3 + 692

N*10^3 + 575

N*10^3 + 458

N*10^3 + 341

N*10^3 + 449

N*10^3 + 332

The loop has 25 steps in a cycle, 13 steps are each +108, the other 12 steps are each -117.

Seems obvious that you could find arbitrarily long loops, although you would obviously be dealing with long numbers. The loop shown above doesn’t apply to any integer smaller than 199999999999332.

Maximilian Hasler:

[Jack Brennen]:

Nice reasoning of yours, abt. multiples of 9.

Just fyi, some experimental data (loops) [above].

You will see & may want to proof some patterns (last digit of elements in a loop, depending on length, especially for L=5)

Aai:

Hi Eric,

The following is obtained by using the J programming language.

Let’s call the canonical form of a terminating cycle the rotation that starts with the smallest value, e.g. 71 has the first 3-cycle:

108 99 117

having the canonical form

99 117 108

Then 99 is smallest number of this cycle.

Of course this cycle has the following three instances

99 117 108

117 108  99

108  99 117

Here are the first 100 terms for 0 <= N <= 12230:

0, 99, 198, 297, 396, 495, 594, 693, 792, 972, 1098, 1197, 1296, 1395, 1494, 1593, 1692, 1962, 2097, 2196, 2295, 2394, 2493, 2592, 2862, 2952, 3096, 3195, 3294, 3393, 3492, 3762, 3852, 3942, 4095, 4194, 4293, 4392, 4662, 4752, 4842, 4932, 5094, 5193, 5292, 5562, 5652, 5742, 5832, 5922, 6093, 6192, 6462, 6552, 6642, 6732, 6822, 6912, 7092, 7362, 7452, 7542, 7632, 7722, 7812, 7902, 8262, 8352, 8442, 8532, 8622, 8712, 8802, 9162, 9252, 9342, 9432, 9522, 9612, 9702, 9999, 10098, 10197, 10296, 10395, 10494, 10593, 10692, 10962, 11097, 11196, 11295, 11394, 11493, 11592, 11862, 11952, 12096, 12195, 12294, ...

having digit sums 0 18 36

Cycle starting values for 500000 <= N < 510000

499914 500094 500193 500292 500562 500652

500742 500832 500922 501093 501192 501462

501552 501642 501732 501822 501912 502092

502362 502452 502542 502632 502722 502812

502902 503262 503352 503442 503532 503622

503712 503802 504162 504252 504342 504432

504522 504612 504702 505062 505152 505242

505332 505422 505512 505602 506052 506142

506232 506322 506412 506502 507042 507132

507222 507312 507402 507879 508032 508122

508212 508302 508779 508878 509022 509112

509202 509679 509778 509877 509994 510093

The digits sums of these values are: 36 18

Q: are all digit sums of these values even multiples of 9?

Jean-Marc Falcoz:

Voici deux images faites avec Mathematica, qui regroupent synthétiquement les chaînes formées par tous les entiers, de 0 à 100.

Hans Havermann:

Known minimal solutions for a given loop-length, in the order in which they arise:

1 {0}

3 {99, 117, 108}

4 {972, 990, 1008, 999}

5 {1962, 1980, 1998, 1971, 1989}

7 {39879, 39915, 39888, 39924, 39897, 39933, 39906}

6 {99954, 99990, 100026, 100017, 100008, 99999}

8 {299934, 299970, 300006, 299997, 299952, 299988, 299943, 299979}

9 {399924, 399960, 399996, 399951, 399987, 399942, 399978, 399933, 399969}

10 {29999916, 29999970, 30000024, 30000015, 30000006, 29999997, 29999934, 29999988, 29999925, 29999979}

11 {39999906, 39999960, 40000014, 40000005, 39999996, 39999933, 39999987, 39999924, 39999978, 39999915, 39999969}

13 {49999806, 49999860, 49999914, 49999968, 49999905, 49999959, 49999896, 49999833, 49999887, 49999824, 49999878, 49999815, 49999869}

14 {2999999808, 2999999880, 2999999952, 3000000024, 3000000015, 3000000006, 2999999997, 2999999916, 2999999988, 2999999907, 2999999979, 2999999898, 2999999817, 2999999889}

12 {3989999808, 3989999880, 3989999952, 3990000024, 3989999997, 3989999916, 3989999988, 3989999907, 3989999979, 3989999898, 3989999817, 3989999889}

17 {3999999708, 3999999780, 3999999852, 3999999924, 3999999996, 3999999915, 3999999987, 3999999906, 3999999978, 3999999897, 3999999816, 3999999888, 3999999807, 3999999879, 3999999798, 3999999717, 3999999789}

With the exception of length-12, the larger solutions are all in the space directly below m*10^n (m=1..9), so using this as a search mechanism, some other loop-lengths and the first element of the (not necessarily minimal) loop:

23 19999999998909

25 99999999999432

16 5999999999998824

29 7999999999999524

19 89999999999899767

15 99999999999899766

20 499999999999989924

33 699999999999999516

37 69999999999999999318

41 19999999999999999899360

49 99999999999999999999999144

31 2999999999999999999999899575

53 7999999999999999999999999326

27 89999999999999999999999899578

57 899999999999999999999999999028

24 2999999999999999999999999999988864

69 2999999999999999999999999999999996334

73 99999999999999999999999999999999899226

35 1999999999999999999999999999999999899369

77 19999999999999999999999999999999999899207

81 2999999999999999999999999999999999999996460

28 199999999999999999999999999999999999999988802

32 899999999999999999999999999999999999999988957

93 1999999999999999999999999999999999999999999899216

97 99999999999999999999999999999999999999999999899298

22 29999999999999999999999999999999999999999999999999998548

48 899999999999999999999999999999999999999999999999999981604

56 999999999999999999999999999999999999999999999999999980604

137 29999999999999999999999999999999999999999999999999999999999999999995038

40 19999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999981800

92 19999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999981206

No sign of 18, 21, 26, ...

The solutions for loop-lengths 16, 19, 15, 40, and 92 were first noted by Lars Blomberg.

Hans Havermann, follow-up:

In our known minimal solutions for a given loop-length, many (lengths

3, 4, 6, 8, 10, 11, 14) have loop members on both sides of the m*10^n

reference point. By contrast, in the subsequent not-necessarily-

minimal solutions only one (length-22) meets this consideration. With

that caveat in mind, it is nevertheless much easier to search for new

lengths based on just such a criterion: One need only determine the

loop starting with ‘(m)zeros(9-m)’ and take its smallest member. Doing

so for n up to 10000 yields 8 new loop-lengths: 18, 26, 39, 21, 36,

43, 30, and 34 (leaving 38 the smallest loop-length with no known

upper bound). The first members of these new loops are quite large:

34’s is an 8779-digit number! Because it is on the smaller end of that

scale, I’ll evolve loop-length 18 here:

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995547

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997023

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995556

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997032

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995565

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997041

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995574

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997050

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995583

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997059

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998535

7000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011

7000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999993

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998508

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999984

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998499

6999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997014

Lars Blomberg:

Using a technique which I guess is similar to the one Hans described lately, namely, to iterate only the small values to the right and keep track of the total DigitSum without actually computing with these enormous numbers, I can supply the following:

An 18-loop:

599999999899999999959

599999999900000000139

599999999900000000040

599999999900000000130

599999999900000000220

599999999900000000310

599999999900000000400

599999999900000000490

599999999900000000391

599999999900000000292

599999999900000000193

599999999900000000094

599999999899999999995

599999999900000000175

599999999900000000076

599999999899999999977

599999999900000000157

599999999900000000058

A 38-loop, starting with

4999989999999999999999999999999999999618

Using a shorthand notation where <n> means n 9’s in sequence, this can more conveniently be expressed as

4<4>8<31>618

This 293-loop is the longest I have found so far:

5<144>(30)1246

where (n) means n 0’s in sequence

And this 186-loop has the largest starting value (610 digits) that I have found:

8<343>8<261>3368

None of the above loops are proven to have the smallest starting number for that loop-length.

Lars Blomberg, update (March 17th, 2011)

Colorless integers -- An enumerator for a series of cycles of length 3

The first cycle of length 3 is {99, 117, 108} with the differences between consecutive values being {18, -9, -9}.

There are many other cycles of length 3 with the same differences but with different start values.

The first few cycle start values are:

{99, 198, 297, 396, 495, 594, 693, 792, 1098, 1197, 1296, 1395, 1494,

1593, 1692, 2097, 2196, 2295, 2394, 2493, 2592, 3096, 3195, 3294, 3393,

3492, 4095, 4194, 4293, 4392, 5094, 5193, 5292, 6093, 6192, 7092, 10098,

10197, 10296, 10395, 10494, 10593, 10692, 11097, ...}

Taking first differences and dividing by 9 we get (all the values are divisible by 9 so the differences are too):

{11, 11, 11, 11, 11, 11, 11, 11, 34, 11, 11, 11, 11, 11, 11, 45, 11, 11, 11, 11,

11, 56, 11, 11, 11, 11, 67, 11, 11, 11, 78, 11, 11, 89, 11, 100, 334, 11, 11,

11, 11, 11, 11, 45, ...}

There is a pattern here in the differences that becomes more obvious as more values are inspected.

After some coding and testing, the following algorithm was found. It is expressed in C#, but it should be understandable since it contains no difficult language features.

List<long> All = new List<long>();

// Creates the list "All" with differences divided by 9

// Parameter "maxSize" is maximum number of digits in the generated differences

public void Create(int maxSize)

{

Start();

for (int i = 2; i <= maxSize; i++)

{

GenerateSize(i);

}

}

// A few values in the beginning cannot be made to fit the algorithm

private void Start()

{

for (int i = 0; i < 8; i++)

{

}

}

// Generate everything for a given size

void GenerateSize(int size)

{

for (int i = 4; i <= 10; i++)

{

Generate(i, size, true);

}

}

// Recursive method

void Generate(int lastDigit, int size, bool startWithNumber)

{

int i, j;

if (startWithNumber)

{

}

if (size > 2)

{

bool swn = false;

for (i = lastDigit; i < 11; i++)

{

Generate(i, size - 1, swn);

swn = true;

}

}

else

{

// Just a number of 11's

for (j = lastDigit; j < 10; j++)

{

}

}

}

// For example, calling with lastDigit=4 and size=5 will return the number 33334

long Number(int lastDigit, int size)

{

return long.Parse(new string((char)('0' + lastDigit - 1), size))+1;

}

Looking at the # of digits in the start value versus the first digit of the start value we get the following table:

# of digits->

Below: Initial digit

2 3 4 5 6 7 8 9 10 11 12

1 1 7 28 84 210 462 924 1716 3003 5005

2 1 6 21 56 126 252 462 792 1287 2002

3 1 5 15 35 70 126 210 330 495 715

4 1 4 10 20 35 56 84 120 165 220

5 1 3 6 10 15 21 28 36 45 55

6 1 2 3 4 5 6 7 8 9 10

7 1 1 1 1 1 1 1 1 1 1

9 1

We see that cycles with low initial digit are more frequent, and increasingly so as the number of digits grow larger.

One can note that initial digit 7 has just one value per order of magnitude (of the form 70...092), 8 has none at all and 9 none at all except the very first cycle (99).

Furthermore, one can count all the cycles starting from a number with a given number of digits.

# of digits 2 3 4 5 6 7 8 9 10 11 12

Count 1 7 28 84 210 462 924 1716 3003 5005 8008

Accumulated count 1 8 35 112 294 672 1386 2640 4719 8008 13013

With the help of OEIS, it is easy to find that the "Count" values are:

A000579, binomial coefficients C(n,6), a(n) = (n^6-15*n^5+85*n^4-225*n^3+274*n^2-120*n)/720.

And the "Accumulated count" values are:

A040977, C(n+5,5)*(n+3)/3, Sequence is n^2*(n^2-1)*(n^2-4)/360 if offset 3.

This indicates that the number of 3-cycles with differences {18, -9, -9} are infinite, but they become increasingly rare: O(n^6)/10^n.

All of the above has come from empirical study, I have no proofs.

Hans also asked me to inform you that he has added loop evolution to the up-to-100 loops page:

__________

Many thanks to all contributors!

Best,

É.

__________

Nage en petits bassins

... on voit bien les entiers, comme autant de billes de verre,

rouler dans un paysage de porcelaine,

dévaler certaines pentes, hésiter,

puis se répartir doucement dans une infinité de bassins d’attraction,

se serrer les uns contre les autres, en spirale,

au bout du labyrinthe des collines et vallées.

[É.A., private e-mail to Alexandre Wajnberg]