# A very simple puzzle: 1,1,2,1,2,2,3

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.

• Why the [wordplay] tag? – Rand al'Thor Aug 17 '15 at 17:41
• 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. – Kingrames Aug 17 '15 at 21:08

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.

• +1 for the Inspiration-Part - It's always nice to see how people approach problems and how they get to a solution! – Falco Aug 17 '15 at 9:31
• @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. – Rohcana Aug 17 '15 at 9:36
• The number of 1's is also known as the Population Count or Hamming Weight. – LeppyR64 Aug 17 '15 at 17:47

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$

• 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. – Kingrames Aug 17 '15 at 14:28
• @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. – Hjulle Aug 17 '15 at 15:20

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

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.

• 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. – Eamonn Kenny Aug 17 '15 at 15:26

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