12
$\begingroup$

Let $u_1=u_2=1$ and
$$u_{n}=\frac{u_{n-1}+u_{n-2}+n}{\gcd\left(u_{n-1},u_{n-2},n\right)}$$ Then I suspect that $$\lim_{n\rightarrow\infty}\frac{u_{n+1}}{u_{n}}=\frac{1+\sqrt{5}}{2}$$ which is equivalent to the fact that $\gcd\left(u_{n-1},u_{n-2},n\right)=1$ for $n$ large enough.

It seems that this property holds for any starting integer values $(u_1,u_2)$. Does anyone see how to prove it?

Proof of the equivalence. If $\lim_{n\rightarrow\infty}\frac{u_{n+1}}{u_{n}}=\frac{1+\sqrt{5}}{2}=\phi$ and since we have $\frac{n}{u_{n-1}}\rightarrow0$ then we get

$$\frac{1+\frac{u_{n-2}}{u_{n-1}}+\frac{n}{u_{n-1}}}{\gcd\left(u_{n-1},u_{n-2},n\right)} \sim\frac{1}{\gcd\left(u_{n-1},u_{n-2},n\right)}\left(1+\frac{1}{\varPhi}\right)\sim\varPhi\ \left(n\rightarrow\infty\right)$$

and necessarily we have $\gcd\left(u_{n-1},u_{n-2},n\right)\rightarrow1$. Since it is an integer value it must be $1$ for $n$ large enough.

In the other way if $\gcd\left(u_{n-1},u_{n-2},n\right)=1$ for $n>n_{0}$ then we have for $n>n_{0}$

$$u_{n}=u_{n-1}+u_{n-2}+n$$

and $u_{n}=a\varPhi^{n}+b\varPhi^{-n}+cn+d$ for some constants $(a,b,c,d)$ with $a>0$.

I add that if we replace $n$ with a function $f(n)$ sufficiently regular like $f(n)=n^2$ i.e. $u_{n}=\frac{u_{n-1}+u_{n-2}+f(n)}{\gcd\left(u_{n-1},u_{n-2},f(n)\right)}$ the property seems to persist.

Thank you

ps: here the values of $n$ such that $\gcd\left(u_{n},u_{n-1},n+1\right)>1$ and the corresponding gcd. No gcd>1 after $n=22933$ until $n=10^6$

