Author |
Topic: 1-Product of Two Integers (Read 449 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
1-Product of Two Integers
« on: May 28th, 2004, 6:01am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 1-Product of Two Integers
« Reply #1 on: May 28th, 2004, 6:11am » |
Quote Modify
|
10000000000000000000000001 * 01111111111111111111111111
But I guess starting with a zero is cheating?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 1-Product of Two Integers
« Reply #2 on: May 28th, 2004, 8:00am » |
Quote Modify
|
on May 28th, 2004, 6:11am, grimbal wrote:| But I guess starting with a zero is cheating? |
|
Yes, it is 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 1-Product of Two Integers
« Reply #3 on: May 28th, 2004, 11:58am » |
Quote Modify
|
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)
|
| « Last Edit: May 28th, 2004, 3:33pm by Grimbal » |
IP Logged |
|
|
|
Leon
Junior Member
Posts: 97
|
|
Re: 1-Product of Two Integers
« Reply #4 on: May 28th, 2004, 12:30pm » |
Quote Modify
|
on May 28th, 2004, 11:58am, 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?
|
| « Last Edit: May 28th, 2004, 12:30pm by Leon » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 1-Product of Two Integers
« Reply #5 on: May 28th, 2004, 1:21pm » |
Quote Modify
|
Oops!  Just a rounding error. it should be ...143.
I corrected my previous post.
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: 1-Product of Two Integers
« Reply #6 on: May 28th, 2004, 3:10pm » |
Quote Modify
|
on May 28th, 2004, 11:58am, 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.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 1-Product of Two Integers
« Reply #7 on: May 28th, 2004, 3:50pm » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 1-Product of Two Integers
« Reply #8 on: May 28th, 2004, 11:31pm » |
Quote Modify
|
Well done, grimbal! 
Your "shorter and nicer" solutions are really nice. Are they also scalable (e.g. to 500 digits)?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 1-Product of Two Integers
« Reply #9 on: May 29th, 2004, 9:40am » |
Quote Modify
|
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)
|
| « Last Edit: May 29th, 2004, 9:42am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print