24
$\begingroup$

I asked this question at MSE, but I think it's more appropriated to MO.

Let $x_{n}$ be a sequence, such that $x_{n+1}= \dfrac{nx_{n}^2+1}{n+1}$ and $x_n>0$ for all $n$.
There is a positive integer $N$ such that $x_n$ is integer for all $n>N$.
Does it follow that $x_n=1$ for all positive integers $n$?

I tried to prove that $x_1 \equiv 1 \text{(mod p)}$ for all prime numbers $p$ but I couldn't make any progress.

Does anyone know if this sequence has ever been studied?

I'm looking for a proof or any reference of this result.
Any help would be appreciated.

$\endgroup$
  • 2
    $\begingroup$ This looks like a math competition problem - where is the problem from? $\endgroup$ – Per Alexandersson Aug 12 '17 at 14:59
  • 2
    $\begingroup$ @PerAlexandersson I found this result while studying some sequences. I conjecture it's true, but maybe it's not the case. I'm also interested in any reference regarding this question. $\endgroup$ – jack Aug 12 '17 at 15:06
  • 1
    $\begingroup$ Do you assume $x_1$ to be an integer? Or is, for example, $x_1 = \sqrt{k}$ possible? Note that $x_1 = \sqrt{k}$ yields rational values for all $n\geq 2$, so it is not directly clear that if $x_1$ is not an integer, it doesn't work. $\endgroup$ – wythagoras Aug 13 '17 at 14:41
  • 3
    $\begingroup$ Yaakov Baruch's formula $(n+1)y_{n+1}=ny_n(y_n+2)$ shows that this sequence is similar to Gobel's sequence satisfying $na_{n+1}=a_n(a_n+n-1)$. See discussion in the comments to mathoverflow.net/q/217894 $\endgroup$ – Max Alekseyev Aug 13 '17 at 15:33
  • 7
    $\begingroup$ Why the close votes? $\endgroup$ – Lucia Aug 13 '17 at 17:30
9
$\begingroup$

I did the following experiment:

Let $p$ be a prime number. Then a necessary condition for the sequence to remain in $\mathbb{Z}$ is that $x_{p-1} \equiv \pm 1 \mod p$.

So for every starting value $x_1$, I calculated $x_{p-1} \mod p$ for the first several prime numbers $p$ to see if there are obstructions. It turns out that for every choice of $x_1$ between $2$ and $100000$, there are always obstructions. The first obstruction (i.e. the smallest prime $p$ such that $x_{p-1}$ is not congruent to $\pm 1$ modulo $p$) for $2 \leq x_1 \leq 100$ is listed below.

