wu :: forums - Print Page


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

        riddles >> easy >> 1-Product of Two Integers
        
(Message started by: Barukh on May 28^th, 2004, 6:01am)

Title: 1-Product of Two Integers
Post by Barukh on May 28^th, 2004, 6:01am

Find two positive integers X, Y with the same number of digits such that the product XY has at least 50 digits - all of them 1s.

Title: Re: 1-Product of Two Integers
Post by grimbal on May 28^th, 2004, 6:11am

10000000000000000000000001 * 01111111111111111111111111
But I guess starting with a zero is cheating?

Title: Re: 1-Product of Two Integers
Post by Barukh on May 28^th, 2004, 8:00am

on 05/28/04 at 06:11:14, grimbal wrote:

But I guess starting with a zero is cheating?

Yes, it is ;D

Title: Re: 1-Product of Two Integers
Post by grimbal on May 28^th, 2004, 11:58am

Let's see.

notation: a digit followed by (n) means n times that digit.
10(4)1 = 100001.

7 | 1(6), therefore 7 | 1(54) but not 1(27).
1(54) = 10(26)1 * 1(27)
7 | 1(54) but not 7|1(27) implies 7|10(26)1
so, 1(54) = (10(26)1 / 7) * 7(27)
both numbers are integers and have 27 digits.

numerically:
142857142857142857142857143 * 777777777777777777777777777 = 1(54).

but there is a shorter solution:
2889514951875839958343511 * 3845320510938316911651601 = 1(50)

Title: Re: 1-Product of Two Integers
Post by Leon on May 28^th, 2004, 12:30pm

on 05/28/04 at 11:58:25, grimbal wrote:

numerically:
142857142857142857142857142 * 777777777777777777777777777 = 1(52).

but there is a shorter solution:
2889514951875839958343511 * 3845320510938316911651601 = 1(50)

Forgive me for questioning since I barely follow what you did....but in regards to the first asnwer, since the last digit of your numbers is 2 and 7, how will that result in a 1 as the last digit of the product?

Title: Re: 1-Product of Two Integers
Post by grimbal on May 28^th, 2004, 1:21pm

Oops! :-[ Just a rounding error. it should be ...143.

I corrected my previous post.

Title: Re: 1-Product of Two Integers
Post by Sir Col on May 28^th, 2004, 3:10pm

on 05/28/04 at 11:58:25, grimbal wrote:

7 | 1(6), therefore 7 | 1(52)

It's only a minor point, but shouldn't that be, "therefore 7 | 1(54)"?

That is a very clever solution, Grimbal, and nicely explained! *hand-clapping-smilie*

By the way, how did you find that amazing solution that contains fifty digits?

Leon, what he has done is the following...
111111 divides perfectly by 7, so if you imagine the process of long division, you can see that 7 divides evenly into every block of six 1's. Hence 7 divides into 1(54).

He then noted that a block of n 1's divides by n/2 1's:
1111/11=101
111111/111=1001
11111111/1111=10001

That is 1(2n)/1(n)=10(n-1)1.

Therefore, 1(54)/1(27)=10(26)1, and we get:
1(54)=1(27)*10(26)1

But as 7 divides into 1(54) (LHS) and 7 does not divide into 1(27) [there must be a multiple of six 1's], 7 must divide into 10(26)1.

As 1(54)=1(27)*10(26)1, 1(54)=(7*1(27))*(10(26)1/7)=7(27)*(10(26)1/7)

Because 10(26)1 contains 28 digits [2x1's and 26x0's], dividing by 7 will contain 27 digits. So both numbers 7(27) and 10(26)1/7 will contain the same number of digits.

Title: Re: 1-Product of Two Integers
Post by grimbal on May 28^th, 2004, 3:50pm

Yes, indeed, it was 1(54).

What I did, is to factorize 1(50). It has 10 prime factors. This give 512 unique factorizations in 2 numbers. I just tried them all to see if the sizes fit. It does for 19 of them. I choose the one closest to the square root.

I just discovered a nicer one:
5556155561555615556155561 * 1999784021165925739277551 = 1(50)

Title: Re: 1-Product of Two Integers
Post by Barukh on May 28^th, 2004, 11:31pm

Well done, grimbal! :D :D :D

Your "shorter and nicer" solutions are really nice. Are they also scalable (e.g. to 500 digits)?

Title: Re: 1-Product of Two Integers
Post by grimbal on May 29^th, 2004, 9:40am

No, but that one is easy:

1(500) = 10(249)1 * 1(250)
we need to make the first term smaller without increasing the second term too much.
Fortunately, 101 | 10(249)1 and 41 | 1(250)
and 101/41 ~ 2.5

So,
A = 10(249)1 / 101 * 41 is integer and has 250 digits
B = 1(250) / 41 * 101 is integer and has 250 digits
and A * B = 1(500).

4059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405940 594059 405941 * 2737 127371 273712 737127 371273 712737 127371 273712 737127 371273 712737 127371 273712 737127 371273 712737 127371 273712 737127 371273 712737 127371 273712 737127 371273 712737 127371 273712 737127 371273 712737 127371 273712 737127 371273 712737 127371 273712 737127 371273 712737 127371 = 1(500)