11
$\begingroup$

I am not really sure what to tag this question as, so please forgive me for wrongly categorising it.

The question is as follows: The first number in a list is 2. After that, each number is calculated by adding the digits of the previous number together and squaring the result. What is the 2022nd number in the list?

If I have not misunderstood, the beginning of the list would be [2, 4, 16, 49, 169...].

Please assist me in solving this problem, as I have no idea how to calculated the nth number in this.

$\endgroup$
3

2 Answers 2

10
$\begingroup$

HINT: The next number is $256$, and then so the next is $169$, and thus the next is $256$ again, and then the next is $169$....

To sum up, the $2022$nd number is $256$ and the $2023$rd number is $169$.

Intuitively, if one were to take a positive number $a_0$ and form a sequence $\{a_k; k=0,1,2,\ldots\}$, where $a_{k+1}=O(\ln(a^2_k))$, then the resulting sequence is bounded--there is a positive number $A$ such that the inequality $a_k \le A$ holds for all integers $k$, and infact $A$ is not that large. Something similar is happening here with this sequence; note that the sum of the digits of a number $M$ is $O(\ln M)$. And so the resulting sequence of positive integers as specified in the problem, is bounded from above, where the upper bound is not that high. Thus, as this is a sequence of positive integers bounded from above, there was guaranteed to be a repeat in this sequence of integers, and as the bound is not that high, this repeat would show itself soon enough for exhaustive search. Then once a repeat is found, one can then observe that a repeat guarantees that this sequence of integers is eventually periodic.

$\endgroup$
3
  • 1
    $\begingroup$ Thank you so much I feel so stupid for not continuing but it seemed like it wouldn't do that $\endgroup$
    – user1065907
    Nov 4, 2022 at 3:31
  • 4
    $\begingroup$ @AlbertEinstein, never be afraid to brute force an problem. I learned a long time ago that just because brute force methods lack elegance, it does not mean that they are inappropriate. Sometimes such methods can provide the jump start to the more elegant solution. $\endgroup$ Nov 4, 2022 at 4:13
  • $\begingroup$ @AlbertEinstein one can check that this sequence of positive integers is bounded. Which then guarantees a repeat. Which then guarantees that this sequence is eventually periodic. That was the intuition--that and a bit of brute force-- that I used to solve this ... $\endgroup$
    – Mike
    Nov 4, 2022 at 4:21
1
$\begingroup$

Let $S(n)$ be the sum of the digits of $n$ where $n$ is some natural number written in base $10$. We have,

$a_1=2$, $a_n=S(a_{n-1})^2\forall n\ge2$.

We simply use the recurrence relation over and over again to get

$a_2=4,$

$a_3=16,$

$a_4=49,$

$a_5=169,$

$a_6=256,$ and

$a_7=169.$

Now, notice that $a_7=a_5$. This forces $a_6=a_8$, and the sequence then just takes the values $169$ and $256$. In general, $a_{n+2}=a_n \forall n \ge5.$ You have everything you need to solve the question now.

$\endgroup$

You must log in to answer this question.