wu :: forums - Print Page


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

        riddles >> easy >> divide by 17
        
(Message started by: BNC on Apr 5^th, 2003, 11:17pm)

Title: divide by 17
Post by BNC on Apr 5^th, 2003, 11:17pm

What is the smallest natural number that:
1. The sum of its digits is divisable by 17, and
2. The sum of the following number's digits also divisable by 17

Title: Re: divide by 17
Post by LZJ on Apr 6^th, 2003, 1:32am

8899?

Title: Re: divide by 17
Post by BNC on Apr 6^th, 2003, 7:16am

Yes.
How did you get it?

Title: Re: divide by 17
Post by LZJ on Apr 6^th, 2003, 7:54am

Well, logic dictates that the 2 numbers have to end off with 99 and 00, but not 999 and 000, so that when modulus 17 is taken, they will have the same remainder. The smallest possible natural number of mod 17 = 0 with this property is 8899.

Title: Re: divide by 17
Post by Noke Lieu on Mar 7^th, 2004, 7:54pm

Just to be picky,

1 is divisible by 17. You get one seventeenth.

Title: Re: divide by 17
Post by rmsgrey on Mar 8^th, 2004, 5:20am

on 03/07/04 at 19:54:07, Noke Lieu wrote:

Just to be picky,

1 is divisible by 17. You get one seventeenth.

It depends on what set of numbers you're retricting yourself to - in [bbn] or [bbz] only some numbers are divisible by 17. In any field including 17, everything is divisible by 17.

Since the question mentions natural numbers, it seems natural to restrict ourselves to functions [bbn][to][bbn]

Title: Re: divide by 17
Post by Sameer on Mar 8^th, 2004, 2:38pm

on 04/06/03 at 07:54:33, LZJ wrote:

Can you prove this? I am unable to get any answers by calculations!!!

Title: Re: divide by 17
Post by rmsgrey on Mar 9^th, 2004, 4:17am

Let f(x)=Sum of x's digits.

Then:
f(x+1)=f(x)+1-9n where x=10ⁿ-1 (mod 10ⁿ) and x[ne]10ⁿ⁺¹-1 (mod 10ⁿ⁺¹)

In other words, if x ends with a string of n 9's, then the sum of its digits gets reduced by 9n-1 when x increases by 1.

Let g(x)=f(x) (mod 17)

We want min{x[epsilon][bbn]: g(x)=g(x+1)=0}

For g(x)=g(x+1), we have 9n-1=0 (mod 17) giving n=2 (mod 17) so x must end in 99 but not 999 unless it goes on to end in 9,999,999,999,999,999,999...

g(99)=1, so we want the minimum number, y, to prefix to 99 that satisfies:
(i) g(y)=16
(ii) y[ne]9 (mod 10)

There is obviously no one digit y, and in two digits, 79 ends in a 9, leaving 88 as the least possible prefix for the 99 giving x=8899, x+1=8900.

Hopefully that fills in the gaps in LZJ's working sufficiently well for anyone interested to fill in any remaining gaps themselves.

[e]Purely cosmetic[/e]

Title: Re: divide by 17
Post by Sameer on Mar 9^th, 2004, 6:50am

Absolutely amazing rmsgrey.

However, would we be able to prove the number itself. E.g. your proof assumes we already have string of n 9s at end. Is there a proof to actually get the number itself or lead to a conclusion that there has to be n 9s at the end?

Title: Re: divide by 17
Post by rmsgrey on Mar 10^th, 2004, 4:08am

My proof assumes there is a string of n[ge]0 9s at the end. If you can find a number in [bbn] that doesn't end in a string of at least 0 9s, I'll willingly try and correct my proof.

[e]Sorry, re-read the written version of my proof, and it turns out my "purely cosmetic" revision dropped a case[/e]
[e2]Re-re-reading throws up the question of what (mod 1) means in context and probably x=10⁰-1 (mod 10⁰ holds for all x[epsilon][bbn]. Certainly the written paraphrase holds.[/e2]