Author |
Topic: Seven Factors (Read 1408 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Re: Seven Factors
« Reply #1 on: Nov 13th, 2003, 6:38pm » |
 Quote  Modify
|
Do you mean 7 divisors?
7 factors works out rather trivally to 128.
And if 7 divisors is wanted: proper divisors or all divisors? 
|
|
 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
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Seven Factors
« Reply #2 on: Nov 14th, 2003, 12:29am » |
Quote Modify
|
When dealing with integers, isn't a factor and a divisor the same thing? And 128, Icarus? I think you meant, 64: 1,2,4,8,16,32,64. 
This does beg a rather interesting general question though. If Fn represents the smallest number with n factors, what is the most efficient method of determining it?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Seven Factors
« Reply #3 on: Nov 14th, 2003, 12:58am » |
Quote Modify
|
well, just take 2^n
(if you count one as a factor, no number has exactly n, since all would have an unlimited number of 1's as factors)
The difference between divisors and factors (aisi), 5^2 has two factors of 5, but only one divisor 5.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Seven Factors
« Reply #4 on: Nov 14th, 2003, 3:33am » |
Quote Modify
|
Not quite, towr. F4=6, as 1,2,3,6, are factors, whereas, 24=16, and has five factors: 1,2,4,8,16.
Athough 2n–1 is guaranteed to have n factors, it is not necessarily the smallest.
For reference this Table of Divisors might be useful.
With reference to the difference between the word factor and divisors, I know that MathWorld is not the authority, but he suggests that the terms are synomynous; he also lists 1 as being a factor/divisor:
http://mathworld.wolfram.com/Divisor.html
Regardless of the technicalities, perhaps we ought to rephrase the problem for clarity...
Let d(n) be the number of integers that evenly divide the natural number n.
Let Fn be the smallest natural number for which d(n)=n.
What is the most efficient method of determining Fn?
Another interesting question would be to ask, for which values of n is Fn=2n–1; in other words, when is the guaranteed form the smallest case?
[e]Edited to correct statement about the number of factors of 2n.[/e]
|
| « Last Edit: Nov 14th, 2003, 6:05am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Seven Factors
« Reply #5 on: Nov 14th, 2003, 3:52am » |
Quote Modify
|
on Nov 14th, 2003, 3:33am, Sir Col wrote:| Not quite, towr. F4=6, as 1,2,3,6, are factors, whereas, 24=16. |
|
No, imo, it has factor 2 and 3, and divisors 1,2,3,6
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Seven Factors
« Reply #6 on: Nov 14th, 2003, 6:02am » |
Quote Modify
|
Oops, I think we've all made a boo-boo here. 
24=16, and using your method there would be 3 factors: 2,4,8, because you're counting neither 1 nor 16; using my method there would be 5 factors: 1,2,4,8,16, as I don't discriminate  ; and using Icarus' method there would be 4 factors: 2,4,8,16 or 1,2,4,8, because he doesn't seem to include 1 or the number itself (I don't know which).
Using the newly defined problem (to avoid differences between interpretation of factors/divisors), 2n would have n+1 divisors. So 2n–1 would be guaranteed to have exactly n divisors.
Anyway, back to the new challenge...
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Seven Factors
« Reply #7 on: Nov 14th, 2003, 6:22am » |
Quote Modify
|
on Nov 14th, 2003, 6:02am, Sir Col wrote:
24=16, and using your method there would be 3 factors: 2,4,8, because you're counting neither 1 nor 16 |
|
towr will surely disagree here. Using his method/notion, 24 has exactly four factors, namely four times the factor 2. If you have the factors 2, 4, 8, then the product would be 64. (Of course you can arrive at other factors of 64.)
I think the term "divisor" is a little more unambiguous.
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Seven Factors
« Reply #8 on: Nov 14th, 2003, 10:04am » |
Quote Modify
|
My point is the same as towr's. By my preference anyway, factors refers to the individual contributions to a product. If you allow 1 to be a factor by this definition, the smallest natural number with 7 factors is (by the traditional definition of "natural number") is 1 = 1*1*1*1*1*1*1. Without allowing 1, it is 128 = 2*2*2*2*2*2*2.
I suggested that "divisor" is a better description because divisor means "a number which divides (leaving an integer result)". Changing the problem to "Find the smallest natural number with 7 divisors" squares things up nicely.
|
|
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
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Seven Factors
« Reply #9 on: Nov 14th, 2003, 10:11am » |
Quote Modify
|
Indeed, wowbagger, that's what I was about to say ..
Though I've come to the realization prime factorization is perhaps an unfair limitation.
So I think proper divisors would be best.
on Nov 14th, 2003, 10:04am, Icarus wrote:| If you allow 1 to be a factor by this definition, the smallest natural number with 7 factors is (by the traditional definition of "natural number") is 1 = 1*1*1*1*1*1*1. |
|
Since the problem asks for exactly 7 factors, this can't work, so 1 would have to be excluded.
|
| « Last Edit: Nov 14th, 2003, 10:17am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Seven Factors
« Reply #10 on: Nov 14th, 2003, 1:36pm » |
Quote Modify
|
First of all, for the question to have an interesting answer, we cannot include both 1 and Fn when counting the number of divisors.
Considering every number to be the product of powers of primes, we have:
Fn = p1ap2bp3c...
The number of different combinations of these prime factors, including both 1 and Fn is (a+1)(b+1)(c+1)..., which is obviously composite unless only one of a,b,c,... is non-zero.
Therefore, we can pick a solution when this product is equal to 8, or when it's equal to 9, giving the two smallest answers under the two "interesting" interpretations (2*2*3*3 = 36, with factors 2,3,4,6,9,12, and 18), or (2*2*2*3 = 24, with factors 2,3,4,6,8,12, and 24). Alternately, we could say that the factors of 24 are 1,2,3,4,6,8, and 12.
For small numbers, this is easy to work out by hand, but the algorithm might still be complex.
|
|
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: Seven Factors
« Reply #11 on: Nov 14th, 2003, 3:33pm » |
Quote Modify
|
on Nov 14th, 2003, 10:11am, towr wrote:| Since the problem asks for exactly 7 factors, this can't work, so 1 would have to be excluded. |
|
I count exactly 7 ones in that product. By the definition I said I was using in the sentence immediately before, this works. That you could also write out a product with more ones is immaterial.
James - I think perhaps the "point" behind this puzzle is that it is impossible to have exactly 7 divisors.
So for proper divisors, the answer is 36. To include one of the "improper divisors" but not the other is a bit nonsensical in my opinion.
|
|
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
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Seven Factors
« Reply #12 on: Nov 14th, 2003, 4:04pm » |
Quote Modify
|
Nice idea, James.
Okay, guys, I'm thoroughly confuddled. What are we actually saying about factors, divisors, and proper divisors?
How can 36 be the answer for proper divisors? As 1,2,3,4,6,9,18, and 12, all evenly divide 36, I get 8 proper divisors. 
Regardless of our personal interpretation of the word 'factor', I thought that the word divisor is clearly defined: a number which evenly divides n; that is, without remainder. A proper divisor is a divisor, excluding n itself.
As you've ignored, or disliked, my attempt to clarify the problem by defining d(n), I suppose we could equally erradicate the ambiguity by asking, "If Fn is the smallest number with n distinct factors, what is F7?"
It's amazing that we can all hold such diverse ideas on something so fundamental. It would be interesting to ask, where would we seek an authority on this, or does it not exist due to cultural diversity in mathematics?
|
| « Last Edit: Nov 14th, 2003, 4:08pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Seven Factors
« Reply #13 on: Nov 14th, 2003, 8:43pm » |
Quote Modify
|
Like most language considerations, there is no one authority to definitely lay down the law. When multiple usages abound, those enamored of one will not accept any authority that says differently.
Speaking of which: The definition of a proper divisor is any divisor other than itself or 1. So 36 has only 7 proper divisors. I have never seen anyone other than you define 1 as a proper divisor!
And as James has pointed out, by your definition, F7 does not exist. (Actually, by the definition as you stated it, Fn does not exist for any odd n, since your definition would also count negative divisors, but I assume that was unintensional.)
|
|
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
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Seven Factors
« Reply #14 on: Nov 14th, 2003, 9:00pm » |
Quote Modify
|
on Nov 14th, 2003, 3:33pm, Icarus wrote:
James - I think perhaps the "point" behind this puzzle is that it is impossible to have exactly 7 divisors. |
|
If we include all divisors, the answer is 64, with divisors 1, 2, 4, 8, 16, 32, 64, as Sir Col pointed out much earlier.
The number of distinct divisors of n (including "improper" divisors) is easily computed from the exponents of n's distinct prime factors. If n has prime factorization [prod]ipiki, then it obviously has [prod]i(ki + 1) distinct divisors -- we can form each divisor of n in exactly one way by taking the prime factorization of n and changing each exponent ki to some value in the closed interval [0, ki].
This gives us a good start on Sir Col's "efficient method" challenge. Suppose we want the least positive integer n with exactly m divisors. We need to look at the possible factorizations of m into factors >1 (not necessarily prime). Each of these is a pattern that the exponents of n's prime factors can have. We then look at each pattern, computing the least n for that pattern by assigning primes in ascending order to exponents in descending order, and check which gives the smallest n. In the stated case m=7, there is only one choice, and so n = 26 = 64 is the answer.
If you only want to count proper divisors, the stated case becomes m=9. There are two patterns: 9=3*3 or 9=9. These give candidate answers 22*32=36 and 28=256, so 36 is the desired result.
I imagine there are some observations I haven't made here that can reduce the number of patterns you have to consider, but this method is already pretty efficient.
|
| « Last Edit: Nov 14th, 2003, 9:07pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Seven Factors
« Reply #15 on: Nov 14th, 2003, 9:28pm » |
Quote Modify
|
I doubt if this is much help on this question, but a related problem that I recently saw was phrased as follows:
Quote:| What is the smallest positive integer that has at least 1000 different integer factors? For example, 12 has six factors: 1, 2, 3, 4, 6, and 12. |
|
|
|
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Seven Factors
« Reply #16 on: Nov 15th, 2003, 12:22pm » |
Quote Modify
|
Great method, TimMann; and beautifully explained!
Applying it to SWF's problem...
::
m=1000=2x2x2x5x5x5.
So least such number with 1000 factors is 24.34.54.7.11.13=810810000.
::
I haven't proved it, but I conjecture that writing n=p1p2p3...pk, without exponents, provides the smallest such number; obviously we assign the larger powers to the smallest primes. For example, solving for m=60=2x2x3x5. The smallest number with 60 factors will be 24x32x5x7=5040.
Anyone care to prove/disprove my conjecture?
Not sure about T&B's problem yet.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Seven Factors
« Reply #17 on: Nov 15th, 2003, 1:22pm » |
Quote Modify
|
Using my method, but not checking all patterns exhaustively, I get the following results, in decreasing order of confidence. Can anyone find a mistake?
I believe the smallest positive integer with exactly 1000 distinct positive integer divisors is 24 * 34 * 54 * 7 * 11 * 13 = 810810000, from the pattern 5 * 5 * 5 * 2 * 2 * 2 = 1000. (This result agrees with Sir Col's, posted while I was composing this message.)
Are there smaller numbers with at least 1000 divisors? (That's what SWF actually asked for.) Yes; for example, 27 * 33 * 5 * 7 * 11 * 13 * 17 = 294053760 has 8 * 4 * 2 * 2 * 2 * 2 * 2 = 1024 divisors. I think this is the smallest with 1024 divisors. (This result refutes Sir Col's conjecture, which would have it that 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6469693230 is the smallest with 1024. Factoring all the way down to primes generally gets you close, but you can often do better.)
The smallest number I've found with at least 1000 divisors is 26 * 32 * 52 * 7 * 11 * 13 * 17 = 245044800, with 1008. I found this one by searching upward from 1000 for numbers whose prime factors are all small.
|
| « Last Edit: Nov 15th, 2003, 1:25pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Seven Factors
« Reply #18 on: Nov 15th, 2003, 4:43pm » |
Quote Modify
|
I love counter-examples; they can save us so much time trying to prove the impossible. Good find, TimMann.
I'd missed that subtle phrasing of SWF's problem. I think you're right about 1008=24.32.7. I've played with numbers just over 1000 too, but as you said, there aren't many factor options that would leave the exponents low.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
