Skip to main content
MathOverflow

Return to Answer

added 53 characters in body
Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Here is one observation, probably not new, which yielded a trajectory of length $64$ given at the end. It seems to be (one of the features) behind the known records.

The last numbers listed in A6538 are $10533599=2^53^25^2\ 7\ 11\ 19-1$ and $10616759=2^33^2\ 5\ 7\ 11\ 383-1$ for trajectories of lengths $56$ and $57$

The value mentioned as sufficient for length $58$ is $58017959=2^33^2\ 5\ 7^2\ 11\ 13 \ 23-1$

It is promising to have $a+1$ divisible by the least common multiple of the first few integers. Then $a \bmod b=b-1$ whenever $b$ divides $a+1.$

For example $N=2^53^35^27\ 11\ 13=21621600$ is divisible by all the integers up to $16$ so for $a=N-1=21621599$ a trajectory which arrives at $16$ will finish $15,14,13,12,11,10,9,8,7,6,5,4,3,2,1.$ Actually that wouldn't be optimal since $a-16=83\cdot 337\cdot 773$ so the preceding value would have to be a divisor of that number.

In fact the longest trajectories for that value of $a$ are $50$ iterations which is good but not a record. One can start at any one of $13122281, 13204151, 15955387, 16009967$ or $13780004.$ For the first four of those the trajectory ends

$346751, 123037, 90124, 81963, 65330, 62699, 53143, 45541, 35165, 30289, 25542, 13067, 8781, 2777, 2654, 2115, 2069, 549, 332, \mathbf{99, 98,\ 55, 54, 53}, 37, \mathbf{20, 19}, 17,\mathbf{ 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}$ Where the transitions in boldface from $b$ to $b-1$ are explained by the fact that the $b$ are divisors of $a+1.$ The last starting value ends the same way starting at $99$ but arrives there

$338777,278648,165703,80209,45378,21671,15612,14591,12328,10615,9459,7784,5431,788,\mathbf{455,454},303,125$

The smallest $a$ allowing a trajectory of length $50$ is $131719=2^33\ 5\ 7\ 23\ 71-1$ The trajectory starting at $831180$ ends $\mathbf{71, 70, 69, 68},\ \mathbf{23, 22}, 19, \mathbf{14, 13}, 11,\mathbf{ 8, 7, 6, 5, 4, 3, 2, 1}.$

So you might reasonably wonder why I bothered with $21621599$ which is almost $16$ times as large as $131719.$

Taking instead $a=t\cdot 21621600-1$ will allow the same values with $b \mapsto b-1$ and some others. One might expect $t=17$ but it turns out to be better to use $a=19\cdot 21621600-1=410810399$ then any one of the starting values $247845109, 258990746, 261971136, 263955764$ allow $64$ iterations with a trajectory ending $37, \mathbf{28, 27, 26, 25, 24, 23}, \ \mathbf{16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}$

The part getting to $37$ is $1561, \mathbf{468, 467}, 306, 197, 192, \mathbf{95, 94}, 37$ for the first, $1499,\mathbf{455,454},327,299,246,239,230,\mathbf{39,38,37}$ for the next two and $\mathbf{1824, 1823}, 995, 769, 602, 181, 129, \mathbf{95, 94}, 37$ for the last one.

The actual exploring (which was far from optimal) that got to that length $64$ example was slightly different. It started (after a number of similar tries) with $1965600=2^5\ 3^3\ 5^2\ 7 \ 13$ then

$a=t\cdot 1965600-1$ would allow $28,27,26,25,24$ along with $16,15,14$ and $10,9,\cdots ,3,2,1$ and it turns out (after trying $t=1,2,3,4$ ) that $5\cdot 1965600-1=9827999$ allows $17,10,9,\cdots,1$

Then , in an attempt to have $18,17,10,\cdots$, I tried values $a=t\cdot 17 \cdot 1965600+ 9827999$ to find one with a small divisor for $a-18.$ It turned out that $t=2$ allowed $31$ , $t=4$ allowed $29$, $t=7$ allowed $23$ and also $41.$ finally $t=12$ allows $19,18,10,9,\cdots$ The best trajectories in those four cases are of length $52,49,54$ and $64$ respectively.

In fact that was a very inefficient way to arrive at that $a,$ The divisors $11,13$ for $a+1$ showed butup, but not by design.

It is known that the least common multiple of the first $n$ integers (a function which changes only when $n$ is a prime or prime power) grows like $e^n$ so the fact that $P(a,b)$ can sometimes be as large as $\ln{a}$ follows from taking $b_1=n$ and $a=\mathop{lcm}(2,3,\cdots,n)-1.$ And it is likely that one can do better for that $a$ starting with a well chosen $b$ that eventually arrives at $n$ or a bit below it. And $a=t \cdot \mathop{lcm}(2,3,\cdots,n)-1$ might be even better.

