A recursive sequence

Probability Level 2

Define a sequence such that $A_1 = 2$ and $A_{n+1}$ is the sum of the squares of the digits of $A_n.$ Determine the value of $A_{1999} + A_{2000}$ .

The answer is 187.

10 solutions

Kiriti Mukherjee
Aug 11, 2013

We know, $a_1 = 2$

So, $a_2 = 2^2 =4$

$a_3 = 4^2 = 16$

$a_4 = 1^2 +6^2 = 37$

$a_5 = 3^2 + 7^2 =58$

$a_6 = 5^2 + 8^2 =89$

$a_7 =8^2 +9^2= 145$

$a_8 = 1^2 +4^2 +5^2 =42$

$a_9 = 4^2 + 2^2 = 20$ and that means $a_9 = 2 = a_1$ .

So, it's clear that, $a_k = a_{k mod 8}$ .

Now, $a_{1999} + a_{2000} = a_7 + a_8 = 145 + 42 = \boxed {\boxed {187}}$

Moderator note:

You obtained that $a_9 = 20$ but then switched to $a_9 = 2.$ Which is correct and why?

Oh! I have made a mistake to write. Actually, $a_{10}$ depends on $a_9$ . And $a_9 = 20$ . So, $a_{10} = 2^2 + 0^2 = 2^2 = 4$ . Here we can remove the $0^2$ only for $a_{10}$ .

But for all $a_{8k +1} = 20$ ,where $k \in \mathbb {N}$ ......

For example : $a_{2001} = 20$

I have written $a_9 = 2$ only for $a_{10}$ ...........

Kiriti Mukherjee - 7 years, 10 months ago

Michael Tang
Aug 11, 2013

We compute the first few values of $A_n$ :

$A_1 = 2$
$A_2 = 2^2 = 4$
$A_3 = 4^2 = 16$
$A_4 = 1^2 + 6^2 = 37$
$A_5 = 3^2 + 7^2 = 58$
$A_6 = 5^2 + 8^2 = 89$
$A_7 = 8^2 + 9^2 = 145$
$A_8 = 1^2 + 4^2 + 5^2 = 42$
$A_9 = 4^2 + 2^2 = 20$
$A_{10} = 2^2 + 0^2 = 4$

Notice that $A_2 = A_{10},$ so the sequence repeats with a period of $8$ (starting with $A_2$ ); we can use this fact to compute $A_{1999}$ and $A_{2000}$ easily. Because $1999 \equiv 7 \pmod{8}$ and $2000 \equiv 0 \pmod{8},$ we have $A_{1999} + A_{2000} = A_7 + A_8 = 145 + 42 = \boxed{187}.$

Moderator note:

If we started with a number other than $2$ , can we arrive at other cycles? How many different cycles could there be? Is it finite, or could there be infinitely many?

CM: Claim: If you start with any number, you will reach one of a finite number of cycles.

Proof: Notice what happens if you start with a $k>3$ digit number, then the maximum value of the sum of the squares of the digits of that number is $81k$ , which will give you a number with less digits. For $k=3$ , an analysis can show you that an iteration will always result in a smaller number. That said, there are clearly a finite number of integers that can be held in the sequence, thus there are a finite number of cycles and all sequences will end in a cycle.

I'll implement a program shortly to find all the possible cycles.

Bob Krueger - 7 years, 10 months ago

I've written some code in Python:

cycles = []

def sum_of_squares(num):
    sum = 0
    for digit in str(num):
        sum += int(digit)**2
    return sum

def analyze(num):
    current_cycle = []
    while(True):
        for cycle in cycles:
            if num in cycle: # cycle already found
                return
        if num in current_cycle: # new cycle!
            new_cycle = current_cycle[current_cycle.index(num):]
            cycles.append(new_cycle)
            break
        current_cycle.append(num)
        num = sum_of_squares(num)

for n in range(1,1000):
    analyze(n)
print(cycles)

It turns out, the only cycles are

$4 \Rightarrow 16 \Rightarrow 37 \Rightarrow 58 \Rightarrow 89 \Rightarrow 145 \Rightarrow 42 \Rightarrow 20 \Rightarrow 4$

and

$1 \Rightarrow 1 \Rightarrow …$

Tim Vermeulen - 7 years, 10 months ago

Nice. I'm rather new to python, so I wasn't exactly sure how to separate the digits from a number.

Bob Krueger - 7 years, 10 months ago

@Bob Krueger – I'm also pretty new to Python, I sometimes spend more time in the documentation and stackoverflow than with actual coding. I'd say it's a matter of breaking each step up into elementary steps (e.g. converting from an integer to a string, or iterating through a string), which can be found online in a matter of seconds.

Tim Vermeulen - 7 years, 10 months ago

Tushar Gautam
Aug 12, 2013

