Iranian Mathematical Olympiad

We define $T(n)$ to be the sum of the cubes of digits of $n$.

In this solution first we give an example of an arithmetic progression of length $1402$ such that all the numbers have the same non-zero digits with the same amount of recurrence. Then we will have an arithmetic progression of $a_1, \dots, a_{1402}$ such that $T(a_1) = \dots = T(a_{1402})$.

By adding some amount of ones on the left sides of these numbers we can keep them as an arithmetic progression and additionally convert all of them to a good number.

Now let's find the promised progression. Let $A = \frac{10^{\varphi(7^m)} - 1}{7^m}$ for an $m > 10$. We claim that $A, 8A, 15A, \dots, (1402 \times 7 + 1)A$ all have the same digits with the same number of recurrence. We shall use a lemma here:

Lemma 1. $10$ is a primitive root for every power of $7$.

Proof. It is enough to see that $10$ is a primitive root modulo $7$ and $7^2$.

Lemma 2. For every $1 \le a \le 7^m$, $\text{gcd}(a, 7) = 1$, $aA$ represents the repeating part in the decimal representation of $\frac{a}{7^m}$. Furthermore it is a cyclic permutation of the digits in $A$.

Proof. Let $\frac{a}{7^m} = 0.\overline{a_1\cdots a_s}$. We have:
$$\overline{a_1 \cdots a_s} = a \times \frac{10^s - 1}{7^m}$$
As the left hand side is an integer, $7^m \mid (10^s - 1)a$. Knowing $\text{gcd}(a, 7) = 1$ and by Lemma 1 we have $s = \varphi(7^m)$.
$$\overline{a_1 \cdots a_s} = a \times \frac{10^{\varphi(7^m)} - 1}{7^m} = aA$$
As $10$ is a primitive root modulo $7^m$ there exists $\alpha$ such that:
$$a \equiv 10^{\alpha} \pmod{7^m} \implies \frac{10^{\alpha}}{7^m} - \frac{a}{7^m} \in \mathbb{Z}$$
$\frac{a}{7^m}$ is less than $1$ resulting in $\frac{a}{7^n} = \{\frac{10^\alpha}{7^n}\}$. However the repeating decimal of $\{\frac{10^\alpha}{7^n}\}$ is a cyclic permutation of the repeating decimal of $\frac{1}{7^n}$ which is $A$ (that is a special case of the first part where $a = 1$).

Let $n = \sum_{j=0}^{k} a_j 10^j$, $T(n) = \sum_{j=0}^{k} a_j^3$. Then, $T(n) = n \pmod{3}$. So, $n$ is good only if $n = 1 \pmod{3}$. We prove that there would be an arithmetic progression of common difference of $3$ of arbitrary length. Let $T^0(x) = x$, $T^m(x) = T(T^{m-1}(x))$. If $T^m(y) = x$ and $x$ is good then $y$ is good.

Lemma 1. Let $x, y, t$ be positive integers and $10^t > y$. Then $T(10^t x + y) = T(x) + T(y)$.

Proof. Obvious.

Lemma 2. For any $a_1, \dots, a_n$ and $r, y$ there are an integer $Y$ such that $T^r(Y + a_i) = y + T^r(a_i), \ i = 1, \dots, n$.

Proof. $T^r(10^t l_r + a_i) = T^{r-1}(T(10^t l_r + a_i)) = T^{r-1}(10^t l_{r-1} + T(a_i)) = T^{r-2}(T(10^t l_{r-1} + T(a_i))) = T^{r-2}(10^t l_{r-2} + T^2(a_i)) = y + T^r(a_i)$.

Since $T(n) = (9)^k \log_{10} a$ we find that for all $a > M$ we have $T(a) < a$. So, if we apply the function $T$ repeatedly to $a$ we eventually reach a cycle with finite length or arrive at $1$. The number of cycles of $T$ is finite.

Claim 1. *There exists a finite set $B$ such that*

i For any positive integer $n$, $T^r(n) \in B$ for some $r = 0$.
ii For any $d \in B$, $T^l(d) = d$ for some integer $l = 0$.

Choose the subset $D = \{x \in B : x = 1 \pmod 3\}$. Since for any integer $n$, $T(n) = n \pmod 3$ we see that $n = 1 \pmod 3$ if and only if $T^r(n) \in D$, for some $r = 0$.

If for $d \in D$ there is a positive integer $y$ such that $y + 1, y + d$ both are good numbers, then there exists a sequence $\{l, l + 3, \dots, l + 3(m - 1)\}$ of good numbers of any length $m$. Let $D = \{1, d_1, \dots, d_k\}$. We prove it by induction on $m$. Assume $m = 2$ then there exists an $r$ such that $T^r(4) \in D$ thus $T^r(4) = 1$ or $d_i$ for some $1 = k = k$. By our assumption, there exists $y_i$ such that both $y_i + 1$ and $y_i+d_i$ are good numbers. According to above lemma, there is $Y$ such that $T^r(Y+1) = y_i+T^r(1) = y_i+1$ and $T^r(Y+4) = y_i+T^r(4) = y_i+d_i$ or $y_i+1$. Let $l = Y+1$ then both $l, l+P$ are good.

Now, assume that the statement holds for $m = u - 1$ that is, there is an $l'$ such that $l', l' + 3, \dots, l' + 3(u - 2)$ are all good. We consider two cases. If $l' + 3(u - 1)$ is happy take $l = l'$ and we are done. If $l' + 3(u - 1)$ is good then since $l' + 3(u - 1) \equiv l' \equiv 1 \pmod 3$. Thus, there exists $r$ such that
$$T^r(l' + 3(u-1)) = d_j,$$
for some $1 \le j \le k$. According to the properties of $D$ there exists a positive integer $v$ such that
$$T^{r+v}(l' + 3(u-1)) = T^r(l' + 3(u-1)) = d_j.$$
Meanwhile, there exists an $R$ such that $T^R(l' + 3(i - 1)) = 1$.

For any $1 \le i \le u - 1$, since $l', \dots, l' + 3(u - 2)$ are all happy. Let $K \equiv r \pmod v$) satisfy $K > R$. Then, by above lemma, there is a positive integer $Y$ such that
$$T^K(Y + l' + 3(i - 1)) = y_j + T^K(l' + 3(i - 1)) = y_j + 1, \quad (1 \le i \le u - 1),$$
moreover,
$$T^K(Y + l' + 3(u-1)) = y_j + T^K(l' + 3(u-1)) = y_j + d_j, \quad (1 \le i \le u-1).$$
That is to say, $Y + l' + 3(i - 1)$, ($1 \le i \le u$) are all good. Taking $l = Y + l'$ then $l, \dots, l + 3(u - 1)$ are all happy. We are done.