(5,5),(6,2),(9,3),(12,2),(27,3),(48,3),(69,3),(90,3),(111,3),(135,3),(159,3),(165,3),(171,3),(177,3),(183,3),(204,3),(225,3),(249,3),(270,3),(273,7),(291,3),(300,5),(306,17),(327,3),(333,3),(357,21),(363,3),(369,3),(393,3),(399,3),(420,3),(426,3),(430,5),(447,3),(471,3),(495,3),(519,3),(525,3),(546,3),(570,3),(594,9),(618,3),(624,3),(645,3),(669,3),(690,3),(714,3),(738,3),(744,3),(750,15),(771,3),(777,3),(801,3),(807,3),(820,5),(834,3),(840,3),(864,3),(885,3),(891,3),(897,3),(903,3),(924,3),(945,3),(951,3),(960,5),(972,9),(993,3),(1017,3),(1038,3),(1059,3),(1075,5),(1080,3),(1095,5),(1116,3),(1122,3),(1143,9),(1167,3),(1191,3),(1212,3),(1236,3),(1242,3),(1248,3),(1260,5),(1278,3),(1280,5),(1358,7),(1428,7),(1444,19),(16781,173),(16800,3),(16806,3),(16808,11),(16814,7),(16830,15),(16836,3),(16857,3),(16863,3),(16870,5),(16890,3),(16911,3),(16932,3),(16953,3),(16977,3),(17001,3),(17007,3),(17028,33),(17034,3),(17050,5),(17055,3),(17061,3),(17067,3),(17073,3),(17079,3),(17103,3),(17109,3),(17130,3),(17136,9),(17160,3),(17166,3),(17175,5),(17178,7),(17187,3),(17195,5),(17208,3),(17220,5),(17221,17),(17241,3),(17262,3),(17286,3),(17300,5),(17304,3),(17325,3),(17331,3),(17355,3),(17376,3),(17400,3),(17424,3),(17445,3),(17466,3),(17487,3),(17511,3),(17532,3),(17538,3),(17544,3),(17550,3),(17556,3),(17562,3),(17586,9),(17610,3),(17616,3),(17622,3),(17628,3),(17633,7),(17652,3),(17673,3),(17685,5),(17697,3),(17718,3),(17725,5),(17733,3),(17754,3),(17766,7),(17775,3),(17790,5),(17810,5),(17811,3),(17835,3),(17856,3),(17862,3),(17868,3),(17892,3),(17898,3),(17919,3),(17940,3),(17961,3),(17967,3),(17988,3),(17994,3),(18015,3),(18039,3),(18063,3),(18081,7),(18084,3),(18108,3),(18125,5),(18132,3),(18138,3),(18162,3),(18164,19),(18168,3),(18189,3),(18195,3),(18201,3),(18225,3),(18249,3),(18273,3),(18279,3),(18300,3),(18321,3),(18340,7),(18342,3),(18348,3),(18354,3),(18368,7),(18378,3),(18402,3),(18408,3),(18414,3),(18435,3),(18441,3),(18465,3),(18471,3),(18480,5),(18492,3),(18498,3),(18515,5),(18522,3),(18528,3),(18535,5),(18555,3),(18561,3),(18565,5),(18582,3),(18606,3),(18615,5),(18618,3),(18642,3),(18648,3),(18654,3),(18660,3),(18681,3),(18702,3),(18723,3),(18729,3),(18750,3),(18774,9),(18798,3),(18810,5),(18828,3),(18849,3),(18870,3),(18876,3),(18882,3),(18906,3),(18912,3),(18918,3),(18924,3),(18928,7),(18948,3),(18972,3),(18978,3),(18999,3),(19020,3),(19026,9),(19032,3),(19038,3),(19059,3),(19080,3),(19086,3),(19103,7),(19110,3),(19115,5),(19128,3),(19134,3),(19140,3),(19164,3),(19170,3),(19176,3),(19182,3),(19206,9),(19227,3),(19248,3),(19254,3),(19275,3),(19285,7),(19296,3),(19320,3),(19341,3),(19347,3),(19353,3),(19359,3),(19360,5),(19365,3),(19386,3),(19392,3),(19413,3),(19419,3),(19425,3),(19446,3),(19467,3),(19473,3),(19479,3),(19485,3),(19506,3),(19515,5),(19527,3),(19548,3),(19558,7),(19569,3),(19575,3),(19596,3),(19602,3),(19626,3),(19635,11),(19647,3),(19653,3),(19659,3),(19665,3),(19669,13),(19671,3),(19677,3),(19698,3),(19715,5),(19725,3),(19746,3),(19752,3),(19776,3),(19782,3),(19788,3),(19809,3),(19830,3),(19851,3),(19872,3),(19896,3),(19920,3),(19935,5),(19953,3),(19959,3),(19965,5),(19968,3),(19989,3),(20013,3),(20034,3),(20058,3),(20064,3),(20085,3),(20106,3),(20125,5),(20127,3),(20148,3),(20154,3),(20175,3),(20199,3),(20220,3),(20244,3),(20268,3),(20274,3),(20295,3),(20316,3),(20322,3),(20328,3),(20334,3),(20355,3),(20376,3),(20382,3),(20390,5),(20406,3),(20412,3),(20418,3),(20442,3),(20460,11),(20481,3),(20487,3),(20493,3),(20499,3),(20523,3),(20544,3),(20550,3),(20571,3),(20577,3),(20583,3),(20604,3),(20610,3),(20634,3),(20658,3),(20679,3),(20700,3),(20721,3),(20727,3),(20748,3),(20769,3),(20790,9),(20796,3),(20817,3),(20838,3),(20846,7),(20862,3),(20883,3),(20907,3),(20913,3),(20919,3),(20925,5),(20928,3),(20952,3),(20958,3),(20982,3),(21006,3),(21020,5),(21027,3),(21028,7),(21035,5),(21048,3),(21054,3),(21060,3),(21084,21),(21105,3),(21129,3),(21153,3),(21159,3),(21165,3),(21171,3),(21192,3),(21213,3),(21230,5),(21237,3),(21243,3),(21264,3),(21270,15),(21291,3),(21312,3),(21333,3),(21339,9),(21345,3),(21351,3),(21357,3),(21378,3),(21399,21),(21420,3),(21425,5),(21438,3),(21462,3),(21476,7),(21483,3),(21500,5),(21510,3),(21534,3),(21555,3),(21576,3),(21595,7),(21597,3),(21621,3),(21630,7),(21642,3),(21648,3),(21654,3),(21660,3),(21665,5),(21666,3),(21687,3),(21708,3),(21714,3),(21720,3),(21725,5),(21735,23),(21750,3),(21756,3),(21762,3),(21783,3),(21807,3),(21828,3),(21852,3),(21876,3),(21880,5),(21900,3),(21924,3),(21930,3),(21945,11),(21963,3),(21984,3),(21990,3),(22005,5),(22026,3),(22047,3),(22071,3),(22077,3),(22083,3),(22089,3),(22100,5),(22104,3),(22125,3),(22146,3),(22170,3),(22180,5),(22191,3),(22197,3),(22203,3),(22209,3),(22220,5),(22224,3),(22245,3),(22269,3),(22280,5),(22284,3),(22305,3),(22326,3),(22332,3),(22341,11),(22353,3),(22359,3),(22365,9),(22386,3),(22407,3),(22417,29),(22428,9),(22434,3),(22435,7),(22455,3),(22461,3),(22467,3),(22473,3),(22494,3),(22500,3),(22521,3),(22527,3),(22535,5),(22548,3),(22554,7),(22572,3),(22593,3),(22603,7),(22614,3),(22638,3),(22659,3),(22680,3),(22686,3),(22710,3),(22734,3),(22755,3),(22765,5),(22776,3),(22797,3),(22821,3),(22827,7),(22835,5),(22842,3),(22848,3),(22855,5),(22875,3),(22880,11),(22932,7)

