This site is supported by donations to The OEIS Foundation.
User:M. F. Hasler/Work in progress/Rowland-Cloitre type prime generating sequences
This is about sequences { u[m], m=1..10 } = A261301..A261310, whose zeros produce primes listed in A186253 - A186263, which equal m*b[m]+m-1, where b[m] lists the zeros of u[m]. The sequences u[m] are defined with u(1) = 1 and u(n+1) = |u(n) - gcd(u(n), mn+m-1)|.
Contents
Definition
As mentioned in the introduction, the starting point are the sequences , defined as
Here the |...| can be dropped except in the case where u(n) = 0 and thus : The latter are exactly the primes listed in the previously mentioned sequences A186253 - A186263 = , where lists the zeros of .
Examples
Thus, the sequences u[m] always start with
- u(1) = 1, u(2) = 0, u(3) = gcd(0, m*2+m-1) = 3m-1,
- u(4) = u(3) - gcd(3m-1, m*3+m-1) = 3m-1 - gcd(3m-1, m) = 3m-2,
- u(5) = u(4) - gcd(3m-2, m*4+m-1) = 3m-2 - gcd(m-3, 7),
i.e., u[m] = (1, 0, 3m-1, 3m-2, ...)
Consequently, the sequences b[m] which list the zeros always start (2, ...), and the sequences m*b[m]+m-1 start (3m-1, ...).
Motivation
Benoît Cloitre has conjectured that these sequences list only primes except for a finite number of terms. In practice, if the first term (3m-1) is not prime, already from the second term on there are only primes in these sequences, except maybe for very rare exceptions. Here we attempt to give a proof of this.
Origin
As outlined in Benoît Cloître's preprint [BC21], this construction is ispired from Rowland's type prime generating sequences which count upwards rather than down to 0, see A106108 and references therein.
Properties
Behaviour of the sequences
The sequences u[m] always count down to zero, i.e., they are strictly decreasing from a given value u(k) > 0 to u(n) = 0 for some n > k, after which it "restarts" from u(n+1) = mn+m-1, usually prime, the next period of strict decrease.
The steps u(k+1) - u(k) = - gcd(u(k),mk+m-1), are most often equal to -1.
As long as this is true, we have u(k+d) = u(k) - d, for d = 0, 1, 2, ..., d[max] <= u(k).
Proposition 1: Here, d[max] = min { a(k) % f ; f ∈ prime factors of m(u(k)+k)+m-1 }, where % denotes the binary mod operator = rest r >= 0 of division by f.
Proof: while 0 <= d <= d[max],
Now this g is by definition the largest f such that and also . Thus, if (which is independent of d), then g > 1 as soon as u(k) = d (mod f ), i.e., d = u(k) % f. Thus, the first step u(k+d+1) - u(k+d) > 1 arises for the smallest such value of d, which is always reached for prime divisors f.
(We can easily prove that if f' is a multiple of f , then x % f ≤ x % f' , for any x . Therefore we can consider the minimum over the prime factors, rather than the minimum over all divisors.)
Asymptotic behaviour of the sequences b[m]
Proposition 2: The sequences b[m] behave as .
From a given zero n = b[m](i) to the next, n' = b[m](i+1) , the sequence u(k) counts down from u(n+1) = m*n+m-1 to 0 = u(n'), with a few steps of size f > 1 which are divisors of m(u(k)+k)+m-1, for some k in the interval n < k < n'. Therefore, in the mean, the difference Δ(n) between the "initial guess" n+u(n+1) (corresponding to a decrease from u(n+1) to 0 by always -1) and the true value for next zero n' , are of the order of the sum of prime factors of m(u(k)+k)+m-1. (Indeed, after each step > 1, one has to consider the prime factors of a new (slightly smaller) number m(u(k')+k')+m-1, where k' = 1 + (value of k where the jump happened).) It can happen in very rare cases that a step of size f is a larger divisor of u(n+1). But the probability of this to happen [to do: give precise estimate] is low enough as to make this effect negligible. Since this sum of the steps > 1 is small w.r.t. u(n+1), it yields asymptotically only a next-to-leading term. The growth is mainly determined by the fact that b[m](k+1) / b[m](k) = n' / n ~ (mn+m-1)/n = m+(m-1)/n ~ m, QED.
Examples
(to be developed)
References
[BC11] B. Cloitre, 10 conjectures in additive number theory, arXiv:1101.4274 [math.NT], 2011.
History
Initial version of this article created: — MFH 16:29, 24 August 2015 (UTC)
Cite this page as
M. F. Hasler, User:M._F._Hasler/Work_in_progress/Rowland-Cloitre_type_prime_generating_sequences. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki.Available at https://oeis.org/wiki/User:M._F._Hasler/Work_in_progress/Rowland-Cloitre_type_prime_generating_sequences