A1=2, A2=4, A3=16, A4=37, A5=58, A6=89, A7=145, A8=42, A9=20, A10=4 so we are getting repeated series after every 8th term we can sayAn=An+8k for n> 1 and k is integer

So A1999=A7+8×249=A7 And A2000=A8+8×249=A8

So our ans is A7+A8=145+42=187

Mihai Nipomici
Aug 13, 2013

we observe that A1=2, A2=4, A3=16, A5=59, A6=89, A7=145, A8=42, A9=20, A10=4,A11=11.... we observe that Ak=A(k+8) it has period 8. Then A1999+A2000=A7+A8=145+42=187

Yunhao King
Aug 12, 2013

Write down the first few An,it is not hard to find out (2,4,16,37,58,89,145,42),(20,4,16,37,58,89,145,42)...

So A1999=145 A2000=42,
A1999+A2000=145+42=187

Soumava Pal
Aug 16, 2013

A1=2 A2=4 A3=16 A4=37 A5=58 A6=89 A7=145 A8=42 A9=20 A10=4=A2 THUS WE SEE THAT EVERY A(8K+2)=4 NOW A1994=4 A1995=16 A1996=37 A1997=58 A1998=89 A1999=145+(A2000=)42=187

Sowmitra Das
Aug 16, 2013

The first couple of values of the sequence are: $A_{1}=2,\, A_{2}=4,\, A_{3}=16,\, A_{4}=37,\, A_{5}=58,\, A_{6}=89,$ $A_{7}=145,\, A_{8}=42,\, A_{9}=20,\, A_{10}=4\,.....$ .

So, we see that, the sequence repeats from here onwards, having recurring groups of $8$ terms with values from $A_2$ to $A_9$ .

Now, $1999=8\times(249)+7$ . So, upto $A_{1999}$ the sequence completes $249$ $8$ -term groups and $7$ additional terms. Since, $A_1$ doesn't repeat, $A_{1999}$ is the $6^{th}$ term of the group, i.e, $145$ . So, the next term, i.e, $A_{2000}$ is $42$ .

Therefore, $A_{1999}+A_{2000}=145+42=\boxed{187}$ .

A Brilliant Member
Aug 13, 2013

Write the first few terms & observe that every 8 numbers repeat. (You may take $A_1$ to be 20,this doesn't alter other terms) From here find the result.

Louie Tan Yi Jie
Aug 12, 2013

Computing A[n] for the first 10 values gives

{2, 4, 16, 37, 58, 89, 145, 42, 20, 4}.

After the initial A[1], A[n] follows a circular pattern of length 8.

A[1999] = A[1 + 1998mod8] = A[7] = 145

A[2000] = A[1 + 1999mod8] = A[8] = 42

A[1999] + A[2000] = 145 + 42 = 187

Moderator note:

You noticed that $A_1$ is not part of the pattern in the sequence. What other numbers can we start with and eventually arrive at this particular cycle of 8 numbers?

To address the CM, we can start with any number whose digits sum to the one of the values in the cycle. This can include just adding 0's and starting with $2000$ or even starting with a number with 37 digits which are all 1's, leading us to a cycle $111..., 37, 58, 89, 145, 42, 20, 4, 16, 37, 58 ...$

Michael Tong - 7 years, 10 months ago

Those start values are trivial. More interestingly:

$3 \Rightarrow 9 \Rightarrow 81 \Rightarrow 65 \Rightarrow 61 \Rightarrow 37,$

which is part of the sequence. Also,

$5 \Rightarrow 25 \Rightarrow 29 \Rightarrow 85 \Rightarrow 89$

and

$6 \Rightarrow 36 \Rightarrow 45 \Rightarrow 41 \Rightarrow 17 \Rightarrow 50 \Rightarrow 25 \Rightarrow 29 \Rightarrow 85 \Rightarrow 89.$

However,

$7 \Rightarrow 49 \Rightarrow 97 \Rightarrow 130 \Rightarrow 10 \Rightarrow 1 \Rightarrow 1 \Rightarrow \dots$

Tim Vermeulen - 7 years, 10 months ago

Geoffrey Kocks
Aug 11, 2013

We begin by writing out several terms of A_{n} to identify a pattern: $A_{1} = 2$ $A_{2} = 4$ $A_{3} = 16$ ... $A_{7} = 145$ $A_{8} = 42$ $A_{9} = 20$ $A_{10} = 4$

At $A_{10}$ , the pattern that started with $A_{2}$ starts all over again. This pattern has 8 terms. Because it starts on $A_{2}$ , to find the value of $A_{2000}$ , we divide 2000-1 by 8, which gives us 249 with a remainder of 7. Thus, $A_{2000}$ is the 7th term of the pattern: 42. Hence, $A_{1999}$ = $A_{7}$ = 145. 145 + 42 = 187.

A recursive sequence

The answer is 187.

10 solutions

Moderator note:

Moderator note:

Moderator note:

0 pending reports