Factorization length test?

siegert81 · 2011-12-19, 09:52

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

LaurV · 2011-12-19, 09:55

No, there is not. And F(16)=1, according with your definition.

R.D. Silverman · 2011-12-19, 16:15

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 + .......

science_man_88 · 2011-12-19, 16:21

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

science_man_88 · 2011-12-19, 16:34

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.

mart_r · 2011-12-19, 18:03

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.

science_man_88 · 2011-12-20, 01:01

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.

LaurV · 2011-12-20, 04:02

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.

retina · 2011-12-20, 04:21

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.

LaurV · 2011-12-20, 04:38

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).

R.D. Silverman · 2011-12-20, 10:59

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.

2011-12-19, 09:52	#1
siegert81 Dec 2010 2×37 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, 18:03	#6
mart_r Dec 2008 you know...around... 2×5×67 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, 04:38	#10
LaurV Romulan Interpreter Jun 2011 Thailand 22665₈ 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

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

2011-12-19, 09:55	#2
LaurV Romulan Interpreter Jun 2011 Thailand 9653₁₀ Posts	No, there is not. And F(16)=1, according with your definition.