 mersenneforum.org Probability that n is a prime power
 Register FAQ Search Today's Posts Mark Forums Read 2017-01-28, 17:55 #1 carpetpool   "Sam" Nov 2016 22×34 Posts 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.    2017-01-28, 18:06   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by carpetpool 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   2017-01-28, 18:17 #3 carpetpool   "Sam" Nov 2016 22×34 Posts 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   2017-01-28, 18:31   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts Quote:
 Originally Posted by carpetpool 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.   2017-01-28, 22:46 #5 CRGreathouse   Aug 2006 3×1,993 Posts 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   2017-01-30, 01:43   #6
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2×31×101 Posts Quote:
 Originally Posted by CRGreathouse 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    2017-01-30, 02:54 #7 CRGreathouse   Aug 2006 3×1,993 Posts 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.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 6 2017-09-01 13:59 carpetpool Miscellaneous Math 27 2017-01-19 21:00 Trilo Homework Help 12 2014-06-06 19:17 Unregistered Information & Answers 2 2010-05-25 20:51 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