The sequence in question is A296768 in the Online Encyclopedia. It starts with 1, 3, 5, 9, 11, 17, 24, 32, 36, 46, ... It is obtained by starting with the positive integers in order, (b(i)= i for all positive integers i),and permuting them again and again. On the k-th pass, we exchange b(k+1) with b(b(k+1) + b(k)). The sequence is the limit of these sequences as k goes to infinity. Is it true that the number 2 gets carried off to infinity, and does not appear in the final sequence? This seems to be the case, based on the first 67 values. More generally, is it true that this sequence is increasing? If it is increasing, what is its growth rate?
$\begingroup$
$\endgroup$
4
-
4$\begingroup$ Link: oeis.org/A296768 Author of the sequence was ... David S. Newman. $\endgroup$– Gerry MyersonCommented Aug 2, 2020 at 23:36
-
1$\begingroup$ I believe a proof by induction exists that the sequence is increasing and that its growth is roughly quadratic. Once you can prove it is increasing the analysis should be straight forward. I think the key is to prove that when looking at moving b(k+1) that b(k) holds "the largest number moved so far", and that b(k+1) will thus be at most b(k)+k+1, and sometimes less. Gerhard "One Swap At A Time" Paseman, 2020.08.03. $\endgroup$– Gerhard PasemanCommented Aug 4, 2020 at 3:12
-
$\begingroup$ Further, subtracting your sequence from the triangular sequence gives 0,0,1,1,1+3,1+3,1+3,1+3,1+3+5,..., which if you can prove this continues and how, may lead to a quickly estimated asymptotic. Gerhard "Good Luck With The Pattern" Paseman, 2020.08.03. $\endgroup$– Gerhard PasemanCommented Aug 4, 2020 at 3:18
-
$\begingroup$ And if I am right about that, one gets something like b(n) stabilizes to n(n+1)/2 - O(n^{3/2}). Gerhard "Check My Lack Of Work" Paseman, 2020.08.03. $\endgroup$– Gerhard PasemanCommented Aug 4, 2020 at 3:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Consider the following set of conditions. Before one swaps $b(k+1)$,
- $b(i)$ is an increasing with $i$ sequence for $i$ less than $k+1$. (And for large enough $k$, $b(k)$ is greater than $k$.)
- For $i$ larger than $k$, $b(i)$ is at most $i$.
- $b(i)$ is less than $i$ exactly when $i$ is greater than $k$ and $i$ is part of the increasing sequence ($i$ is one of $b(1)$ or $b(2)$ or ... or $b(k)$).
Thus $b(k+1)$ is a value at most $k+1$ which gets swapped with the value $b(k)+b(k+1)=b(b(k)+b(k+1))$. We see the conditions 1,2, and 3 hold for $k+1$ in place of $k$ after the swap.
As a result, $b(k)$ stabilizes into an increasing sequence. It seems to be the case that the $k$th triangular number $T(k)=b(k)+b(1)+b(2)+\cdots+b(j)$ with $b(j)$ largest value less than or equal to $k$, or something close to that. If this is true, then $b(k)$ grows like $k(k+1)/2$ minus a term like $O(k^{3/2})$.
Edit 2020.08.05
Here is an alternate definition of the sequence. Define $pr(k)$ to be $b(i)$ when $k$ equals $b(i+1)$, otherwise $pr(k)$ is 0. Then $$b(k+1)=b(k)+k+1-pr(k+1).$$
Of course $i$ is positive and $b(1)=1$, or define $b(0)$ to be 0 to take one step back.
End Edit 2020.08.05.
Gerhard "Maybe Like K Power Phi?" Paseman, 2020.08.03.
answered Aug 4, 2020 at 5:27
-
$\begingroup$ As we swap b(k+1), the stable version is b(k+1)=b(k)+old version of b(k+1), where the old version is either k+1=b(k+1), or it is some smaller value j=b(k+1) where k+1-j = b(i) for some relatively small i. The difference T(k+1)-stable b(k+1)=b(1)+...+b(i) with all these terms b(j) strictly smaller than k+1 is k to some fractional power, but I don't know whether the power is like 3/2. Gerhard "It Could Be Like Phi" Paseman, 2020.08.04. $\endgroup$ Commented Aug 4, 2020 at 14:54
-
$\begingroup$ I just noticed this. Let b(0) be 0, and take the definition above. Then pr(1) is used to define b(1) but depends on b(1). So better not to take a step back. To be safe, define b(2)=3 as well, then start using the definition using pr. Gerhard "Should Comprehend What I Write" Paseman, 2020.08.07. $\endgroup$ Commented Aug 7, 2020 at 18:57