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
straight
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
alinazarboland
16.03.2023 00:16
Here's an sketch(forgive me if it's wrong it's around 1 a.m here and I'm posting this after like a minute since I saw the problem )
Clearly the final number would be sth between $1$,$9$ for any positive integer .so distribute them into 9 different sets. Note that it's enough to show that the density of any two of these sets are tightly close ; since then we're done by Szemeredi's theorem which states that every dense subset of positive integers has any arbitrary long arithmetic progression.
Now , consider a large enough $N=10^t$ and consider a number i smaller than $N$. The main point is that the number of integers $m$ less than $N$ which satisfies $s(m)=i$ are tightly close to the number of ones which satisfies $s(m)=i+1$. This can be proven easily by playing a bit with the digits of $m$ you should just find a non-$9$ among the $t-1$ right digits.
The restcan be done easily so the density of each of the $9$ sets are non-zero since they were close enough to each other and we're done by Szemeredi's theorem.
@below yeah I completely forgot the "cube"..my bad
R8kt
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
R8kt
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.
Ziert
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.
M11100111001Y1R
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.