Here is one observation, probably not new, which yielded a trajectory of length $64$ given at the end. It seems to be (one of the features) behind the known records.

The last numbers listed in A6538 are $10533599=2^53^25^2\ 7\ 11\ 19-1$ and $10616759=2^33^2\ 5\ 7\ 11\ 383-1$ for trajectories of lengths $56$ and $57$

The value mentioned as sufficient for length $58$ is $58017959=2^33^2\ 5\ 7^2\ 11\ 13 \ 23-1$

It is promising to have $a+1$ divisible by the least common multiple of the first few integers. Then $a \bmod b=b-1$ whenever $b$ divides $a+1.$

For example $N=2^53^35^27\ 11\ 13=21621600$ is divisible by all the integers up to $16$ so for $a=N-1=21621599$ a trajectory which arrives at $16$ will finish $15,14,13,12,11,10,9,8,7,6,5,4,3,2,1.$ Actually that wouldn't be optimal since $a-16=83\cdot 337\cdot 773$ so the preceding value would have to be a divisor of that number.

In fact the longest trajectories for that value of $a$ are $50$ iterations which is good but not a record. One can start at any one of $13122281, 13204151, 15955387, 16009967$ or $13780004.$ For the first four of those the trajectory ends

$346751, 123037, 90124, 81963, 65330, 62699, 53143, 45541, 35165, 30289, 25542, 13067, 8781, 2777, 2654, 2115, 2069, 549, 332, \mathbf{99, 98,\ 55, 54, 53}, 37, \mathbf{20, 19}, 17,\mathbf{ 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}$ Where the transitions in boldface from $b$ to $b-1$ are explained by the fact that the $b$ are divisors of $a+1.$ The last starting value ends the same way starting at $99$ but arrives there

$338777,278648,165703,80209,45378,21671,15612,14591,12328,10615,9459,7784,5431,788,\mathbf{455,454},303,125$

The smallest $a$ allowing a trajectory of length $50$ is $131719=2^33\ 5\ 7\ 23\ 71-1$ The trajectory starting at $831180$ ends $\mathbf{71, 70, 69, 68},\ \mathbf{23, 22}, 19, \mathbf{14, 13}, 11,\mathbf{ 8, 7, 6, 5, 4, 3, 2, 1}.$

So you might reasonably wonder why I bothered with $21621599$ which is almost $16$ times as large as $131719.$

Taking instead $a=t\cdot 21621600-1$ will allow the same values with $b \mapsto b-1$ and some others. One might expect $t=17$ but it turns out to be better to use $a=19\cdot 21621600-1=410810399$ then any one of the starting values $247845109, 258990746, 261971136, 263955764$ allow $64$ iterations with a trajectory ending $37, \mathbf{28, 27, 26, 25, 24, 23}, \ \mathbf{16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}$

The part getting to $37$ is $1561, \mathbf{468, 467}, 306, 197, 192, \mathbf{95, 94}, 37$ for the first, $1499,\mathbf{455,454},327,299,246,239,230,\mathbf{39,38,37}$ for the next two and $\mathbf{1824, 1823}, 995, 769, 602, 181, 129, \mathbf{95, 94}, 37$ for the last one.

The actual exploring (which was far from optimal) that got to that length $64$ example was slightly different. It started (after a number of similar tries) with $1965600=2^5\ 3^3\ 5^2\ 7 \ 13$

$a=t\cdot 1965600-1$ would allow $10,9,\cdots ,3,2,1$ and it turns out (after trying $t=1,2,3,4$ ) that $5\cdot 1965600-1=9827999$ allows $17,10,9,\cdots,1$

Then , in an attempt to have $18,17,10,\cdots$, I tried values $a=t\cdot 17 \cdot 1965600+ 9827999$ to find one with a small divisor for $a-18.$ It turned out that $t=2$ allowed $31$ , $t=4$ allowed $29$, $t=7$ allowed $23$ and also $41.$ finally $t=12$ allows $19,18,10,9,\cdots$ The best trajectories in those four cases are of length $52,49,54$ and $64$ respectively.

In fact that was a very inefficient way to arrive at that $a,$ The divisors $11,13$ for $a+1$ showed but not by design.

It is known that the least common multiple of the first $n$ integers (a function which changes only when $n$ is a prime or prime power) grows like $e^n$ so the fact that $P(a,b)$ can sometimes be as large as $\ln{a}$ follows from taking $b_1=n$ and $a=\mathop{lcm}(2,3,\cdots,n)-1.$ And it is likely that one can do better for that $a$ starting with a well chosen $b$ that eventually arrives at $n$ or a bit below it. And $a=t \cdot \mathop{lcm}(2,3,\cdots,n)-1$ might be even better.

