Author |
Topic: Exactly 7 common factors (Read 1359 times) |
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender: 
Posts: 1001
|
 |
Exactly 7 common factors
« on: Sep 11th, 2003, 8:12am » |
 Quote  Modify
|
What is the probability that 2 numbers chosen at random from the first 1000 natural numbers have exactly 7 common factors??
|
|
 IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Exactly 7 common factors
« Reply #1 on: Sep 11th, 2003, 10:44am » |
Quote Modify
|
Distinct factors? I guess not.
Distinct numbers? I guess so.
|
| « Last Edit: Sep 11th, 2003, 10:00pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
visitor
Guest
|
|
Re: Exactly 7 common factors
« Reply #2 on: Sep 11th, 2003, 11:16am » |
Quote Modify
 Remove
|
Is 0.14% close?
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Exactly 7 common factors
« Reply #3 on: Sep 11th, 2003, 12:53pm » |
Quote Modify
|
This problem seems really difficult to me, but if I'm correct in assuming you mean prime and composite factors, then we have three possible cases:
1) Three different prime factors are common. (common factors are a, b, c, ab, ac, bc, and abc)
2) Two different prime factors, with one repeated three times. (common factors are a, b, aa, ab, aaa, aab, and aaab).
3) Both share one prime factor repeated seven times. (common factors are a, a2, a3, ..., a7)
In addition to this, each number can be a multiple of these shared factors. There is also no restriction on having more multiples of some of the shared prime factors in one number as long as the other one has only the specified number.
Really, quite difficult I would say ... but maybe I'm missing something ...
|
| « Last Edit: Sep 11th, 2003, 12:55pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Exactly 7 common factors
« Reply #4 on: Sep 11th, 2003, 2:05pm » |
Quote Modify
|
I got 460/500500. (wrong)
Edited because I made a mistake!
If we're picking two distinct numbers from the set of numbers less than 1000, I get 71/499500.
For your information, the pairs are listed below.
::
(64, 128) (64, 192) (64, 256) (64, 320) (64, 384) (64, 448) (64, 512) (64, 576) (64, 640) (64, 704) (64, 768) (64, 832) (64, 896) (64, 960)
(128, 192) (128, 320) (128, 448) (128, 576) (128, 704) (128, 832) (128, 960)
(192, 256) (192, 320) (192, 448) (192, 512) (192, 640) (192, 704) (192, 832) (192, 896)
(256, 320) (256, 448) (256, 576) (256, 704) (256, 832) (256, 960)
(320, 384) (320, 448) (320, 512) (320, 576) (320, 704) (320, 768) (320, 832) (320, 896)
(384, 448) (384, 704) (384, 832)
(448, 512) (448, 576) (448, 640) (448, 704) (448, 768) (448, 832) (448, 960)
(512, 576) (512, 704) (512, 832) (512, 960)
(576, 640) (576, 704) (576, 832) (576, 896)
(640, 704) (640, 832)
(704, 768) (704, 832) (704, 896) (704, 960)
(768, 832)
(832, 896) (832, 960)
(896, 960)
::
However, if we're just picking two random numbers less than 1000, and duplicates are possible, then numbers with seven factors would be included: (64,64) and (729,729), and the probability would be 73/500500.
|
| « Last Edit: Sep 12th, 2003, 3:11pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Exactly 7 common factors
« Reply #5 on: Sep 13th, 2003, 9:44pm » |
Quote Modify
|
ofcourse i am talking of two distinct numbers and yes 71/499500 is correct!!!
Hint : (Don't see if you don't want to)
1>Concentrate on GCD of two numbers
2>if n=p1x1*p2x2*....*pnxn
then number of divisors of n = (x1+1)(x2+1)(x3+1)....(xn+1)
so what can we say abt the GCD??and further what are the numbers under consideration??
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Exactly 7 common factors
« Reply #6 on: Sep 15th, 2003, 9:27am » |
Quote Modify
|
I think there are a lot more of these numbers than you guys are saying. For instance, all the following pairs have exactly seven factors (not including 1) in common:
(30,60), (30,90), (30,120), (30, 150), ... (30, 990)
(60,90), (60,150), (60,210), (60,270), ... (60, 990)
(90,60), (90,120), (90,150), (90,210), ... (90, 960)
...
These all have only the following seven common factors: {2,3,5,6,10,15,30}
(24,48), (24,72), (24, 96), ... (24,984)
(48,72), (24,120), (24,178), ... (24,984)
(72,96), (72,120), (72,168), ... (72,984)
These all have only the following seven common factors:{2,3,4,6,8,12,24}
And then there are all the solutions you have found.
Unless I'm really not understanding the question here...
|
| « Last Edit: Sep 15th, 2003, 9:31am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Exactly 7 common factors
« Reply #7 on: Sep 15th, 2003, 9:43am » |
Quote Modify
|
You're not misunderstanding, you're just playing by a different set of rules, James. If you're not including 1 as a common factor, then you will get a different list of numbers.
The smallest pair of numbers in my list was (64,128), because:
64 has 1,2,4,8,16,32,64
128 has 1,2,4,8,16,32,64(,128)
Making 7 factors in common.
In your list you have (30,60) as the smallest pair, but it wouldn't work according to my method:
30 has 1,2,3,5,6,10,15,30
60 has 1,2,3(,4),5,6,10(,12),15(,20),30(,60)
Making 8 factors in common.
Using your rule, you'd get 2093/499500; as you said, there are many more.
I know it comes down to interpretation, but if you were asked for the highest common factor of 3 and 4, wouldn't you say 1, being the HCF, is a common factor?
|
| « Last Edit: Sep 15th, 2003, 9:44am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Exactly 7 common factors
« Reply #8 on: Sep 15th, 2003, 10:48am » |
Quote Modify
|
I think I'd just say they had no common factors. 1 isn't a very useful factor because you can't tell how many times it's included.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Exactly 7 common factors
« Reply #9 on: Sep 15th, 2003, 3:31pm » |
Quote Modify
|
on Sep 15th, 2003, 10:48am, James Fingas wrote:| I think I'd just say they had no common factors. 1 isn't a very useful factor because you can't tell how many times it's included. |
|
I don't believe "useful" appears anywhere in the definition of "common factor". It may not be useful, but 1 is still a factor of all integers.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Exactly 7 common factors
« Reply #10 on: Sep 15th, 2003, 11:03pm » |
Quote Modify
|
If euler's totient function includes 1 , then i would say '1' is a "useful" common factor  (and it is indeed useful!!)
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print