Find the $1717$th term of the sequence of positive integers whose binary representation reads the same left to right as right to left.

67 Views Asked by At

The question is to find the number of $1$'s in the $1717$th term.

I solved it but my method is not elegant IMO and it goes like this.

Let the number of digits in one binary representation in this pattern be $x$. Let $f(x)$ be the amount of representations having $x$ digits.

Then $f(1)=f(2)=1$, $f(3)=f(4)=2$, $f(5)=f(6)=4=2^2, f(7)=f(8)=8=2^3 \cdots \cdots$

So, $2^n$ gives the amount of the binary representations with $2n+2$ and $2n+1$ digits.

And $1+1+2+2+\cdots 2^n+2^n=2(2^{n+1}-1)$ gives the total number of the binary representations from $1$-digit representation to $2n$-digit representations.

Hence, $2(2^{n+1}-1)=1717$, so $512\le 2^{n+1}=859.5\le 1024$. That means $8\le n\le 9$.

Until $n=8$, there are altogether $2(2^9-1)=1022$ numbers, and until $n=9$ there are altogether $2046$ numbers.

So, for the $1717$th term, it corresponds to $n=9$. Since there are $1024$ terms in the case where $n=9$, which is corresponding to $512$ representations with $19$ and another $512$ representations with $20$ digits, the $1717$th term should have $20$ digits, and it is in fact the $1717-512-1022=183$th term starting from the first $20$-digit representation.

Then since every representation is symmetric, we only need to consider what is going on in the first 10 digits.

Since it must start with $1$, and for each digit, it can be either $0$ or $1$, the $k$ in $2^k<183, k\in \mathbb Z$ implies where the "highest" $1$ is other than the starting $1$.

Since $k=8$, it is 1 _ 1 _ _ _ _ _ _ _.

Then since $2^{k_1}<183-128$ that means $k_1=5$, the representation is 1 _ 1 _ _ 1 _ _ _ _.

Similarly, I finally got 1 _ 1 _ _ 1 1 _ 1 1. That means the $1717$th term will have $12$ $1$'s.

Ok now could anyone offer a more elegant method?

1

There are 1 best solutions below

0
On

You need to find a way of calculating exactly the first half of the binary representation knowing the place, in this case $1717$. If you create the sequence of numbers that give you only the first half you find this one: A162751. There are some good properties about it, the most important one is that for $i \geq 2$ we have $a(2^i-1) = 2^{i-1}$. You could prove this by induction, having in mind that each "cycle" that we see in the sequence is just writing numbers with odd $0$ and $1$s in its binary representation first (which we know there is a particular power of $2$ of them) and after that the same repeated sequence but for ones with even number of $0$ and $1$. So you end up ending each cycle after a power of $2$, so it's natural to have a formula like the one before.

Now you can use this to obtain $a(1023) = 512$. We know the sequence of $512$ numbers after this one repeats, and we notice $1717$ is in the second half. We need to know where exactly it ends. You can see that the cycle repeats exactly in $2^i - 1 + 2^{i-1}$, in this case $i=10$ and it repeats in $1535 = 1023+512$, so $a(1535) = 512$. Until $1717$ the sequence just adds one, so $a(1717) = a(1535) + 1717-1535 = 512+182 = 694$. If you count the number of this number in binary ($1010110110$) you're counting the number of $1$ in the first half, so take that number, in this case six $1$, and double it to obtain $12$ ones.