Here is one observation, probably not new, which yielded a trajectory of length $64$ given at the end. It seems to be (one of the features) behind the known records.

The last numbers listed in A6538 are $10533599=2^53^25^2\ 7\ 11\ 19-1$ and $10616759=2^33^2\ 5\ 7\ 11\ 383-1$ for trajectories of lengths $56$ and $57$

The value mentioned as sufficient for length $58$ is $58017959=2^33^2\ 5\ 7^2\ 11\ 13 \ 23-1$

It is promising to have $a+1$ divisible by the least common multiple of the first few integers. Then $a \bmod b=b-1$ whenever $b$ divides $a+1.$

For example $N=2^53^35^27\ 11\ 13=21621600$ is divisible by all the integers up to $16$ so for $a=N-1=21621599$ a trajectory which arrives at $16$ will finish $15,14,13,12,11,10,9,8,7,6,5,4,3,2,1.$ Actually that wouldn't be optimal since $a-16=83\cdot 337\cdot 773$ so the preceding value would have to be a divisor of that number.

In fact the longest trajectories for that value of $a$ are $50$ iterations which is good but not a record. One can start at any one of $13122281, 13204151, 15955387, 16009967$ or $13780004.$ For the first four of those the trajectory ends

$346751, 123037, 90124, 81963, 65330, 62699, 53143, 45541, 35165, 30289, 25542, 13067, 8781, 2777, 2654, 2115, 2069, 549, 332, \mathbf{99, 98,\ 55, 54, 53}, 37, \mathbf{20, 19}, 17,\mathbf{ 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}$ Where the transitions in boldface from $b$ to $b-1$ are explained by the fact that the $b$ are divisors of $a+1.$ The last starting value ends the same way starting at $99$ but arrives there

$338777,278648,165703,80209,45378,21671,15612,14591,12328,10615,9459,7784,5431,788,\mathbf{455,454},303,125$

The smallest $a$ allowing a trajectory of length $50$ is $131719=2^33\ 5\ 7\ 23\ 71-1$ The trajectory starting at $831180$ ends $\mathbf{71, 70, 69, 68},\ \mathbf{23, 22}, 19, \mathbf{14, 13}, 11,\mathbf{ 8, 7, 6, 5, 4, 3, 2, 1}.$

So you might reasonably wonder why I bothered with $21621599$ which is almost $16$ times as large as $131719.$

Taking instead $a=t\cdot 21621600-1$ will allow the same values with $b \mapsto b-1$ and some others. One might expect $t=17$ but it turns out to be better to use $a=19\cdot 21621600-1=410810399$ then any one of the starting values $247845109, 258990746, 261971136, 263955764$ allow $64$ iterations with a trajectory ending $37, \mathbf{28, 27, 26, 25, 24, 23}, \ \mathbf{16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}$

The part getting to $37$ is $1561, \mathbf{468, 467}, 306, 197, 192, \mathbf{95, 94}, 37$ for the first, $1499,\mathbf{455,454},327,299,246,239,230,\mathbf{39,38,37}$ for the next two and $\mathbf{1824, 1823}, 995, 769, 602, 181, 129, \mathbf{95, 94}, 37$ for the last one.

The actual exploring (which was far from optimal) that got to that length $64$ example was slightly different. It started (after a number of similar tries) with $1965600=2^5\ 3^3\ 5^2\ 7 \ 13$ then

$a=t\cdot 1965600-1$ would allow $28,27,26,25,24$ along with $16,15,14$ and $10,9,\cdots ,3,2,1$ and it turns out (after trying $t=1,2,3,4$ ) that $5\cdot 1965600-1=9827999$ allows $17,10,9,\cdots,1$

Then , in an attempt to have $18,17,10,\cdots$, I tried values $a=t\cdot 17 \cdot 1965600+ 9827999$ to find one with a small divisor for $a-18.$ It turned out that $t=2$ allowed $31$ , $t=4$ allowed $29$, $t=7$ allowed $23$ and also $41.$ finally $t=12$ allows $19,18,10,9,\cdots$ The best trajectories in those four cases are of length $52,49,54$ and $64$ respectively.

In fact that was a very inefficient way to arrive at that $a,$ The divisors $11,13$ for $a+1$ showed up, but not by design.

It is known that the least common multiple of the first $n$ integers (a function which changes only when $n$ is a prime or prime power) grows like $e^n$ so the fact that $P(a,b)$ can sometimes be as large as $\ln{a}$ follows from taking $b_1=n$ and $a=\mathop{lcm}(2,3,\cdots,n)-1.$ And it is likely that one can do better for that $a$ starting with a well chosen $b$ that eventually arrives at $n$ or a bit below it. And $a=t \cdot \mathop{lcm}(2,3,\cdots,n)-1$ might be even better.