x[1] = 2:       obstruction at 2
x[1] = 3:       obstruction at 5
x[1] = 4:       obstruction at 2
x[1] = 5:       obstruction at 5
x[1] = 6:       obstruction at 2
x[1] = 7:       obstruction at 5
x[1] = 8:       obstruction at 2
x[1] = 9:       obstruction at 23
x[1] = 10:      obstruction at 2
x[1] = 11:      obstruction at 7
x[1] = 12:      obstruction at 2
x[1] = 13:      obstruction at 5
x[1] = 14:      obstruction at 2
x[1] = 15:      obstruction at 5
x[1] = 16:      obstruction at 2
x[1] = 17:      obstruction at 5
x[1] = 18:      obstruction at 2
x[1] = 19:      obstruction at 11
x[1] = 20:      obstruction at 2
x[1] = 21:      obstruction at 7
x[1] = 22:      obstruction at 2
x[1] = 23:      obstruction at 5
x[1] = 24:      obstruction at 2
x[1] = 25:      obstruction at 5
x[1] = 26:      obstruction at 2
x[1] = 27:      obstruction at 5
x[1] = 28:      obstruction at 2
x[1] = 29:      obstruction at 13
x[1] = 30:      obstruction at 2
x[1] = 31:      obstruction at 7
x[1] = 32:      obstruction at 2
x[1] = 33:      obstruction at 5
x[1] = 34:      obstruction at 2
x[1] = 35:      obstruction at 5
x[1] = 36:      obstruction at 2
x[1] = 37:      obstruction at 5
x[1] = 38:      obstruction at 2
x[1] = 39:      obstruction at 7
x[1] = 40:      obstruction at 2
x[1] = 41:      obstruction at 11
x[1] = 42:      obstruction at 2
x[1] = 43:      obstruction at 5
x[1] = 44:      obstruction at 2
x[1] = 45:      obstruction at 5
x[1] = 46:      obstruction at 2
x[1] = 47:      obstruction at 5
x[1] = 48:      obstruction at 2
x[1] = 49:      obstruction at 7
x[1] = 50:      obstruction at 2
x[1] = 51:      obstruction at 19
x[1] = 52:      obstruction at 2
x[1] = 53:      obstruction at 5
x[1] = 54:      obstruction at 2
x[1] = 55:      obstruction at 5
x[1] = 56:      obstruction at 2
x[1] = 57:      obstruction at 5
x[1] = 58:      obstruction at 2
x[1] = 59:      obstruction at 7
x[1] = 60:      obstruction at 2
x[1] = 61:      obstruction at 11
x[1] = 62:      obstruction at 2
x[1] = 63:      obstruction at 5
x[1] = 64:      obstruction at 2
x[1] = 65:      obstruction at 5
x[1] = 66:      obstruction at 2
x[1] = 67:      obstruction at 5
x[1] = 68:      obstruction at 2
x[1] = 69:      obstruction at 11
x[1] = 70:      obstruction at 2
x[1] = 71:      obstruction at 11
x[1] = 72:      obstruction at 2
x[1] = 73:      obstruction at 5
x[1] = 74:      obstruction at 2
x[1] = 75:      obstruction at 5
x[1] = 76:      obstruction at 2
x[1] = 77:      obstruction at 5
x[1] = 78:      obstruction at 2
x[1] = 79:      obstruction at 29
x[1] = 80:      obstruction at 2
x[1] = 81:      obstruction at 7
x[1] = 82:      obstruction at 2
x[1] = 83:      obstruction at 5
x[1] = 84:      obstruction at 2
x[1] = 85:      obstruction at 5
x[1] = 86:      obstruction at 2
x[1] = 87:      obstruction at 5
x[1] = 88:      obstruction at 2
x[1] = 89:      obstruction at 13
x[1] = 90:      obstruction at 2
x[1] = 91:      obstruction at 7
x[1] = 92:      obstruction at 2
x[1] = 93:      obstruction at 5
x[1] = 94:      obstruction at 2
x[1] = 95:      obstruction at 5
x[1] = 96:      obstruction at 2
x[1] = 97:      obstruction at 5
x[1] = 98:      obstruction at 2
x[1] = 99:      obstruction at 11
x[1] = 100:     obstruction at 2

Up to $x_1 = 100000$, the biggest "first obstruction" appears at:

x[1] = 13589:   obstruction at 103

Even if one allows $x_1$ to be $\sqrt{k}$ for some integer $k$, the results are similar - one just starts from $x_2$, and for $2 \leq x_2 \leq 10000$ there are always obstructions at (small) prime numbers.


These results seem to support the original conjecture.

EDIT

Following this idea, I further calculated, for a given prime $p$, the residue classes of $x_1 \mod p$ that will lead to an obstruction at $p$. Let us call them "bad" residues. The result seems to be interesting for its own sake.

p       bad residues x[1] mod p
mod 2:  0
mod 3:
mod 5:  0 2 3
mod 7:  0 3 4
mod 11: 0 3 5 6 8
mod 13: 0 2 3 5 8 10 11
mod 17: 2 4 5 12 13 15
mod 19: 0 6 8 11 13
mod 23: 3 7 8 9 11 12 14 15 16 20
mod 29: 0 3 5 6 7 8 10 11 13 14 15 16 18 19 21 22 23 24 26
mod 31: 0 2 5 8 10 13 15 16 18 21 23 26 29
mod 37:
mod 41:
mod 43: 0 2 3 4 5 6 7 8 9 10 11 14 16 18 19 20 21 22 23 24 25 27 29 32 33 34 35 36 37 38 39 40 41
mod 47: 0 7 8 9 10 11 12 13 14 15 18 21 23 24 26 29 32 33 34 35 36 37 38 39 40
mod 53: 0 9 12 15 17 18 20 23 30 33 35 36 38 41 44
mod 59: 3 5 8 13 14 15 16 18 21 26 33 38 41 43 44 45 46 51 54 56
mod 61: 0 2 5 8 11 12 15 17 19 20 21 22 23 24 26 29 32 35 37 38 39 40 41 42 44 46 49 50 53 56 59
mod 67:
mod 71: 5 6 15 19 20 24 25 31 33 35 36 38 40 46 47 51 52 56 65 66
mod 73: 9 23 27 28 29 44 45 46 50 64
mod 79:
mod 83:
mod 89: 0 2 3 4 5 16 17 22 23 24 27 30 31 32 35 40 49 54 57 58 59 62 65 66 67 72 73 84 85 86 87
mod 97: 0 2 3 8 11 14 15 17 21 23 24 28 29 30 35 38 39 44 47 50 53 58 59 62 67 68 69 73 74 76 80 82 83 86 89 94 95

And here is the table which counts the number of bad residues modulo $p$:

p               number of bad residues x[1] mod p
mod 2:          1
mod 3:          0
mod 5:          3
mod 7:          3
mod 11:         5
mod 13:         7
mod 17:         6
mod 19:         5
mod 23:         10
mod 29:         19
mod 31:         13
mod 37:         0
mod 41:         0
mod 43:         33
mod 47:         25
mod 53:         15
mod 59:         20
mod 61:         31
mod 67:         0
mod 71:         20
mod 73:         10
mod 79:         0
mod 83:         0
mod 89:         31
mod 97:         37
mod 101:        50
mod 103:        35
mod 107:        29
mod 109:        20
mod 113:        30
mod 127:        22
mod 131:        93
mod 137:        33
mod 139:        115
mod 149:        121
mod 151:        59
mod 157:        6
mod 163:        111
mod 167:        85
mod 173:        111
mod 179:        98
mod 181:        127
mod 191:        0
mod 193:        83
mod 197:        4
mod 199:        130
mod 211:        85
mod 223:        34
mod 227:        77
mod 229:        57
mod 233:        85
mod 239:        137
mod 241:        56
mod 251:        140
mod 257:        79
mod 263:        0
mod 269:        44
mod 271:        129
mod 277:        20
mod 281:        26
mod 283:        231
mod 293:        171

The most noticeable thing, to me, is those primes with "$0$" bad residues. Here are they:

3, 37, 41, 67, 79, 83, 191, 263, 347, 353, 373, 379, 421, 449, 463, 509, 557, 619, 647, 661, 673, 719, 733, 757, 787, 823, 839, 911

This sequence is not found in OEIS.

Let us call those primes "exceptional". If one excludes those exceptional primes, then the proportion of bad residues (i.e. [number of bad residues mod $p$] divided by $p$) seems to distribute uniformly on the interval $[0, 1)$. This suggests that the exceptional primes may of particular interest.

EDIT

To illustrate the distribution of the proportion of bad residues, here I add the statistical data (for primes $p < 5000$):

"bad proportion"    number of primes
0                   77      (i.e. number of exceptional primes)
(0.00, 0.02]        10
(0.02, 0.04]        15
(0.04, 0.06]        13
(0.06, 0.08]        18
(0.08, 0.10]        7
(0.10, 0.12]        11
(0.12, 0.14]        8
(0.14, 0.16]        14
(0.16, 0.18]        21
(0.18, 0.20]        14
(0.20, 0.22]        16
(0.22, 0.24]        11
(0.24, 0.26]        17
(0.26, 0.28]        15
(0.28, 0.30]        13
(0.30, 0.32]        11
(0.32, 0.34]        15
(0.34, 0.36]        15
(0.36, 0.38]        17
(0.38, 0.40]        17
(0.40, 0.42]        19
(0.42, 0.44]        13
(0.44, 0.46]        15
(0.46, 0.48]        23
(0.48, 0.50]        20
(0.50, 0.52]        16
(0.52, 0.54]        11
(0.54, 0.56]        15
(0.56, 0.58]        16
(0.58, 0.60]        14
(0.60, 0.62]        12
(0.62, 0.64]        6
(0.64, 0.66]        13
(0.66, 0.68]        20
(0.68, 0.70]        14
(0.70, 0.72]        8
(0.72, 0.74]        9
(0.74, 0.76]        9
(0.76, 0.78]        6
(0.78, 0.80]        11
(0.80, 0.82]        12
(0.82, 0.84]        7
(0.84, 0.86]        6
(0.86, 0.88]        5
(0.88, 0.90]        6
(0.90, 0.92]        3
(0.92, 0.94]        3
(0.94, 0.96]        2
(0.96, 0.98]        0
(0.98, 1.00]        0

