3
$\begingroup$

Take a number between 2001 and 2100 inclusive. Cube the digits of the number and add them together, then repeat the process with the new sum and restart the process over and over. For example if I take 2016, the next number will then be 225, then 141, then 66, then 432, then 99, then 1458, then 702, then 351, then 153, then 153, then 153,... and 153 reappears forever. How many numbers between 2001 and 2100 inclusive have a 153 never ending loop? Please don’t use computers.

$\endgroup$
0

2 Answers 2

5
$\begingroup$

I observed the following:

The residue modulo $3$ does not change.

This is because

$$x^3\equiv x \mod 3$$ from Fermat's little theorem. Therefore the digital root of the number remains the same modulo $3$, and hence the number itself does too.

This observation immediately excludes many numbers from consideration.

To end in $153$, which is a multiple of $3$, the starting number must also be a multiple of $3$.

It remains to be shown that the numbers that were not excluded do all end at $153$.

Or, maybe it can be shown that there exists no other loop made of multiples of $3$.

For completeness, here is my working out of the remaining cases. Rand al'Thor already did this first in his answer. Like him, I do not see any clever way that this work can be avoided.

The numbers $20ab$ and $20ba$ give the same result after one step, so we can assume $a\le b$. Also $2100$ gives the same result as $2001$. That leaves only 17 cases that need to be checked. We can stop the chain as soon as it hits a number with the same digits as a previous one (ignoring any zeroes).
It turns out that they all work - all $34$ multiples of $3$ from $2001$ to $2100$ lead to $153$.

2001 9  729  1080  513 (153)
2004 72  351 (153)
2007 351 (153)
2013 36  243  99  1458  702 (72)
2016 225 141 66 432 (243)
2019 738 882 1032 (2013)
2022 24 (2004)
2025 (225)
2028 (882)
2034 (243)
2037 378 (738)
2046 288 (882)
2049 801 513 (153)
2055 258 645 405 189 1242 81 (801)
2058 (258)
2067 567 684 792 (729)
2079 (729)
2088 (882)

$\endgroup$
2
  • 1
    $\begingroup$ Great catch! I was looking for something with modular arithmetic, but didn't manage to find this invariant. I've completed the puzzle using case-by-case checking, since the OP said no computers, not no boring calculation :-) I suspect such boring calculation is necessary for these puzzles, since sums of cubes lead to very difficult problems in general, but it would be awesome if there's another neat workaround. $\endgroup$ Jul 30, 2020 at 14:37
  • $\begingroup$ Congratulations. $\endgroup$ Jul 30, 2020 at 15:07
4
$\begingroup$

Considering cycles

The largest number such a chain can ever reach is $1486$ (every number between $2001$ and $2100$ gives at most $8+0+729+729=1466$ at the first step, and the largest possibility resulting from any number up to there is $1+27+729+729=1486$). So we have an upper bound, which means every chain must eventually end in a cycle.

In the OP you mentioned $\overline{153}$ as a cycle of length 1; there are only five cycles of length 1, namely $\overline{1}$, $\overline{153}$, $\overline{370}$, $\overline{371}$, $\overline{407}$. I found most of these and also a length-three cycle $\overline{133\rightarrow55\rightarrow250}$ just by experimenting with starting with single-digit numbers:

  • $9\rightarrow729\rightarrow1080\rightarrow513\rightarrow\overline{153}$

  • $8\rightarrow512\rightarrow134\rightarrow92\rightarrow737\rightarrow713\rightarrow\overline{371}$

  • $7\rightarrow343\rightarrow118\rightarrow514\rightarrow190\rightarrow730\rightarrow\overline{370}$

  • $6\rightarrow216\rightarrow225\rightarrow141$, goes to $\overline{153}$ as in the OP.

  • $5\rightarrow125$, goes to $\overline{371}$ as for $8\rightarrow512$ above.

  • $4\rightarrow64\rightarrow280\rightarrow520\rightarrow\overline{133\rightarrow55\rightarrow250}$

  • $3\rightarrow27\rightarrow351\rightarrow\overline{153}$

  • $2\rightarrow8$, goes to $\overline{371}$ as seen above.

  • $\overline{1}$ is of course its own fixed cycle.

Eliminating cases

The chain you've given in the OP also gives a bunch of numbers that must end with $\overline{153}$:

$2007,2016,2025,2034,2043,2052,2061,2070$.

Knowing that $9$ goes there also gives:

$2001,2010,2079,2097,2100$.

However, from $8$ and $4$ we also find that

$2015,2051$ go to $\overline{371}$ instead, while $2005,2008,2050,2080$ go to the length-three cycle.

So far, among the 100 given starting points, we know that 13 of them do go to $\overline{153}$ and 6 of them don't. We also know the ending point must be a cycle, either one of the five possible single-point cycles or a multi-point cycle; at least one multi-point cycle is possible, but I don't know how many are.

As Jaap Scherpuis astutely notes, the only possible numbers which could go to $\overline{153}$ are

the multiples of 3, of which there are only 34 in the given set.

We already know 13 of these do go to $\overline{153}$, so that leaves 21 left to check. Checking the first couple of them:

  • $2004\rightarrow66$ which is in the chain given in the OP.

  • $2013\rightarrow36\rightarrow243\rightarrow99$ which is in the chain given in the OP.

  • $2019\rightarrow738\rightarrow882\rightarrow1032$ which goes like $2013$.

  • $2022\rightarrow24$ which goes like $2004$.

Now we already get ten more for free:

$2004,2013,2019,2022,2031,2034,2040,2043,2088,2091$.

Next one:

$2028\rightarrow528\rightarrow645\rightarrow405\rightarrow189\rightarrow1242\rightarrow81\rightarrow513\rightarrow\overline{153}$,

giving us four more for free:

$2028,2058,2082,2085$.

Only seven left to check, namely

$2037,2046,2049,2055,2064,2073,2094$.

We just need to check four of these:

  • $2037\rightarrow378$ which goes like $738$ above.

  • $2046\rightarrow288$ which goes like $882$ above.

  • $2049\rightarrow801$ which goes like $1080$ above.

  • $2055\rightarrow258$ which goes like $528$ above.

Final solution

34 of the given 100 numbers end up at $\overline{153}$, namely all the multiples of 3.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.