Source Link
Aaron Meyerowitz
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

Here is one observation, probably not new, which yielded a trajectory of length $64$ given at the end. It seems to be (one of the features) behind the known records.

The last numbers listed in A6538 are $10533599=2^53^25^2\ 7\ 11\ 19-1$ and $10616759=2^33^2\ 5\ 7\ 11\ 383-1$ for trajectories of lengths $56$ and $57$

The value mentioned as sufficient for length $58$ is $58017959=2^33^2\ 5\ 7^2\ 11\ 13 \ 23-1$

It is promising to have $a+1$ divisible by the least common multiple of the first few integers. Then $a \bmod b=b-1$ whenever $b$ divides $a+1.$

For example $N=2^53^35^27\ 11\ 13=21621600$ is divisible by all the integers up to $16$ so for $a=N-1=21621599$ a trajectory which arrives at $16$ will finish $15,14,13,12,11,10,9,8,7,6,5,4,3,2,1.$ Actually that wouldn't be optimal since $a-16=83\cdot 337\cdot 773$ so the preceding value would have to be a divisor of that number.

In fact the longest trajectories for that value of $a$ are $50$ iterations which is good but not a record. One can start at any one of $13122281, 13204151, 15955387, 16009967$ or $13780004.$ For the first four of those the trajectory ends

$346751, 123037, 90124, 81963, 65330, 62699, 53143, 45541, 35165, 30289, 25542, 13067, 8781, 2777, 2654, 2115, 2069, 549, 332, \mathbf{99, 98,\ 55, 54, 53}, 37, \mathbf{20, 19}, 17,\mathbf{ 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}$ Where the transitions in boldface from $b$ to $b-1$ are explained by the fact that the $b$ are divisors of $a+1.$ The last starting value ends the same way starting at $99$ but arrives there

$338777,278648,165703,80209,45378,21671,15612,14591,12328,10615,9459,7784,5431,788,\mathbf{455,454},303,125$

The smallest $a$ allowing a trajectory of length $50$ is $131719=2^33\ 5\ 7\ 23\ 71-1$ The trajectory starting at $831180$ ends $\mathbf{71, 70, 69, 68},\ \mathbf{23, 22}, 19, \mathbf{14, 13}, 11,\mathbf{ 8, 7, 6, 5, 4, 3, 2, 1}.$

So you might reasonably wonder why I bothered with $21621599$ which is almost $16$ times as large as $131719.$

Taking instead $a=t\cdot 21621600-1$ will allow the same values with $b \mapsto b-1$ and some others. One might expect $t=17$ but it turns out to be better to use $a=19\cdot 21621600-1=410810399$ then any one of the starting values $247845109, 258990746, 261971136, 263955764$ allow $64$ iterations with a trajectory ending $37, \mathbf{28, 27, 26, 25, 24, 23}, \ \mathbf{16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}$

The part getting to $37$ is $1561, \mathbf{468, 467}, 306, 197, 192, \mathbf{95, 94}, 37$ for the first, $1499,\mathbf{455,454},327,299,246,239,230,\mathbf{39,38,37}$ for the next two and $\mathbf{1824, 1823}, 995, 769, 602, 181, 129, \mathbf{95, 94}, 37$ for the last one.

The actual exploring (which was far from optimal) that got to that length $64$ example was slightly different. It started (after a number of similar tries) with $1965600=2^5\ 3^3\ 5^2\ 7 \ 13$

$a=t\cdot 1965600-1$ would allow $10,9,\cdots ,3,2,1$ and it turns out (after trying $t=1,2,3,4$ ) that $5\cdot 1965600-1=9827999$ allows $17,10,9,\cdots,1$

Then , in an attempt to have $18,17,10,\cdots$, I tried values $a=t\cdot 17 \cdot 1965600+ 9827999$ to find one with a small divisor for $a-18.$ It turned out that $t=2$ allowed $31$ , $t=4$ allowed $29$, $t=7$ allowed $23$ and also $41.$ finally $t=12$ allows $19,18,10,9,\cdots$ The best trajectories in those four cases are of length $52,49,54$ and $64$ respectively.

In fact that was a very inefficient way to arrive at that $a,$ The divisors $11,13$ for $a+1$ showed but not by design.

It is known that the least common multiple of the first $n$ integers (a function which changes only when $n$ is a prime or prime power) grows like $e^n$ so the fact that $P(a,b)$ can sometimes be as large as $\ln{a}$ follows from taking $b_1=n$ and $a=\mathop{lcm}(2,3,\cdots,n)-1.$ And it is likely that one can do better for that $a$ starting with a well chosen $b$ that eventually arrives at $n$ or a bit below it. And $a=t \cdot \mathop{lcm}(2,3,\cdots,n)-1$ might be even better.