2
$\begingroup$

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

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

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$

$\endgroup$
  • $\begingroup$ I looked at this Wikipedia page... Good job on figuring this out! $\endgroup$ – Martijn Sep 12 '15 at 22:31
  • $\begingroup$ 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) $\endgroup$ – Rohcana Sep 13 '15 at 6:06
  • $\begingroup$ Bravo that's the right answer pal $\endgroup$ – Oussama Boussif Sep 14 '15 at 21:01
6
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Oussama Boussif Sep 10 '15 at 9:41
  • 5
    $\begingroup$ @OussamaBoussif Simple is better than complicated, otherwise we can just use polynomial fittings for any sequence question. $\endgroup$ – Rohcana Sep 10 '15 at 9:44
  • $\begingroup$ It's not very compmicated. No polynomials or series are involved here. Well I think this time for a new hint $\endgroup$ – Oussama Boussif Sep 10 '15 at 9:50
  • 1
    $\begingroup$ @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. $\endgroup$ – Rohcana Sep 10 '15 at 9:51
  • $\begingroup$ Well look at the new hint and see what you can do. $\endgroup$ – Oussama Boussif Sep 10 '15 at 9:52
4
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Oussama Boussif Sep 11 '15 at 23:34
  • $\begingroup$ @OussamaBoussif Hmm, you made this hard for me. I really don't see the function... $\endgroup$ – Martijn Sep 11 '15 at 23:36
  • $\begingroup$ 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 $\endgroup$ – Oussama Boussif Sep 11 '15 at 23:40
  • $\begingroup$ @OussamaBoussif There was an error in my maths. I corrected it. $\endgroup$ – Martijn Sep 12 '15 at 12:07
  • $\begingroup$ You got farther from the solution than you were before. $\endgroup$ – Oussama Boussif Sep 12 '15 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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