A sequence $a_1,a_2,a_3,\ldots $ of non-negative integers is such that $a_{n+1}$ is the last digit of $a_n^n+a_{n-1}$ for all $n>2$. Is it always true that for some $n_0$ the sequence $a_{n_0},a_{n_0+1},a_{n_0+2},\ldots$ is periodic?
Problem
Source: Baltic Way 2011
Tags: modular arithmetic, least common multiple, algebra proposed, algebra
Swistak
06.11.2011 19:56
Answer is yes. (I think this problem is rather combinatorics xd) For every digit $d$ sequence $d, d^2, d^3, ...$ is periodic. Let $N$ be the least common multiple of periods of this sequences (in fact $N=4$ but it's sufficient that $N$ is finite ). For every $n>2$ assign a triple $(r(n,N), a_n, a_{n-1})$, where $r(n,N)$ is the least nonnegative integer such that $N|n-r(n, N)$. It's clear that if we know a triple for one specific $n$ we also know $r((n+1),N)$, $a_n^n$, so we also know next triple. There are finitely many possible triples so answer is yes.
waver123
12.12.2011 15:06
consider the sequence ${(a_n,a_{n+1}) \ mod 10}$. there are $10*10=100$ possibilities ,so consider first $101 $ terms(i.e. till $(a_{n+101},a_{n+102})$. Two of these pairs must be the same. Hence the sequence is periodic. Also the maximum period is $100$
Swistak
13.12.2011 00:46
Not a nice try xd. Fact that two of these pairs must be the same proves nothing.
waver123
13.12.2011 14:35
Swistak wrote: Not a nice try xd. Fact that two of these pairs must be the same proves nothing. But any two consecutive terms determine all the rest of the terms. Am i missing something?
Swistak
16.12.2011 23:28
Yes, you're missing something, beacause fact that $a_k \equiv_{10} a_l$ doesn't imply that $a_k ^k \equiv_{10} a_l^l$
palapol
19.03.2012 23:53
Swistak wrote: Answer is yes. (I think this problem is rather combinatorics xd) For every digit $d$ sequence $d, d^2, d^3, ...$ is periodic. Let $N$ be the least common multiple of periods of this sequences (in fact $N=4$ but it's sufficient that $N$ is finite ). For every $n>2$ assign a triple $(r(n,N), a_n, a_{n-1})$, where $r(n,N)$ is the least nonnegative integer such that $N|n-r(n, N)$. It's clear that if we know a triple for one specific $n$ we also know $r((n+1),N)$, $a_n^n$, so we also know next triple. There are finitely many possible triples so answer is yes. I don't see how your use of the triples proves anything. Can someone please explain? Thanks.
ThinkFlow
04.04.2012 18:20
Swistak's solution is saying the triples $(n\pmod{4},a_n \pmod{10},a_{n-1}\pmod{10})$ have finitely many possibilities, so eventually they must repeat. Since these three pieces of information determine the sequence entirely, the sequence becomes periodic at this point. We need only keep track of $n\pmod{4}$ since $\phi{10}=4$, as Swistak mentioned.