mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-01-28, 17:55   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22×34 Posts
Post Probability that n is a prime power

What is the probability n has the form p^k with p prime and k > 0? The answer isn't addressed in here, but should it be a similar result to 1/log(n)? Thanks.
carpetpool is offline   Reply With Quote
Old 2017-01-28, 18:06   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by carpetpool View Post
What is the probability n has the form p^k with p prime and k > 0? The answer isn't addressed in here, but should it be a similar result to 1/log(n)? Thanks.
http://mathworld.wolfram.com/PrimePower.html ?

Last fiddled with by science_man_88 on 2017-01-28 at 18:08
science_man_88 is offline   Reply With Quote
Old 2017-01-28, 18:17   #3
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22×34 Posts
Post

That source includes exponents > 2, which is fine. What about exponents > 1?


Is O (x^(1/2) log x) + x/(log (x)) a good estimate? Anyone think of a better one? Thanks sm88 for that?

(This is for the number of prime powers < x, not the probability that n is a prime power, what was originally asked which should easily be inferred from the counting of prime powers < x.)

Last fiddled with by carpetpool on 2017-01-28 at 18:19
carpetpool is offline   Reply With Quote
Old 2017-01-28, 18:31   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by carpetpool View Post
That source includes exponents > 2, which is fine. What about exponents > 1?


Is O (x^(1/2) log x) + x/(log (x)) a good estimate? Anyone think of a better one? Thanks sm88 for that?

(This is for the number of prime powers < x, not the probability that n is a prime power, what was originally asked which should easily be inferred from the counting of prime powers < x.)
well they're related ( although most likely tangentially) we have x numbers and we know how many are prime powers in theory also this includes the exponent 2 if you read it carefully. I'm not sure I actually agree with it in that not all squares less than x are powers of primes ( although I guess that's the exponent being prime part?). technically I would just use logint to figure out a rough upper bound to the number of values that are powers of primes or use the PARI/GP isprimepower to count them for low values). also you could start with the probability that a number is composite then multiply the probabilities of being not divisible by certain primes to get the odds of the number being a power of a specific prime.
science_man_88 is offline   Reply With Quote
Old 2017-01-28, 22:46   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

The 'probability', in an appropriate sense, that a random number near x is a prime power with exponent >= 1 is 1/log x. For exponent >= 2 the 'probability' is 1/sqrt(x log x). For exponent >= k the 'probability' is (x log x)^(1/k)/x.

Last fiddled with by CRGreathouse on 2017-01-28 at 22:47
CRGreathouse is offline   Reply With Quote
Old 2017-01-30, 01:43   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×31×101 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
The 'probability', in an appropriate sense, that a random number near x is a prime power with exponent >= 1 is 1/log x. For exponent >= 2 the 'probability' is 1/sqrt(x log x). For exponent >= k the 'probability' is (x log x)^(1/k)/x.
If I take k=2 then:

1/sqrt(x log x) != (x log x)^(1/k)/x

retina is offline   Reply With Quote
Old 2017-01-30, 02:54   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Oops. I think I was wrong on both.

I think the probability should be 1/(x^(1 - 1/k) log x) which is 1/(sqrt(x) log(x)) for k = 2. You get a different constant term if you look at the numbers up to x rather than near x as I did.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Probability that N is prime given each divisor of N has the form 2*k*p+1 carpetpool Miscellaneous Math 6 2017-09-01 13:59
Probability that n is a semi-prime or prime carpetpool Miscellaneous Math 27 2017-01-19 21:00
probability a number is prime with a weighted k. Trilo Homework Help 12 2014-06-06 19:17
Sieve depth vs. prime probability Unregistered Information & Answers 2 2010-05-25 20:51
Probability of finding a prime number Deamiter Software 4 2002-10-11 16:36

All times are UTC. The time now is 00:33.


Sun Sep 26 00:33:35 UTC 2021 up 64 days, 19:02, 0 users, load averages: 1.03, 1.31, 1.50

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