

A336957


The Enots Wolley sequence: the lexicographically earliest infinite sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n1) but not with a(n2).


119



1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, 51, 34, 38, 57, 69, 46, 40, 65, 91, 42, 30, 85, 119, 56, 24, 75, 95, 76, 36, 87, 145, 50, 44, 99, 93, 62, 52, 117, 105, 70, 58, 261, 111, 74, 68, 153, 123, 82, 80, 115, 161, 84, 60, 155, 217, 98, 48, 129, 215, 100
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Suggested by the Yellowstone permutation A098550 except that now the key conditions in the definition have been reversed.
Let Ker(k), the kernel of k, denote the set of primes dividing k. Thus Ker(36} = {2,3}, Ker(1) = {}. Then Product_{p in Ker(k)} p = A000265(k), which is denoted by ker(k).
Theorem 1: For n>2, a(n) is the smallest number m not yet in the sequence such that
(i) Ker(m) intersect Ker(a(n1)) is nonempty,
(ii) Ker(m) intersect Ker(a(n2)) is empty, and
(iii) The set Ker(m) \ Ker(a(n1)) is nonempty.
(Without condition (iii), every prime dividing m might also divide a(n1), which would make it impossible to find a(n+1).)
Idea of proof: m always exists and is unique; no smaller choice for a(n) is possible; and taking a(n)=m does not lead to a contradiction. So a(n) must be m.
Theorem 2: For n>2, Ker(a(n)) contains at least two primes. (Immediate from Theorem, since a(n) must contain a prime in a(n1) and a prime not in a(n1)).)
It follows that no odd prime p or evenorodd prime power q^k, k>1, appears in the sequence. Obviously this sequence is not a permutation of the positive integers.
Theorem 3. For any M there is an n_0 such that n > n_0 implies a(n) > M. (This is a standard property of any sequence of distinct positive terms  see the Yellowstone paper).
Theorem 4. For any prime p, some term is divisible by p.
Proof. Take p=17 for concreteness. If 17 does not divide any term, then 19 cannot either (because the first time 19 appears, we could have used 17 instead).
So all terms are products only of 2,3,5,7,11,13. Go out a long way, use Theorem 2, and consider two huge successive terms, A*B, C*D, where Ker(B) = Ker(C) and Ker(A) intersect Ker(D) is empty. Either C or D must contain a huge prime power q^k, 2 <= q <= 13. If it is in C, replace it by q and multiply D by 17. If it is in D, replace it by 17. Either way we get a smaller legal candidate for C*D that is a multiple of 17. QED
Theorem 5. There are infinitely many even terms.
Proof. Suppose the prime p appears for the first times as a factor of a(n). Then we have a(n1) = x*q^i, a(n) = q*p, where q<p is a prime and i >= 1. If q=2 then a(n) is even. So we may suppose q is odd. If x is odd then a(n+1) = 2*p. If x is even then obviously a(n1) is even. So one of a(n1), a(n), or a(n+1) is even for every prime p. So there are infinitely many even terms. QED  N. J. A. Sloane, Aug 28 2020
Theorem 6: For any prime p, infinitely many terms are divisible by p.  N. J. A. Sloane, Sep 09 2020. (I thought I had a proof that for any odd prime p, there is a term equal to 2p, but there was a gap in the argument.  N. J. A. Sloane, Sep 23 2020)
Theorem 7: There are infinitely many odd terms.  N. J. A. Sloane, Sep 12 2020
Conjecture 1: Every number with at least two distinct prime factors is in the sequence. In other words, apart from 1 and 2, this sequence is the complement of A000961.
[It seems very likely that the arguments used to prove Theorem 1 of the Yellowstone Permutation paper can be modified to prove the conjecture.]
The conditions permit us to start with a(1)=1, a(2)=2, and that does not lead to a contradiction, so those are the first two terms.
After 1, 2, the next term cannot be 4 or 5, but a(3) = 6 works.
For a(4), we can rule out 3, 4, 5, 7, 8, 9 11, 13 (powers of primes), and 10, 12, and 14 have a common factor with a(2). So a(4) = 15.
The graph of the first 100000 terms (see link) is similar to that of the Yellowstone permutation, but here the points lie on more lines.
The sequence has fixed points at n = 1, 2, 10, 90, 106, 150, 162, 246, 394, 398, 406, 410, ... (see A338050).  Scott R. Shannon, Aug 13 2020
The initial pattern of odd and even terms: (odd, even, even, odd), repeat, is misleading as it does not persist. (See A337644 for more about this point.)
Discussion of when primes first divide some term, from N. J. A. Sloane, Oct 21 2020: (Start)
When an odd prime p first divides a term of the Enots Wolley sequence (the present sequence), that term a(n) is equal to q*p where q<p is also a prime. We say that p is introduced by q. It appears q is almost always 2 (the corresponding values of p form A337648), that there are precisely 34 instances when q = 3 (see A337649), and q>3 happens just once, at a(5) = 35 when q=5 and p=7.
We conjecture that even if p is introduced by some prime q>2, 2*p appears later.
Sequence A337275 lists the index k such that a(k) = 2*prime(n), or 1 if 2*prime(n) is missing, and A338074 lists the indices k such that a(k) is twice a prime.
Comparison of those two sequences shows that they appear to be essentially identical (see the table in A337275).
The differences between the two sequences are caused by the fact that although normally if p and q are odd primes with p < q, then 2p precedes 2q, this is not true for the following primes: (7,5), (31,29), and (109, 113, 107), which appear in the order shown. We conjecture that these are the only exceptions.
Combining the above observations, we conjecture that for n >= 755 (at which point we have seen all the primes <= 367), every prime p is introduced by 2*p, and the terms 2*p appear in their natural order.
(End)


