Sheldon Numbers

According to Sheldon Cooper, the best number is 73. In his own words: "The best number is 73. 73 is the 21st prime number. Its mirror, 37, is the 12th, and its mirror, 21, is the product of multiplying 7 and 3. In binary, 73 is a palindrome: 1001001, which backwards is 1001001. Exactly the same."

Prime numbers are familiar ground, and so are palindromes. The binary representation of 73 holds one more rule worth noting: 1 one, then 2 zeros, then 1 one, then 2 zeros, then 1 one. That rule generalizes. Put $N$ ones, then $M$ zeros, then $N$ ones, then $M$ zeros, and so on, ending in either a block of $N$ ones or a block of $M$ zeros. For 73, $N$ is 1, $M$ is 2, and there are 5 blocks of equal symbols. With $N = 2$, $M = 1$ and 4 blocks you get the string 110110, which is the binary representation of 54.

This gives the notion of a Sheldon number: a positive integer whose binary representation matches the pattern $ABABAB \dots ABA$ or the pattern $ABABAB \dots AB$, where every occurrence of $A$ is a string of $N$ bits 1 and every occurrence of $B$ is a string of $M$ bits 0, with $N > 0$ and $M > 0$. The representation must contain at least one occurrence of $A$, but the number of occurrences of $B$ may be zero.

Many well known numbers are Sheldon numbers: 1755, the year of the great Lisbon earthquake, 1984, the title of Orwell's novel, and 2015. So is 21, which Sheldon mentions, and so is 42, the answer given by the computer Deep Thought to the Great Question of Life, the Universe and Everything.

There are infinitely many Sheldon numbers. Given two integers, write a program that counts the Sheldon numbers in the range they define.

The input contains one line with two space separated integers $X$ and $Y$.

Print one line with the number of Sheldon numbers that are greater than or equal to $X$ and less than or equal to $Y$.

• $0 \le X \le Y < 2^{63}$