36
$\begingroup$

Here's a simple puzzle,
I know that you will find.
As long as you can count,
It shouldn't take much time.

1
1
2
1
2
2
3
1
2
2
3

Find the next 4 numbers in this sequence.

$\endgroup$
  • 1
    $\begingroup$ Why the [wordplay] tag? $\endgroup$ – Rand al'Thor Aug 17 '15 at 17:41
  • $\begingroup$ Well the "as long as you can count" was supposed to be a hint that it involved counting, as well as a very roundabout way of implying binary, but I don't remember what I was thinking when I was writing the rhyme, and that bit may have been lost when I rounded out the words. $\endgroup$ – Kingrames Aug 17 '15 at 21:08
60
$\begingroup$

Represent natural numbers in binary. Count the 1's in the binary representation.

Number Binary Number of 1's
1 1 1
2 10 1
3 11 2
4 100 1
5 101 2
6 110 2
7 111 3
8 1000 1
9 1001 2
10 1010 2
11 1011 3
12 1100 2
13 1101 3
14 1110 3
15 1111 4

Next are 2, 3, 3, 4

Inspiration

Looked at where the 1's occur. They occur at indexes 1, 2, 4, 8. After that it was simple.

$\endgroup$
  • 17
    $\begingroup$ +1 for the Inspiration-Part - It's always nice to see how people approach problems and how they get to a solution! $\endgroup$ – Falco Aug 17 '15 at 9:31
  • 6
    $\begingroup$ @Falco Thanks! I've often encountered solutions which leave you wondering how on earth could somebody think of that. I think sharing the approach is as important as posting the solution. $\endgroup$ – Rohcana Aug 17 '15 at 9:36
  • 5
    $\begingroup$ The number of 1's is also known as the Population Count or Hamming Weight. $\endgroup$ – LeppyR64 Aug 17 '15 at 17:47
16
$\begingroup$

Elements in the sequence are computed with the following recursive formula:

$a_n = \begin{cases}0, & \text{if $n \le 0$}\\a_{\frac{n}{2}}, & \text{if $n$ is even}\\ a_{n-1}+1, & \text{if $n$ is odd} \end{cases}$

Thus, the values for $a_{12}$ to $a_{15}$ are

$a_{12} = a_{6} = a_{3} = a_{2} + 1 = a_{1} + 1 = a_{0} + 1 + 1 = 2$
$a_{13} = a_{12} + 1 = 3$
$a_{14} = a_{7} = a_{6} + 1 = 3$
$a_{15} = a_{14} + 1 = 4$

$\endgroup$
  • $\begingroup$ That's interesting. I wonder if that's a more complicated way of expressing the pattern and if it holds true for more of the binary numbers. $\endgroup$ – Kingrames Aug 17 '15 at 14:28
  • 4
    $\begingroup$ @Kingrames It does indeed calculate the number of 1's in the binary representation. The operation corresponds to looking at the rightmost digit and then right-shifting (divide by two) until we come to zero. $\endgroup$ – Hjulle Aug 17 '15 at 15:20
3
$\begingroup$

Maybe not too much in the spirit of the riddle since it ignores the tag, but here is another potential continuation of the sequence:

Clearly the sequence is a level-order traversal of the binary tree
\begin{matrix}&&&(1)&&&\\&(1,2)&&&&(1,2)&\\(2,3,1,2)&&(2,3,?,?)& & (?,?,?,?)&&(?,?,?,?) \\\end{matrix}
where each node at level $n$ is a $(2^n)$-tuple $N_n=(N_{n,0},...,N_{n,2^n-1})$ which is decided by the equations \begin{gather*}N_{0,0}=1\\N_{n,i}=N_{n-1,\lfloor\frac{2^n-1-i}{2}\rfloor}+i-2\lfloor \frac{i}{2}\rfloor\end{gather*} so the next elements in the sequence are
\begin{gather*}N_{2,2}=N_{1,\lfloor\frac{1}{2}\rfloor}+2-2\lfloor \frac{2}{2}\rfloor=N_{1,0}+0=1\\N_{2,3}=N_{1,\lfloor\frac{0}{2}\rfloor}+3-2\lfloor \frac{3}{2}\rfloor=N_{1,0}+1=2\\N_{2,0}=N_{1,\lfloor\frac{3}{2}\rfloor}+0-2\lfloor \frac{0}{2}\rfloor=N_{1,1}+0=2\\N_{2,1}=N_{1,\lfloor\frac{2}{2}\rfloor}+1-2\lfloor \frac{1}{2}\rfloor=N_{1,1}+1=3\end{gather*}

$\endgroup$
1
$\begingroup$

Looks like $2, 3, 3, 4$ to me, since the first number is the head node of a binary tree. Going to the left you change nothing, but going to the right you add one. So,

  • $1$ goes to $1,2$.
  • $2$ goes to $2,3$ and
  • $3$ goes to $3,4$

So when you get to $1,2,2,3$ this can only go to $1,2,2,3,2,3,3,4$. In the statement of the problem we see $1,2,2,3$ but we don't see the next $4$ numbers, which are the solution.

$\endgroup$
  • $\begingroup$ By the way, it took me about 5 seconds to see the answer, whereas a lot of puzzles seem to take hours. Must be the way your brain is wired on the day you look at the puzzle. $\endgroup$ – Eamonn Kenny Aug 17 '15 at 15:26
0
$\begingroup$

Saw this Question Late , Anyways i recognised a pattern Take an iterator with initial value 1 , count upto n (initial value = 1). While counting repeat every number < n, n times so ,

i=1 and n=1
1
i=1 , n=2
1
2
i=1 , n=3
1
2
2
3
i=1 , n=4
1
2
2
3
3
3
4
i=1 , n=5
1
2
2
3
3
3
4
4
4
4
5

So answer is 3 , 3 , 4 , 1

$\endgroup$

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.