Date: Sat, 22 Jun 1996 16:53:18 +0200
To: rusin@math.niu.edu (Dave Rusin)
From: pak00453@pixie.co.za (David Franklin)
Subject: Re: Representation of multiples of 5^n
David,
Thanks for the analysis.
This problem with n assigned a particular value - it was equal to
the year then current, 199? I think - was given to school pupils in the
USSR in a national competition. Unless there was a misprint, the base _was_
5 in the problem; I don't think a base coprime to 10 would have been chosen
as the problem would then have been too close to familiar ones.
I keep thinking we must be missing some simple solution - though
not, to me, a very obvious one.
I'll let you know if anyone comes up with anything.
Thanks again.
David.
==============================================================================
From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Representation of multiples of 5^n - affirmative answer.
Date: 25 Jun 1996 19:14:17 GMT
It was recently asked in this group if every power of 5 has a multiple
whose base-10 expansion is free of zeros. The answer is "yes", and
the reasoning is elementary, so these ideas may already have been posted.
(The discussion seems to have rolled off my system's spool.)
We will find a multiple of 5^n which is zero-free in increasingly
large portions of its right-hand end (the least-significant digits side).
Clearly 5^n is congruent to 5 mod 10 for all n>0, so the last
digit is not a zero as long as we multiply 5^n by any odd integer.
In particular of course we can multiply it by M=1!
Assume by induction that 5^n * M has no zeros among its last d digits,
and that M < 2^d and that d <= n.
If the (d+1)-st digit is nonzero, do nothing; otherwise replace M with
M' = M+2^d. Clearly 5^n*M' is congruent to 5^n*M mod 10^d, so the
last d digits are not changed (and so are not zero) but the (d+1)-st digit
from the end is different (and thus now nonzero) since
5^n*M' = 5^n*M + 10^d*(5^(n-d)); this last summand has a 5 as its last
non-zero digit (or a 1, if n=d).
Observe that our new M' is by induction less than 2^(d+1). Thus we
may repeat this argument to find a multiple 5^n * M with no zeros
among its last n+1 digits, with M < 2^(n+1). But such a multiple
is less than 2*10^n, and so has at most n+1 digits anyway. Thus
it's zero-free.
Example: 5^93 has a couple of high zeros (it's just over 10^65):
100974195868289511092701256356196637398170423693954944610595703125
The procedure above finds the multiplier
M=2^0+2^4+2^9+2^10+2^12+2^13+2^18+2^29+2^36+2^40+2^42+2^48+2^56+2^68+2^69+
+2^76+2^79+2^80+2^87
giving a 92-digit multiple of 5^93 with no zeros in its decimal expansion.
As I'm sure others have noticed, the problem is only non-trivial since
5 is not coprime with the base; each power of 7, for example, divides
some integer of the form 10^k - 1, providing easy zero-free multiples
of the powers of 7.
dave