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

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

[QUOTE=LaurV;282777]No, there is not. And F(16)=1, according with your definition.[/QUOTE]

Grossly False. He did not give a definition.

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

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

[QUOTE=siegert81;282776]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[/QUOTE]

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

[QUOTE=R.D. Silverman;282809]Grossly False. He did not give a definition.

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

then his F function could simply be a1 + a2 + .......[/QUOTE]

I get what you mean now.

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.

[QUOTE=siegert81;282776]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[/QUOTE]

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.

[QUOTE=R.D. Silverman;282809]Grossly False. He did not give a definition.

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

then his F function could simply be a1 + a2 + .......[/QUOTE]

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? :smile:


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

[QUOTE=LaurV;282865]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? :smile:[/QUOTE]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=LaurV;282865]** 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.[/QUOTE]"1" is a proper divisor, but it is not a prime divisor.

Thanks retina. So, 75 has 3 prime factors, 3, 5, and... 5. And 1 is a divisor which is "[URL="http://en.wiktionary.org/wiki/proper"]proper[/URL]" to any number. Got it :P
And again, how do you call ([B]in a word[/B]) 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 [B]every number[/B] is divisible by 1 and by the number itself, these divisors are [B]not proper[/B]. 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).

[QUOTE=LaurV;282865]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? :smile:
[/QUOTE]

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 [tex]\Omega(n)[/tex]. It is WELL KNOWN.
It counts prime factors with MULTIPLICITY. It is different from
[tex]\omega(n)[/tex] 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.