Excepted number of primes of the form (k*b^n+c)/gcd(k+c,b-1) for n <= given number

sweety439 · 2020-11-25, 14:07

According to the page https://oeis.org/wiki/User:Charles_R...special_primes, the excepted number of primes of the polynomial function form a₀+a₁n+a₂n²+a₃n³+a₄n⁴+...+a_rn^r (with r>=1 is integer, all a_i (0<=i<=r) integers, a_r>=1), for 1<=n<=N is (N^(1/r))/(ln(N)), if this is an irreducible polynomial over the integers, and the values of this polynomial at n = 1, 2, 3, ... are relatively prime (Bunyakovsky conjectures is that there are infinitely many n such that this polynomial produces prime values, if this is an irreducible polynomial over the integers, and the values of this polynomial at n = 1, 2, 3, ... are relatively prime)

However, for the exponential function form (k*b^n+c)/gcd(k+c,b-1) (with k>=1 is integer, b>=2 is integer, c is (positive or negative) integer, |c|>=1, gcd(k,c) = 1, gcd(b,c) = 1), what is the excepted number of primes of this form for 1<=n<=N, if this form does not have algebraic covering set (e.g. 1*8^n+1, 8*27^n+1, (1*8^n-1)/7, (1*9^n-1)/8, 4*9^n-1, 2500*16^n+1, etc.) or numerical covering set (e.g. 78557*2^n+1, (11047*3^n+1)/2, (419*4^n+1)/3, 509203*2^n-1, (334*10^n-1)/9, 14*8^n-1, etc.) or partial algebraic/partial numerical covering set (e.g. 4*24^n-1, 4*39^n-1, (4*19^n-1)/3, (343*10^n-1)/9, 1369*30^n-1, 2500*55^n+1, etc.)?

sweety439 · 2020-11-25, 14:09

the page only writes "trivial density O(ln(N))", however, I know that the density is different by triple (k,b,c), e.g. 29*2^n-1 has much low density as 17*2^n-1

carpetpool · 2020-11-30, 00:44

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.

LaurV · 2020-12-01, 10:42

Quote:

Originally Posted by sweety439

Excepted number of primes...

they were excepted from what?
(I had a German colleague who always confused the two terms, haha, he moved to Philippines few years ago, are you that guy?)

sweety439 · 2020-12-01, 16:05

Quote:

Originally Posted by LaurV

they were excepted from what?
(I had a German colleague who always confused the two terms, haha, he moved to Philippines few years ago, are you that guy?)

No, it is just a typo, should be "expected" ....

kar_bon · 2020-12-02, 15:04

Previous is a double post from your own thread!

sweety439 · 2020-12-02, 16:26

Quote:

Originally Posted by kar_bon

Previous is a double post from your own thread!

Yes, I want to let more people know this conjecture, as Riemann hypothesis and abc conjecture and Schinzel's hypothesis H

This conjecture would imply all Sierpinski conjectures and Riesel conjectures in CRUS to every base b>=2, also the dual Sierpinski conjecture (whether 78557 is the smallest odd number k such that 2^n+k is composite for all n>=1) and the dual Riesel conjecture (whether 509203 is the smallest odd number k such that |2^n-k| is composite for all n>=1), and also imply there are infinitely many such primes:

* Mersenne primes
* Fermat primes
* Generalized repunit primes (b^n-1)/(b-1) to every base b>=2 not of the form m^r with r>1
* Generalized nega-repunit primes (b^n+1)/(b+1) to every base b>=2 not of the form m^r with odd r>1 and not of the form 4*m^4 with integer m
* Generalized Fermat primes b^(2^n)+1 to every even base b>=2 not of the form m^r with odd r>1
* Generalized half Fermat primes (b^(2^n)+1)/2 to every odd base b>=2 not of the form m^r with odd r>1
* Williams primes of the 1st kind (b-1)*b^n-1 to every base b>=2
* Williams primes of the 2nd kind (b-1)*b^n+1 to every base b>=2 (not always true if b-1 is of the form m^r with odd r>1 or of the form 4*m^4 with integer m)
* Williams primes of the 3rd kind (b+1)*b^n-1 to every base b>=2

