mersenneforum.org  

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

Reply
 
Thread Tools
Old 2009-06-28, 00:41   #1
plandon
 
May 2009
Loughborough, UK

1011002 Posts
Default Prime Powers

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) = n1/2log(n)

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

Which is it?
plandon is offline   Reply With Quote
Old 2009-06-29, 17:54   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22·23·113 Posts
Default

Quote:
Originally Posted by plandon View Post
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

Last fiddled with by xilman on 2009-06-29 at 17:55 Reason: Example: 3^2 - 1 = 2*2*2
xilman is online now   Reply With Quote
Old 2009-06-29, 18:25   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

173216 Posts
Default

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.

Last fiddled with by CRGreathouse on 2009-06-29 at 18:27
CRGreathouse is offline   Reply With Quote
Old 2009-06-30, 11:06   #4
plandon
 
May 2009
Loughborough, UK

22×11 Posts
Default

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

Quote:
Originally Posted by xilman View Post
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 Phia(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 32-1=23
but apart from that no ax+-1 = by
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 Phia(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(n1/2log(n))
or O(n1/2log(n)-1/2) ?

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

Hmmm, for the density then I need little-oh.
plandon is offline   Reply With Quote
Old 2009-06-30, 12:35   #5
plandon
 
May 2009
Loughborough, UK

22·11 Posts
Default

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
plandon is offline   Reply With Quote
Old 2009-06-30, 13:56   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

593810 Posts
Default

Quote:
Originally Posted by plandon View Post
But I need the density of Prime Powers for something else anyway,
is it O(n1/2log(n))
or O(n1/2log(n)-1/2) ?

I get it, it was my slip of missing the big-Ohs out
n1/2log(n)-1/2 is O(n1/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:
Quote:
Originally Posted by plandon View Post
This
http://math.crg4.com/PrimePowers.pdf
has C(n) = li(n1/2) + O(n1/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) = n1/2 / (log(n1/2)) + O(stuff), which is not the same as C(n) = (n/log(n))1/2 + O(stuff).
CRGreathouse is offline   Reply With Quote
Old 2009-06-30, 15:51   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

Quote:
Originally Posted by plandon View Post
they can contain repeated factors, but Wieferichs (and their generalisations) are not common in Phia(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
wblipp is offline   Reply With Quote
Old 2009-06-30, 21:29   #8
plandon
 
May 2009
Loughborough, UK

22×11 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.

Quote:
Originally Posted by CRGreathouse View Post
Do be careful, though:
This would make C(n) = n1/2 / (log(n1/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
~2n1/2/log(n)
or BigTheta(n1/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 108

===============
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
plandon is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve mickfrancis Factoring 2 2016-05-06 08:13
2^x using powers of e? nibble4bits Math 31 2007-12-11 12:56
Sums of prime powers grandpascorpion Math 49 2007-04-22 17:06
Powers, and more powers Numbers Puzzles 3 2005-07-13 04:42
Question on prime powers JuanTutors Math 2 2004-07-07 07:07

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

Thu Dec 3 17:31:20 UTC 2020 up 13:42, 1 user, load averages: 1.56, 1.63, 1.65

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.