Straight Dope Message Board > Main Math Question, not for HW
 Register FAQ Calendar Mark Forums Read

#1
07-16-2012, 09:24 AM
 pancakes3 Guest Join Date: Nov 2008
Math Question, not for HW

In how many distinct ways can eight different colored beads be arranged on a circular necklace with no clasp or noticeable break?
#2
07-16-2012, 09:27 AM
 Simplicio Guest Join Date: Dec 2003
7!

ETA: (that's seven factorial, not me being really excited about the number seven)

Last edited by Simplicio; 07-16-2012 at 09:27 AM.
#3
07-16-2012, 09:29 AM
 Munch Guest Join Date: Mar 2000
Quote:
 Originally Posted by Simplicio ETA: (that's seven factorial, not me being really excited about the number seven)
Haha - I was going to say!

7! comes out to 40,320.
#4
07-16-2012, 09:35 AM
 fachverwirrt Guest Join Date: Jul 2006
Quote:
 Originally Posted by Munch Haha - I was going to say! 7! comes out to 40,320.
I get 5040. I'm pretty sure you calculated 8! there.
#5
07-16-2012, 09:38 AM
 Simplicio Guest Join Date: Dec 2003
Its easy to see why if you already know the number of different combinations for n objects where the order matters is n!. On a circular wire, the order still matters, but there's no "first" spot.

But you can choose an arbitrary color to mark the "start" of the series. Then the one to the right is the "first"spot, the one to the right of that the "second" and so on. So you end up with (n-1) spots for (n-1) beads. Thus (n-1)! total combinations.
#6
07-16-2012, 09:45 AM
 md2000 Guest Join Date: Feb 2009
Quote:
 Originally Posted by Simplicio Its easy to see why if you already know the number of different combinations for n objects where the order matters is n!. On a circular wire, the order still matters, but there's no "first" spot. But you can choose an arbitrary color to mark the "start" of the series. Then the one to the right is the "first"spot, the one to the right of that the "second" and so on. So you end up with (n-1) spots for (n-1) beads. Thus (n-1)! total combinations.
yes, if the following are all equivalent ( necklace with no beginning, no end)...

12345678
23456781
34567812

etc. - 8 different "identical" arrangements.
then yes, it's 8!/8 or 7!
#7
07-16-2012, 10:35 AM
 Munch Guest Join Date: Mar 2000
Quote:
 Originally Posted by fachverwirrt I get 5040. I'm pretty sure you calculated 8! there.
Yup - you're right.
#8
07-16-2012, 10:44 AM
 septimus Guest Join Date: Dec 2009
Since the necklace seems to be symmetric, let me ... Nitpick:

Only 7!/2
2520 arrangements can be obtained from one of the other 2520 arrangements by simply turning the necklace upside-down.
#9
07-16-2012, 11:07 AM
 TriPolar Member Join Date: Oct 2007 Location: rhode island Posts: 20,171
Since there's no mention that the beads take up the entire necklace, there should be an infinite number of distinct arrangement of beads including the gaps between them. I doubt that's what the OP had in mind, but I've got a lot of experience reviewing customer specs for ambiguities. I wouldn't sign that contract until it was clarified. On top of that, the OP isn't clear that there are only 8 beads, just 8 different colors of beads.
#10
07-16-2012, 11:36 AM
 yorick73 Guest Join Date: Sep 2003
Wait....there is no break in the necklace so the beads cannot be randomly placed. Wouldn't that equal just 8 combinations. I think the OP is suggesting that we start with 8 beads already on a closed necklace. Am I missing something basic?
#11
07-16-2012, 11:52 AM
 ultrafilter Guest Join Date: May 2001
The general solution is a little more complicated. You need to specify whether you're allowing reflections of a necklace to be distinct, and after that you can use the linked formulas.
#12
07-16-2012, 12:12 PM
 ZenBeam Charter Member Join Date: Oct 1999 Location: I'm right here! Posts: 6,980
Quote:
 Originally Posted by TriPolar Since there's no mention that the beads take up the entire necklace, there should be an infinite number of distinct arrangement of beads including the gaps between them. I doubt that's what the OP had in mind, but I've got a lot of experience reviewing customer specs for ambiguities. I wouldn't sign that contract until it was clarified. On top of that, the OP isn't clear that there are only 8 beads, just 8 different colors of beads.
The OP says "eight different colored beads". The words "eight", "different", and "colored" are all adjectives modifying "beads", so I don't see how you're getting this ambiguity in the number of beads.

I will add to the nitpick that we don't know if the beads are symmetric. If each bead isn't mirror-symmetric in the along-string direction, and could be strung in either direction, then the number would grow to 7! * 2^7.

Last edited by ZenBeam; 07-16-2012 at 12:14 PM.
#13
07-16-2012, 12:57 PM
 TriPolar Member Join Date: Oct 2007 Location: rhode island Posts: 20,171
Quote:
 Originally Posted by ZenBeam The OP says "eight different colored beads". The words "eight", "different", and "colored" are all adjectives modifying "beads", so I don't see how you're getting this ambiguity in the number of beads. I will add to the nitpick that we don't know if the beads are symmetric. If each bead isn't mirror-symmetric in the along-string direction, and could be strung in either direction, then the number would grow to 7! * 2^7.
In that case the ambiguity is that there may not be eight different colors. We don't know whether or not 'eight' is the extent of the enumeration of 'color'.
#14
07-16-2012, 02:06 PM
 Frylock Guest Join Date: Jun 2001
Quote:
 Originally Posted by yorick73 Wait....there is no break in the necklace so the beads cannot be randomly placed. Wouldn't that equal just 8 combinations. I think the OP is suggesting that we start with 8 beads already on a closed necklace. Am I missing something basic?
Seconded. I do not understand how to interpret "with no clasp or noticeable break" except as implying that the beads basically can't be rearranged. If there's no clasp or noticeable break, how do you get them off the chain to rearrange them?

But if that's not what "no clasp or noticeable break" means, then what does it mean?
#15
07-16-2012, 02:15 PM
 md2000 Guest Join Date: Feb 2009
Quote:
 Originally Posted by septimus Since the necklace seems to be symmetric, let me ... Nitpick: Only 7!/2 2520 arrangements can be obtained from one of the other 2520 arrangements by simply turning the necklace upside-down.
Doh! Of course, unless they are weird one-side-up-only-can't-be-flipped beads.

(Edit - but then they could be rotated on the string after the necklace is flipped. Doh!)

Last edited by md2000; 07-16-2012 at 02:16 PM.
#16
07-16-2012, 02:17 PM
 Indistinguishable Guest Join Date: Apr 2007
Quote:
 Originally Posted by Frylock Seconded. I do not understand how to interpret "with no clasp or noticeable break" except as implying that the beads basically can't be rearranged. If there's no clasp or noticeable break, how do you get them off the chain to rearrange them? But if that's not what "no clasp or noticeable break" means, then what does it mean?
It means there's no distinguished starting spot; rotating the beads around the necklace without changing their adjacency relation does not produce a new arrangement.
#17
07-16-2012, 02:28 PM
 ultrafilter Guest Join Date: May 2001
The necklace is really only a way to visualize the problem. If you're hung up on the details, think of how many ways there are to arrange the letters in ABCDEFGH if you don't distinguish between the circular shifts of the words.
#18
07-16-2012, 02:30 PM
 Indistinguishable Guest Join Date: Apr 2007
In other words, "How many ways can 8 different symbols be arranged into a sequence, where two sequences are considered the same if they are cyclic shifts of each other (the way ABCDEFGH and DEFGHABC are)?".

ETA: Er, I wrote this before refreshing the page; ultrafilter's post wasn't there yet.

Last edited by Indistinguishable; 07-16-2012 at 02:30 PM.
#19
07-16-2012, 04:43 PM
 ZenBeam Charter Member Join Date: Oct 1999 Location: I'm right here! Posts: 6,980
Quote:
 Originally Posted by TriPolar In that case the ambiguity is that there may not be eight different colors. We don't know whether or not 'eight' is the extent of the enumeration of 'color'.
It doesn't matter. There'd still be eight different beads, even if some are the same color. Maybe they have different sizes or shapes.
#20
07-16-2012, 05:37 PM
 Senegoid Guest Join Date: Sep 2011
Quote:
 Originally Posted by Simplicio 7! ETA: (that's seven factorial, not me being really excited about the number seven)
My 11th grade Algebra teacher was quite careful to make the same point, explicitly telling us that 6! (the example he always used), is not pronounced
SIX!

A friend of mine, a molecular biologist and research mathematecian, told me of a time he didn't know the factorial notation. He saw some derivation or something in his undergrad textbook, which ended up (skipping a few step) pronouncing that the final answer reduced to 6!

My friend tried and tried to figure how one got 6 for the answer (not knowing that ! meant factorial), and upon failing to do so, that only reinforced his interpretation that the ! simply meant that this was a surprising and remarkable fact. !

Last edited by Senegoid; 07-16-2012 at 05:40 PM.
#21
07-16-2012, 08:25 PM
 pancakes3 Guest Join Date: Nov 2008
thanks guys (factorial)
#22
07-18-2012, 09:39 AM
 pancakes3 Guest Join Date: Nov 2008
Got another one. These are practice mathcounts question that a friend's daughter of mine is trying and when he doesn't get it, he forwards it to me, and I am now forwarding to this forum.

The digits 1-9 are each used once to form a positive 9-digit integer. There are 362880 possible integers like this. How many of them have the digits 1, 2, and 3 in order from least to greatest throughout the integer? One such example is 451,728,936

(so the 1-2-3 doesn't have to go in order.)
#23
07-18-2012, 10:04 AM
 Frylock Guest Join Date: Jun 2001
Quote:
 Originally Posted by pancakes3 Got another one. These are practice mathcounts question that a friend's daughter of mine is trying and when he doesn't get it, he forwards it to me, and I am now forwarding to this forum. The digits 1-9 are each used once to form a positive 9-digit integer. There are 362880 possible integers like this. How many of them have the digits 1, 2, and 3 in order from least to greatest throughout the integer? One such example is 451,728,936 (so the 1-2-3 doesn't have to go in order.)
You just need to figure out how many items are in the following list:

123......
12.3.....
12..3....
.
.
.
1..2...3.
1..2....3
1...23...
.
.
.
.
....1..23
.....123.
.....12.3
.....1.23
......123

No time now to count it up but I imagine conceptualizing the problem that way should make the math more obvious.
#24
07-18-2012, 10:06 AM
 Frylock Guest Join Date: Jun 2001
nvm

Last edited by Frylock; 07-18-2012 at 10:11 AM. Reason: misread the problem
#25
07-18-2012, 10:07 AM
 TriPolar Member Join Date: Oct 2007 Location: rhode island Posts: 20,171
Ok, I wrote all the numbers down on a piece of paper, then used 3 different colored highlighters for the digits 1, 2, and 3, with the colors red, green, and blue. Then I counted up the ones that an RGB pattern in them and got 60480. I may not have done this carefully, so I'll try it again to check.
#26
07-18-2012, 10:10 AM
 Frylock Guest Join Date: Jun 2001
Quote:
 Originally Posted by TriPolar Ok, I wrote all the numbers down on a piece of paper, then used 3 different colored highlighters for the digits 1, 2, and 3, with the colors red, green, and blue. Then I counted up the ones that an RGB pattern in them and got 60480. I may not have done this carefully, so I'll try it again to check.
#27
07-18-2012, 10:11 AM
 Frylock Guest Join Date: Jun 2001
Never mind what I posted above: I completely misread the problem.
#28
07-18-2012, 10:11 AM
 TriPolar Member Join Date: Oct 2007 Location: rhode island Posts: 20,171
Yep, recounted, 60480 is it.
#29
07-18-2012, 10:12 AM
 Great Antibob Guest Join Date: Feb 2003
Here's how to work that problem in a more formal way.

There are 9 "positions". There are C(9,3) = 84 ways to choose which positions the 1, 2, 3 go in.

This is the simple way to compute what Frylock was trying to do by hand.

*Note: equivalently, you can choose which positions the other 6 numbers go in, or C(9,6) = 84, which works out to the same.

For the other 6 numbers, there are 6! = 720 permutations. For example, if the first three numbers are 123, there are 720 ways to arrange the remaining 6 numbers:

123456789
123456798
123987654
etc

So, there are a total of C(9,3)*6! = 84*720 = 60,480 such integers, which matches what TriPolar got by hand.

Last edited by Great Antibob; 07-18-2012 at 10:12 AM.
#30
07-18-2012, 10:12 AM
 Frylock Guest Join Date: Jun 2001
Quote:
 Originally Posted by Frylock You just need to figure out how many items are in the following list: 123...... 12.3..... 12..3.... . . . 1..2...3. 1..2....3 1...23... . . . . ....1..23 .....123. .....12.3 .....1.23 ......123 No time now to count it up but I imagine conceptualizing the problem that way should make the math more obvious.
To correct the above, you take the number of items on the implied list I gave, and multiply it by the number of possible combinations of six digits in six spaces.
#31
07-18-2012, 10:29 AM
 pancakes3 Guest Join Date: Nov 2008
Quote:
 Originally Posted by Great Antibob Here's how to work that problem in a more formal way. There are 9 "positions". There are C(9,3) = 84 ways to choose which positions the 1, 2, 3 go in. This is the simple way to compute what Frylock was trying to do by hand. *Note: equivalently, you can choose which positions the other 6 numbers go in, or C(9,6) = 84, which works out to the same. For the other 6 numbers, there are 6! = 720 permutations. For example, if the first three numbers are 123, there are 720 ways to arrange the remaining 6 numbers: 123456789 123456798 123987654 etc So, there are a total of C(9,3)*6! = 84*720 = 60,480 such integers, which matches what TriPolar got by hand.
doesn't 9C3 method just give the exact combinations where 1-2-3 are in a row?
#32
07-18-2012, 10:33 AM
 TriPolar Member Join Date: Oct 2007 Location: rhode island Posts: 20,171
Quote:
 Originally Posted by pancakes3 doesn't 9C3 method just give the exact combinations where 1-2-3 are in a row?
I don't know, but he got the same total I did, which included all that had the sequence 1-2-3 going left to right, including numbers like 516283794.

ETA: I assumed you weren't counting rotations like 345678912.

Last edited by TriPolar; 07-18-2012 at 10:34 AM.
#33
07-18-2012, 10:34 AM
 jpei Guest Join Date: Feb 2009
Here's another way to get the same answer:

Let us call this set of 9-digit integers with the digits 1-9 used once, the set X.

Ignoring all other digits, there's nothing special about the digits 1, 2, and 3 being in ascending order. They could just as easily be in the order 1, 3, and 2, or 2, 1, and 3.

We can imagine dividing this set X into:
{The subset with 1,2,3 being in the order 123}
{The subset with 1,2,3 being in the order 132}
{The subset with 1,2,3 being in the order 213}
{The subset with 1,2,3 being in the order 231}
{The subset with 1,2,3 being in the order 312}
{The subset with 1,2,3 being in the order 321}

One may check that each number in X belongs to exactly one of these subsets.

Given no further restrictions, one may conclude that by symmetry, these sets are of equal size. The problem statement gives the size of X as 362880, so there are 362880/3! = 60480 such numbers having the digits 1, 2, and 3 in order.

Last edited by jpei; 07-18-2012 at 10:35 AM. Reason: missed a word
#34
07-18-2012, 10:34 AM
 Great Antibob Guest Join Date: Feb 2003
Quote:
 Originally Posted by pancakes3 doesn't 9C3 method just give the exact combinations where 1-2-3 are in a row?
No, it's the number of different positions you can choose for the numbers.

Let's say you have 9 "positions"

_ _ _ _ _ _ _ _ _

How many ways can you choose 3 of these positions for 1-2-3? The answer is 9C3.

You can always verify it by counting them by hand:

1 2 3 _ _ _ _ _ _
1 _ 2 3 _ _ _ _ _
1 _ _ 2 3 _ _ _ _
etc

There are 9C3 = 84 of these.

As I noted, you can equivalently use 9C6, which is the number of ways of choosing which positions 1-2-3 are NOT in.

After you have that, 6! is the number of combinations for the rest, i.e. after the positions of 1-2-3 are decided.

For example, if you have _ _ 1 _ 2 _ _ 3 _, then there are 6! = 720 ways to arrange the other 6 digits in the blanks.
#35
07-18-2012, 10:47 AM
 Great Antibob Guest Join Date: Feb 2003
By the way, another way to check the 9C3 is ok is by allowing permutations of 1-2-3.

So, if you allowed 3-2-1, 1-2-3, 1-3-2, etc, we'd have 9P3, instead.

Including the other 6 digits, the total number of integers would be:

9P3 * 6!, which works out to (9!/6!)*6! = 9!

So, the calculation using 9C3 is consistent with allowing permutations of all 9 digits without constraint.

This is the same thing that jpei noted but from the other direction.
#36
07-18-2012, 10:51 AM
 TriPolar Member Join Date: Oct 2007 Location: rhode island Posts: 20,171
Ok, so if you want to count rotations, I just looked for all combinations of RGB, BRG, and GBR. There are 181440 of those.

I just realized I didn't have write down ALL the numbers, just the integers between 123456789 and 987654321. It was really hard writing down those irrational numbers, and you don't even use them.
#37
07-18-2012, 12:02 PM
 Jas09 Guest Join Date: Jan 2007
Props to jpei (I did it the longer way) - that's very elegant and exactly the sort of thing MathCounts would applaud.
#38
07-18-2012, 12:17 PM
 TriPolar Member Join Date: Oct 2007 Location: rhode island Posts: 20,171
Quote:
 Originally Posted by TriPolar Ok, so if you want to count rotations, I just looked for all combinations of RGB, BRG, and GBR. There are 181440 of those.
Quote:
 Originally Posted by Jas09 Props to jpei (I did it the longer way) - that's very elegant and exactly the sort of thing MathCounts would applaud.
Yes, look at that! 3*60480=181440. That would have been way easier.
#39
07-19-2012, 10:01 AM
 pancakes3 Guest Join Date: Nov 2008
Twofer:

1) What is the largest value of n for which 213! is divisible by (7!)^n

2) Let N be any 3-digit integer which has none of its digits equal to zero. Let M be the 3-digit integer formed by reversing the order of N's digits. What is the greatest integer that is always a factor of the positive difference of N and M. (is it 0?)
#40
07-19-2012, 10:07 AM
 truthSeeker2 Guest Join Date: Jun 2012
Quote:
 Originally Posted by pancakes3 Twofer: 1) What is the largest value of n for which 213! is divisible by (7!)^n 2) Let N be any 3-digit integer which has none of its digits equal to zero. Let M be the 3-digit integer formed by reversing the order of N's digits. What is the greatest integer that is always a factor of the positive difference of N and M. (is it 0?)
1.

Since 7 is the largest prime number from 1 to 7. Count all the factors of 7 from 1 to 213 for the answer:
Answer = 213/7 + 213/49 = 34
#41
07-19-2012, 10:12 AM
 truthSeeker2 Guest Join Date: Jun 2012
Quote:
 Originally Posted by pancakes3 Twofer: 1) What is the largest value of n for which 213! is divisible by (7!)^n 2) Let N be any 3-digit integer which has none of its digits equal to zero. Let M be the 3-digit integer formed by reversing the order of N's digits. What is the greatest integer that is always a factor of the positive difference of N and M. (is it 0?)
