Arman starts with a number and calculates the sum of the cubes of its digits. He then repeats this procedure with the resulting number, and continues this procedure. Arman considers a number to be 'good' if, after a certain number of steps, it reaches . Prove that there exists an arithmetic progression of length consisting of good numbers.
Solutions — 2
Solution 1
We define to be the sum of the cubes of digits of .
In this solution first we give an example of an arithmetic progression of length 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 such that .
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 for an . We claim that all have the same digits with the same number of recurrence. We shall use a lemma here:
Lemma 1. is a primitive root for every power of .
Proof. It is enough to see that is a primitive root modulo and .
Lemma 2. For every , , represents the repeating part in the decimal representation of . Furthermore it is a cyclic permutation of the digits in .
Proof. Let . We have:
As the left hand side is an integer, . Knowing and by Lemma 1 we have .
As is a primitive root modulo there exists such that:
is less than resulting in . However the repeating decimal of is a cyclic permutation of the repeating decimal of which is (that is a special case of the first part where ).
Solution 2
Let , . Then, . So, is good only if . We prove that there would be an arithmetic progression of common difference of of arbitrary length. Let , . If and is good then is good.
Lemma 1. Let be positive integers and . Then .
Proof. Obvious.
Lemma 2. For any and there are an integer such that .
Proof. .
Since we find that for all we have . So, if we apply the function repeatedly to we eventually reach a cycle with finite length or arrive at . The number of cycles of is finite.
Claim 1. *There exists a finite set such that*
i For any positive integer , for some .
ii For any , for some integer .
Choose the subset . Since for any integer , we see that if and only if , for some .
If for there is a positive integer such that both are good numbers, then there exists a sequence of good numbers of any length . Let . We prove it by induction on . Assume then there exists an such that thus or for some . By our assumption, there exists such that both and are good numbers. According to above lemma, there is such that and or . Let then both are good.
Now, assume that the statement holds for that is, there is an such that are all good. We consider two cases. If is happy take and we are done. If is good then since . Thus, there exists such that
for some . According to the properties of there exists a positive integer such that
Meanwhile, there exists an such that .
For any , since are all happy. Let ) satisfy . Then, by above lemma, there is a positive integer such that
moreover,
That is to say, , () are all good. Taking then are all happy. We are done.