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)|.

Definition

As mentioned in the introduction, the starting point are the sequences $u[m]=u_{m}$, defined as

$u_{m}(1)=1~;~~u_{m}(n+1)=|u(n)-\gcd(u(n),mn+m-1)|~.$

Here the |...| can be dropped except in the case where u(n) = 0 and thus $u(n+1)=mn+n-1$: The latter are exactly the primes listed in the previously mentioned sequences A186253 - A186263 = $\{m*b_{m}+m-1,m=1..10\}$, where $b_{m}$ lists the zeros of $u_{m}$.

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],

$\gcd(u(k+d),m(k+d)+m-1)=\gcd(u(k)-d,m(k+d)+m-1)=\gcd(u(k)-d,m(u(k)+k)+m-1)=:g~.$

Now this g is by definition the largest f such that $f\mid m(u(k)+k)+m-1$ and also $f\mid u(k)-d$. Thus, if $f\mid m(u(k)+k)+m-1$ (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 $b_{m}(n)\sim c\cdot n^{m+1}$.

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