|
|
Re: Runs of zeros in the decimal representation of powers of two
Posted:
Apr 3, 2012 7:23 PM
|
|
I've given this a bit more thought.
Let's say 10^n has 18 consecutive zeroes. Then for example 10^(n+23)
will still have 11 consecutive zeroes, because the digits right of the
first of the zeroes have been multiplied by 2^23 < 10^7, so at most 7
zeroes are gone. We can also show that 10^(n-10) must have 11
consecutive zeroes: Multiplying by 2 can create only one zero digit,
not two. So multiplying by 2^10 could have created only 10 zero
digits, so 8 zero digits must have been there already. But the digits
to the right of the first of the 18 zero digits must have a value <
1/1024 or we would have created a new non-zero digit, so there must
have been 3 zero digits to the right as well, for a total of 11.
Instead of the number 11 we can choose any number, and we get this
table:
2^(n-1) .. 2^(n+3): 17 zero digits
2^(n-2) .. 2^(n+6): 16 zero digits
2^(n-3) .. 2^(n+9): 15 zero digits
2^(n-5) .. 2^(n+13): 14 zero digits
2^(n-7) .. 2^(n+16): 13 zero digits
2^(n-8) .. 2^(n+19): 12 zero digits
2^(n-10) .. 2^(n+23): 11 zero digits
2^(n-11) .. 2^(n+26): 10 zero digits
2^(n-12) .. 2^(n+29): 9 zero digits
2^(n-14) .. 2^(n+33): 8 zero digits
2^(n-15) .. 2^(n+36): 7 zero digits
2^(n-17) .. 2^(n+39): 6 zero digits
So we can multiply for example by 2^34 at each step and check for 11
consecutive zeroes, and if we don't find them then there cannot be 18
consecutive zeroes.
We do the calculation in base 10^k. Checking for k+1 or k+2
consecutive zero digits is not trivial, but very fast: If there are k
+1 or k+2 consecutive zero digits, then the highest two or three
digits of some base 10^k number must both be zero. And that happens
only in one in 100 or 1 in 1000 cases.
This works out quite well if we choose k = 9 and n = 34: Do the
calculation in base 10^9. At each step we multiply by 2^34. We look
for sequences with 11 consecutive zeroes; this can only happen if one
of the base 10^9 digits is less than 10^6, which happens only in one
in 1000 cases. When that happens you can check
bool elevenzeroes;
if (number > 99999) elevenzeroes = (next % 100000000 == 0);
else if (number > 9999) elevenzeroes = (next % 10000000 == 0);
else if (number > 999) elevenzeroes = (next % 1000000 == 0);
else if (number > 99) elevenzeroes = (next % 100000 == 0);
else if (number > 9) elevenzeroes = (next % 10000 == 0);
else if (number > 0) elevenzeroes = (next % 1000 == 0);
else elevenzeroes = (previous <= 9999999 || (previous <= 99999999
&& next % 10 == 0) || next % 100 == 0);
This checks for 11 consecutive zeroes, which will be exceedingly rare.
We need to keep part of the previous result around in case you found
11 consecutive zeroes and have to check for 18 digits.
|
|
