43
$\begingroup$

Let $x_{n} \in \mathbb Z$ be the $n$-th term of the recurrence relation

$$ x_{n+1} = \frac{x_{n} + x_{n-1}}{(x_{n},x_{n-1})} + 1$$

where $(x_{n},x_{n-1})$ is the gcd of $x_{n}$ and $x_{n-1}$.

Some examples:

  • $1, 1, 3, 5, 9, 15, 9, 9, 3, 5, 9, 15,\dots \qquad $ (periodic sequence)

  • $1, 12, 14, 14, 3, 18, 8, 14, 12, 14, 14, 3, \dots \qquad$ (periodic sequence)

  • $3, 1, 5, 7, 13, 21, 35, 9, 45, 7, 53, 61, 115, 177, 293, 471, 765, 413, \dots \qquad$ (not periodic?)

If $x_{0}$ is even or $x_{1}$ is even, the sequence seems to be always periodic: how to prove it?

More difficult, I suppose, is to predict the character of the sequence (periodic or not periodic), given its initial values $x_{0}$ and $x_{1}$.


Addendum

The recurrence relation

$$ x_{n+1} = \frac{x_{n} + x_{n-1}}{(x_{n},x_{n-1})} + 3$$

admits the following periodic sequence (period equal to 81):

$2, 5, 10, 6, 11, 20, 34, 30, 35, 16, 54, 38, 49, 90, 142, 119, 264, 386, 328, 360, 89, 452, 544, 252, 202, 230, 219, 452, 674, 566, 623, 1192, 1818, 1508, 1666, 1590, 1631, 3224, 4858, 4044, 4454, 4252, 4356, 2155, 6514, 8672, 7596, 4070, 5836, 4956, 2701, 7660, 10364, 4509, 14876, 19388, 8569, 27960, 36532, 16126, 26332, 21232, 11894, 16566, 14233, 30802, 45038, 37923, 82964, 120890, 14564, 6160, 474, 3320, 1900, 264, 544, 104, 84, 50, 70, 15, 20, 10, 6, 11, 20, \dots$

enter image description here

The recurrence relation

$$ x_{n+1} = \frac{x_{n} + x_{n-1}}{(x_{n},x_{n-1})} + 17$$

with $x_0=1$ and $x_1=4$ produces the following periodic sequence (period equal to 422):

enter image description here

The recurrence relation

$$ x_{n+1} = \frac{x_{n} + x_{n-1}}{(x_{n},x_{n-1})} + 199$$

with $x_0=1$ and $x_1=2$ produces the following periodic sequence (period equal to 2920):

enter image description here


I made some numerical experiments. The following screenshots show some of the obtained results.

Each image consists of a 20x20 matrix $T(c)$, depending on the value of $c$, in which

  • $x_0$ is the row index;
  • $x_1$ is the column index;
  • $t_{\,x_0,\,x_1}(c)$ represents the period of the sequence generated by the recurrence relation starting with the initial conditions $x_0,\,x_1$ (the symbol "+" stands for a not periodic sequence that diverges).

Results for $\,c=1$:

enter image description here

Results for $\,c=2$:

enter image description here

Results for $\,c=3$:

enter image description here

Results for $\,c=4$:

enter image description here

Results for $\,c=5$:

enter image description here

Here it seems that we have only two possible periods: one of lenght 17, the other of lenght 63. Notice that if we focus on the sequences of period equal to 17 and plot them for the following initial values $(x_0,x_1)=(2,2),\,(3,8),\,(7,12)$, we obtain the same "wave form"!

enter image description here

enter image description here

enter image description here

I conjecture that this fact is always true.

The wave form for the period of lenght 63 is completely different:

  • for $(x_0,x_1)=(3,10)$ we have

enter image description here

  • for $(x_0,x_1)=(13,6)$ we have

enter image description here

Results for $\,c=6$:

enter image description here

Results for $\,c=7$:

enter image description here

Results for $\,c=8$:

enter image description here

Results for $\,c=9$:

enter image description here

Results for $\,c=10$:

enter image description here

Results for $\,c=11$:

enter image description here

Results for $\,c=13$:

enter image description here

Results for $\,c=15$:

enter image description here

Results for $\,c=17$:

enter image description here

Results for $\,c=19$:

enter image description here

$\endgroup$
8
  • 1
    $\begingroup$ Where does this recursion come from ? $\endgroup$ Dec 29, 2021 at 19:56
  • $\begingroup$ I haven't found anything about it yet ... just personal curiosity. $\endgroup$ Dec 29, 2021 at 20:06
  • 3
    $\begingroup$ It’s always interesting how and why people come up with such non-trivial problems by “just curiosity”. $\endgroup$ Dec 29, 2021 at 20:22
  • $\begingroup$ If one term is even, then there cannot be two successive odd terms, and in every four terms, there are at least two successive even terms. This means that, heuristically, the sequence cannot grow very fast, given that the $\gcd$ randomly decreases it. It is then likely that the sequence becomes periodic. $\endgroup$
    – WhatsUp
    Dec 30, 2021 at 2:54
  • $\begingroup$ @Augusto Santi +1 Very interesting extension of the Fibonacci recurrence $\endgroup$ Jan 6 at 11:15

1 Answer 1

11
+50
$\begingroup$

Alright, I finally managed to "prove" the case when at least one of $x_0$ and $x_1$ is even and you add an odd integer after the division. I say "prove" as this is really a heuristic argument but it is still pretty interesting nonetheless and might illuminate a way forward.

