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

        riddles >> easy >> Smallest Positive Integer
        
(Message started by: THUDandBLUNDER on May 11th, 2004, 7:14pm)
Title: Smallest Positive Integer
Post by THUDandBLUNDER on May 11th, 2004, 7:14pm
What is the smallest positive integer divisible by 225 that can be expressed using only zeroes and ones?

Title: Re: Smallest Positive Integer
Post by Cathos on May 11th, 2004, 7:55pm
Can't any number be expressed using zeros and ones if you have enough of them?
Title: Re: Smallest Positive Integer
Post by BNC on May 11th, 2004, 10:14pm

on 05/11/04 at 19:55:56, Cathos wrote:
Can't any number be expressed using zeros and ones if you have enough of them?


I assume he means in decimal notation. I also assume he means a number > 0.

My thinking:
::[hide]
A number divisible by 225 must end with either 5 or 0. To meet the conditions of the problem, it has to end with 0, hence be divisible by 450.

So, we have a number XX..XX0 that is divisible by 450. Dividing both by 10, we're looking for a number composed of 1's and 0's that is divisible by 45.

A number divisible by 45 is divisible by 9 and 5. The "5" meens it ends with 0. To be divisible by 9, the sum of the digits must be a divisible by 9. Since the number ends with 0, the rest of the digits (1's and 0's) must add to at least 9. That is, 9 1's.
This number is obviously 1111111110.

The number answering the original riddle is 11111111100.
[/hide]::
Title: Re: Smallest Positive Integer
Post by THUDandBLUNDER on May 12th, 2004, 6:43am
Well done, BNC.


Quote:
I also assume he means a number > 0.

Yes, the smallest 'positive integer' > 0    ::)
Title: Re: Smallest Positive Integer
Post by BNC on May 12th, 2004, 1:08pm

on 05/12/04 at 06:43:42, THUDandBLUNDER wrote:
Yes, the smallest 'positive integer' > 0    ::)


;D ;D ;D
Title: Re: Smallest Positive Integer
Post by Eigenray on May 12th, 2004, 10:35pm
Is it true that, for any base b, and any integer n, there exists an integer multiple of n that uses only the digits 0 and 1 when written in base b?

Harder: What about other sets of digits?
Title: Re: Smallest Positive Integer
Post by Barukh on May 13th, 2004, 8:44am

on 05/12/04 at 22:35:33, Eigenray wrote:
Is it true that, for any base b, and any integer n, there exists an integer multiple of n that uses only the digits 0 and 1 when written in base b?

[smiley=blacksquare.gif][hide]
The answer is yes. It is sufficient to consider the case when n and b are co-prime.

According to Euler's theorem, there exists an integer p such that bp = 1 (mod n). Then,  bp + b2p… + bnp is divisible by n and uses only digit 0 and 1 (base b).
[/hide][smiley=blacksquare.gif]
Title: Re: Smallest Positive Integer
Post by Eigenray on May 13th, 2004, 8:46pm
That's the same proof I first came up with, Barukh, but there's a more elementary proof that also gives a much better upper bound on the multiple.

Of course, it follows that it's always possible with [hide]0 and any other digit[/hide].
So let's suppose that [hide]0 is not allowed.  Then we obviously can't write any multiple of b in base b, for example[/hide].
A necessary condition is that [hide]at least one of the allowed digits be divisible by gcd(b,n).  (If 0 is allowed, this will always be true.  Otherwise, there will always be pairs b,n for which it fails.)[/hide]
A sufficient condition is that [hide]gcd(n,b)=1.  Then it's possible using just the digit 1, and therefore also using just any single digit.[/hide]
I don't know any necessary and sufficient conditions though.
Title: Re: Smallest Positive Integer
Post by TenaliRaman on May 14th, 2004, 10:40am
Answer to original Q,
::[hide]11111111100[/hide]::
Title: Re: Smallest Positive Integer
Post by Barukh on May 15th, 2004, 10:18am

on 05/13/04 at 20:46:07, Eigenray wrote:
...but there's a more elementary proof that also gives a much better upper bound on the multiple.

Yes, of course! I wish it took me less time to figure it out…  :D

[smiley=blacksquare.gif][hide]
Consider n b-ary numbers 1, 11, 111, 1…1.

If all numbers are different modulo n, then one is a multiple of n, and we are done.

