0
$\begingroup$

Define the sequence $x_n$ by $x_1=0$ and $$ x_n=x_{\lfloor n / 2\rfloor}+(-1)^{n(n+1) / 2} $$ for $n \geq 2$. Find the number of $n \leq 2023$ such that $x_n=0$.

My approach was the following:

To find the number of values of $n \leq 2023$ for which $x_n = 0$, we can observe some patterns in the sequence and use it to our advantage.

Let's start by calculating the first few terms of the sequence:

$x_1 = 0$ $x_2 = x_1 + (-1)^{2(2+1)/2} = 0 + (-1)^3 = -1$ $x_3 = x_1 + (-1)^{3(3+1)/2} = 0 + (-1)^6 = 1$ $x_4 = x_2 + (-1)^{4(4+1)/2} = -1 + (-1)^{10} = -1 - 1 = -2$ $x_5 = x_2 + (-1)^{5(5+1)/2} = -1 + (-1)^{15} = -1 + 1 = 0$ $x_6 = x_3 + (-1)^{6(6+1)/2} = 1 + (-1)^{21} = 1 - 1 = 0$ $x_7 = x_3 + (-1)^{7(7+1)/2} = 1 + (-1)^{28} = 1 + 1 = 2$ $x_8 = x_4 + (-1)^{8(8+1)/2} = -2 + (-1)^{36} = -2 + 1 = -1$

From the above calculations, we can observe some patterns:

  1. $x_1 = 0$
  2. $x_2 = -1$
  3. $x_3 = 1$
  4. $x_4 = -2$
  5. $x_5 = x_6 = 0$
  6. $x_7 = 2$
  7. $x_8 = -1$

We can see that the sequence repeats itself in a pattern of length 6: $0, -1, 1, -2, 0, 0$. After these initial terms, the sequence becomes periodic.

Now, to find the number of values of $n \leq 2023$ for which $x_n = 0$, we can break it down as follows:

  1. The values of $x_1, x_2, x_3, x_4, x_5, x_6$ are fixed, and they are not equal to 0.
  2. For $n \geq 7$, the sequence becomes periodic with a period of 6. Therefore, for any $n$ such that $n \geq 7$, $x_n = x_{n \mod 6 + 7}$.

Now, let's calculate the values of $x_n$ for $n = 7, 8, 9, 10, 11, 12$:

$x_7 = x_1 + (-1)^{7(7+1)/2} = 0 + (-1)^{28} = 0 + 1 = 1$ $x_8 = x_2 + (-1)^{8(8+1)/2} = -1 + (-1)^{36} = -1 + 1 = 0$ $x_9 = x_3 + (-1)^{9(9+1)/2} = 1 + (-1)^{45} = 1 - 1 = 0$ $x_{10} = x_4 + (-1)^{10(10+1)/2} = -2 + (-1)^{55} = -2 - 1 = -3$ $x_{11} = x_5 + (-1)^{11(11+1)/2} = 0 + (-1)^{66} = 0 + 1 = 1$ $x_{12} = x_6 + (-1)^{12(12+1)/2} = 0 + (-1)^{78} = 0 + 1 = 1$

Now we see that $x_8, x_9, x_{11}, x_{12}$ are equal to 0.

So, every 6th value of $n$ starting from $n = 7$ will have $x_n = 0$, i.e., $n = 7, 13, 19, 25, \ldots$.

To find the number of such values of $n$ less than or equal to 2023, we can calculate the largest value of $n$ in this sequence that is less than or equal to 2023:

$$ 7 + 6k \leq 2023 $$

Solving for $k$:

$$ 6k \leq 2016 $$

$$ k \leq 336 $$

So, there are 336 values of $k$ that satisfy this inequality. Therefore, there are 336 values of $n$ such that $x_n = 0$ and $n \leq 2023$.

$\endgroup$
6
  • $\begingroup$ I see: $x_5=x_2+(-1)^{15}=-1-1=-2$. And then $x_{10}=x_5+(-1)^{55}=-3$. For example. $\endgroup$
    – lulu
    Sep 24, 2023 at 20:58
  • 1
    $\begingroup$ What is the source of this problem? Puzzles involving the current year often appear in competitions. $\endgroup$
    – lulu
    Sep 24, 2023 at 21:01
  • $\begingroup$ It is not periodic. Indeed for $2^{2m-1} \le n \lt 2^{2m}$ you find $a_n$ is always odd and for $2^{2m} \le n \lt 2^{2m+1}$ you find $a_n$ is always even. For example, this means there can be no zeros from $a_{512}$ through to $a_{1023}$ since they are all odd. $\endgroup$
    – Henry
    Sep 24, 2023 at 21:15
  • $\begingroup$ @Henry Thanks for your comment. Do you have any ideas on how to solve this problem? I would appreciate a more detailed approach to know how this problem could be solved. $\endgroup$
    – Snowball
    Sep 24, 2023 at 21:51
  • $\begingroup$ You could simply brute-force it. Telling us the source of the problem might suggest the desired method. $\endgroup$
    – Henry
    Sep 24, 2023 at 23:25

