mersenneforum.org > Math Factorization length test?
 Register FAQ Search Today's Posts Mark Forums Read

 2011-12-19, 09:52 #1 siegert81   Dec 2010 10010102 Posts Factorization length test? Hello, Is there a specific test for any given integer that determines its number of prime factors? (Aside from actually finding the actual factors...) Examples: F(10) = 2 F(16) = 4 F(17) = 1 F(110) = 3
 2011-12-19, 09:55 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 23×23×53 Posts No, there is not. And F(16)=1, according with your definition.
2011-12-19, 16:15   #3
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by LaurV No, there is not. And F(16)=1, according with your definition.
Grossly False. He did not give a definition.

If N = p1^a1 * p2^a2 * ........

then his F function could simply be a1 + a2 + .......

2011-12-19, 16:21   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 Originally Posted by siegert81 Hello, Is there a specific test for any given integer that determines its number of prime factors? (Aside from actually finding the actual factors...) Examples: F(10) = 2 F(16) = 4 F(17) = 1 F(110) = 3
I think everyone sees that the definition is inconsistent because f(10)=2 10 has 2 and 5 as prime factors, but 16 = 2^4 has only 1 prime factor namely 2 so it doesn't fit in with the previous line F(17)=1 also only seems to make sense to me if it's prime factors because a prime has but 1 prime factor namely itself. Also contrary to what RDS might say 10 doesn't fit x^2 for any whole number x

Last fiddled with by science_man_88 on 2011-12-19 at 16:22

2011-12-19, 16:34   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by R.D. Silverman Grossly False. He did not give a definition. If N = p1^a1 * p2^a2 * ........ then his F function could simply be a1 + a2 + .......
I get what you mean now.

 2011-12-19, 18:03 #6 mart_r     Dec 2008 you know...around... 33×52 Posts The only thing that comes to my mind is, that if N is not prime (simple PRP-test) and you have trial divided further than N^(1/3) without finding a factor, then you can say that N has two factors without actually finding them. But that's all. Last fiddled with by mart_r on 2011-12-19 at 18:04 Reason: +"without finding a factor"
2011-12-20, 01:01   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by siegert81 Hello, Is there a specific test for any given integer that determines its number of prime factors? (Aside from actually finding the actual factors...) Examples: F(10) = 2 F(16) = 4 F(17) = 1 F(110) = 3
only thing I can give based on what RDS has found is F(x*y)=F(x)+F(y) but this doesn't help unless you know a factorization already in which case you know if it's prime or not already.

Last fiddled with by science_man_88 on 2011-12-20 at 01:05

2011-12-20, 04:02   #8
LaurV
Romulan Interpreter

Jun 2011
Thailand

23×23×53 Posts

Quote:
 Originally Posted by R.D. Silverman Grossly False. He did not give a definition. If N = p1^a1 * p2^a2 * ........ then his F function could simply be a1 + a2 + .......
How in the hack you define "the number of prime factors" in English???

Does 9 have one prime factor, or two? Does 75 have 2 prime factors, or 3? Maybe English math is different then the math I have learned**. Did you read his post? Or you did not find anybody to tease now, and you started with me?

** that was not rhetorical, for example, I always had trouble to understand the concept of "proper" divisor in English, as "1" is considered to be "proper" divisor. All definitions of aliquot sequences say "the sum of all proper divisors", where also "1" is summed. So, the English math considers only the number itself to be un-proper. But 1 divides any number, so, it is not proper to nothing. How do you call the divisors of a number which are not 1 and not the number itself? "Not-trivial" divisors? But in that case, any even number has the factor 2, which is also "trivial". etc. etc. The discussion is endless. In my language a "proper" divisor is that one which is not "1" and not the number itself. That I have learned in elementary math.

Last fiddled with by LaurV on 2011-12-20 at 04:08

2011-12-20, 04:21   #9
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

11×569 Posts