$\endgroup$
5
  • 1
    $\begingroup$ Why did you say that $\lim_{n\rightarrow\infty}\frac{u_{n+1}}{u_{n}}=\frac{1+\sqrt{5}}{2}$ is equivalent to $\gcd\left(u_{n-1},u_{n-2},n\right)=1$ for $n$ large enough $\endgroup$
    – Jane
    Sep 15 at 19:58
  • 2
    $\begingroup$ I put the answer in my question $\endgroup$
    –  Babar
    Sep 16 at 6:03
  • $\begingroup$ Can you give some numerical simulations that consolidate your prediction $\endgroup$
    – Jane
    Sep 16 at 12:49
  • 2
    $\begingroup$ Of course. I added the values of $n$ such that $\gcd\left(u_{n},u_{n-1},n+1\right)>1$ $\endgroup$
    –  Babar
    Sep 16 at 18:17
  • $\begingroup$ We must have $u_{n} = \lambda F_{n} + \mu F_{n+1}-n-3$ for some fixed constants $\lambda, \mu \in \mathbb{Z}$ for sufficiently large $n$ If $\text{gcd}(u_{m-1}, u_{m-2}, m) = 1$ for large $m$. $\endgroup$ Sep 20 at 7:35

1 Answer 1

3
+50
$\begingroup$

The property probably does not hold.

An argument can be made that the property is unlikely to hold. Define $d_n = \gcd(u_{n-1},u_{n-2},n)$, $d_{\infty}=1$ and pick $N$ s.t. $d_{N-1} = 1$. Let $M$ be the smallest integer such that $d_{M} \neq 1, M\geq N$ or $M=+\infty$ if no such integer exists. For $n=N$ define $$a_n = 2 + 3n/2 + u_{n-2} + u_{n-1}/2,\\ b_n = 1 + n/2 + u_{n-1}/2. \tag{1}$$ We assume that the numbers $a_n$ and $b_n$ are integers with even $a_n + b_n$. For $u_1=u_2=1$ this assumption holds starting from $n=14$; if it does not hold, we can check that $2$ will divide $d_n$ within 6 iterations.

For $n>N$ define $a_n$ and $b_n$ by the recursive relation $$\begin{pmatrix}a_{n}\\b_{n}\end{pmatrix} = \frac12 \begin{pmatrix} 1 & 5\\ 1 & 1 \end{pmatrix}\begin{pmatrix}a_{n-1}\\b_{n-1}\end{pmatrix}.\tag{2}$$ It is easy to check that then equations (1) hold for $N \leq n \leq M$ and not only for $n=N$. Define

$$\widetilde{d}_n = \gcd(a_n-2, b_n-1). \tag{3}$$

Lemma 1.

  1. If $p \mid d_M, p\notin \{2\}$ then $p \mid \widetilde{d}_n$,
  2. If $p \mid \widetilde{d}_n, p\notin \{2,5\}$ then $M < \infty$.

Proof. #1 follows from $p\mid n$, $p\mid u_{n-1}$, $p\mid u_{n-2}$ and the formulas (1).

To prove #2 assume the contrary: $M=\infty$. Then (1) hold for all $n\geq N$. Define the field $F$ by $F=\text{GF}(p)$ when $\sqrt{5} \in \text{GF}(p)$ (i.e. when $p\equiv\pm 1 \mod 5$) and $F=\text{GF}(p)[\sqrt{5}]$ otherwise. In both cases $u_{\pm} = \frac{1\pm\sqrt{5}}{2} \in F$. Define $v_{\pm} = \frac{a_{N} \pm b_{N}\sqrt{5}}{2 \pm \sqrt{5}}\in F$. Let $\text{order}(u_{\pm})$ be the multiplicative order of $u_{\pm}$. It divides $p^2-1$ and, hence, $\text{lcm}_{\pm}(\text{order}(u_{\pm}))$ is coprime with $p$. We have $p\mid \widetilde d_n$ iff $u_{\pm}^{n-N}v_{\pm} = 1$ for both choices of $\pm$. If $n_0$ is the first such integer, then for $n=n_0+k\;\text{lcm}_{\pm}(\text{order}(u_{\pm}))$ also satisfies $p\mid \widetilde d_n$ for any non-negative integer $k$. Since $\text{lcm}_{\pm}(\text{order}(u_{\pm}))$ is coprime with $p$ we can pick $k$ such that $p\mid n_0 + k\;\text{lcm}_{\pm}(\text{order}(u_{\pm}))$. Then $p\mid d_n$.$\;\;\square$

