$x_1$ is a natural constant. Prove that there does not exist any natural number $m> 2500$ such that the recursive sequence $\{x_i\} _{i=1} ^ \infty $ defined by $x_{n+1} = x_n^{s(n)} + 1$ becomes eventually periodic modulo $m$. (That is there does not exist natural numbers $N$ and $T$ such that for each $n\geq N$, $m\mid x_n - x_{n+T}$). ($s(n)$ is the sum of digits of $n$.)
Problem
Source: Iran MO Third Round 2021 N3
Tags: number theory
26.09.2021 11:45
we will prove for all numbers except those of the form $2^a b$ where $a\leq2 , b|511$. the largest of these numbers is $2044<2500$ step 1: if $8|m$, there is no such sequence: assume the contrary, there is such a sequence. if it is eventually periodic mod $m$ then it must be so for $8$ as well.(in this part, $\equiv$ means equal mod $8$) first if $x_n$ is even and $s(n)>2$ then $x_{n+1}\equiv 1$. thus if there is $k>N$ such that $x_k=3,5,7$ then $s(k-1)\leq2$. because k is in the period, then the density of numbers $k$ s.t $s(k)\leq2$ must tend to $\frac{1}{T}$. on the other hand there are at most $a+a^2$ such numbers less than $10^a$ but because $\frac{10^a}{T}>a+a^2+c$ for large enough a, then we have a contradiction. so if $x_n$ is in the period and is odd, then $x_n\equiv 1$. now note that if $x_n\equiv1$ then $x_{n+1}\equiv 2$ and the period is alternating beteen odd and even. thus combining the previous facts gives us that the period must be $1,2,1,2,\dots$ or $2,1,2,1,\dots$. we have two possibilities: P1: $n>N$ then $x_n\equiv 1$ if n odd and $x_n\equiv 2$ if n even. we check $n=10^b$ for large $b$ and get a contradiction. P2: $n>N$ then $x_n\equiv 2$ if n odd and $x_n\equiv 1$ if n even. we check $n=10^b+1$ for large $b$ and get a contradiction. either way we get a contradiction. so step 1 is done. step 2: if $m\neq 2^a \cdot b$ where $b|511$: because of the definition of m, there is an odd $p^k$ where $p^k|m$ and does not divide $511$.($p$ is a prime number) if the sequence is periodic mod $m$ then it is also periodic mod$p^k$.(in this part $\equiv$ means equal mod $p^k$) now, define A, the set of all residues of the period, mod $p^k$. first we say that $2\in A$: set $n=10^a(10^{\phi(p^k)-1} +\dots+1)$ such that $n>N$ then, $\phi(p^k)=s(n)$ thus $x_{n+1}\equiv c^{\phi(p^k)} +1\equiv 1,2$. if it is equal to 2, we have $2\in A$ else, $x_{n+1}\equiv 1$ then $x_{n+2}\equiv 2$. either way we have $2\in A$. let $x_{nT+r} \equiv 2$ for a constant $r>N$ and all $n\geq 0$. then we conclude that by looking at $x_{Tn+r+1}$, we have $2^{s(nT+r)}\equiv 2^{s(r)}$. set $n\rightarrow 10^a\cdot n$ for a very large $a$. then $s(10^anT+r)= s(nT)+s(r)$ so we conclude that $2^{s(nT)}\equiv 1$. call this ** by the pigeonhole principle, $T$ has a multiple composed of some consecutive ones and to the right of them multiple zeroes. (similar to $11\dots10\dots0$) set such a number as $bT$ where it has $i$ consecutive ones and $j$ consecutive zeroes. now, $n_1=b(9+10^i) , n_2=b(9+10^{(i-1)}$ then $s(n_1 T)=9+s(n_2 T)$. thus putting these in ** and combining we get that $2^9\equiv 1$ so $511\equiv 0$. but $p^k$ does not divide $511$. a contradiction. combining steps 1 and 2 proves what we wanted so we are done
26.07.2022 18:26
Lemma:Let $S(n)$ be sum of the digits of $n$. Then if for some natural numbers $n$ , $m$ and $T$ , numbers $S(n) , S(n+T) , S(n+2T) , ...$ are equivalent mod $m$ , then $m|9$. Proof: Let $T=2^a5^bT'$ such that $gcd(T' , 10)=1$. so for natural numbers $k_T>k_{T-1}>...>k_1$ which $\phi(T')k_1>log n , max(a , b)$ we define $l$ and $l'$ such below and from Euler Theorem we can get : $l=10^{\phi(T')k_T}+10^{\phi(T')k_{T-1}}+...+10^{\phi(T')k_1}+n \equiv T+n \equiv n ( mod T )$ $l'=10^{\phi(T')k_{T-9}}+10^{\phi(T')k_{T-10}}+...+10^{\phi(T')k_1+1}+n \equiv T-10+10+n \equiv n ( mod T )$ so one can see that $S(l)=T+S(n)$ and $S(l')=T-9+S(n)$ , and while $l \equiv l' \equiv n ( mod T )$ , Then $S(l) \equiv S(l') ( mod m )$ and $m|9$ as desired. Back to the problem. Now suppose that the sequence is eventually periodic mod $m$. Then if $m=p_1^{a_1}p_2^{a_2}...p_t^{a_t}$ and $p_i$be one of its odd prime factors , then the sequence is periodic mod $p_i^{a_i}$ too. Then if for some big enough natural $n$ , $x_n$ is relatively prime to $p_i$ , one can see that for each natural $k$ we have : $x_n \equiv x_{n+Tk} ( mod$ $ p_i^{a_i} ) , x_n^{S(n)} \equiv x_{n+Tk}^{S(n+Tk)} ( mod$ $ p_i^{a_i} ) \implies x_n^{S(n)} \equiv x_{n}^{S(n+Tk)} \implies S(n) \equiv S(n+Tk) ( mod $ $ord_{pi^{a_i}}x_n ) $ So by Lemma , $ord_{pi^{a_i}}x_n | 9$ and for each term like $x_n$ which is relatively prime to $p_i$ , we have $x_n^9 \equiv 1 ( mod $ $p_i^{a_i} )$. Now for some natural $t$ which $9t>a_i$ , take the number $n=10^t-1$. Then if $p_i|x_n$ , so $p_i^{a_i}|x_n^{S(n)}=x_n^{9t}$ which satisfies that $x_{n+1} \equiv 1$ and $x_{n+2} \equiv 2 ( mod $ $p_i^{a_i} ) $. so $p_i^{a_i} | 2^9-1=511$. And if $x_n$ and $p_i$ are relatively prime to each other , then $x_n^{S(n)} \equiv x_n^{9t} \equiv 1$ and $x_{n+1} \equiv 2 ( mod $ $p_i^{a_i} ) $ which implies $p_i^{a_i} | 2^9-1=511$ again. Now if the show that the sequence can't be eventually periodic mod $8$ , then $m<4.511=2044$ and we will done. It's clear that $gcd(\phi{(8)} , 9)=1$ so each odd term of the sequence equals to $1$ mod $8$. So this sequence is $1 , 2 , 1 , 2 , ...$ mod $8$ and the rest we can get the result just like TheBarioBario. So we're done.