wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> String of Nines
        
(Message started by: Sir Col on Jun 20^th, 2003, 12:30pm)

Title: String of Nines
Post by Sir Col on Jun 20^th, 2003, 12:30pm

Given that k is a positive odd integer, prove that
(i) 9^k ends in 9.
(ii) 99^k ends in 99.
(iii) 999^k ends in 999.

Generalise.

Title: Re: String of Nines
Post by NickH on Jun 20^th, 2003, 1:20pm

::[hide]
It follows by considering the results, respectively, mod 10, mod 100, mod 1000. For example, for (iii), (-1)^k = -1 (mod 1000) if k is odd. (And equals 1 if k is even, of course.) Generally, (-1)^k = -1 (mod a^r) if k is odd, so the number represented in base a by a string of r (a-1)s will end in the same string of (a-1)s when raised to an odd power. (If a is an integer > 1.)

Could also be proved using the binomial theorem.
[/hide]
::

Title: Re: String of Nines
Post by Sir Col on Jun 20^th, 2003, 1:42pm

Nice proof, NickH.

::
[hide]Of course, your conguence base 10ⁿ method is a simplification of the binomial theorem approach anyway.

For odd k,
(10ⁿ–1)^k=(10ⁿ)^k–k(10ⁿ)^k–1+...+k(10ⁿ)–1=(10ⁿ)Q–1==–1 mod (10ⁿ).[/hide]
::

Title: Re: String of Nines
Post by Sir Col on Jun 20^th, 2003, 6:19pm

It can be verified that 9⁹ is a 9 digit number, but 99⁴⁹ has 98 digits and 99⁵⁰ has 100 digits.

Can you find a value for k, where k is a natural number, such that 999^k contains 999 digits?

What about (10^m–1)^k, containing 10^m–1 digits?

Title: Re: String of Nines
Post by LZJ on Jun 21^st, 2003, 8:37am

For 999³, I suspect that k = 999/3.
Furthermore, for (10^m - 1)^k, k is only a natural number if (10^m - 1)/m is a natural number (ie k = (10^m - 1)/m) ...but I still need to work on it to be sure...

Title: Re: String of Nines
Post by NickH on Jun 22^nd, 2003, 5:46am

I think LZJ's result is correct...
::[hide]
We require 10^{10^m-2} <= (10^m - 1)^k < 10^{10^m-1}
Using the binomial theorem, (10^m - 1)^k = 10^mk(1 - C(k,1)/10^m + C(k,2)/10^2m - ...)
If k = (10^m - 1)/m, then C(k,1) < 10^m, and it can easily be shown that C(k,i+1)/C(k,i) < 10^m, for 1 < i < k.
With a bit of hand waving (regarding the alternating signs, for one), the result follows.
[/hide]::

Title: Re: String of Nines
Post by Sir Col on Jun 22^nd, 2003, 4:52pm

Good spot, LZJ! It's a really nice result and surprising, isn't it?

I like your method, NickH, although a deductive proof that leads to the solution would be nice. Perhaps someone can tidy up my 'proof' (I don't the hand waving that I do towards the end):

(10^m–1)^k lies between two consecutive perfect powers of 10.
10^a < (10^m–1)^k < 10^a+1

Solving 10^b = (10^m–1)^k

b=k log(10^m–1)

As a<b<a+1, it follows that a=[b] (the integer part function).

Therefore a=[k log(10^m–1)].

As m–1<log(10^m–1)<m, and is incredibly close to m...

*waves magic wand*
[k log(10^m–1)]=km–1 (I know, it's shameful, but it is true).

As 10^a contains a+1 digits and we wish our number to contain 10^m–1 digits, a=10^m–2.

Therefore a=km–1=10^m–2.

Hence k=(10^m–1)/m.