18 zeros in a power of two - again

[Clive Tooth]

I am looking for 18 consecutive zeros in a power of two.

I have implemented Christian Bau's method described here...
http://mathforum.org/kb/message.jspa?messageID=7761205

In particular, I am doing the calculation in base 10^9 and at each
step I am usually multiplying by 2^34. [It is nice the way that this
*just* fits into a 64 bit computation: 10^9 ~ 2^29.9, so we need 63.9
bits.]

On each iteration of the program we either multiply the current power
of two by 2^34, or we just double it. [At the moment, about one step
in about 2000 is a doubling step.]

Having got the next power of two we look for runs of 11, or more,
zeros. Obviously if this run contains 18, or more, digits we are done.
Otherwise, for each such run we do the following:

Let us call the digit just to the left of the run of zeros the
critical digit.

If the critical digit is a '5' we mark the next iteration to be a
doubling step.

Else... If the critical digit is odd, there is nothing special to do.

Else... (the critical digit is even) We may, in multiplying by 2^34,
have skipped over a run of 18 consecutive zeros. This could have
occurred at most 23 powers of two ago. The program takes the 32 digits
to the left of the run of zeros and converts it into binary (using
just 32 bit arithmetic). It then determines the number of trailing
binary zeros in that number. Call this number n. It is the number of
powers of two ago where the longest run of zeros occurred. [There may
also be runs of the same length either side of it.] The program then
divides the number (the first 9 or so digits of it) to the right of
the run of zeros by 2^n, and looks at its decimal string, to see how
many digits would have been lost during the n doubling steps.

Here is an example:

2^1,406,303,961 [a numbers with about 420 million digits] contains a
run of 11 zeros. Here it is, with its surrounding digits:

...199274408961651218304274536535559916800000000000957388714057606...

So the critical digit is an '8'. The last 32 bits of the binary value
of 1992744089616512183042745365355599168 are (in hexadecimal)
e64c9540. That bit string has 6 trailing zeros.

Dividing
957388714057606 (the number to the right of the zeros) by 2^6 gives
14959198657150

So, 6 powers ago, the power of two would have had a run of 12 zeros.

In summary...

5355599168000000000009573887140: current power, 11 zeros
6333681237000000000000149591986: 6 powers ago, 12 zeros
8166840618500000000000074795993: 7 powers ago, also 12 zeros
4083420309250000000000037397996: 8 powers ago, 11 zeros
etc

--
Clive Tooth