mersenneforum.org > Math Prime Powers
 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

1188610 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 22×3×499 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

4410 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 4410 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

598810 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
Near Grandkid

2,377 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

548 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 02:19.

Wed Oct 4 02:19:28 UTC 2023 up 21 days, 1 min, 0 users, load averages: 0.63, 0.79, 0.83