Quote:
 Originally Posted by LaurV How in the hack you define "the number of prime factors" in English??? Does 9 have one prime factor, or two? Does 75 have 2 prime factors, or 3? Maybe English math is different then the math I have learned**. Did you read his post? Or you did not find anybody to tease now, and you started with me?
Try:
"The number of unique prime factors" would mean that nine has one i.e. 3.
"The number of unique divisors" would mean that nine has three i.e. 1, 3 and 9.
"The number of prime factors" (perhaps this one is not well defined) would mean that nine has two i.e. 3 and 3.
Quote:
 Originally Posted by LaurV ** that was not rhetorical, for example, I always had trouble to understand the concept of "proper" divisor in English, as "1" is considered to be "proper" divisor. All definitions of aliquot sequences say "the sum of all proper divisors", where also "1" is summed. So, the English math considers only the number itself to be un-proper. But 1 divides any number, so, it is not proper to nothing. How do you call the divisors of a number which are not 1 and not the number itself? "Not-trivial" divisors? But in that case, any even number has the factor 2, which is also "trivial". etc. etc. The discussion is endless. In my language a "proper" divisor is that one which is not "1" and not the number itself. That I have learned in elementary math.
"1" is a proper divisor, but it is not a prime divisor.

 2011-12-20, 04:38 #10 LaurV Romulan Interpreter     Jun 2011 Thailand 23×23×53 Posts Thanks retina. So, 75 has 3 prime factors, 3, 5, and... 5. And 1 is a divisor which is "proper" to any number. Got it :P And again, how do you call (in a word) all the divisors of a number (by the way, divisor means "not necessarily prime", see pari function with the same name) except 1 and the number itself?? For example, for 24, this set is {2,3,4,6,8,12}. These I would call proper divisors, in my language. As every number is divisible by 1 and by the number itself, these divisors are not proper. A prime is a number without proper divisors. These definitions are translated mot-a-mot from an elementary arithmetics book in my language. By the same book, "factor" is always prime, a construction like "prime factor" is pleonastic. Of course, you will agree that all this discussion is just for the sake of the discussion itself. But I still would like to get an answer for the question. Is there any word in English math to describe the set of all divisors, except 1 and the number itself? Beside of "non-trivial", or its relatives, as the term "trivial" is in itself more confusing: 2 is a trivial factor of any even number, same as 5 is a trivial factor of any number ending in 0 or 5, because you can see that factor in a blink of an eye, so it is "trivial"... As 64 is a trivial square root of 2 (mod 2^11-1). Last fiddled with by LaurV on 2011-12-20 at 04:56
2011-12-20, 10:59   #11
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by LaurV How in the hack you define "the number of prime factors" in English??? Does 9 have one prime factor, or two? Does 75 have 2 prime factors, or 3? Maybe English math is different then the math I have learned**. Did you read his post? Or you did not find anybody to tease now, and you started with me?
You stated, quite clearly that his function F was wrong for F(16) according
to his definition. But he DID NOT GIVE a definition. I pointed out that
there was a very consistent way to define F.

This function is known as $\Omega(n)$. It is WELL KNOWN.
It counts prime factors with MULTIPLICITY. It is different from
$\omega(n)$ which counts DISTINCT prime factors.

I said that your assertion was wrong and it was. It is clear that it was
you who failed to read the post, otherwise you would not claim that
a definition was given when one was not.

And your accusation that I was looking for someone to tease is
way off base.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 5 2018-02-05 05:20 Alberico Lepore Alberico Lepore 26 2017-12-17 18:44 Unregistered Information & Answers 0 2011-12-05 02:07 tichy Software 2 2011-01-12 21:18 svempasnake Software 42 2002-10-24 19:27

All times are UTC. The time now is 17:26.

Sat Sep 18 17:26:45 UTC 2021 up 57 days, 11:55, 0 users, load averages: 2.95, 2.34, 1.88