login
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(n-1) but not with a(n-2).
125

%I #246 Dec 05 2023 08:12:04

%S 1,2,6,15,35,14,12,33,55,10,18,21,77,22,20,45,39,26,28,63,51,34,38,57,

%T 69,46,40,65,91,42,30,85,119,56,24,75,95,76,36,87,145,50,44,99,93,62,

%U 52,117,105,70,58,261,111,74,68,153,123,82,80,115,161,84,60,155,217,98,48,129,215,100

%N 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(n-1) but not with a(n-2).

%C Suggested by the Yellowstone permutation A098550 except that now the key conditions in the definition have been reversed.

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

%C Theorem 1: For n>2, a(n) is the smallest number m not yet in the sequence such that

%C (i) Ker(m) intersect Ker(a(n-1)) is nonempty,

%C (ii) Ker(m) intersect Ker(a(n-2)) is empty, and

%C (iii) The set Ker(m) \ Ker(a(n-1)) is nonempty.

%C (Without condition (iii), every prime dividing m might also divide a(n-1), which would make it impossible to find a(n+1).)

%C 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.

%C 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(n-1) and a prime not in a(n-1)).)

%C It follows that no odd prime p or even-or-odd prime power q^k, k>1, appears in the sequence. Obviously this sequence is not a permutation of the positive integers.

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

%C Theorem 4. For any prime p, some term is divisible by p.

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

%C 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

%C Theorem 5. There are infinitely many even terms.

%C Proof. Suppose the prime p appears for the first times as a factor of a(n). Then we have a(n-1) = 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(n-1) is even. So one of a(n-1), 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

%C 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)

%C Theorem 7: There are infinitely many odd terms. - _N. J. A. Sloane_, Sep 12 2020

%C 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.

%C [It seems very likely that the arguments used to prove Theorem 1 of the Yellowstone Permutation paper can be modified to prove the conjecture.]

%C 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.

%C After 1, 2, the next term cannot be 4 or 5, but a(3) = 6 works.

%C 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.

%C 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.

%C 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

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

%C Discussion of when primes first divide some term, from _N. J. A. Sloane_, Oct 21 2020: (Start)

%C 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.

%C We conjecture that even if p is introduced by some prime q>2, 2*p appears later.

%C 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.

%C Comparison of those two sequences shows that they appear to be essentially identical (see the table in A337275).

%C 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.

%C 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.

%C (End)

%H Scott R. Shannon, <a href="/A336957/b336957.txt">Table of n, a(n) for n = 1..20000</a>.

%H David L. Applegate, Hans Havermann, Bob Selcoe, Vladimir Shevelev, N. J. A. Sloane, and Reinhard Zumkeller, <a href="http://arxiv.org/abs/1501.01669">The Yellowstone Permutation</a>, arXiv preprint arXiv:1501.01669 [math.NT], 2015. Also Journal of Integer Sequences, Vol. 18 (2015), Article 15.6.7

%H Scott R. Shannon, <a href="https://oeis.org/A336957/a336957.7z">The first million terms (7-Zip compressed file)</a>

%H Scott R. Shannon, <a href="/A336957/a336957_2.png">Image of the first 100000 terms</a>. The green line is y=x.

%H Scott R. Shannon, <a href="/A336957/a336957_3.png">Image of the first 1000000 terms</a>. The green line is y=x.

%H Scott R. Shannon, <a href="/A336957/a336957_6.png">Graph of 11.33 million terms</a>, based on F. Stevenson's data, plotted with colors indicating the least prime factor (lpf). Terms with an lpf of 2 are shown in white, terms with an 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 an lpf >= 23 are shown in gray.

%H Scott R. Shannon, <a href="/A336957/a336957_7.png">Graph of the terms with lpf = 2</a>. This, and the similar graphs below, are using F. Stevenson's data of 11.33 million terms. The y-axis scale is the same as the above multi-colored image. The green line is y = x.

%H Scott R. Shannon, <a href="/A336957/a336957_8.png">Graph of the terms with lpf = 3</a>.

%H Scott R. Shannon, <a href="/A336957/a336957_9.png">Graph of the terms with lpf = 5</a>.

%H Scott R. Shannon, <a href="/A336957/a336957_10.png">Graph of the terms with lpf = 7</a>.

%H Scott R. Shannon, <a href="/A336957/a336957_11.png">Graph of the terms with lpf = 11</a>.

%H Scott R. Shannon, <a href="/A336957/a336957_12.png">Graph of the terms with lpf = 13</a>.

%H Scott R. Shannon, <a href="/A336957/a336957_13.png">Graph of the terms with lpf = 17</a>.