If two numbers are equal modulo n, then their difference is a multiple of n and has the form 1…10…0.
[/hide][smiley=blacksquare.gif]
Title: Re: Smallest Positive Integer
Post by TenaliRaman on May 16th, 2004, 1:16am
How elementary indeed!
c'est merveilleux!
PHP is so simple yet so powerful to prove some of the wonderful things.
Title: Re: Smallest Positive Integer
Post by Sir Col on May 17th, 2004, 1:45pm
(Thanks for the original problem, T&B)


I'd been avoiding this thread since Eigenray posted the extension to the original problem (thanks!) in an attempt to solve it. Alas, I was unsuccessful... so I peeked!

Cor! you're good, Barukh!

The best I could manage was the case for primes, which interestingly is similar to your first method, Barukh. My attempt went as follows...

By Fermat's Little Theorem, 10p–1[equiv]1 mod p (working in base 10 here).
As 10k(p–1)[equiv]1 mod p, N=10p–1+102(p–1)+...+10p(p–1)[equiv]1+1+...+1=p mod p.
That is, N consists entirely of 1's and 0's, and is divisible by p.

Your final solution was truly inspired, Barukh!

I know in light of that solution your first solution is redundant, but I do have a query about your choice of the (Fermat-)Euler Theorem.

It is true that b[phi](n)[equiv]1 mod n, where [phi](n) is Euler's Totient function (the number of numbers less than n which are co-prime), and it necessary that b and n are co-prime (which you stated). I'm probably being stupid, but why is it sufficient to only consider this case? For example, what about b=10, n=14? [phi](14)=6, and 106[equiv]8 mod 14.


TenaliRaman, what does PHP stand for? I only know of the recursive acronym, PHP:Hypertext Preprocessor (the scripting language).
Title: Re: Smallest Positive Integer
Post by Leonid Broukhis on May 17th, 2004, 5:28pm

on 05/17/04 at 13:45:11, Sir Col wrote:
(Thanks for the original problem, T&B)

TenaliRaman, what does PHP stand for? I only know of the recursive acronym, PHP:Hypertext Preprocessor (the scripting language).


It stands for whatever returned by acronymfinder.com, modulo spelling errors.
Title: Re: Smallest Positive Integer
Post by TenaliRaman on May 17th, 2004, 6:21pm

Quote:
It stands for whatever returned by acronymfinder.com, modulo spelling errors.

hehe,
or just PigeonHole Principle
(PigeonHole Principal, acronymfinder spelling  :D)
Title: Re: Smallest Positive Integer
Post by Barukh on May 19th, 2004, 7:38am

on 05/17/04 at 13:45:11, Sir Col wrote:
I know in light of that solution your first solution is redundant, but I do have a query about your choice of the (Fermat-)Euler Theorem.

It is true that b[phi](n)[equiv]1 mod n, where [phi](n) is Euler's Totient function (the number of numbers less than n which are co-prime), and it necessary that b and n are co-prime (which you stated). I'm probably being stupid, but why is it sufficient to only consider this case? For example, what about b=10, n=14? [phi](14)=6, and 106[equiv]8 mod 14.


Sir Col, I am sorry I didn't notice your question... Well, probably I was too fast to claim this. Currently, I don't see a nice demonstration.  :(
Title: Re: Smallest Positive Integer
Post by Aryabhatta on May 19th, 2004, 9:33am
Sir Col wrote:
>I know in light of that solution your first solution is
>redundant, but I do have a query about your choice of the
>(Fermat-)Euler Theorem.


>It is true that b^phi(n) = 1 mod n, where phi(n) is Euler's
> Totient function (the number of numbers less than n which
> are co-prime), and it necessary that b and n are coprime
> (which you stated). I'm probably being stupid, but why is it
> sufficient to only consider this case? For example,what
> about b=10, n=14? phi(14)=6, and 10^6 = 8 mod 14.  


if gcd(n,b) = g.
Then some multiple of n/g has only 1's and 0's base b.
since g divides b, some multiple of g is a power of b.
so some multiple of n/g*g = n has only 1's and 0's base b.

So i guess it is sufficient.
Title: Re: Smallest Positive Integer
Post by Leon on May 19th, 2004, 3:12pm
How about:

a) What is the smallest positive integer divisible by 41 that can be expressed using only zeroes and ones?

b) What is the smallest positive integer divisible by 14 that can be expressed using only zeroes and ones?

big hint:[hide]I discovered digital roots while reading "Scientific American Book of Mathematical puzzles and diversions" printed in 1961, remembered this post and started playing with them.They are very interesting[/hide]:
Title: Re: Smallest Positive Integer
Post by Sir Col on May 19th, 2004, 4:46pm

