Arman, starting from a number, calculates the sum of the cubes of the digits of that number, and again calculates the sum of the cubes of the digits of the resulting number and continues the same process. Arman calls a number $Good$ if it reaches $1$ after performing a number of steps. Prove that there is an arithmetic progression of length $1402$ of good numbers. Proposed by Navid Safaei
Problem
Source: Iran TST 2023 ; Exam 1 Problem 3
Tags: combinatorics
15.03.2023 22:57
This seems hard Only useful thing I can think of is that $370$ or $371$ never reaches one so you can't just say that every number is good
16.03.2023 00:16
@below yeah I completely forgot the "cube"..my bad
16.03.2023 00:41
@above It’s not necessary that the final number is between 1 and 9. For example 133 -> 55 -> 250 -> 133
16.03.2023 01:35
First we prove that there exists an arithmetic progression of length 1402 where each element has the same number of each digit. To do this we will 'forge' some arithmetic progressions in the following way: Say we have arithmetic progressions $A_1, A_2 ... A_n$ we create a new arithmetic progression B = $A_1 + 10^xA_2 + 10^{2x}A_3 + ... + 10^{(n-1)x}A_n$ where $x$ is a big enough number. For example say we $A_1 = (1, 2, 3)$ and $A_2 = (2, 5, 8)$ when we forge them correctly we get something like this $B = (2001, 5002, 8003)$. With this in mind we forge the following arithmetic progressions with difference 1: $(10^8 + 1,... 10^8+1402), (10^8 + 2, ... 10^8 + 1403), (10^8 + 3, 10^8 + 1404), .... (10^9, 10^9+1401)$. In this new arithmetic progression (call it X) each element will have the same number of each digit, hence the same sum of cubes of digits. Call this number $N$.\newline Now it's easy to show that there is a good number which is a multiple of $N$, hence I will skip this part. Say that good number is $cN$. All that is left is to forge X with itself $c$ times with itself and we are done.
10.05.2023 07:44
Sketch: (constructing the arithmetic progression by using circulating decimal.) For simple situations such as replacing 1402 by 6, we consider k/7 ,k=1,2,...,6, whose periods are 142857,285714,428571,571428,714285 and 857142, respectively.Then we find an arithmetic progression of length 6 with every term containing the same digits. Now for 1402 we need to find a larger prime p>1402 such that the period of 1/p contains exactly p-1 digits. This happens if and only if 10 is a primitive root of p. Here we choose p to be the 4th Fermat’s prime 2^16+1=65537, then by Euler’s Criterion it suffices to show 10 is quadratic non-residue of p. One can check it easily by the quadratic reciprocity law. Finally pick the periods of 1/p, 2/p,......,1402/p, then we find an arithmetic progression of length 1402 with every term containing the same digits. So we just need to add some 1s in front of them in order to make the sum of the cubes of the digits is 10^k for some k. So we are done.
27.06.2023 00:36
Here is a construction: Consider this number $g_0=100\cdots 0,$ just note that the number of zeros are greater than $1402$ in this moment, we define $g_i=g_{i-1}+2$ all terms of this sequence are $Good.$ Also, because they didn't mention that our arithmetic progression can't be constant you can easily find a constant sequence.