Properties of A280864
=====================
N. J. A. Sloane
Last revised Apr 25, 2017

Abstract
--------
Various properties of Rémy Sigrist's sequence A280864 are
established, in particular that it contains every prime and every even number.
However, the conjecture that it is a permutation of the
positive integers remains open. To complete the
proof it would be enough to show that it contains every odd square.
The cycles of the (putative) permutation are investigated experimentally. 

Notation
--------
Throughout, a(n) denotes the n-th term of A280864.
The radical (or square-free part) of n, A007947(n), is denoted by rad(n).

The definition
--------------
Definition (1.1). A280864 is the lexicographically earliest sequence of distinct terms 
such that, for any prime p, any run of consecutive multiples of p 
has length exactly 2. (Contributed to the OEIS by Rémy Sigrist, Jan 09 2017)

Definition (1.2). To state the definition another way, let a(1)=1, a(2)=2, and for n >= 2, let
    r_1(n) = rad(gcd( a(n-1),a(n) )),
    r_2(n) = rad(a(n))/r_1(n).
Thus r_1(n) = product of distinct primes linking a(n) to previous term,
     r_2(n) = product of distinct primes linking a(n) to next term.

Then a(n+1) is defined to be the smallest number m which has not yet 
appeared in the sequence and is such that gcd(m,r_1(n))=1 and r_2(n) divides rad(m).

In words, the radical of m is divisible by all primes that divide
a(n) but do not divide a(n-1), and by none of the primes
that divide both a(n-1) and a(n).

It follows from the definition that r_1(n+1) = r_2(n) for n >= 2.  
We also define r_1(1) = r_1(2) = 1; r_2(1) = 1, r_2(2) = 2. 
Then r_1(n) is the sequence A280738.

Definition (1.3): Definition of B_i(n):
For i >= 1, n >= 1, let B_i(n) denote the smallest multiple of i that is
missing from a(1), a(2),...,a(n-1).
Then it is easy to see that:
B_1(n) <= n,
B_i(1) = i for all i,
B_i(2) = i except B_1(2) = 2,
B_i(n) <= i(n-1) for i >= 2, n >= 2,
B_i(n) <= i(n-2) for i >= 3, n >= 3,
and in all cases, 

(1.3.1)    B_i(n) <= i*n,   for n >= 1, i >= 1.

Definition (1.4): Definition of B_{i,j}(n):
Let i and j be square-free and relatively prime numbers >= 1.
For n >= 2, let B_{i,j}(n) denote the smallest multiple of i that is
missing from a(1), a(2),...,a(n-1) and is relatively prime to j.
Certainly B_i(n) <= B_{i,j}(n).

Definition (1.5): An equivalent definition of the sequence is:
a(1)=1, a(2)=2, and for n >= 2, 

                a(n+1) = B_{i,j}(n+1),

where (compare (1.2))

    j = r_1(n) = rad(gcd( a(n-1),a(n) )),
    i = r_2(n) = rad(a(n))/j.

Remark (1.6): Unfortunately, I do not know of any nontrivial upper bounds
for B_{i,j}(n) that are analogous to those for B_i(n) given in (1.3).
Jacobsthal's function g(n) (see A048669 and A132468) is relevant
to this question.  A trivial upper bound is:

(1.6.1)   B_{i,j}(n) <= pi*rad(a(n))  where pi is the smallest
prime not dividing any of a(1),...,a(n).

Proof: rad(a(n)) is a multiple of i and pi*rad(a(n)) is not already in the sequence.

It would be nice to have a bound analogous to (1.3.1), something
like  B_{i,j}(n) <= i*n (?) for j not much larger than i.

Definition (1.7): Call a(n) satisfied if all its prime factors already 
appeared in a(n-1). Equivalently, a(n) is satisfied if r_2(n)=1.
If a(n) is satisfied then a(n+1) is the smallest number
not yet in the sequence that is relatively prime to a(n). 