2. yes its 0
say:
N =111
M =111
#42
07-19-2012, 11:23 AM
 Indistinguishable Guest Join Date: Apr 2007
Quote:
 Originally Posted by truthSeeker2 2. yes its 0 say: N =111 M =111
It's 99 (which happens to divide 0; also, the question-writer was unduly skittish about digits being equal to zero).

Let the original number be A * 100 + B * 10 + C. Its reverse is then C * 100 + B * 10 + A. The difference will be (A - C) * 99. (And taking its absolute value won't change what divides it). So 99 always divides the difference, and if |A - C| = 1, nothing greater will.
#43
07-19-2012, 11:41 AM
 truthSeeker2 Guest Join Date: Jun 2012
Quote:
 Originally Posted by Indistinguishable It's 99 (which happens to divide 0; also, the question-writer was unduly skittish about digits being equal to zero). Let the original number be A * 100 + B * 10 + C. Its reverse is then C * 100 + B * 10 + A. The difference will be (A - C) * 99. (And taking its absolute value won't change what divides it). So 99 always divides the difference, and if |A - C| = 1, nothing greater will.
Oops I missed that the question mentions "positive difference" , so the difference cant be zero. Hence A cant be same as C.
You are right.

Last edited by truthSeeker2; 07-19-2012 at 11:43 AM.
#44
07-19-2012, 11:54 AM
 Indistinguishable Guest Join Date: Apr 2007
