Sequences Formed By Removing Zeros

It's interesting to consider what happens to a sequence if a certain rule is applied but with the stipulation that any zeros arising must be removed. If we start with 1, double it and then double the result and continue this process, we end up with an infinite sequence:

1, 2, 4, 6, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, ...

But what happens once any zeros that arise are removed? Well, nothing until 1024 is reached and it becomes 124, then 248, 496 etc. It turns out that the sequence enters a loop (marked in blue below) that has a period of 36. The minimum value within the loop is 28714 and the largest is 11,772,544. The maximum value reached overall is 765,257,552.

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 124, 248, 496, 992, 1984, 3968, 7936, 15872, 31744, 63488, 126976, 253952, 5794, 11588, 23176, 46352, 9274, 18548, 3796, 7592, 15184, 3368, 6736, 13472, 26944, 53888, 17776, 35552, 7114, 14228, 28456, 56912, 113824, 227648, 455296, 91592, 183184, 366368, 732736, 1465472, 293944, 587888, 1175776, 2351552, 47314, 94628, 189256, 378512, 75724, 151448, 32896, 65792, 131584, 263168, 526336, 152672, 35344, 7688, 15376, 3752, 754, 158, 316, 632, 1264, 2528, 556, 1112, 2224, 4448, 8896, 17792, 35584, 71168, 142336, 284672, 569344, 1138688, 2277376, 4554752, 91954, 18398, 36796, 73592, 147184, 294368, 588736, 1177472, 2354944, 479888, 959776, 1919552, 383914, 767828, 1535656, 371312, 742624, 1485248, 297496, 594992, 1189984, 2379968, 4759936, 9519872, 1939744, 3879488, 7758976, 15517952, 313594, 627188, 1254376, 258752, 51754, 1358, 2716, 5432, 1864, 3728, 7456, 14912, 29824, 59648, 119296, 238592, 477184, 954368, 198736, 397472, 794944, 1589888, 3179776, 6359552, 1271914, 2543828, 587656, 1175312, 235624, 471248, 942496, 1884992, 3769984, 7539968, 1579936, 3159872, 6319744, 12639488, 25278976, 5557952, 1111594, 2223188, 4446376, 8892752, 1778554, 355718, 711436, 1422872, 2845744, 5691488, 11382976, 22765952, 4553194, 916388, 1832776, 3665552, 733114, 1466228, 2932456, 5864912, 11729824, 23459648, 46919296, 93838592, 187677184, 375354368, 7578736, 15157472, 3314944, 6629888, 13259776, 26519552, 533914, 167828, 335656, 671312, 1342624, 2685248, 537496, 174992, 349984, 699968, 1399936, 2799872, 5599744, 11199488, 22398976, 44797952, 8959594, 17919188, 35838376, 71676752, 14335354, 286778, 573556, 1147112, 2294224, 4588448, 9176896, 18353792, 3677584, 7355168, 1471336, 2942672, 5885344, 1177688, 2355376, 471752, 94354, 18878, 37756, 75512, 15124, 3248, 6496, 12992, 25984, 51968, 13936, 27872, 55744, 111488, 222976, 445952, 89194, 178388, 356776, 713552, 142714, 285428, 57856, 115712, 231424, 462848, 925696, 1851392, 372784, 745568, 1491136, 2982272, 5964544, 1192988, 2385976, 4771952, 954394, 198788, 397576, 795152, 15934, 31868, 63736, 127472, 254944, 59888, 119776, 239552, 47914, 95828, 191656, 383312, 766624, 1533248, 366496, 732992, 1465984, 2931968, 5863936, 11727872, 23455744, 46911488, 93822976, 187645952, 37529194, 7558388, 15116776, 3233552, 646714, 1293428, 2586856, 5173712, 1347424, 2694848, 5389696, 1779392, 3558784, 7117568, 14235136, 2847272, 5694544, 1138988, 2277976, 4555952, 911194, 1822388, 3644776, 7289552, 1457914, 2915828, 5831656, 11663312, 23326624, 46653248, 9336496, 18672992, 37345984, 74691968, 149383936, 298767872, 597535744, 119571488, 239142976, 478285952, 95657194, 191314388, 382628776, 765257552, 15351514, 37328, 74656, 149312, 298624, 597248, 1194496, 2388992, 4777984, 9555968, 19111936, 38223872, 76447744, 152895488, 3579976, 7159952, 1431994, 2863988, 5727976, 11455952, 2291194, 4582388, 9164776, 18329552, 3665914, 7331828, 14663656, 29327312, 58654624, 11739248, 23478496, 46956992, 93913984, 187827968, 375655936, 751311872, 152623744, 35247488, 7494976, 14989952, 2997994, 5995988, 11991976, 23983952, 4796794, 9593588, 19187176, 38374352, 7674874, 15349748, 3699496, 7398992, 14797984, 29595968, 59191936, 118383872, 236767744, 473535488, 9477976, 18955952, 3791194, 7582388, 15164776, 3329552, 665914, 1331828, 2663656, 5327312, 1654624, 339248, 678496, 1356992, 2713984, 5427968, 1855936, 3711872, 7423744, 14847488, 29694976, 59389952, 11877994, 23755988, 47511976, 9523952, 194794, 389588, 779176, 1558352, 311674, 623348, 1246696, 2493392, 4986784, 9973568, 19947136, 39894272, 79788544, 15957788, 31915576, 63831152, 12766234, 25532468, 5164936, 1329872, 2659744, 5319488, 1638976, 3277952, 655594, 1311188, 2622376, 5244752, 148954, 29798, 59596, 119192, 238384, 476768, 953536, 19772, 39544, 7988, 15976, 31952, 6394, 12788, 25576, 51152, 1234, 2468, 4936, 9872, 19744, 39488, 78976, 157952, 31594, 63188, 126376, 252752, 5554, 1118, 2236, 4472, 8944, 17888, 35776, 71552, 14314, 28628, 57256, 114512, 22924, 45848, 91696, 183392, 366784, 733568, 1467136, 2934272, 5868544, 1173788, 2347576, 4695152, 93934, 187868, 375736, 751472, 152944, 35888, 71776, 143552, 28714, 57428, 114856, 229712, 459424, 918848, 1837696, 3675392, 735784, 1471568, 2943136, 5886272, 11772544, 2354588, 479176, 958352, 191674, 383348, 766696, 1533392, 366784