%H Scott R. Shannon, <a href="/A336957/a336957_14.png">Graph of the terms with lpf = 19</a>.

%H Scott R. Shannon, <a href="/A336957/a336957_15.png">Graph of the terms with lpf >= 23</a>.

%H N. J. A. Sloane, <a href="/A336957/a336957.txt">Table of n, a(n) for n = 1..161734</a>

%H N. J. A. Sloane, <a href="/A336957/a336957_4.png">Graph of 11.33 million terms</a>, 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.

%H N. J. A. Sloane, <a href="/A336957/a336957_5.png">Blowup of last 1.133 million points of the previous graph</a>. There are a very large number of points in a narrow band below the red line.

%H N. J. A. Sloane, <a href="https://vimeo.com/457349959">Conant's Gasket, Recamán Variations, the Enots Wolley Sequence, and Stained Glass Windows</a>, Experimental Math Seminar, Rutgers University, Sep 10 2020 (video of Zoom talk).

%H N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 16.

%H Frank Stevenson, <a href="https://oeis.org/A336957/a336957-5M.zip">First five million terms</a> (zipped file, starting with a(4)=15)

%H Frank Stevenson, <a href="https://oeis.org/A336957/a336957_11M.zip">First 11333573 terms</a> (zipped file, starting with a(4)=15)

%p with(numtheory);

%p N:= 10^4: # to get a(1) to a(n) where a(n+1) is the first term > N

%p B:= Vector(N, datatype=integer[4]):

%p for n from 1 to 2 do A[n]:= n: od:

%p for n from 3 do

%p for k from 3 to N do

%p if B[k] = 0 and igcd(k, A[n-1]) > 1 and igcd(k, A[n-2]) = 1 then

%p if nops(factorset(k) minus factorset(A[n-1])) > 0 then

%p A[n]:= k;

%p B[k]:= 1;

%p break;

%p fi;

%p fi

%p od:

%p if k > N then break; fi;

%p od:

%p s1:=[seq(A[i], i=1..n-1)]; # _N. J. A. Sloane_, Sep 24 2020, based on Theorem 1 and _Robert Israel_'s program for sequence A098550

%t M = 1000;

%t A[1] = 1; A[2] = 2;

%t Clear[B]; B[_] = 0;

%t For[n = 3, True, n++,

%t For[k = 3, k <= M, k++,

%t If[B[k] == 0 && GCD[k, A[n-1]] > 1 && GCD[k, A[n-2]] == 1, If[Length[ FactorInteger[k][[All, 1]] ~Complement~ FactorInteger[A[n-1]][[All, 1]]] > 0, A[n] = k; B[k] = 1; Break[]]]]; If[k > M, Break[]]];

%t Array[A, n-1] (* _Jean-François Alcover_, Oct 20 2020, after Maple *)

%o (Python)

%o from math import gcd

%o from sympy import factorint

%o from itertools import count, islice

%o def agen(): # generator of terms

%o a, seen, minan = [1, 2], {1, 2}, 3

%o yield from a

%o for n in count(3):

%o an, fset = minan, set(factorint(a[-1]))

%o while True:

%o if an not in seen and gcd(an, a[-1])>1 and gcd(an, a[-2])==1:

%o if set(factorint(an)) - fset > set():

%o break

%o an += 1

%o a.append(an); seen.add(an); yield an

%o while minan in seen: minan += 1

%o print(list(islice(agen(), 70))) # _Michael S. Branicky_, Jan 22 2022

%Y Cf. A000961, A098550, A098548, A064413, A255582, A020639, A006530, A337648, A337649, A338050 (fixed points), A338051 (a(n)-n).

%Y A337007 and A337008 describe the overlap between successive terms.

%Y See A337066 for when n appears, A337275 for when 2p appears, A337276 for when 2k appears, A337280 for when p first divides a term, A337644 for runs of three odd terms, A337645 & A338052 for smallest missing legal number, A337646 & A337647 for record high points, A338056 & A338057 for record high values for a(n)/n.

%Y See A338053 & A338054 for the "early" terms.

%Y Further properties of the present sequence are studied in A338062-A338071.

%Y A338059 has the missing prime powers inserted (see also A338060, A338061).

%Y See A338055, A338351 for variants.

%Y A280864 is a different but very similar lexicographically earliest sequence.

%K nonn

%O 1,2

%A _Scott R. Shannon_ and _N. J. A. Sloane_, Aug 09 2020

%E Added "infinite" to definition. - _N. J. A. Sloane_, Sep 03 2020

%E 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