Quote:
 Originally Posted by truthSeeker2 Oops I missed that the question mentions "positive difference" , so the difference cant be zero. Hence A cant be same as C. You are right.
A CAN be the same as C, and the answer would still be 99, in the sense that 99 divides 0. The question is distractingly, unnecessarily paranoid in its wording.

Last edited by Indistinguishable; 07-19-2012 at 11:55 AM.
#45
07-19-2012, 12:19 PM
 Indistinguishable Guest Join Date: Apr 2007
Quote:
 Originally Posted by truthSeeker2 Since 7 is the largest prime number from 1 to 7. Count all the factors of 7 from 1 to 213 for the answer: Answer = 213/7 + 213/49 = 34
This is the correct answer, but it's not clear to me that we can get away with only counting factors of 7 (and not the other prime factors of 7!) just because it's the largest prime from 1 to 7.

For example, 7 is also the largest prime from 1 to 10. But 10!34 doesn't divide 213!. The largest power of 10! which divides 213! is only 10!25.

Last edited by Indistinguishable; 07-19-2012 at 12:23 PM.
#46
07-19-2012, 01:00 PM
 truthSeeker2 Guest Join Date: Jun 2012
Quote:
 Originally Posted by Indistinguishable This is the correct answer, but it's not clear to me that we can get away with only counting factors of 7 (and not the other prime factors of 7!) just because it's the largest prime from 1 to 7. For example, 7 is also the largest prime from 1 to 10. But 10!34 doesn't divide 213!. The largest power of 10! which divides 213! is only 10!25.
