I'm sorry there's an algebra error here, but fortunately the proof
still works. It should be
>From this, algebra provides
10^e - 1 == 0 (mod 9Y) and
10^e == 1 (mod 9Y).
But 9Y and 10^e are still coprime, so we're good.
Here is code that seems to be working fine.
#include <stdio.h>
int main(int argc, char *argv[])
{
int x, x9, m, p, a, b;
if (argc > 1 && sscanf(argv[1], "%d", &x) == 1) {
a = b = 0;
while (x % 2 == 0) {
a++;
x /= 2;
}
while (x % 5 == 0) {
b++;
x /= 5;
}
x9 = 9 * x;
m = 10 % x9;
p = 1;
while (m != 1) {
m = (10 * m) % x9;
p++;
}
printf("divides %d 1's followed by %d 0's\n",
p, a > b ? a : b);
}
return 0;
}
For example:
$ ./a.out 45
divides 9 1's followed by 1 0's
$ ./a.out 192
divides 3 1's followed by 6 0's
./a.out 947838840
divides 299910 1's followed by 3 0's
On Mar 16, 4:27 pm, Gene <gene.ress...@gmail.com> wrote:
> This is very beautiful. Here is a less elegant proof, though it leads
> to an efficient algorithm.
>
> In a different problem some time ago, there was a statement that every
> number with a 3 in the units position has a multiple that consists of
> all 1s. The proof needs a little number theory. Any number Z that is
> all 1's can be written as (10^e - 1) / 9 for some integer e. So if Y
> is the number we are given (ending in 3), we must find e such that
> (10^e - 1) / 9 == 0 (mod Y). From this, algebra provides 10^e - 1 ==
> 0 (mod Y) and 10^e == 1 (mod Y). Note 10^e and Y are coprime. The
> prime factors of the former are all 5 and 2, and since Y ends in 3, it
> can have neither of these. Then by Euler's Theorem, e must exist (and
> in fact Euler's Totient Function gives its value)! So we are done.
>
> Corollary: a number with 1, 7, or, 9 in the units position also has a
> multiple that's all 1s. Proof: Multiply by 3, 9, or 7 respectively to
> get a number with 3 in the units position, then use the result above.
>
> The rest:
>
> Let X be the (arbitrary) number we are given. Divide out all its
> factors of 2 and 5 to obtain Y.
>
> Claim: Y has 1, 3, 7, or 9 in the units position. Proof: If it ended
> with any other digit, it would be divisible by 2 or 5!
>
> Therefore we can find a number Z consisting of all 1's that is a
> multiple of Y. Suppose we factored out (2^a)(5^b) above. Then Z
> (10^max(a, b)) is a number consisting of all 1's and 0's that is a
> multiple of X as desired!
>
> It's not hard to implement in this in time linear to the number of
> digits of the multiple (assuming a real RAM model of computation).
>
> Please let me know if you see any problems with this argument.
> On Mar 7, 4:32 pm, Don <dondod...@gmail.com> wrote:
>
>
>
>
>
>
>
> > Theorem: In any set of (n+1) distinct integers there exists two whose
> > difference is divisible by n.
>
> > Proof: Each of these integers leaves a remainder between 0 and n-1
> > inclusive upon division by n. Since there are n possible remainders
> > and (n+1) integers that means there exist two which have the same
> > remainder by the PigeonHole Principle. So their difference is
> > divisible by n.
>
> > Theorem: Given any positive integer n there exists a positive number
> > consisting of only 1's and 0's which is divisible by n.
>
> > Proof: Construct the sequence of (n+1) integers:
> > 1,11,111,....,111...1
> > By the first theorem two of these numbers have a difference divisible
> > by n. That difference will be a number consisting of only 1's and
> > 0's.
>
> > On Mar 7, 1:17 pm, karthikeya s <karthikeya.a...@gmail.com> wrote:
>
> > > A math problem: Prove that for all positive integer n, there exist at
> > > least
> > > one positive integer whose digits are only 1s and 0s and is divisible by
> > > n.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