LINKS

David L. Applegate, Hans Havermann, Bob Selcoe, Vladimir Shevelev, N. J. A. Sloane, and Reinhard Zumkeller, The Yellowstone Permutation, arXiv preprint arXiv:1501.01669 [math.NT], 2015. Also Journal of Integer Sequences, Vol. 18 (2015), Article 15.6.7
Scott R. Shannon, Graph of 11.33 million terms, based on F. Stevenson's data, plotted with colors indicating the least prime factor (lpf). Terms with a lpf of 2 are shown in white, terms with a lpf of 3,5,7,11,13,17,19 are shown as one of the seven rainbow colors from red to violet, and terms with a lpf >= 23 are shown in grey.
Scott R. Shannon, Graph of the terms with lpf = 2. This, and the similar graphs below, are using F. Stevenson's data of 11.33 million terms. The yaxis scale is the same as the above multicolored image. The green line is y = x.
N. J. A. Sloane, Graph of 11.33 million terms, based on F. Stevenson's table. The red line is y=x. It is hard to believe, but there are as many points above the red line as there are below it (see the next graph). Out of 11333576 points, 46% (5280697), all even, lie below the red line. All the odd points lie above the red line.


MAPLE

with(numtheory);
N:= 10^4: # to get a(1) to a(n) where a(n+1) is the first term > N
B:= Vector(N, datatype=integer[4]):
for n from 1 to 2 do A[n]:= n: od:
for n from 3 do
for k from 3 to N do
if B[k] = 0 and igcd(k, A[n1]) > 1 and igcd(k, A[n2]) = 1 then
if nops(factorset(k) minus factorset(A[n1])) > 0 then
A[n]:= k;
B[k]:= 1;
break;
fi;
fi
od:
if k > N then break; fi;
od:


MATHEMATICA

M = 1000;
A[1] = 1; A[2] = 2;
Clear[B]; B[_] = 0;
For[n = 3, True, n++,
For[k = 3, k <= M, k++,
If[B[k] == 0 && GCD[k, A[n1]] > 1 && GCD[k, A[n2]] == 1, If[Length[ FactorInteger[k][[All, 1]] ~Complement~ FactorInteger[A[n1]][[All, 1]]] > 0, A[n] = k; B[k] = 1; Break[]]]]; If[k > M, Break[]]];


PROG

(Python)
from math import gcd
from sympy import factorint
from itertools import count, islice
def agen(): # generator of terms
a, seen, minan = [1, 2], {1, 2}, 3
yield from a
for n in count(3):
an, fset = minan, set(factorint(a[1]))
while True:
if an not in seen and gcd(an, a[1])>1 and gcd(an, a[2])==1:
if set(factorint(an))  fset > set():
break
an += 1
a.append(an); seen.add(an); yield an
while minan in seen: minan += 1


CROSSREFS

Cf. A000961, A098550, A098548, A064413, A255582, A020639, A006530, A337648, A337649, A338050 (fixed points), A338051 (a(n)n).
Further properties of the present sequence are studied in A338062A338071.
A280864 is a different but very similar lexicographically earliest sequence.


KEYWORD

nonn


AUTHOR



EXTENSIONS

Added Scott R. Shannon's name "Enots Wolley" (Yellowstone backwards) for this sequence to the definition, since that has been mentioned in several talks.  N. J. A. Sloane, Oct 11 2020


STATUS

approved