There is clearly a concentration on $0$, i.e. on the exceptional primes.

The "average proportion", calculated as $\frac{\sum_p proportion_p}{\sum_p 1}$, is about $0.37551$.

$\endgroup$
  • 1
    $\begingroup$ You can make the obstruction $>n$ by starting with $x_1=\text{lcm}(2,3,…n)+1$. (This is clear from the recursion for $y_i$ in my "answer" below.) $\endgroup$ – Yaakov Baruch Aug 13 '17 at 16:03
  • 1
    $\begingroup$ Heuristically, for each prime $p$ there should be about $p/e$ obstructions modulo $p$ (i.e. about $p/e$ residue classes modulo $p$ that would lead to an obstruction at $p$ if $x_1$ falls in one of these classes). Probabilistic heuristics then predict that any given $x_1$ has only an exponentially small chance of surviving all the obstructions, and so the conjecture is highly likely to be true, though perhaps beyond reach of existing techniques to prove. $\endgroup$ – Terry Tao Aug 13 '17 at 18:00
  • $\begingroup$ One gets almost the same but slightly different table if to $x_1$ is assigned the length of the longest initial sequence that stays integer. For example, with $x_1=79$ the first non-integer appears earlier than at $x_{29}$, already $x_{26}$ is not integer. Record breakers are $$ \begin{aligned} x_1=2&\textrm{ (length = $2$)},\\ 3&\textrm{ (length = $5$)},\\ 9&\textrm{ (length = $23$)},\\ 79&\textrm{ (length = $25$)},\\ 799&\textrm{ (length = $29$)},\\ \dots& \end{aligned} $$ $\endgroup$ – მამუკა ჯიბლაძე Aug 13 '17 at 18:48
  • $\begingroup$ @TerryTao It seems that your heuristic does not match the experimental results... I have added further results in the post. $\endgroup$ – WhatsUp Aug 14 '17 at 3:15
  • $\begingroup$ The distribution is going to be rather irregular because of the two-to-one multiplicity in the map $x \mapsto (nx^2+1)/(n+1)$, which has the effect of applying a number of "double or nothing" bets to the distribution. It looks like the density is still about 1/e on the average, though. $\endgroup$ – Terry Tao Aug 14 '17 at 3:30
7
$\begingroup$

I suspect the answer is no. First rewrite $x_n=y_n+1$, then the recursion becomes

$(n+1)y_{n+1}=ny_n(y_n+2)=(y_n+2)(y_{n-1}+2)\cdots (y_2+2) (y_1+2)y_1$

and for the integrality of $y_{n+1}$ it is sufficient to prove that all prior terms are integral and that $(n+1) \mid i y_i (y_i+2)$ for some $i\le n$.

Using that, if one starts from $y_1=8$ (i.e. $x_1=9$) it gets interesting: does the sequence stay in ${\mathbb Z}$? Barring mistakes $y_i$ stays integral for at least $i\le48$... But I can't prove it's the case for all $i$'s.

UPDATE. As per WhatsUp's comment below, I was wrong: $y_{23}$ is not integral (starting from $y_1=8$).

$\endgroup$
  • 2
    $\begingroup$ It's strange ... according to my calculation, if one takes $x_1 = 9$, then $x_{22} \equiv 11 \mod 23$, hence $x_{23}$ cannot be integer. One of us must have made a mistake... $\endgroup$ – WhatsUp Aug 13 '17 at 14:09
  • $\begingroup$ @WhatsUp: the mistake is mine. I'm updating accordingly. Thank you! $\endgroup$ – Yaakov Baruch Aug 13 '17 at 14:17
  • $\begingroup$ OK, I'll try to post my experiments later. $\endgroup$ – WhatsUp Aug 13 '17 at 14:18
  • 2
    $\begingroup$ This reminds me another famous sequence mathoverflow.net/q/217894 (see also discussion in the comments there) $\endgroup$ – Max Alekseyev Aug 13 '17 at 15:23
  • $\begingroup$ @MaxAlekseyev. Indeed the reasoning offered over there applies here too: the early factors $y_i+2$ contain most small primes (and some powers thereof) but the later terms contribute $2$ and increasingly sparse larger primes. $\endgroup$ – Yaakov Baruch Aug 13 '17 at 15:45

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.