Hide

Problem G
Sheldon Numbers

/problems/sheldon/file/statement/en/img-0001.jpg

According to Sheldon Cooper, the best number is $73$. In his own words, “The best number is $73$. $73$ is the $21$st prime number. Its mirror, $37$, is the $12$th, 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 boring stuff, and so are palindromes. On the other hand, the binary representation of $73$ is rather remarkable: it’s $1$ one followed by $2$ zeroes, followed by $1$ one, followed by $2$ zeros, followed by $1$ one. This is an interesting pattern that we can generalize: $N$ ones, followed by $M$ zeros, followed by $N$ ones, followed by $M$ zeros, etc, ending in either $N$ ones or $M$ zeroes. For $73$, $N$ is $1$, $M$ is $2$, and there are $5$ runs of equal symbols. With $N = 2$, $M = 1$ and $4$ runs, we would have the string $110110$, which is the binary representation of $54$.

Acknowledging Sheldon’s powerful insight, let us introduce the concept of a Sheldon number: a positive integer whose binary representation matches the pattern $ABABAB\ldots ABA$ or the pattern $ABABAB\ldots AB$, where all the occurrences of $A$ represent a string with $N$ occurrences of the bit $1$ and where all the occurrences of $B$ represent a string with $M$ occurrences of the bit $0$, with $N > 0$ and $M > 0$. Furthermore, in the representation, there must be at least one occurrence of the string $A$ (but the number of occurrences of the string $B$ may be zero).

Many important numbers are Sheldon numbers: $1755$, the year of the great Lisbon earthquake, $1984$, of Orwellian fame, and $2015$, the current year! Also, $21$, which Sheldon mentions, is a Sheldon number, and so is $42$, the answer given by the Deep Thought computer to the Great Question of Life, the Universe and Everything.

Clearly, there is an infinite number of Sheldon numbers, but are they more dense or less dense than prime numbers?

Task

Your task is to write a program that, given two positive integers, computes the number of Sheldon numbers that exist in the range defined by the given numbers.

Input

The input contains one line, with two space separated integer numbers, $X$ and $Y$.

Constraints

$0 \leq X \leq Y < 2^{63}$

Output

The output contains one line, with one number, representing the number of Sheldon numbers that are greater or equal to $X$ and less or equal to $Y$.

Sample Output Explanation

In the first sample, all numbers between $1$ and $10$ are Sheldon Numbers. In the second sample, $73$ is the only Sheldon number in the given range.

Sample Input 1 Sample Output 1
1 10
10
Sample Input 2 Sample Output 2
70 75
1

Please log in to submit a solution to this problem

Log in