1 Answer 1

1
$\begingroup$

Let us pick some random number $n$ and see how to compute $x_n$ in this specific case. The computer gave me:

sage: import random; n = random.choice([1000..2023])
sage: n
1399

OK, we take $n=1399$ and write it in base two.

sage: n.digits(base=2)
[1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1]

This representation is "reversed", well $n$ is seven mod eight. So: $$ n = 10101110111_{\text{base two}}\ . $$ Now we inspect $n$ and the corresponding term. I will write $x(n)$ instead of $x_n$, since the music should not be minimalized in a sub index. We have $x(n)$ defined in terms of $x(m)$ with $m={[n/2]}$, and $m$ is obtained from $n$ by deleting the last binary digit. What about the contribution of $(-1)$ to the power $n(n+1)/2$? Well, we separate into cases. For $n$ with last digits:

  • $00_{\text{base two}}$ we have $n=0$ mod four, so $n(n+1)/2$ is even, $(-1)^{n(n+1)/2}=+1$,
  • $01_{\text{base two}}$ we have $n=1$ mod four, so $n(n+1)/2$ is odd, $(-1)^{n(n+1)/2}=-1$,
  • $10_{\text{base two}}$ we have $n=2$ mod four, so $n(n+1)/2$ is odd, $(-1)^{n(n+1)/2}=-1$,
  • $11_{\text{base two}}$ we have $n=3$ mod four, so $n(n+1)/2$ is even, $(-1)^{n(n+1)/2}=+1$.

It may be useful to define $s$ to be the above function of "two binary digits", so $s(00)=s(11)=+1$, $s(01)=s(10)=-1$. So $s$ is $+1$ for two equal digits, its contribution in the recursive computation of $x_n$ is $+1$ for two equal consecutive digits, and $-1$ for ... non equal consecutive digits. So: $$ \begin{aligned} &x(1399)\\ &=x\left(10101110111_{\text{base two}}\right)\\ &=x\left(1010111011_{\text{base two}}\right) + s(11)\\ &=x\left(101011101_{\text{base two}}\right) + s(11) + s(11)\\ &=x\left(10101110_{\text{base two}}\right) + s(01) + s(11) + s(11)\\ &=x\left(1010111_{\text{base two}}\right) + s(10) + s(01) + s(11) + s(11)\\ &=x\left(101011_{\text{base two}}\right) + s(11) + s(10) + s(01) + s(11) + s(11)\\ &=x\left(10101_{\text{base two}}\right) + s(11) + s(11) + s(10) + s(01) + s(11) + s(11)\\ &=x\left(1010_{\text{base two}}\right) + s(01) + s(11) + s(11) + s(10) + s(01) + s(11) + s(11)\\ &=x\left(101_{\text{base two}}\right) + s(10) + s(01) + s(11) + s(11) + s(10) + s(01) + s(11) + s(11)\\ &=x\left(10_{\text{base two}}\right) + s(01) + s(10) + s(01) + s(11) + s(11) + s(10) + s(01) + s(11) + s(11)\\ &= \underbrace{x\left(1_{\text{base two}}\right)}_{=0} + s(10) + s(01) + s(10) + s(01) + s(11) + s(11) + s(10) + s(01) + s(11) + s(11)\ , \end{aligned} $$ So in essence, we write $n$ in base two, consider the result as a "word" in alphabet $0,1$, and count the number of

  • consecutive two letters which are equal,
  • consecutive two letters which are not equal,
    in this representation, take the difference of the counts, and check if it is zero.

Before we start solving the problem, let us check the receipt found for the first some numbers: $$ \begin{aligned} x(1) &= 0\ ,\\[2mm] x(2) &= x(10) = s(10) = 0-1=-1\ ,\\ x(3) &= x(11) = s(11) = 1-0=1\ ,\\[2mm] x(4) &= x(100) = s(10)+s(00) = 1-1=0\ ,\\ x(5) &= x(101) = s(10)+s(01) = 0-2=-2\ ,\\ x(6) &= x(110) = s(11) + s(10) =1-1=0\ ,\\ x(7) &= x(111) = s(11) + s(11) =2-0=2\ ,\\[2mm] x(8) &= x(1000) = s(10) + s(00) + s(00) =2-1=1\ ,\\ x(9) &= x(1001) = s(10) + s(00) + s(01) =1-2=-1\ ,\\ x(10) &= x(1010) = s(10) + s(01) + s(10) =0-3=-3\ ,\\ x(11) &= x(1011) = s(10) + s(01) + s(11) =1-2=-1\ ,\\ x(12) &= x(1100) = s(11) + s(10) + s(00) =2-1=1\ ,\\ x(13) &= x(1101) = s(11) + s(10) + s(01) =1-2=-1\ ,\\ x(14) &= x(1110) = s(11) + s(11) + s(10) =2-1=1\ ,\\ x(15) &= x(1111) = s(11) + s(11) + s(11) =3-0=3\ ,\\[2mm] x(16) &= x(10000) = s(10) + s(00) + s(00) + s(00) =3-1=2\ ,\\ x(17) &= x(10001) = s(10) + s(00) + s(00) + s(01) =2-2=0\ ,\\ x(18) &= x(10010) = s(10) + s(00) + s(01) + s(10) =1-3=-2\ ,\\ x(19) &= x(10011) = s(10) + s(00) + s(01) + s(11) =2-2=0\ ,\\ x(20) &= x(10100) = s(10) + s(01) + s(10) + s(00) =1-3=-2\ ,\\ x(21) &= x(10101) = s(10) + s(01) + s(10) + s(01) =0-4=-4\ , \end{aligned} $$ and so on. We can draw some conclusions. If the number of the $s$-terms is odd, we cannot get the difference result zero. So there are no $n$ values with $x(n)=0$ for $n$ in the ranges:

  • $n$ between $2=2^1$ and $3=2^2-1$,
  • $n$ between $8=2^3$ and $15=2^4-1$,
  • $n$ between $32=2^5$ and $63=2^6-1$,
  • $n$ between $128=2^7$ and $255=2^8-1$,
  • $n$ between $512=2^9$ and $1023=2^{10}-1$,
  • $n$ between $2048=2^{11}$ and $4095=2^{12}-1$, and so on.

