About a mysterious sequence who seems to follow some patterns

Solution 1:

I'm answering a heuristic question, so I won't go out of my way to be too precise. Roughly speaking, the explosions you are looking at have to do with the continued fraction of $\log3 / \log2$.

You're looking for the pair $(a,b)$ with minimal $a$ such that $n \leq 2^a / 3^b < n+1$. Taking logs of everything, we want $\log(n) \leq a \log 2 - b \log 3 < \log(n+1).$ There's no particular reason to restrict this to the integers; we can reparametrize with $x = \log n$ and substitute to get the inequality $x \leq a \log 2 - b \log 3 < x + \log(1 + e^{-x})$. Let's write $\varepsilon(x) = \log(1 + e^{-x})$; note that $\varepsilon(x)$ is very close to $e^{-x} = 1/n$.

So we're interested in what numbers of the form $a \log2 + b \log3$ fall into the moving and rapidly narrowing interval between $x$ and $x + \varepsilon(x)$. Some of the effects you're observing are due to the fact that the window is moving, some are due to the fact that it's narrowing, and some are due to the fact that you only plot the result when $e^x$ is an integer. If you want to isolate some of these behaviors you could, say, let the window slide continuously without narrowing.

The explosions are due to the fact that the window is narrowing. They correspond to rapid increases in the answer to the following question: given $x$, how big do we need to let $a$ to be, in order for all gaps between the values of $a\log2 + b\log3$ to be smaller $\varepsilon(x)$?

We care about size of the biggest gaps in the set $S_A = \{a\log2 + b\log3 ; a, b \in \mathbb Z, 0 \leq a < A\}$. This set is periodic with period $\log 3$, so we might as well mod out by multiples of $\log 3$: Letting $\alpha = \log3 / \log2$, we're looking a circle of circumference $\log 3$, and the subset $\widetilde S_A$ of that circle consisting of a point, the rotation of that point by $\alpha^{-1}$ of a full rotation, by $2\alpha^{-1}$ of a full rotation, and so on up until $(A-1)\alpha^{-1}$ of a full rotation. Specifically, we care how the size of the biggest gap between points of $\widetilde S_A$ depends on $A$. This displays the sort of 'jumpy' behavior where one thing happens for a while until another thing starts happening, and so on.

At first, the size of the biggest gap shrinks down from $1$ by $\alpha^{-1}$ of a full circle each time you increase $A$ by 1. But eventually at step $A_1 = \lfloor \alpha \rfloor$ you wrap around and the smallest gaps begin shrinking by $1-A_1/\alpha$ full rotations instead, and it takes $A_1$ steps to shrink them all. Eventually you suffer another slowdown, and another, and so on. Note that if $\alpha$ were rational then eventually you would end up right back where you started, and the gaps would stop shrinking entirely.

You suffer a severe slowdown when you happen to hit a particularly good rational approximation $A/B$ of $\alpha$; a convergent of the continued fraction of $\alpha$. At a time like that, making $A$ rotations by $\alpha^{-1}$ brings you particularly close to an integer number $B$ full rotations around the circle, and the rate at which our gaps shrink drops to an amount of $A\alpha^{-1} - B$ full rotations every $A$ steps, and that's how big the largest gaps will be at the next slowdown.

For example in our case 1054 rotations by $\alpha^{-1}$ brings you unusually close to 665 full rotations around the circle, within $1054\alpha^{-1} - 665$ of the starting point, i.e. a distance of $s = |1054\log2 - 665\log 3| \approx 1/23000$. At this time the big gaps in $\widetilde S_A$ have size corresponding to the previous convergent: $|485\log 2 - 306\log 3| \approx 1/1000$. To actually cover the circle with gaps as short as $s$, we need to wait until we reach the next good rational approximation of $\alpha$, which is $24727/15601$. So for values of $A$ between 1054 and 24727, the biggest gap in $\widetilde S_A$ shrinks down roughly linearly from around 1/1000 to 1/23000.

That means that while $\varepsilon(x)$ remains above 1/1000 or so, the set $S_{1054}$ has elements in every interval of length $\varepsilon(x)$, and in particular, you can always find an $a$ between 0 and 1054 for which $x \leq a \log2 - b\log3 < x + \varepsilon(x)$. But as $\varepsilon(x)$ gets below 1/1000, you fairly quickly start to need larger values of $a$. By the time $\varepsilon(x)$ is as small as 1/2000 or so, $A$ needs to be halfway between 1054 and 24727 to ensure no gaps in $S_A$ of size above $\varepsilon(x)$. So you experience a rapid jump in how big $a$ needs to be when $\varepsilon(x)$ is around 1/1000, i.e. when $n$ is around 1000. When $n$ is smaller values of $a$ less than 1054 suffice, so you have $a + b = p(n)$ less than around 1700. When $n$ is larger, you rapidly start to need bigger values of $a$, giving you bigger values of $p(n)$.

More generally, if $A/B$ is a convergent of the continued fraction of $\log3 / \log2$, then you experience this explosion when $\varepsilon(x)$ gets as small as $A \log2 - B\log3$, i.e. around $n = |A \log2 - B \log 3|^{-1}$. The convergent 485/306 leads us to expect an explosion when $n$ is around 1000, and the next convergent 1054/665 leads us to expect one when $n$ is around 23000. The next explosion, corresponding to the convergent 24727/15601, will occur when $n$ is around 55000.

Heuristically, the upper bound you're looking for is one where $p$ is a piecewise linear function of $1/n$, interpolating between the explosions. Particularly big explosions will occur when you have particularly good rational approximations of $\alpha$, i.e. when you have particularly large terms in the continued fraction. The limiting case of this is when $\alpha$ turns out to be rational, in which case $p$ won't even be well-defined past a certain point. (Though of course you'd need numbers other than 2 and 3 in the definition to see this happen.)