# Don't try this if you don't know your maths!

Find the next number in this sequence:

$120, 106, 112, 108, 80, 92, 84,...$

This sequence might be easy for some, but you won't be able to solve it if you don't know a certain subject in maths (That I will reveal if nobody finds the answer in 30 minutes).

First Hint:

Look at the title!

Second Hint:

It doesn't involve any special series or integrals.

Third hint:

It is in the number theory puzzle

Fourth hint:

It is an easy recurrence relation.

Fifth hint:

It uses a well known function

Sixth hint:

120 and 106 are just starting values

• 550? ${}{}{}{}{}$ – warspyking Sep 9 '15 at 19:28
• @warspyking No sorry that's not the answer. How did you arrive a that answer? – Oussama Boussif Sep 9 '15 at 19:29
• I used an addition table – warspyking Sep 9 '15 at 19:31
• -594? ${}{}{}{}$ – warspyking Sep 9 '15 at 19:32
• @warspyking no the number is a positive integer. There's addition but there's something else involved – Oussama Boussif Sep 9 '15 at 19:33

The next number in this sequence is,

$80$

Because the sequence is defined as such:

$a_0 = 120,\:a_1 = 106,\:a_n = \phi(a_{n-1} + a_{n-2})$

Where $\phi$ denotes Euler's totient function, defined as the number of integers between 1 and $x-1$ inclusive that are coprime to $x$.

The sequence continues,

$120,\,106,\,112,\,108,\,80,\,92,\,84,\,80,\,80,\,64,\,48,\,48,\,\overline{32,\,32,\,32},\,\dots$

• I looked at this Wikipedia page... Good job on figuring this out! – Martijn Sep 12 '15 at 22:31
• I don't know why I tried sigma, but not phi. (If you could see deleted answers, you could see that I even posted one (wrong) answer) – Rohcana Sep 13 '15 at 6:06
• Bravo that's the right answer pal – Oussama Boussif Sep 14 '15 at 21:01

The sequence and its difference sequence are-

$S = 120,\ 106,\ 112,\ 108,\ 80,\ 92,\ 84,...$
$\Delta S= -14,\ 6,\ -4,\ -28,\ 12,\ -8...$

It seems that the difference sequence doubles every 3 terms. So, I would guess that the next three terms in the difference sequence would be

-14, 6, -4, -28, 12, -8, (-56, 24, -16) or (-42,18,-12)

So, the next terms might be:

120, 106, 112, 108, 80, 92, 84, (28, 52, 36) or (42, 60, 48)

• It's a bit more complicated. Look at the hint, it says you'll have to use NUMBER THEORY. Maybe you'll find a pattern by exploiting that. But differences here won't get you to the answer. – Oussama Boussif Sep 10 '15 at 9:41
• @OussamaBoussif Simple is better than complicated, otherwise we can just use polynomial fittings for any sequence question. – Rohcana Sep 10 '15 at 9:44
• It's not very compmicated. No polynomials or series are involved here. Well I think this time for a new hint – Oussama Boussif Sep 10 '15 at 9:50
• @OussamaBoussif Okay, waiting to see the intended solution. I do hope that it is better than mine. I myself would have been disappointed at the question if this was the answer. – Rohcana Sep 10 '15 at 9:51
• Well look at the new hint and see what you can do. – Oussama Boussif Sep 10 '15 at 9:52

These are the known numbers so far:

$$S = \left(\begin{matrix} 0 & 120 \\ 1 & 106 \\ 2 & 112 \\ 3 & 108 \\ 4 & 80 \\ 5 & 92 \\ 6 & 84 \end{matrix}\right)$$

When investigating the numbers, I noticed a pattern in them:

$$\Delta S = 112 - 106 = 6 \\ \Delta S = 112 - 108 = 4$$

$$\Delta S = 92 - 80 = 12 \\ \Delta S = 92 - 84 = 8$$

These number seem to be related to each other in groups of 3 and their $\Delta$'s between each other seem to be doubling. Backwards engineering using this, leaves us with:

$$\Delta S = a - 120 = 2 \\ a = 2 \\ S(-1) = 122$$

Now let's compare the highest numbers of all the known triplets:

$$\Delta S = 122 - 112 = 10 \\ \Delta S = 112 - 92 = 20$$

Which confirms my theory that the pattern must be:

$$\text{in }\mathbb{Z} \\[12pt] S(x) = \begin{cases} S(x+1) - \left(6 * 2^{\left\lfloor\frac{x-1}{3}\right\rfloor}\right) & \text{if } ((x-1) \text{ mod } 3) = 0 \\ 132 - \left(20 * 2^{\left\lfloor\frac{x-1}{3}\right\rfloor}\right) & \text{if } ((x-2) \text{ mod } 3) = 0 \\ S(x-1) - \left(4 * 2^{\left\lfloor\frac{x-1}{3}\right\rfloor}\right) & \text{if } (x \text{ mod } 3) = 0 \end{cases}$$

The next number in the sequence would be:

\begin{align} S(7) &= S(7+1) - \left(6 * 2^{\left\lfloor\frac{7-1}{3}\right\rfloor}\right) \\ &= \left(132 - \left(20 * 2^{\left\lfloor\frac{8-1}{3}\right\rfloor}\right)\right) - \left(6 * 2^{\left\lfloor\frac{7-1}{3}\right\rfloor}\right) \\ &= \left(132 - \left(20 * 4\right)\right) - \left(6 * 4\right) \\ &= \left(132 - 80\right) - 24 \\ &= 52 - 24 \\ &= 28 \end{align}

• Ah no that's not the right answer but +1. Just one thing, why nobody used the fact that there's a number theoretical function involved and the relationship is very simple. – Oussama Boussif Sep 11 '15 at 23:34
• @OussamaBoussif Hmm, you made this hard for me. I really don't see the function... – Martijn Sep 11 '15 at 23:36
• If you find the function then you have your solution. At first I tought you found the answer as $S(-1)$ and $S(0)$ followed the sequence – Oussama Boussif Sep 11 '15 at 23:40
• @OussamaBoussif There was an error in my maths. I corrected it. – Martijn Sep 12 '15 at 12:07
• You got farther from the solution than you were before. – Oussama Boussif Sep 12 '15 at 12:31