Now we are ready to start. I will call simply a pair a "subword" of length two in the (word of the) binary representation of a number. We count the $n$'s with equal pairs of the shape $AA$, and of the shape $AB$, $A\ne B$. Such an $n$ has an even number of pairs. Thus an odd number of digits, call it $d$. The first digit is one. We follow the word from the next place, the "second place" to the "last place" in its writing. We mark with a star the positions in the word where the second letter in the pair coincides with the first one. The other are not marked, so there is a blank - and if we want to still mark somehow the place, there will be a small dot. The first position remains unmarked. In case of $x(n)=0$ we have an equal number of blanks and stars. We count these words. Looking at only the positions of the stars we obtain a subset of the index set $(d-1),\dots,3,2,1,0$. Conversely, if such a subset is given, we can complete $n$ in a unique manner, so that the stars associated to $n$ are in the given position.

Example:

Consider the numbers $n$ between $256=2^8$ and $511=2^9-1$. Each of them needs $d=$nine digits. The first digit is $a_8=$one. So $n$ is written like: $$ \overline{1a_7a_6a_5a_4a_3a_2a_1a_0}_{\text{base two}}=2^8+a_7\cdot 2^7+\dots+a_1\cdot 2+a_0\ .$$ Fix some subset with four elements in the index set $\{7,6,5,4,3,2,1,0\}$. For instance $7,4,3,1$. Then $7$ is a star place, so $a_7=a_8=1$. And $6$ is not a star place, so $a_6\ne a_7=1$, so $a_6=0$. And $a_5\ne a_6$, so $a_5=1$. And $4$ is on a star place, so $a_4=a_5=1$. Then $3$ is also on a star place, so $a_3=a_4=1$. And $a_2\ne a_3$, so $a_2=0$. And $1$ is on a star place, so $a_1=a_2=0$. Finally $a_0\ne a_1$, so $a_0=1$.

In a picture:

110111001
 *  ** *

How many such "good" numbers are thus in the range from $256$ to $511$? Exactly $\binom84=\frac{8\cdot7\cdot6\cdot5}{4\cdot3\cdot2\cdot1}=7\cdot 2\cdot 5=70$.


Which are explicitly the "good" numbers with $d=5$ digits? We search for star patterns on the relevant last four places. Blanks are dots. Here they are:

..** 10111 = 23
.*.* 10011 = 19
*..* 11011 = 27
.**. 10001 = 17
*.*. 11001 = 25
**.. 11101 = 29

How many such good numbers are between one and $2048$? Exactly: $$ \underbrace{\binom00}_{1} + \underbrace{\binom21}_{4,6} + \underbrace{\binom42}_{17,19,23,25,27,29} + \underbrace{\binom63}_{68,\dots,122} + \underbrace{\binom84}_{261,\dots,501} + \underbrace{\binom{10}5}_{1034,\dots,2026} \ . $$


For some reasons, the problems wants us to stop at $2023$, so we miss exactly one "good" number, the greatest one. This greatest one is obtained by insisting to start with "ones" (as digits)

1|11111|?????|
  *****

so the five stars are consumed, we need only blanks/dots after, and the number is

1|11111|01010| = 1 11111 11111 - 10101 = 2047 - (16+4+1) = 2026 .
  ***** .....

(The numbers $2024$ and $2025$ also have the pattern $1\ 11111\ ?????$ but introduce in the last five digits further equal pairs. So we miss only the $2026$ when we stop at $2023$.)


So the answer to the problem is: $$ \bbox[yellow]{\qquad \binom 00 + \binom 21 + \binom 42 + \binom 63 + \binom 84 + \binom {10}5 - 1 \\ = 1+2+6+20+70+252-1 = 350\ .\qquad} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .