View Single Post
Old 2020-11-30, 00:44   #3
carpetpool's Avatar
Nov 2016

32610 Posts

Finding the expected number of primes of (k*b^n+c)/gcd(k+c,b-1) shouldn't be much different than finding the expected number of primes of the form k*b^n+c. If we treat numbers of the form k*b^n+c as "random" integers, then each candidate has probability of about

{1\over n\ln b + \ln k}

If we care about the expected number of primes from {a} to {n}, then we should expect

L = \sum_{x=a}^{n} {1\over x\ln b + \ln k}

or equivalently

L = {1\over \ln b} \sum_{x=a + \ln k}^{n + \ln k} {1\over x}

(note that for small k, it is practical to ignore the {\ln k} term as it will not make much of a difference in calculating the probability. Therefore, it's acceptable to rewrite as

L = {1\over \ln b} \sum_{x=a}^{n} {1\over x}

So for any sequence of randomly behaving integers, we can assume that there will be

L = C \sum_{x=a}^{n} {1\over x}

primes in the sequence up to nth term, where {C} is a constant. Without any assumptions about the sequence of integers, we can assume that {C = 1\over \ln b} since the growth rate of k*b^n+c (or (k*b^n+c)/gcd(k+c,b-1) in your case), is b.

However, as you mentioned, such sequences are not "completely" random. They are random enough that the prime number theorem can be used to predict their primality, but divisibility by small primes isn't as random and can easily be predicted:

Once one candidate is found to be divisible by a prime p, another predictable candidate will also be divisible by p. This decreases the probability of expected primes.
Sometimes though, the candidates will never be divisible by a prime p, which increases the probability of expected primes.

For example, if (k*b^n+c)/gcd(k+c,b-1) is always odd, we can double our constant: C = {2\over \ln b}, and if (k*b^n+c)/gcd(k+c,b-1) is coprime to 6, we can triple our constant: C = {3\over \ln b}, and this can go on for however many primes we know won't divide any of our candidates.

The most accurate way to predict primes occurring in particular sequences from the a-th term to n-th term, is to sieve or remove candidates that are divisible by primes up to some constant P. Suppose we have r remaining candidates. Then we should expect about 1 in every k = r/(n-1) candidates left to test for primality. The growth rate, in a sense, changes from b, to b^k. The new probability that a random integer N is prime, given that it has no prime factors less than P, is about

{e^{gamma} \ln P \over \ln N}

Putting two and two together, one can obtain a more accurate estimate for the expected number of primes of the form (k*b^n+c)/gcd(k+c,b-1), the new constant C is:

C = {e^{gamma} \ln P \over k\ln b}

Just in case you weren't aware: The Nash value tells you how many candidates remain after sieving a certain number of terms to a certain depth.

Last fiddled with by carpetpool on 2020-11-30 at 00:46
carpetpool is offline   Reply With Quote