RE: A mathematical problem I can't seem to get Mathematica to auto solve.
May 22, 2022 at 9:46 am
(May 21, 2022 at 6:45 pm)Paleophyte Wrote: Looks like it was a good night for falling down prime number theory rabbit holes. After wandering afoul of Euler and Reimann I bumped into number sieves and am now wondering how to calculate their efficiency. 2 takes care of 50% of all candidates, 3 eliminates 1 in 3, 5 does for 1 in 5... but what is the value of evaluating the remaining prime factors? Yes, I know you have to do it for clear and obvious reasons but I'm wondering how diminishing the returns are.
Put in what I hope are slightly less muddled terms: For any candidate k, where k is a finite but arbitrarily large positive integer, what is the probability (What is the convention for discussing primes and probabilities? Both seem to use p, which leads opens the doorway to some magnificent confusions.) that k is prime if k is not evenly divisible by the first n primes (2, 3, 5, 7, 11... pn) assuming that pn <<< sqrt(k).
I suspect that the answer to this is either laughably trivial or mind-breakingly difficult. There doesn't seem to be a lot of middle ground.
Use capital P for probability and lower case p for primes.
There is an extension of the prime number theorem for primes appearing in an arithmetic progression that might be useful for the probability you are wanting.