mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-12-19, 09:52   #1
siegert81
 
Dec 2010

10010102 Posts
Default 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
siegert81 is offline   Reply With Quote
Old 2011-12-19, 09:55   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

23×23×53 Posts
Default

No, there is not. And F(16)=1, according with your definition.
LaurV is offline   Reply With Quote
Old 2011-12-19, 16:15   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 + .......
R.D. Silverman is offline   Reply With Quote
Old 2011-12-19, 16:21   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by siegert81 View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-12-19, 16:34   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-12-19, 18:03   #6
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

33×52 Posts
Default

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"
mart_r is offline   Reply With Quote
Old 2011-12-20, 01:01   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by siegert81 View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-12-20, 04:02   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

23×23×53 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
LaurV is offline   Reply With Quote
Old 2011-12-20, 04:21   #9
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11×569 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 View Post
** 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.
retina is online now   Reply With Quote
Old 2011-12-20, 04:38   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

23×23×53 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2011-12-20, 10:59   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primality test based on factorization of n^2+n+1 carpetpool Miscellaneous Math 5 2018-02-05 05:20
Factorization and primality test O([log_9(N)]^3) Alberico Lepore Alberico Lepore 26 2017-12-17 18:44
Blend test is failing on FFT length 1120k every time Unregistered Information & Answers 0 2011-12-05 02:07
Unfixing FFT length for LL test tichy Software 2 2011-01-12 21:18
Does the LL test:s factorization save or waste CPU time? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.