carpetpool · 2020-12-02, 21:19

Quote:

Originally Posted by sweety439

Yes, I want to let more people know this conjecture, as Riemann hypothesis and abc conjecture and Schinzel's hypothesis H

Then write up a paper explaining your conjectures, and provide more evidence for your claims, like I have given or some of your own research.

LaurV · 2020-12-03, 06:40

Quote:

Originally Posted by sweety439

No, it is just a typo ....

Three or four times in a row?

(also always in the text, not only in the title)

2020-11-25, 14:07	#1
sweety439 Nov 2016 2793₁₀ Posts	*Excepted number of primes of the form (kb^n+c)/gcd(k+c,b-1) for n <= given number** According to the page https://oeis.org/wiki/User:Charles_R...special_primes, the excepted number of primes of the polynomial function form a₀+a₁n+a₂n²+a₃n³+a₄n⁴+...+a_rn^r (with r>=1 is integer, all a_i (0<=i<=r) integers, a_r>=1), for 1<=n<=N is (N^(1/r))/(ln(N)), if this is an irreducible polynomial over the integers, and the values of this polynomial at n = 1, 2, 3, ... are relatively prime (Bunyakovsky conjectures is that there are infinitely many n such that this polynomial produces prime values, if this is an irreducible polynomial over the integers, and the values of this polynomial at n = 1, 2, 3, ... are relatively prime) However, for the exponential function form (kb^n+c)/gcd(k+c,b-1) (with k>=1 is integer, b>=2 is integer, c is (positive or negative) integer, \|c\|>=1, gcd(k,c) = 1, gcd(b,c) = 1), what is the excepted number of primes of this form for 1<=n<=N, if this form does not have algebraic covering set (e.g. 18^n+1, 827^n+1, (18^n-1)/7, (19^n-1)/8, 49^n-1, 250016^n+1, etc.) or numerical covering set (e.g. 785572^n+1, (110473^n+1)/2, (4194^n+1)/3, 5092032^n-1, (33410^n-1)/9, 148^n-1, etc.) or partial algebraic/partial numerical covering set (e.g. 424^n-1, 439^n-1, (419^n-1)/3, (34310^n-1)/9, 136930^n-1, 2500*55^n+1, etc.)?

2020-11-25, 14:09	#2
sweety439 Nov 2016 AE9₁₆ Posts	the page only writes "trivial density O(ln(N))", however, I know that the density is different by triple (k,b,c), e.g. 292^n-1 has much low density as 172^n-1 Last fiddled with by sweety439 on 2020-11-25 at 14:10

2020-11-30, 00:44	#3
carpetpool "Sam" Nov 2016 2·163 Posts	Finding the expected number of primes of (kb^n+c)/gcd(k+c,b-1) shouldn't be much different than finding the expected number of primes of the form kb^n+c. If we treat numbers of the form kb^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 kb^n+c (or (kb^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 (kb^n+c)/gcd(k+c,b-1) is always odd, we can double our constant: $C = {2\over \ln b}$ , and if (kb^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 (kb^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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Question about number of the form 2^n + 1	jshort	Math	12	2020-10-15 14:04
Special Form of Mersenne and Fermat Number Factors	michael	Math	31	2015-09-04 05:57
Estimating the number of primes in a partially-factored number	CRGreathouse	Probability & Probabilistic Number Theory	15	2014-08-13 18:46
Lucas-number prime factor form proofs	Raman	Math	1	2012-09-12 13:21
Closed form solution of x^2 = 2 mod Fermat number	mpenguin	Factoring	10	2005-09-29 07:46

2020-12-02, 15:04	#6
kar_bon Mar 2006 Germany 13²×17 Posts	Previous is a double post from your own thread!