Let's now estimate the likelihood that there is no $p,n$ s.t. $p\mid \widetilde d_{n}, p \notin \{2,5\}$ (which is required from Lemma 1 for $M=\infty$).

Conjecture 1. There is a positive density of primes $p$ s.t. $r \geq p-1$, where $r = \gcd_{\pm}(\text{order}(u_{\pm}))$.

Note 1.1. For $p\equiv \pm 1\mod 5$ we have $r\mid (p-1)$. For $p \equiv \pm2 \mod 5$ we have $r\mid (2p+2)$. Indeed

$$\left(\frac{1+\sqrt{5}}{2}\right)^{p} = \frac{1-\sqrt{5}}{2},$$ $$\left(\frac{1+\sqrt{5}}{2}\right)^{p+1} = -1,$$ $$\left(\frac{1+\sqrt{5}}{2}\right)^{2p+2} = 1.$$

Thus, the condition $r \geq p-1$ is equivalent to $r=p-1$ when $p\equiv \pm 1\mod 5$ and $r=2p+2$ when $p\equiv \pm2\mod5$.

Note 1.2. If one were to try to prove conjecture 1, methods in Kurlberg, Pomerance "On a problem of Arnold: The average multiplicative order of a given integer" could be useful. There is a related open problem "Artin's conjecture on primitive roots".


Non-rigorous speculation part

There is no easy way to talk about likelihoods of mathematical statements. In most cases they are either true or false. E.g. we can say that the probability the digit $9$ occurs more than $10^5$ times in the first $10^6$ digits of $\pi$ is about $0.5$, but in fact one can check the digits of $\pi$ and deduce that probability to be either $0$ or $1$. Yet, sometimes that sort of speculation is helpful to decide our confidence in facts which are not easy to check.

Given that setting, for $r \geq p-1$ we can speculate that for $p\equiv \pm 2 \mod 5$ the element $v_{+}$ is one of $p^2$ possible elements of $\text{GF}(p)[\sqrt{5}]$, and $2p+2$ of them lie on the orbit of $u_{+}$. Thus, there is roughly $\frac{2p+2}{p^2} > \frac{1}{p}$ probability that $v_{+}$ lies on the orbit of $u_{+}$. For $p \equiv \pm 1 \mod 5$ two conditions need to hold: $u_{+}^m = v_{+}$ and $u_{-}^m = v_{-}$ for the same $m$. Under the assumption $r=p-1$ the first of them determines a unique $m$ unless $v_{+}=0$, hence we estimate the likelihood they both hold at the same time as $\frac{p-1}{p^2} = \frac{1}{p} + o(1)$. Assuming these likelihoods to be independent for different $p$ and denoting the density of the primes satisfying conjecture 1 as $C$ and using the density of primes we get

$$\left(\text{Likelihood of $M = \infty$}\right) \leq \prod_{p\in\text{Primes}\setminus\{2,5\}}\left(1-\frac{C(1+o(1))}{p}\right) \\ = \exp\left(-C\int_{5}^\infty \frac{1+o(1)}{n\ln(n)}dn\right) = 0,$$

because the integral in the exponent diverges. The divergence is slow (as $C\ln\ln n$), hence, although the above argument suggests that a prime $p$ s.t. $p\mid \widetilde d_n$ is very likely to exist, it could be very large. E.g. this argument suggests that if we know that there are no such $p < 10^6$, and $C=0.5$ then one would need to search up to $p \simeq 10^{2400}$ if we want the above bounds to "guarantee" a $95\%$ confidence to find such $p$. If we do a more careful estimate instead of the bounds, effective $C$ could be higher, putting an estimate at around $p\simeq 10^{120}$ ($\pm$ a few dozen orders of magnitude) to "guarantee" the same confidence. I don't know any feasible way to do that.

$\endgroup$
2
  • $\begingroup$ Thank you very much for these nice heuristic arguments which once again recall the difficulty of making conjectures in number theory based on experimentation. $\endgroup$
    –  Babar
    Sep 21 at 9:11
  • $\begingroup$ I think we can't do better $\endgroup$
    – Jane
    Sep 21 at 21:07

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.