Interesting Powers Of 2 - algorithm/ Math (from Hackerrank ACM APC)

Question

I came across a problem from a recent competition. I was unable to figure out a solution, and no editorial for the question is yet available.

Question Link

I am quoting the problem statement here also in case the link doesn't work.

Find the number of integers n which are greater than or equal to A and less than or equal to B (A<= n <=B) and the decimal representation of 2^n ends in n.

Ex: 2^36 = 68719476736 which ends in “36”.

INPUT

The first line contains an integer T i.e. number of test cases. T lines follow, each containing two integers A and B.

Constraints

1 <= T <= 10^5

A<=B

A,B <= 10^150

OUTPUT

Print T lines each containing the answer to the corresponding testcase.

---

Sample Input

2
36 36
100 500

Sample Output

1
0

Answer 1

As often happens on programming competitions I have come up with an heuristics I have not proven, but seems plausible. I have written a short program to find the numbers up to 1000000 and they are:

36
736
8736
48736
948736

Thus my theory is the following - each consecutive number is suffixed with the previous one and only adds one digit. Hope this will set you on the right track for the problem. Note that if my assumption is right than you only need to find 150 numbers and finding each consecutive number requires checking 9 digits that may be added.

A general advice for similar problems - always try to find the first few numbers and think of some relation.

Also often it happens on a competition that you come up with a theory like the one I propose above, but have no time to prove it. You can't afford the time to prove it. Simply hope you are right and code.

EDIT: I believe I was able to prove my conjecture above(in fact I have missed some numbers -see end of the post). First let me point out that as v3ga states in a comment the algorithm above works up until 75353432948736 as no digit can be prepended to make the new number "interesting" as per the definition you give. However I completely missed another option - you may prepend some number of 0 and then add a non-zero digit.

I will now proof a lemma:

Lemma: if a₁a₂...a_n is an interesting number and n is more than 3, then a₂...a_n also is interesting.

Proof: 2^{a₁a₂...a_n} = 2^{a₁*10n - 1}*2^{a₂a₂...a_n}

Now I will prove that 2^{a₁*10n - 1}*2^{a₂a₂...a_n} is comparable to 2^{a₂a₂...a_n} modulo 10^n-1.

To do that lets prove that 2^{a₁*10n - 1}*2^{a₂a₂...a_n} - 2^{a₂a₂...a_n} is divisible by 10^n-1.

2^{a₁*10n - 1}*2^{a₂a₂...a_n} - 2^{a₂a₂...a_n} = 2^{a₂a₂...a_n} * (2^{a₁*10n - 1} - 1) a₂a₂...a_n is more than n-1 for the values we consider.

Thus all that's left to prove to have 10^n-1 dividing the difference is that 5^n-1 divides 2^{a₁*10n - 1} - 1.
For this I will use Euler's theorem:

2^phi(5n-1) = 1 (modulo 5^n-1).

Now phi(5^n-1) = 4*(5^n-2) and for n >= 3 4*(5^n-2) will divide a₁*10^{n - 1}(actually even solely 10^{n - 1}).

Thus 2^{a₁*10n - 1} gives remainder 1 modulo 5^n-1 and so 5^n-1 divides 2^{a₁*10n - 1} - 1.

Consequently 10^n-1 divides 2^{a₂a₂...a_n} * (2^{a₁*10n - 1} - 1) and so the last n - 1 digits of 2^{a₁a₂a₂...a_n} and 2^{a₂a₃a₄...a_n} are the same.

Now as a₁a₂a₂...a_n is interesting the last n digits of 2^{a₁a₂a₂...a_n} are a₁a₂a₂...a_n and so the last n-1 digits of 2^{a₂a₃a₄...a_n} are a₂a₃a₄...a_n and consequently a₂a₃a₄...a_n is also interesting. QED.

Use this lemma and you will be able to solve the problem. Please note that you may also prepend some zeros and then add a non-zero number.