on 05/19/04 at 09:33:33, Aryabhatta wrote:
if gcd(n,b) = g.
Then some multiple of n/g has only 1's and 0's base b.
since g divides b, some multiple of g is a power of b.
so some multiple of n/g*g = n has only 1's and 0's base b.

So i guess it is sufficient.

I might still be missing something here, but...

Let p=[phi](n)
If (b,n)=1, then bp[equiv]1 mod n.
Barukh's method depended on this, so that bkp[equiv]1 mod n, and the sum of n such powers would be congruent with zero modulo n.

If (b,n)=g, (b/g,n)=1, so (b/g)p[equiv]1 mod n, but this fails as b/g will not consist of ones and zeros (unless g=b).



Leon, I agree the results are really interesting. I've done an analysis of the cases for the smallest n consisting of ones and zeros that is divisible by d. However, I've not managed to find a method, other than a brute search, to obtain the minimal case. Has anyone else done a similar thing with any success? I'll post my data next time I get a chance.
Title: Re: Smallest Positive Integer
Post by Leon on May 19th, 2004, 5:04pm

on 05/19/04 at 16:46:47, Sir Col wrote:
Leon, I agree the results are really interesting. I've done an analysis of the cases for the smallest n consisting of ones and zeros that is divisible by d. However, I've not managed to find a method, other than a brute search, to obtain the minimal case. Has anyone else done a similar thing with any success? I'll post my data next time I get a chance.


Major spoiler for the 41 and 14 variations:
:[hide]Sir Col, what I found was to have the series of 1's for the digital root (e.g. in the original question, the digital root of 225 is 9, so you need 9 1's). The only thing I've found to indicate the number of zeros to tack on is to divide and see how many decimal places the answer has. Add that many zeros and you have the answer.