Right, I know. Since 7 was a smaller number I took smallest way for explaining.

Otherwise one would need to count factors of every prime number. like in 10! :
2's factor comes 8 times
3's factor comes 4 times
5's factor comes 2 times
7's factor comes once.

Count factors in 213! for each of these
For 2:
213/2+213/4+213/8+213/16+213/32+213/64 + 213/128
Divide it by 8. Call it a

For 3
213/3+213/9+213/27+213/81
Divide it by 4. Call it b

For 5
213/5+213/25+213/125
Divide it by 2. Call it c.

For 7
213/7+213/49
Divide it by 1. Call it d.

The minimum of a,b,c,d is the answer. Turns out b=c=25 is the minimum here.
Could there be another shorter procedure??
#47
07-19-2012, 02:01 PM
 Indistinguishable Guest Join Date: Apr 2007
Right, that's what I would've done (and I would've done the same thing for the multiple prime factors of 7!). But, like you, I am curious if there is a more efficient, shorter procedure.

For example, I know it is always the case that a! * b! * ... * z! divides k! whenever k >= a + b + ... + z. [Since (a + b + ... + z)!/(a! * b! * ... * z!) has a combinatoric interpretation as the number of ways to arrange in sequence a set comprised of a indistinguishable items of one color, b items of another color, etc.]. From this, we know that b!n always divides (nb)!, without having to tediously check all the prime factors; thus, we immediately know that 7!30 and 10!21 divide 213!. And, of course, by checking just the largest prime factor, we obtain upper bounds on the exponent. But tightening to the precise cutoff, I don't yet know how to do efficiently.

Last edited by Indistinguishable; 07-19-2012 at 02:02 PM.
#48
07-19-2012, 02:59 PM
 truthSeeker2 Guest Join Date: Jun 2012
Quote:
 Originally Posted by Indistinguishable Right, that's what I would've done (and I would've done the same thing for the multiple prime factors of 7!). But, like you, I am curious if there is a more efficient, shorter procedure. For example, I know it is always the case that a! * b! * ... * z! divides k! whenever k >= a + b + ... + z. [Since (a + b + ... + z)!/(a! * b! * ... * z!) has a combinatoric interpretation as the number of ways to arrange in sequence a set comprised of a indistinguishable items of one color, b items of another color, etc.]. From this, we know that b!n always divides (nb)!, without having to tediously check all the prime factors; thus, we immediately know that 7!30 and 10!21 divide 213!. And, of course, by checking just the largest prime factor, we obtain upper bounds on the exponent. But tightening to the precise cutoff, I don't yet know how to do efficiently.
Good job.
Here's what I could understand till now:
1. For x! when x is prime, there is only need to check factors of x and that is the anwser. For ex. in 13! the anwser is simply 213/13+213/169

2. For x! when x is non-prime, find the largest prime smaller than x.
For ex. in 33! it is 31, one needs to check for 31 i.e. 213/31. Now go to: 32=25 and 33=3*11. In this case one needs to only check for 2,3,11,31 and no other prime factors.

I might now look at this topic tomorrow only as it is 1:30 am here.
#49
07-19-2012, 03:22 PM
 Indistinguishable Guest Join Date: Apr 2007
I'm not sure I understand your #2; are you saying that, if p is the largest prime <= x, you only need to check the prime factors of p, p + 1, ..., x? Why is that? (Indeed, even for the special case of #1, which I find very plausible, I'd like the assurance of a proof)

Last edited by Indistinguishable; 07-19-2012 at 03:22 PM.
#50
07-19-2012, 11:30 PM
 truthSeeker2 Guest Join Date: Jun 2012
Quote:
 Originally Posted by Indistinguishable I'm not sure I understand your #2; are you saying that, if p is the largest prime <= x, you only need to check the prime factors of p, p + 1, ..., x? Why is that? (Indeed, even for the special case of #1, which I find very plausible, I'd like the assurance of a proof)
Yes, you understood #2 correctly.
#1 can be concluded if one visualizes 213! as blocks of x. For ex., for 13!, as blocks 1 to 13, 14 to 26 and so on.
#2 can be arrived upon using #1 and the method we used in post#46.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     Straight Dope Chicago     General Questions     Great Debates     Elections     Cafe Society     The Game Room     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit Side Conversations     The Barn House

All times are GMT -5. The time now is 09:06 AM.