Thursday, 28 October 2021

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.

No comments:

Post a Comment