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.