Prime Powers

[plandon]

Prime Powers (exponent >= 2) are supposed to be rare, but how rare?

No Cunningham numbers can be prime powers, so there is no problem there with SNFS or GNFS.

How rare are they?
Let C(n) be the number of prime powers (exponent >= 2) below n.

Mathworld cites Hardy
http://mathworld.wolfram.com/PrimePower.html
as C(n) = n^1/2log(n)

This
http://math.crg4.com/PrimePowers.pdf
has C(n) = li(n^1/2) + O(n^1/3/exp(a.log(n)^1/2))
li(x)=O(x/log(x))
So C(n) = (n/log(n))^1/2

Which is it?

[xilman]

Originally Posted by plandon

Prime Powers (exponent >= 2) are supposed to be rare, but how rare?

No Cunningham numbers can be prime powers, so there is no problem there with SNFS or GNFS.

This is wrong.

Repeated factors are possible and, indeed, common in Cunningham numbers. In principle all the unique factors could be removed by other methods, such as ECM, leaving a residue which is a prime power.

In practice, the repeated factors are quite small and found by trial division.


Paul

[CRGreathouse]

xilman, you and plandon are addressing different issues.

plandon is asking about numbers p^e with e >= 2. You are addressing numbers divisible by such numbers.

xilman: the average number of prime power (>= 2) factors in a large random integer should be primezeta(2) = 0.45224742.... Removing factors beneath a million, the expectation drops to 0.00000006777569137 ("1 in 15 million"); removing those a billion drops it to 4.612e-11 ("1 in 20 billion"). This matches your "in practice" statement.

plandon: MathWorld states that the expectation is O(sqrt(n) log n) which is true but not sharp.

[plandon]

Apologies for missing out a few big-Ohs or "~=" in my first post.

Originally Posted by xilman

Repeated factors are possible and, indeed, common in Cunningham numbers.

Xilman is right, they can contain repeated factors, but Wieferichs (and their generalisations) are not common in Phi_a(x) with the small numbers that we are playing with,
but as a or x tends to infinity, something has to fill up Phi...??????

Also of course 3²-1=2³
but apart from that no a^x+-1 = b^y
Catalan's Conjecture or Preda Mihailescu's Theorem.
So (except 2,3-) no Cunningham number can be a Prime Power.

I suppose it has not yet been proven that Phi_a(x) can't be a Prime Power. (except 2,3-)

But I need the density of Prime Powers for something else anyway,
is it O(n^1/2log(n))
or O(n^1/2log(n)^-1/2) ?

I get it, it was my slip of missing the big-Ohs out
n^1/2log(n)^-1/2 is O(n^1/2log(n))
but sharper.

Hmmm, for the density then I need little-oh.

[plandon]

I meant 2,3+ or 3,2- ;/

All sloppiness and imprecision is mine and hopefully original and unique.
Whenever I type + I usually mean -
IANAM

[CRGreathouse]

Originally Posted by plandon

But I need the density of Prime Powers for something else anyway,
is it O(n^1/2log(n))
or O(n^1/2log(n)^-1/2) ?

I get it, it was my slip of missing the big-Ohs out
n^1/2log(n)^-1/2 is O(n^1/2log(n))
but sharper.

First of all, I can't independently verify that the result you linked to in your first post is correct, since I wrote it in the first place!

But it's clear, even "obvious", that it's correct. Do be careful, though:

Originally Posted by plandon

This
http://math.crg4.com/PrimePowers.pdf
has C(n) = li(n^1/2) + O(n^1/3/exp(a.log(n)^1/2))
li(x)=O(x/log(x))
So C(n) = (n/log(n))^1/2

This would make C(n) = n^1/2 / (log(n^1/2)) + O(stuff), which is not the same as C(n) = (n/log(n))^1/2 + O(stuff).

[wblipp]

Originally Posted by plandon

they can contain repeated factors, but Wieferichs (and their generalisations) are not common in Phi_a(x) with the small numbers that we are playing with

The generalization to different bases, sometimes called Vanishing Fermat Quotients, are not all that rare:

http://www1.uni-hamburg.de/RRZ/W.Kel...tQuotient.html

[plandon]

Originally Posted by CRGreathouse

First of all, I can't independently verify that the result you linked to in your first post is correct, since I wrote it in the first place!

But it's clear, even "obvious", that it's correct.).

Cool, respect.

Originally Posted by CRGreathouse

Do be careful, though:
This would make C(n) = n^1/2 / (log(n^1/2)) + O(stuff), which is not the same as C(n) = (n/log(n))^1/2 + O(stuff).

Of course -d'uh!

So after I have made every basic mistake possible I end up with
~2n^1/2/log(n)
or BigTheta(n^1/2/log(n))

On repeated factors of Phi, or generalised Weiferichs or disappearing Fermat quotients,
I would still call them rare.
The searches have gone on much further than it says there, including all prime bases up to 10⁸

===============
Sig:
All sloppiness and imprecision is mine and hopefully original and unique.
Whenever I type + I usually mean -
IANAM
unless stated otherwise O means o means O
This line intentionally left blank