mersenneforum.org > Math Prime Powers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2009-06-28, 00:41 #1 plandon   May 2009 Loughborough, UK 22×11 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) = 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?
2009-06-29, 17:54   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

132×67 Posts

Quote:
 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

Last fiddled with by xilman on 2009-06-29 at 17:55 Reason: Example: 3^2 - 1 = 2*2*2

 2009-06-29, 18:25 #3 CRGreathouse     Aug 2006 3×1,993 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.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
2009-06-30, 11:06   #4
plandon

May 2009
Loughborough, UK

22·11 Posts

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

Quote:
 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 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.

 2009-06-30, 12:35 #5 plandon   May 2009 Loughborough, UK 22×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
2009-06-30, 13:56   #6
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 Originally Posted by plandon 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 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).

2009-06-30, 15:51   #7
wblipp

"William"
May 2003
New Haven

237110 Posts

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

2009-06-30, 21:29   #8
plandon

May 2009
Loughborough, UK

22×11 Posts

Quote:
 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.

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

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Factoring 2 2016-05-06 08:13 nibble4bits Math 31 2007-12-11 12:56 grandpascorpion Math 49 2007-04-22 17:06 Numbers Puzzles 3 2005-07-13 04:42 JuanTutors Math 2 2004-07-07 07:07

All times are UTC. The time now is 03:07.

Sun May 29 03:07:48 UTC 2022 up 45 days, 1:09, 0 users, load averages: 0.74, 0.93, 1.01

Copyright ©2000 - 2022, 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.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