mersenneforum.org Probability that n is a prime power
 User Name Remember Me? Password
 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

 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

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.