Author |
Topic: Smallest Positive Integer (Read 1351 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Smallest Positive Integer
« on: May 11th, 2004, 7:14pm » |
 Quote  Modify
|
What is the smallest positive integer divisible by 225 that can be expressed using only zeroes and ones?
|
| « Last Edit: May 11th, 2004, 7:17pm by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Cathos
Full Member
Carpe Canum
Gender:
Posts: 246
|
|
Re: Smallest Positive Integer
« Reply #1 on: May 11th, 2004, 7:55pm » |
Quote Modify
|
Can't any number be expressed using zeros and ones if you have enough of them?
|
|
IP Logged |
Sum Arbor
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Smallest Positive Integer
« Reply #2 on: May 11th, 2004, 10:14pm » |
Quote Modify
|
on May 11th, 2004, 7:55pm, 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:
::
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.
::
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Smallest Positive Integer
« Reply #3 on: May 12th, 2004, 6:43am » |
Quote Modify
|
Well done, BNC.
Quote:| I also assume he means a number > 0. |
|
Yes, the smallest 'positive integer' > 0 
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Smallest Positive Integer
« Reply #4 on: May 12th, 2004, 1:08pm » |
Quote Modify
|
on May 12th, 2004, 6:43am, THUDandBLUNDER wrote:| Yes, the smallest 'positive integer' > 0 |
|
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Smallest Positive Integer
« Reply #5 on: May 12th, 2004, 10:35pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Smallest Positive Integer
« Reply #6 on: May 13th, 2004, 8:44am » |
Quote Modify
|
on May 12th, 2004, 10:35pm, 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]
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).
[smiley=blacksquare.gif]
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Smallest Positive Integer
« Reply #7 on: May 13th, 2004, 8:46pm » |
Quote Modify
|
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 0 and any other digit.
So let's suppose that 0 is not allowed. Then we obviously can't write any multiple of b in base b, for example.
A necessary condition is that 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.)
A sufficient condition is that gcd(n,b)=1. Then it's possible using just the digit 1, and therefore also using just any single digit.
I don't know any necessary and sufficient conditions though.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Smallest Positive Integer
« Reply #8 on: May 14th, 2004, 10:40am » |
Quote Modify
|
Answer to original Q,
::11111111100::
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Smallest Positive Integer
« Reply #9 on: May 15th, 2004, 10:18am » |
Quote Modify
|
on May 13th, 2004, 8:46pm, 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… 
[smiley=blacksquare.gif]
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.
[smiley=blacksquare.gif]
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Smallest Positive Integer
« Reply #10 on: May 16th, 2004, 1:16am » |
Quote Modify
|
How elementary indeed!
c'est merveilleux!
PHP is so simple yet so powerful to prove some of the wonderful things.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Smallest Positive Integer
« Reply #11 on: May 17th, 2004, 1:45pm » |
Quote Modify
|
(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).
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Smallest Positive Integer
« Reply #12 on: May 17th, 2004, 5:28pm » |
Quote Modify
|
on May 17th, 2004, 1:45pm, 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.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Smallest Positive Integer
« Reply #13 on: May 17th, 2004, 6:21pm » |
Quote Modify
|
Quote:| It stands for whatever returned by acronymfinder.com, modulo spelling errors. |
|
hehe,
or just PigeonHole Principle
(PigeonHole Principal, acronymfinder spelling )
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Smallest Positive Integer
« Reply #14 on: May 19th, 2004, 7:38am » |
Quote Modify
|
on May 17th, 2004, 1:45pm, 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. 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Smallest Positive Integer
« Reply #15 on: May 19th, 2004, 9:33am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Leon
Junior Member
Posts: 97
|
|
Re: Smallest Positive Integer
« Reply #16 on: May 19th, 2004, 3:12pm » |
Quote Modify
|
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: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:
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Smallest Positive Integer
« Reply #17 on: May 19th, 2004, 4:46pm » |
Quote Modify
|
on May 19th, 2004, 9:33am, 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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Leon
Junior Member
Posts: 97
|
|
Re: Smallest Positive Integer
« Reply #18 on: May 19th, 2004, 5:04pm » |
Quote Modify
|
on May 19th, 2004, 4:46pm, 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:
: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:
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Smallest Positive Integer
« Reply #19 on: May 19th, 2004, 5:09pm » |
Quote Modify
|
on May 19th, 2004, 4:46pm, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Smallest Positive Integer
« Reply #20 on: May 20th, 2004, 1:15am » |
Quote Modify
|
on May 19th, 2004, 5:04pm, 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 
41: 11111
14: 10010
|
| « Last Edit: May 20th, 2004, 1:37am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Leon
Junior Member
Posts: 97
|
|
Re: Smallest Positive Integer
« Reply #21 on: May 20th, 2004, 7:26am » |
Quote Modify
|
on May 20th, 2004, 1:15am, 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
41: 11111
14: 10010
|
|
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?
|
| « Last Edit: May 20th, 2004, 8:27am by Leon » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Smallest Positive Integer
« Reply #22 on: May 20th, 2004, 8:21am » |
Quote Modify
|
I calculated the first few powers of 10 modulo n, and then looked how I could add them to a multiple of n.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Smallest Positive Integer
« Reply #23 on: May 20th, 2004, 9:07am » |
Quote Modify
|
on May 19th, 2004, 9:33am, 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!
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Smallest Positive Integer
« Reply #24 on: May 20th, 2004, 4:25pm » |
Quote Modify
|
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)
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print