Author |
Topic: Scant-digit Multiples (Read 2272 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Scant-digit Multiples
« on: Mar 24th, 2013, 4:58am » |
 Quote  Modify
|
Prove the following statements:
1. Every positive integer has a multiple containing only digits 0 and 1.
2. Every positive power of 2 has a multiple containing only digits 1 and 2.
3. Every positive power of 36 has a multiple containing only digits 3 and 6.
All the numbers are in base 10.
|
|
 IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Scant-digit Multiples
« Reply #1 on: Mar 24th, 2013, 7:27am » |
Quote Modify
|
For part 1:
| hidden: | - Write n = 2a3b5cr, where r is not divisible by 2, 3, or 5.
- If r=1, take p=1 and go to the next step. Otherwise, by the long division algorithm, 1/r is a repeating decimal, say with period p. But then 10p-1 is divisible by r, say 10p-1 = kr. It is also the repdigit 999...999 (p nines), so it is divisible by 9, and since r is not divisible by 3, k must be divisible by 9. Thus, (k/9)r is an integer multiple of r, and it can be written as 111...111 (p ones).
- To add the factors 3b back in, we use the procedure "write the current multiple three times in a row and concatenate" b times. This procedure corresponds to multiplying by 1(lot of zeros)1(lot of zeros)1, which is divisible by 3, so each iteration adds a factor of 3. We now have 111...111 (3bp ones) as a multiple of 3br.
- Finally, multiply by 10max{a,c} to get the desired multiple of n: specifically, (3bp ones)(max{a,c} zeros). |
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Scant-digit Multiples
« Reply #2 on: Mar 24th, 2013, 7:46am » |
Quote Modify
|
It seems to me that part 2 is a lot easier:
| hidden: | We'll actually find a k-digit multiple of 2k that only consists of 1s and 2s. For k=1, obviously 2 is a multiple of 2.
For larger k, we use induction. Take the previously found multiple of 2k-1 and check whether it happens to be divisible by 2k.
- If the answer is yes, tacking the digit 2 to the front of it won't hurt, because we're adding 2*10k-1 = 2k5k-1.
- Otherwise, the previous number is equal to 2k-1 mod 2k. But so is 10k-1, so tacking a 1 to the front of the previous multiple makes it a multiple of 2k.
The first few multiples found in this manner are 2, 12, 112, 2112, 22112, 122112, 2122112, 12122112, 212122112, 1212122112, 11212122112, 111212122112, 1111212122112, 11111212122112, 211111212122112, ... |
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Scant-digit Multiples
« Reply #3 on: Mar 24th, 2013, 7:46am » |
Quote Modify
|
1. Let N be the positive integer.
Take the numbers 1, 11, 111, 1111, ..., take the remainders mod N of these. Sooner or later (in fact after at most N+1 values) two of the remainders must be equal.
Take the difference D between two values having equal remainders.
D is a multiple of N because the remainders mod N cancel each other.
And D is written as a number of 1's followed by a number of 0's. (that is not trivial to prove, but is obvious if you try to calculate one such difference).
QED
If N is not a multiple of 2 or 5, you can divide D by 10^k to remove the 0's at the end of D. The result is still a multiple of N and it is written as a sequence of 1's only.
PS: I will not mention that technically, 0 is a multiple of any positive integer. I will not.
|
| « Last Edit: Mar 27th, 2013, 12:33pm by Grimbal » |
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Scant-digit Multiples
« Reply #4 on: Mar 24th, 2013, 7:58am » |
Quote Modify
|
on Mar 24th, 2013, 7:46am, Grimbal wrote:Take the numbers 1, 11, 111, 1111, ..., take the remainders mod N of these. Sooner or later (in fact after at most N+1 values) two of the remainders are equal.
Take the difference D between two values having equal remainders.
D is a multiple of N because the remainders mod N cancel each other.
And D is written as a number of 1's followed by a number of 0's. (that is difficult to prove, but is obvious if you try to calculate one such difference).
QED
If N is not a multiple of 2 or 5, you can divide D by 10^k to remove the 0's at the end of D. It remains a multiple of N and it is written as a sequence of 1's only.
|
|
Yes, that's a lot easier. 
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Scant-digit Multiples
« Reply #5 on: Mar 24th, 2013, 8:14am » |
Quote Modify
|
Very inefficient answer for part 3:
| hidden: | | 36n = 22n32n. Use my answer to part 2 to find a multiple of 22n that only contains ones and twos. Multiply by three to get all threes and sixes. Then, use the concatenation trick I described for part 1 to get to the right power of 3. That needs to be done at most 2n-1 times, so the resulting number can have up to 2n*32n-1 digits. |
The multiple of 362 that's found by this method is 633663366336633663366336633663366336. The smallest one that appears to work is 636336, so there is some room for improvement here... Grimbal?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Scant-digit Multiples
« Reply #6 on: Mar 24th, 2013, 9:37am » |
Quote Modify
|
Well done, pex and Grimbal! 
on Mar 24th, 2013, 8:14am, pex wrote:| Very inefficient answer for part 3: |
|
I used a slightly different approach, but got the same number of digits. And - it took me much more time!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Scant-digit Multiples
« Reply #7 on: Mar 24th, 2013, 11:14am » |
Quote Modify
|
So let me get this right, if you have any number N that's not divisible by 2 or 5, then for any power Nk there's a number that only repeats N and is a multiple of Nk?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Scant-digit Multiples
« Reply #8 on: Mar 24th, 2013, 11:47am » |
Quote Modify
|
on Mar 24th, 2013, 11:14am, towr wrote:| So let me get this right, if you have any number N that's not divisible by 2 or 5, then for any power Nk there's a number that only repeats N and is a multiple of Nk? |
|
Correct. I find this beautiful.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Scant-digit Multiples
« Reply #9 on: Mar 24th, 2013, 11:54am » |
Quote Modify
|
on Mar 24th, 2013, 11:14am, towr wrote:| So let me get this right, if you have any number N that's not divisible by 2 or 5, then for any power Nk there's a number that only repeats N and is a multiple of Nk? |
|
Isn't the implication of Grimbal's proof even stronger? If you have any positive number N, and any number M that's not divisible by 2 or 5, then there's a number that only repeats N and is a multiple of M.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Scant-digit Multiples
« Reply #10 on: Mar 24th, 2013, 1:15pm » |
Quote Modify
|
Yes, seems like it.
(And in these cases it's probably easier to just find the (1(0)k)n1 which is 0 mod M, than finding two that have the same modulus, subtracting them and dividing off the trailing 0s.)
|
| « Last Edit: Mar 24th, 2013, 1:17pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: Scant-digit Multiples
« Reply #11 on: Mar 27th, 2013, 5:59am » |
Quote Modify
|
A perhaps even easier solution to #1.
Make a series:
Rn = 10n-1 mod N.
There are N potential values, so once n=N*(N-1)+1 steps there will be one value with N occurences. Choose those ones and add the N pieces of 1000...000 type numbers. It will be devideable with N.
(There are lots of simplifications possible, but not needed. It gives a shorter solution, but a longer proof. E.g.
If Ri=0 then finished. So it is already true for n=(N-1)*(N-1)+1 steps.
Actually complementer numbers (Ri=A, Rj=N-A) already solves. So it is (roughly) n=(N/2)*(N-1)+1.
2s and 5s can be dropped easily.
Etc.)
|
| « Last Edit: Mar 27th, 2013, 6:00am by jollytall » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Scant-digit Multiples
« Reply #12 on: Mar 27th, 2013, 10:02am » |
Quote Modify
|
Grimbal's solution sounds easier.
But you can modify this to a method for finding the lowest such number.
Python Code:def foo(N):
d = {0:[], 1:[0]}
R=1
for i in range(1,N*N):
R = (R*10) % N
for el in list(d.keys()):
t = (el+R) % N
if t not in d:
d[t] = d[el] + [i]
if t == 0:
return d[el] + [i]
|
|
(The N*N is a bit of an overestimation, up to N = 9999, 35 is the highest i gets.)
|
| « Last Edit: Mar 27th, 2013, 10:59am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print