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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ This looks like a math competition problem - where is the problem from? $\endgroup$
    – Per Alexandersson
    Commented Aug 12, 2017 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
    Commented Aug 12, 2017 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
    Commented Aug 13, 2017 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
    Commented Aug 13, 2017 at 15:33
  • 7
    $\begingroup$ Why the close votes? $\endgroup$
    – Lucia
    Commented Aug 13, 2017 at 17:30

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
8
  • 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
    Commented Aug 13, 2017 at 16:03
  • 2
    $\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
    Commented Aug 13, 2017 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$
    – მამუკა ჯიბლაძე
    Commented Aug 13, 2017 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
    Commented Aug 14, 2017 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
    Commented Aug 14, 2017 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$).

Improve this answer
$\endgroup$
5
  • 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
    Commented Aug 13, 2017 at 14:09
  • $\begingroup$ @WhatsUp: the mistake is mine. I'm updating accordingly. Thank you! $\endgroup$
    – Yaakov Baruch
    Commented Aug 13, 2017 at 14:17
  • $\begingroup$ OK, I'll try to post my experiments later. $\endgroup$
    – WhatsUp
    Commented Aug 13, 2017 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
    Commented Aug 13, 2017 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
    Commented Aug 13, 2017 at 15:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .