wu :: forums - Print Page


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

        riddles >> medium >> Scant-digit Multiples
        
(Message started by: Barukh on Mar 24^th, 2013, 4:58am)

Title: Scant-digit Multiples
Post by Barukh on Mar 24^th, 2013, 4:58am

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.

Title: Re: Scant-digit Multiples
Post by pex on Mar 24^th, 2013, 7:27am

For part 1:
[hideb]- Write n = 2^a3^b5^cr, 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 10^p-1 is divisible by r, say 10^p-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 3^b 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 (3^bp ones) as a multiple of 3^br.
- Finally, multiply by 10^max{a,c} to get the desired multiple of n: specifically, (3^bp ones)(max{a,c} zeros).[/hideb]

Title: Re: Scant-digit Multiples
Post by pex on Mar 24^th, 2013, 7:46am

It seems to me that part 2 is a lot easier:
[hideb]We'll actually find a k-digit multiple of 2^k 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 2^k-1 and check whether it happens to be divisible by 2^k.
- If the answer is yes, tacking the digit 2 to the front of it won't hurt, because we're adding 2*10^k-1 = 2^k5^k-1.
- Otherwise, the previous number is equal to 2^k-1 mod 2^k. But so is 10^k-1, so tacking a 1 to the front of the previous multiple makes it a multiple of 2^k.
The first few multiples found in this manner are 2, 12, 112, 2112, 22112, 122112, 2122112, 12122112, 212122112, 1212122112, 11212122112, 111212122112, 1111212122112, 11111212122112, 211111212122112, ...[/hideb]

Title: Re: Scant-digit Multiples
Post by Grimbal on Mar 24^th, 2013, 7:46am

1. Let N be the positive integer.
[hide]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.
[/hide]

PS: I will not mention that technically, 0 is a multiple of any positive integer. I will not.

Title: Re: Scant-digit Multiples
Post by pex on Mar 24^th, 2013, 7:58am

on 03/24/13 at 07:46:42, Grimbal wrote:

[hide]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.
[/hide]

Yes, that's a lot easier. :-[

Title: Re: Scant-digit Multiples
Post by pex on Mar 24^th, 2013, 8:14am

Very inefficient answer for part 3:
[hideb]36ⁿ = 2²ⁿ3²ⁿ. Use my answer to part 2 to find a multiple of 2²ⁿ 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*3^2n-1 digits.[/hideb]
The multiple of 36² 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?

Title: Re: Scant-digit Multiples
Post by Barukh on Mar 24^th, 2013, 9:37am

Well done, pex and Grimbal! :D

on 03/24/13 at 08:14:43, 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!

Title: Re: Scant-digit Multiples
Post by towr on Mar 24^th, 2013, 11:14am

So let me get this right, if you have any number N that's not divisible by 2 or 5, then for any power N^k there's a number that only repeats N and is a multiple of N^k?

Title: Re: Scant-digit Multiples
Post by Barukh on Mar 24^th, 2013, 11:47am

on 03/24/13 at 11:14:17, 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 N^k there's a number that only repeats N and is a multiple of N^k?

Correct. I find this beautiful.

Title: Re: Scant-digit Multiples
Post by pex on Mar 24^th, 2013, 11:54am

on 03/24/13 at 11:14:17, 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 N^k there's a number that only repeats N and is a multiple of N^k?

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.

Title: Re: Scant-digit Multiples
Post by towr on Mar 24^th, 2013, 1:15pm

Yes, seems like it.

(And in these cases it's probably easier to just find the (1(0)^k)ⁿ1 which is 0 mod M, than finding two that have the same modulus, subtracting them and dividing off the trailing 0s.)

Title: Re: Scant-digit Multiples
Post by jollytall on Mar 27^th, 2013, 5:59am

A perhaps even easier solution to #1.

Make a series:
R_n = 10^n-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 R_i=0 then finished. So it is already true for n=(N-1)*(N-1)+1 steps.
Actually complementer numbers (R_i=A, R_j=N-A) already solves. So it is (roughly) n=(N/2)*(N-1)+1.
2s and 5s can be dropped easily.
Etc.)

Title: Re: Scant-digit Multiples
Post by towr on Mar 27^th, 2013, 10:02am

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.)