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