Define the sequence

$$x_{n+2}=\frac{x_{n+1}+x_n}{\gcd(x_{n+1},x_n)}+s$$

where at least one of $x_0$ and $x_1$ is even and $s$ is odd. It is obvious that to prove that the sequence is periodic it is sufficient to show that it is bounded as there are only a finite number of pairs $(x_{n+1},x_n)$ that define the term $x_{n+2}$. Starting with a pair of integers with parity $(E,O)$ (that is, $x_n$ is even and $x_{n+1}$ is odd) it is easy to show by induction that

$$(E,O)\to (O,E)\to (E,E)$$

That is, we get that both $x_{n+2}$ and $x_{n+3}$ is even. But what about $x_{n+4}$? At this point, we have $x_{n+4}$ is odd if $x_{n+3}=2^qa$ and $x_{n+2}=2^qb$ for some odd $a$ and $b$. Otherwise, $x_{n+4}$ will be even. Thus $(E,E)\to (E,O)$ or $(E,E)\to (E,E)$. At this point, this is all I can concretely say about this problem and now move to the heuristics.

Quick Definition: As an aside, from here on out when I say "the probability" that an integer has a certain property $\chi$ I mean

$$P(\chi)=\lim_{n\to\infty}\frac{\left|\{z\in\{1,2,...,n\}:z\text{ has property }\chi\}\right|}{n}$$

Heuristic $1$: What is the probability that $(E,E)\to (E,O)$ versus $(E,E)\to (E,E)$. Well, for to large even integers $x=2^pa$ and $y=2^qb$ (WLOG assume $p\geq q$) we have

$$\frac{x+y}{\gcd(x,y)}+s=\frac{2^{p-q}a+b}{\gcd(a,b)}+s$$

This sum is odd if and only if $2^{p-q}a$ is odd. But for large integers, the probability that a number is odd is $\frac12$. Thus, the probability that $(E,E)\to (E,O)$ versus $(E,E)$ is $\%50$. Now, a quick discussion on why this is an acceptable heuristic. Basically, in order to show that the sequence is bounded it is better if $(E,E)$ leads to $(E,E)$ versus $(E,O)$. In fact, just looking at some randomly generated data it appears that $(E,E)\to (E,E)$ more frequently than not. However, this is fine as the $\frac12$ mark can really just be thought of as an upper bound (even if we had to hand wave to get it). If it isn't quite the correct number, I feel confident that it is an upper bound since we didn't take into account any structure of the problem when considering if $2^{p-q}a$ (from above) was odd or not.

Heuristic $2$: What is the expected value of the $x_{n+2}$ if $(x_n,x_{n+1})=(E,E)$? From here we can say that the probability that two numbers $x$ and $y$ have a specific greatest common divisor $k$ is

$$P(\gcd(x,y)=k)=\frac{1}{k^2\zeta(2)}$$

Thus, the expected value of $\frac{x_{n+2}}{\max(x_n,x_{n+1})}$ is

$$E(x_{n+2})\leq 2\sum_{n=1}^\infty \frac{P(\gcd(x_n,x_{n+1})=2n)}{2n}=\frac{2}{\zeta(2)}\sum_{n=1}^\infty \frac{1}{(2n)^3}=\frac{\zeta(3)}{4\zeta(2)}$$

Call this value $E(E)$.

Heuristic $3$: What is the expected value of the $\frac{x_{n+2}}{\max(x_n,x_{n+1})}$ if $(x_n,x_{n+1})=(E,O)$ or $(O,E)$? In the same manner as above, we have

$$E(x_{n+2})\leq 2\sum_{n=1}^\infty \frac{P(\gcd(x_n,x_{n+1})=2n-1)}{2n-1}=\frac{2}{\zeta(2)}\sum_{n=1}^\infty \frac{1}{(2n-1)^3}=\frac{7\zeta(3)}{4\zeta(2)}$$

Call this value $E(O)$.

Heuristic $4$: Using Heuristic $1$ above, we know that half the time our sequence would trace the following

$$(E,E)\to (E,O)\to (O,E)\to (E,E)$$

If we start at $x_n$ and $x_{n+1}$, then the expected value of of the sequence member divided by $\max(x_n,x_{n+1})$ the next time we hit $(E,E)$ (denoted by $x_t$) is bounded by

$$E(x_{t}|(E,O))\leq E(E)E(O)^2$$

On the other hand, if $(E,E)\to (E,E)$ then we have $E(x_{t}|(E,E))=E(E)$. Putting these together gives us

$$E(x_t)=\frac{E(x_{t}|(E,O))+E(x_{t}|(E,E))}{2}$$

$$=\frac{1}{8}\left(\frac{49}{16}\cdot\left(\frac{\zeta(3)}{\zeta(2)}\right)^3+\frac{\zeta(3)}{\zeta(2)}\right)<\frac{1}{4}$$

Basically, by the time $(E,E)$ shows up again, we would expect the sequence member to be on average a quarter the size.

Addendum: As an addendum, here is a discussion on why this method would not work for the starting case $(O,O)$. In this case, it is obvious that we simply go $(O,O)\to (O,O)$. But then we would have

$$E(x_t)=E(O)=\frac{7\zeta(3)}{4\zeta(2)}=1.27>1$$

Thus, for large integers on average you would expect the sequence to increase in size. Again, this isn't a proof and there clearly are cases where all odd sequences can be periodic. However, it seems much more random to try to show when these cases arise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.