This sequence is in fact OEIS  A242350:

A242350

Multiply a(n-1) by 2 and drop all 0's where a(0)=1.

Figure 1 shows a graph of the sequence with a logarithmic scale for the y axis.

Figure 1: permalink

It doesn't matter what the starting point, the sequence will cycle sooner or later. If the starting point is 3 then the cycle begins with 479712 at the 207th term and returns to this number on the 387th term. The largest value reached overall is 582,269,952. Figure 2 shows the graph of the sequence using a logarithmic scale for the y axis.

Figure 2: permalink

The pattern in Figure 2 is very similar to that in Figure 1. The removal of zeroes, when they occur, brings the size of the number down, often drastically. The logarithmic scale gives a false sense of the magnitude of these ups and downs. Figure 3 shows the data without the logarithmic scale for the starting value of 3.

Figure 3: permalink

The same thing can be done with the Fibonacci sequence and again a cycle is reached. The 26th term is 7841 and this number is reached again at the 434th term. I won't list all the terms, just those up to 7841 (permalink):

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 61, 438, 499, 937, 1436, 2373, 389, 2762, 3151, 5913, 964, 6877, 7841, ...

Notice how 233 + 377 = 610 --> 61 and 3151 + 5913 = 9064 --> 964 in the sequence above.

These numbers form OEIS A243063:

A243063

Numbers generated by a Fibonacci-like sequence in which zeros are suppressed.

Another example is provided by OEIS A256227:

A256227

Naught-y numbers (A011540) that after removing all zeros become zeroless primes (A038618).

The initial members of the sequence (up to 1000) are (permalink):

20, 30, 50, 70, 101, 103, 107, 109, 110, 130, 170, 190, 200, 203, 209, 230, 290, 300, 301, 307, 310, 370, 401, 403, 407, 410, 430, 470, 500, 503, 509, 530, 590, 601, 607, 610, 670, 700, 701, 703, 709, 710, 730, 790, 803, 809, 830, 890, 907, 970

This sequence of course is infinite. Up to one million, there are 45304 terms or about 4.5% of the numbers in the range. That's enough for the time being.

An Interesting Iteration

Having turned 26506 days old today, my attention was drawn to this OEIS sequence:

A219960

Numbers which do not reach zero under the repeated iteration \(x \rightarrow \lceil \sqrt{x} \, \rceil \times  (\lceil \sqrt{x}\, \rceil ^2 - x) \).

Figure 1 shows that 26506 is the 511th such number and thus the frequency of such numbers is about 1.93%.

Figure 1

The first members of this sequence are as follows:

366, 680, 691, 1026, 1136, 1298, 1323, 1417, 1464, 1583, 1604, 1702, 2079, 2125, 2222, 2223, 2374, 2507, 2604, 2627, 2821, 2844, 2897, 3152, 3157, 3159, 3183, 3210, 3231, 3459, 3697, 3715, 3762, 3802, 3866, 3888, 3936, 3948, 4004, 4111, 4133, 4145, 4231, 4299, ...

Here is a permalink to the algorithm on SageMathCell that will return all members of OEIS A219960 up to and including 26506. 