For example, using 22. The digital root is 4.
4 1's = 1,111.
1,111 / 22 = 50.5. That is one decimal place.
The answer is 11,110 (4 1's and 1 zero). I haven't found any rhyme or reason to the number of zeros, which is why I used 14 and 41 in my variation.When you run the math  you will see the huge disparity in the asnwer for those two which both have the same digital root[/hide]:
Title: Re: Smallest Positive Integer
Post by Aryabhatta on May 19th, 2004, 5:09pm

on 05/19/04 at 16:46:47, Sir Col wrote:
I might still be missing something here, but...

Let p=[phi](n)
If (b,n)=1, then bp[equiv]1 mod n.
Barukh's method depended on this, so that bkp[equiv]1 mod n, and the sum of n such powers would be congruent with zero modulo n.

If (b,n)=g, (b/g,n)=1, so (b/g)p[equiv]1 mod n, but this fails as b/g will not consist of ones and zeros (unless g=b).



if (b,n) = g then (b,n/g) = 1. (Don't look at b/g)
Now look at Barukh's proof with n replaced by n/g.
Some multiple (say K*n/g) of n/g will have only 1's and 0's in base b.

g divides b, so some multiple of g (say L*g) is b.
so we have that (K*L)*n = (K*n/g)*(L*g) consists of only 1's and 0's.
Title: Re: Smallest Positive Integer
Post by towr on May 20th, 2004, 1:15am

on 05/19/04 at 17:04:34, Leon wrote:
For example, using 22. The digital root is 4.
4 1's = 1,111.
1,111 / 22 = 50.5. That is one decimal place.
The answer is 11,110 (4 1's and 1 zero)
personally, I'd prefer 110 = 5*22, it's a 101 times smaller
I also wouldn't suggest trying your method for 13, 4 1's with an infinite amount of 0's tagged on seems a bit large :P

41: [hide]11111[/hide]
14: [hide]10010[/hide]
Title: Re: Smallest Positive Integer
Post by Leon on May 20th, 2004, 7:26am

on 05/20/04 at 01:15:49, towr wrote:
personally, I'd prefer 110 = 5*22, it's a 101 times smaller
I also wouldn't suggest trying your method for 13, 4 1's with an infinite amount of 0's tagged on seems a bit large :P

41: [hide]11111[/hide]
14: [hide]10010[/hide]


Interesting. Obviously I will have to delve more into digital roots.

On 13 - 4 1's and 13 zeros gets there. --- Correction - you are right. I did this in Excel and 13 zeros is the answer there. But my HP calc proves this answer wrong. Gotta love Microsoft. ---

Obviously my answer for 14 was 5 1's and 12 zeros, proved quite wrong now. ---- And is wrong outright. Excel got me again. Guess I should verify that the last digit works ---

Towr - did you calculate those in any way other than plug and chug?
Title: Re: Smallest Positive Integer
Post by towr on May 20th, 2004, 8:21am
I calculated the first few powers of 10 modulo n, and then looked how I could add them to a multiple of n.
Title: Re: Smallest Positive Integer
Post by Barukh on May 20th, 2004, 9:07am

on 05/19/04 at 09:33:33, Aryabhatta wrote:
if gcd(n,b) = g.
Then some multiple of n/g has only 1's and 0's base b.
since g divides b, some multiple of g is a power of b.
so some multiple of n/g*g = n has only 1's and 0's base b.

So i guess it is sufficient.

Yes, it is. Nice demonstration, Aryabhatta!  :D
Title: Re: Smallest Positive Integer
Post by Sir Col on May 20th, 2004, 4:25pm
This is very humbling for me; I am reminded of how my own students must feel all too often! I'm really sorry, but I still don't see how this improvisation demonstrates the method.  ???

Let me continue with the example I stated above:

If b=10, n=14, we aim to show that a number in base 10 exists, consisting of ones and zeros, that is divisible by 14.

(10,14)=2, so (10,7)=1, and as [phi](7)=6, 106[equiv]1 mod 7.

How is this then used to show that such a number exists?


Quote:
Then some multiple of n/g has only 1's and 0's base b.
since g divides b, some multiple of g is a power of b.
so some multiple of n/g*g = n has only 1's and 0's base b.

This reads as...

Some multiple of 7 has only 1's and 0's in base 10; why?
Since 2 divides 10, some multiple of 2 is a power of 10; true, but how does this help?
So some multiple of 7*2 = 14 has only 1's and 0's in base 10; this is what we're trying to show, but how have we proved it?

(Thanks for your patience with this duffer)
Title: Re: Smallest Positive Integer
Post by Barukh on May 20th, 2004, 10:41pm
Aryabhatta, I hope you don't mind if I try to explain this time.


on 05/20/04 at 16:25:41, Sir Col wrote:
I am reminded of how my own students must feel all too often! I'm really sorry, but I still don't see how this improvisation demonstrates the method.  ???

Don't worry, let's take it easy.  :D


Quote:
If b=10, n=14, we aim to show that a number in base 10 exists, consisting of ones and zeros, that is divisible by 14.

(10,14)=2, so (10,7)=1, and as [phi](7)=6, 106[equiv]1 mod 7.

How is this then used to show that such a number exists?

This reads as...

Some multiple of 7 has only 1's and 0's in base 10; why?

Because 7 and 10 are relatively prime, we know that such a multiple exists – remember, that's what we proved in the first place. So, 10 divides 7*K, and 7*K is a "good" number in base 10.


Quote:
Since 2 divides 10, some multiple of 2 is a power of 10; true, but how does this help?

It helps because "being a power of 10" means "is written as 10…0 in base 10". So: 2*L = 1…0 in base 10.


Quote:
So some multiple of 7*2 = 14 has only 1's and 0's in base 10; this is what we're trying to show, but how have we proved it?

We have: 7*K * 2*L is a "good" number (since it is obtained from another good number – 7*K – by adding some zeroes to the right). But this number clearly is a multiple of 14.


Quote:
Thanks for your patience with this duffer)

You are always welcome.
Title: Re: Smallest Positive Integer
Post by Sir Col on May 21st, 2004, 5:51am
Like a light coming on – actually it was the morning sun coming through a crack in my curtains, and a good nights sleep – I suddenly grasped it! A slightly different explanation I offered myself...

If (10,14)=2, (10,7)=1, [phi](7)=6, so b6[equiv]1 mod 7. Hence N=b6+b12+...+b42[equiv]7[equiv]0 mod 7.

In other words, a number, N, comprising zeroes and ones exists that is divisible by 7.

Clearly any multiple of N is divisible by 7: 2N will be divisible by 14 (or in general gN will be divisible by n). But more importantly, b=10=2*5 contains the essential factor, g=2, to make N divisible by n=14. As multiplying by b will only add an extra zero, the number will still contain zeroes and ones. Hence, in general, bN will always be an example of such a number we seek.


The difficulty I had with understanding it before was the step from knowing that 106[equiv]1 mod 7 suddenly produced a number consisting of 0's and 1's that was a multilpe of 7. I needed to explicitly visualise the construction of such a number (by the sum of powers) before I could proceed with the demonstration. Of course, the rest makes sense now!

Thank you for your time and explanations.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board