(1.8) It follows from the definition (see (1.2)) that if a(n+1) = m, then
all numbers k < m with rad(k)=rad(m) already appeared in
the sequence before a(n+1).

(1.9) Conjecture: Every positive integer appears in the sequence,
and therefore the sequence is a permutation of the positive integers.

Of course by definition no term is repeated, so an equivalent conjecture is
that every positive integer appears in the sequence.

Definition (1.6). There are two types of primes p in the sequence: 
Type I, the first time a term a(n) is divisible by p is when a(n)=p for some n.
These are the primes that are "born naked". It appears
that most primes of of this type. In this case, r_2(n-1)=1.
Type II, the first time a term a(n) is divisible by p is when a(n)=k*p 
for some n and some k>1. In this case, r_2(n) = k. 
The Type II primes are listed in A280745.


Lemmas
------
(2.1) Given an odd integer n >= 5, there is an odd prime p < 3 log(n)
such that gcd(p,n) = 1.
(2.2) A weaker version: Given an odd integer n >= 3, there is an odd prime 
p < 5 log(n) such that gcd(p,n) = 1.
These two lemmas follow easily from standard bounds on the growth of primorial
numbers.
(See A284721.)

Basic properties of the sequence
--------------------------------

Theorem (3.1): The sequence contains every prime and every even number.
(Added by _N. J. A. Sloane_, Jan 15 2017)
 
Proof. 
3.1.1. By definition no term is repeated.
3.1.2. The sequence is clearly infinite, by (1.6.1).
3.1.3. So for any integer m, there is an n_0 such that for all n > n_0, a(n) > m.
3.1.4. For any prime p, there is a term a(n) that is divisible by p. 
   For if not, no prime greater than p can appear either, or we 
   could have used p instead. This means all terms are products 
   of the primes less than p. Go out a long way in the sequence 
   until the terms exceed p!. Then r_2(n) is a (possibly empty) product of
   of the distinct primes less than p, and p*r_2(n) < p! is a smaller candidate
   for a(n+1), So p will appear. Contradiction.
3.1.5. For a prime p, let a(n) be the first term divisible by p. 
   There are two cases: 
   (I) a(n) = p, in which case a(n-1) was satisfied, r_2(n) = p, and a(n+1) = 2p; 
   (II) a(n) = k*p, where r_2(n-1) = k>1 , r_2(n) = p, and a(n+1) = p,
   and a(n+1) is satisfied.  
   In both cases p appears in the sequence. So every prime appears.
3.1.6. Every even number appears. For suppose 2m did not appear. 
   Choose a prime a(n) = p >> 2m. If p is of Type I, we would have used 2m 
   instead of p unless gcd(a(n-1),2m) > 1, but in that case we 
   would get a(n+1) = 2p and a(n+2) = 2m. 
   If p is of Type II, we get a(n+1) = p, r_2(n+1) = 1, gcd(p,2m)=1 (by
   hypothesis), and so a(n+2) = 2m. 
   So in both cases 2m does appear, a contradiction.  QED

Theorem (3.2): The sequence contains infinitely many odd composite numbers.
(Added by _N. J. A. Sloane_, Feb 14 2017)
(The next theorem is stronger, but this is included
because the proof is simple,)

Proof: 
   If not, let C be the smallest odd composite number that is not 
   in the sequence, and as usual go out a long way in the 
   sequence until the terms are >> C. Using the previous theorem, 
   find a term a(n) = 2^r >> C. If a(n-1) is even then a(n) is 
   satisfied, and C is a smaller candidate for a(n+1). 
   If a(n-1) is odd then by hypothesis it is a prime >> C, 
   and is satisfied, and C is a smaller candidate than 2^r for a(n).   QED 


Theorem (3.3): If Q is an odd square-free number, the sequence contains
infinitely many odd multiples of Q.
(Added by _N. J. A. Sloane_, Apr 12 2017)