The OEIS comments include the following conjectures:

• Conjecture 1: All numbers under the iteration reach 0 or, like the elements of this sequence, reach a finite loop, and none expand indefinitely to infinity. 

• Conjecture 2: There are an infinite number of such finite loops, though there is often significant distance between them. 

• Conjecture 3: There are an infinite number of pairs of consecutive integers in this sequence despite being less abundant than in A219303.

OEIS A219303 refers to the iterative process where the ceiling function is replaced by the floor function. So what happens to 26506 under this iteration? Here is the trajectory:

26506, 10269, 13770, 18172, 7155, 5950, 10452, 16171, 27264, 48472, 81549, 70642, 30324, 52675, 51750, 53352, 2079, 1702, 2604, 5200, 9417, 18326, 23120, 44217, 64144, 94488, 115808, 161293, 125022, 104076, 81719, 22022, 26671, 36900, 67357, 63180, 81648, 42328, 22248, 37800, 43875, 47250, 59732, 71785, 10452

As can be seen, after five steps a loop of length 38 is entered with a length of 43 steps overall. Figure 2 shows this trajectory using a log scale for the vertical axis.

Figure 2

Up to 26506, the trajectory of maximum length is associated with the number 25923 that has a trajectory of length 86 and ends in 0:

25923, 52002, 100531, 188574, 283185, 481832, 829135, 716046, 1154461, 1251300, 963459, 849430, 602988, 575757, 245916, 49600, 28767, 22610, 28841, 10030, 17271, 20196, 36179, 57682, 96159, 174782, 326401, 447876, 686080, 962469, 1821610, 1201500, 2094173, 3664888, 4475355, 4445716, 4565985, 1675408, 2094015, 3893672, 5929896, 10231200, 7680799, 8828820, 11781008, 15383273, 26111488, 3127320, 3610529, 6220072, 12357735, 15895836, 1327671, 2003914, 1617072, 1160064, 2177560, 1499616, 1236025, 577128, 358720, 48519, 71162, 33909, 58460, 25168, 17967, 34830, 25993, 40662, 28684, 36720, 27648, 40247, 30954, 3872, 6111, 10270, 13668, 2457, 2150, 2773, 1908, 1232, 2304, 0

Figure 3 shows the trajectory of 25923 using a log scale for the vertical axis.

Figure 3

Figure 4 shows the distribution of trajectory lengths between 1 and 26506. All square numbers immediately become zero under the iteration. Using 25 as an example, we get:

\( \lceil \sqrt{25} \rceil \times ( \lceil \sqrt{25} \, \rceil ^2 - 25) = 5 \times (25 - 25) = 5 \times 0 = 0 \)

Figure 4

So far only the numbers up to and including 26506 have been examined because the algorithm is processor intensive. However, if we search from 26507 to 50000, we find that the record length increases slightly to 91, again ending in 0. Here is the record length attained by 35727:

35727, 70870, 111873, 117920, 143104, 203523, 353012, 602735, 772338, 266337, 492184, 435240, 237600, 265472, 404544, 780325, 999804, 196000, 110307, 193806, 297675, 240786, 144845, 120396, 4511, 7684, 5280, 3577, 1380, 2432, 3400, 4779, 8470, 16647, 32890, 42588, 54027, 61046, 113584, 223080, 306977, 581640, 403627, 552684, 633888, 1052837, 1943084, 211888, 291813, 469588, 691488, 612352, 577071, 402040, 752475, 823732, 664656, 979200, 891000, 128384, 178423, 214038, 153253, 161112, 197784, 107245, 111192, 121576, 78525, 122516, 240435, 317186, 513240, 608733, 959068, 1305360, 1244727, 813564, 36080, 3800, 2728, 4293, 4158, 4355, 66, 135, 108, 143, 12, 16, 0

Here is the permalink for this calculation. Note that the penultimate number in the trajectory is 16 which is a square number (\(4^2\)), just as the penultimate number for the previous record trajectory was 2304, also a square number (\(48^2\)). Clearly, it is only when a square number is reached in the trajectory that a result of zero will arise in the next iteration. However, in the case of over 98% of numbers (at least in the range up to 26506), the trajectory does not terminate at zero but instead enters a loop.

Conjecture 3, included earlier, states that "there are an infinite number of pairs of consecutive integers" so let's investigate this further. In the range up to 26506, the following pairs occur:

• 2222 2223 
• 8399 8400 
• 11457 11458 
• 12950 12951 
• 19005 19006 
• 19847 19848 
• 22444 22445 
• 23597 23598 
• 25089 25090 
• 25175 25176 
• 25742 25743 

So eleven pairs in that range shows that pairs of such numbers are not that common and of course there's no way to confirm that there are an infinite number of them.