20090628, 00:41  #1 
May 2009
Loughborough, UK
2C_{16} Posts 
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) = n^{1/2}log(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? 
20090629, 17:54  #2  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
11,657 Posts 
Quote:
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 20090629 at 17:55 Reason: Example: 3^2  1 = 2*2*2 

20090629, 18:25  #3 
Aug 2006
5,987 Posts 
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.612e11 ("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 20090629 at 18:27 
20090630, 11:06  #4  
May 2009
Loughborough, UK
2^{2}×11 Posts 
Apologies for missing out a few bigOhs or "~=" in my first post.
Quote:
but as a or x tends to infinity, something has to fill up Phi...?????? Also of course 3^{2}1=2^{3} 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/2}log(n)) or O(n^{1/2}log(n)^{1/2}) ? I get it, it was my slip of missing the bigOhs out n^{1/2}log(n)^{1/2} is O(n^{1/2}log(n)) but sharper. Hmmm, for the density then I need littleoh. 

20090630, 12:35  #5 
May 2009
Loughborough, UK
2^{2}·11 Posts 
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 
20090630, 13:56  #6  
Aug 2006
5,987 Posts 
Quote:
But it's clear, even "obvious", that it's correct. Do be careful, though: Quote:


20090630, 15:51  #7  
"William"
May 2003
Near Grandkid
3×7×113 Posts 
Quote:
http://www1.unihamburg.de/RRZ/W.Kel...tQuotient.html 

20090630, 21:29  #8  
May 2009
Loughborough, UK
101100_{2} Posts 
Quote:
Quote:
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^{8} =============== 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 

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  20160506 08:13 
2^x using powers of e?  nibble4bits  Math  31  20071211 12:56 
Sums of prime powers  grandpascorpion  Math  49  20070422 17:06 
Powers, and more powers  Numbers  Puzzles  3  20050713 04:42 
Question on prime powers  JuanTutors  Math  2  20040707 07:07 