Proof:
Suppose not; let L*Q be the largest odd multiple of Q in the sequence.
By studying the beginning of the sequence (the b-file gives 100000 terms)
we may assume L*Q > 100.
Go out far enough in the sequence so that all terms are > G = (L*Q)^4
- that is, for all n-1 >= n_0, a(n) > G.
Find n>n_0 such that a(n)=2^r, and let A = a(n-1). There are two cases:
(i) 2 divides A: a(n) is satisfied, and we could have used (L+2)*Q for a(n+1),
a contradiction.
(ii) 2 does not divide A, Note that A and Q may share some primes.
Now a(n-1) is satisfied.
Let A_1 = product of distinct primes q that divide A and are less than (L*Q)^2.
Let A_2 = product of distinct primes q that divide A and are greater than (L*Q)^2.
Then rad(A) = A_1 * A_2.

We now define an integer k.
Case (iia): If A_1 = 1 or 3, let k = 5.
Case (iib): If A_1 >= 5, then (see A034386) from
    Rosser and Schoenfield, Ill. J. Math. (1962),
    or Mitrinovic, H'book of Number Theory, Section VII.35, p. 268,
    log(A_1) < 1.01624(L*Q)^2.  Using Lemma 2.1, let k be an odd prime
    with gcd(k,A_1)=1 and k < 3*log(A_1).

In both cases, k is on odd prime with
k < 4*(L*Q)^2, gcd(k,A_1) = 1, gcd(k,A_2) = 1, and so gcd(k,A)=1.
Choose s so that
L < k^s <= k*L
and let M = k^s*Q. Then we have:
M is not in the sequence (because M > L*Q),
gcd(M,A) = 1 (by construction),
and M < 2^r.
(For M = k^s*Q <= k*L*Q
         < 4*(L*Q)^3
         < G = (L*Q)^4  )

But now M is a smaller candidate for a(n) than 2^r, a contradiction.
QED


Theorem (3.4): The sequence is a permutation of the positive integers
if and only if it contains every square.

Proof: If any square is missing then obviously the sequence is not a permutation.
On the other hand, suppose it contains every square, yet some number m (say)
is missing. However, m^2 is in the sequence, and since rad(m^2) = rad(m), by (1.8),
m is in the sequence, a contradiction.   QED

The positions of the squares are given by A285181.


Summary
-------
To complete the proof of Conjecture (1.9), it would
be enough to prove any of the following:
- the sequence contains every odd number 
- the sequence contains every odd square 
- the sequence contains infinitely many Type II primes
- the sequence contains infinitely many powers of 2 that are preceded by even numbers

Cycles
------
Assuming that A280864 is a permutation of the natural numbers, one
may ask for its decomposition into cycles.
There are several short cycles, and apparently at least two infinite cycles:
Short cycles:
[1]; [2]; [3,4];
[5, 6, 8, 10, 9, 12, 14, 11, 7];
[13, 16, 18, 20, 21, 28, 19, 24, 17, 15, 22, 26, 30, 32, 46, 44, 39, 29, 38, 48, 49, 31, 23];
[37,42,55];
[40,58,63,41];
[47, 77, 69, 99, 136, 83, 91, 59, 51, 50, 62, 75, 76, 72, 70];
[53, 78, 92, 118, 161, 162, 103, 108, 87];
[54];
[56,74,57]; ...
Apparently infinite cycles:
The first apparently infinite cycle has 25 as its smallest term, 
and in the forward direction begins
25, 34, 27, 45, 52, 65, 64, 82, 84, 104, 67, ... (A281369)
and in the reverse direction begins
25, 35, 36, 33, 43, 66, 68, 60, 61, 95, 101, ... (A281370)'
There appears to be another infinite cycle that has 73 as its smallest 
term (although it is only a conjecture that these two cycles never 
merge and are both infinite). 

Acknowledgments
---------------
Thanks to Max Alekseyev, Alex Ryba, and Bob Selcoe for helpful discussions.