cp's OEIS Frontend

The differences |a(n)-A064664(n)| seem surprisingly small (see A255482).

About the definition: the map n -> A255582(n) is an element of the group of all permutations of the positive integers; this is the inverse of that permutation.

Although the sequences have very similar definitions, A254077 is a mystery while A255582 is easily shown to be a permutation of the natural numbers.

By definition, a(n) <= A255480(n) for n >= 4.

The result is to change a three-pronged graph to a single line.

First differs from A256528 at a(29).

It would be nice to have a definition for this sequence which is independent of A255582.

Locally, the graph looks like an EKG (American English) or ECG (British English).

Calculating the square of A064413 and plotting the results shows the EKG behavior even more dramatically - see A104125. - Parthasarathy Nambi, Jan 27 2005

Theorem: (1) Every number appears exactly once: this is a permutation of the positive numbers. - J. C. Lagarias, E. M. Rains, N. J. A. Sloane, Oct 03 2001

The permutation has cycles (1) (2) (3, 4, 6, 9, 10, 5) (..., 20, 18, 12, 7, 14, 13, 28, 26, ...) (8) ...

Theorem: (2) The primes appear in increasing order. - J. C. Lagarias, E. M. Rains, N. J. A. Sloane, Oct 03 2001

Theorem: (3) When an odd prime p appears it is immediately preceded by 2p and followed by 3p. - Conjectured by Lagarias-Rains-Sloane, proved by Hofman-Pilipczuk.

Theorem: (4) Let a'(n) be the same sequence but with all terms p and 3p (p prime) changed to 2p (see A256417). Then lim a'(n)/n = 1, i.e., a(n) ~ n except for the values p and 3p for p prime. - Conjectured by Lagarias-Rains-Sloane, proved by Hofman-Pilipczuk.

Conjecture: If a(n) != p, then almost everywhere a(n) > n. - Thomas Ordowski, Jan 23 2009

Conjecture: lim #(a_n > n) / n = 1, i.e., #(a_n > n) ~ n. - Thomas Ordowski, Jan 23 2009

Conjecture: A term p^2, p a prime, is immediately preceded by p*(p+1) and followed by p*(p+2). - Vladimir Baltic, Oct 03 2001. This is false, for example the sequence contains the 3 terms p*(p+2), p^2, p*(p+3) for p = 157. - Eric Rains

Theorem: If a(k) = 3p, then |{a(m) : a(m>k) < 3p}| = 3p - k. Proof: If a(k) = 3p, then all a(mk) > p and |{a(m) : a(m>k) < 3p}| = 3p - k. - Thomas Ordowski, Jan 22 2009

Let ...,a_i,...,2p,p,3p,...,a_j,... There does not exist a_i > 3p. There does not exist a_j < p. - Thomas Ordowski, Jan 20 2009

Let...,a,...,2p,p,3p,...,b,... All a<3p and b>p. #(a>2p) <= #(b<2p). - Thomas Ordowski, Jan 21 2009

If a(k)=3p then |{a(m):a(m>k)<3p}|=3p-k. - Thomas Ordowski, Jan 22 2009

GCD(a(n),n) = A247379(n). - Reinhard Zumkeller, Sep 16 2014

If the definition is changed to require that the GCD of successive terms be a prime power > 1, the sequence stays the same until a(578)=620, at which point a(579)=610 has GCD = 10 with the previous term. - N. J. A. Sloane, Mar 30 2015

From Michael De Vlieger, Dec 06 2021: (Start)

For prime p > 2, we have the chain {j : 2|j} -> 2p -> p -> 3p -> {k : 3|k}. The term j introducing 2p must be even, since 2p is an even squarefree semiprime proved by Hofman-Pilipczuk to introduce p itself. Hence no term a(i) such that p | a(i) exists in the sequence for i < n-1, where a(n) = p, leaving 2|j. Similarly, the term k following 3p must be divisible by 3 since the terms mp that are not coprime to p (thus implying p | mp) have m >= 4, thereby large compared to numbers k such that 3|k that belong to the cototient of 3p. For the chain {4, 6, 3, 9, 12}, the term 12 following 3p indeed is 4p, but p = 3; this is the only case of 4p following 3p in the sequence. As a consequence, for i > 1, A073734(A064955(i)-1) = 2 and A073734(A064955(i)+2) = 3.

For Fermat primes p, we have the chain {j : 2|j} -> 2^e-> {2p = 2^e + 2} -> {p = 2^(e-1) + 1} -> 3p -> {k : 3|k}.

a(3) = 4 = 2^2, a(5) = 3 = 2^1 + 1;

a(8) = 8 = 2^3, a(10) = 5 = 2^2 + 1;

a(31) = 32 = 2^5, a(33) = 17 = 2^4 + 1;

a(485) = 512 = 2^9, a(487) = 257 = 2^8 + 1;

a(127354) = 131072 = 2^17, a(127356) = 65537 = 2^16 + 1.

(End)

For n > 3, gcd(a(n), a(n-1)) = 1 and gcd(a(n), a(n-2)) > 1. (This is just a restatement of the definition.)

This is now known to be a permutation of the natural numbers: see the 2015 article by Applegate, Havermann, Selcoe, Shevelev, Sloane, and Zumkeller.

From N. J. A. Sloane, Nov 28 2014: (Start)

Some of the known properties (but see the above-mentioned article for a fuller treatment):

1. The sequence is infinite. Proof: We can always take a(n) = a(n-2)*p, where p is a prime that is larger than any prime dividing a(1), ..., a(n-1). QED

2. At least one-third of the terms are composite. Proof: The sequence cannot contain three consecutive primes. So at least one term in three is composite. QED

3. For any prime p, there is a term that is divisible by p. Proof: Suppose not. (i) No prime q > p can divide any term. For if a(n)=kq is the first multiple of q to appear, then we could have used kp < kq instead, a contradiction. So every term a(n) is a product of primes < p. (ii) Choose N such that a(n) > p^2 for all n > N. For n > N, let a(n)=bg, a(n+1)=c, a(n+2)=dg, where g=gcd(a(n),a(n+2)). Let q be the largest prime factor of g. We know q < p, so qp < p^2 < dg, so we could have used qp instead of dg, a contradiction. QED

3a. Let a(n_p) be the first term that is divisible by p (this is A251541). Then a(n_p) = q*p where q is a prime less than p. If p < r are primes then n_p < n_r. Proof: Immediate consequences of the definition.

4. (From David Applegate, Nov 27 2014) There are infinitely many even terms. Proof:

Suppose not. Then let 2x be the maximum even entry. Because the sequence is infinite, there exists an N such that for any n > N, a(n) is odd, and a(n) > x^2.

In addition, there must be some n > N such that a(n) < a(n+2). For that n, let g = gcd(a(n),a(n+2)), a(n) = bg, a(n+1)=c, a(n+2)=dg, with all of b,c,d,g relatively prime, and odd.

Since dg > bg, d > b >= 1, so d >= 3. Also, g >= 3.

Since a(n) = bg > x^2, one of b or g is > x.

Case 1: b > x. Then 2b > 2x, so 2b has not yet occurred in the sequence. And gcd(bg,2b)=b > x > 1, gcd(2b,c)=1, and since g >= 3, 2b < bg < dg. So a(n+2) should have been 2b instead of dg.

Case 2: g > x. Then 2g > 2x, so 2g has not yet occurred in the sequence. And gcd(bg,2g)=g > 1, gcd(2g,c)=1, and since d >= 3, 2g < dg. So a(n+2) should have been 2g instead of dg.

In either case, we derive a contradiction. QED

Conjectures:

5. For any prime p > 97, the first time we see p, it is in the subsequence a(n) = 2b, a(n+2) = 2p, a(n+4) = p for some n, b, where n is about 2.14*p and gcd(b,p)=1.

6. The value of |{k=1,..,n: a(k)<=k}|/n tends to 1/2. - Jon Perry, Nov 22 2014 [Comment edited by N. J. A. Sloane, Nov 23 2014 and Dec 26 2014]

7. Based on the first 250000 terms, I conjectured on Nov 30 2014 that a(n)/n <= (Pi/2)*log n.

8. The primes in the sequence appear in their natural order. This conjecture is very plausible but as yet there is no proof. - N. J. A. Sloane, Jan 29 2015

(End)

The only fixed points seem to be {1, 2, 3, 4, 12, 50, 86} - see A251411. Checked up to n=10^4. - L. Edson Jeffery, Nov 30 2014. No further terms up to 10^5 - M. F. Hasler, Dec 01 2014; up to 250000 - Reinhard Zumkeller; up to 300000 (see graph) - Hans Havermann, Dec 01 2014; up to 10^6 - Chai Wah Wu, Dec 06 2014; up to 10^8 - David Applegate, Dec 08 2014.

From N. J. A. Sloane, Dec 04 2014: (Start)

The first 250000 points lie on about 8 roughly straight lines, whose slopes are approximately 0.467, 0.957, 1.15, 1.43, 2.40, 3.38, 5.25 and 6.20.

The first six lines seem well-established, but the two lines with highest slope at present are rather sparse. Presumably as the number of points increases, there will be more and more lines of ever-increasing slopes.

These lines can be seen in the Havermann link. See the "slopes" link for a list of the first 250000 terms sorted according to slope (the four columns in the table give n, a(n), the slope a(n)/n, and the number of divisors of a(n), respectively).

The primes (with two divisors) all lie on the lowest line, and the lines of slopes 1.43 and higher essentially consist of the products of two primes (with four divisors).

(End)

The eight roughly straight lines mentioned above are actually curves. A good fit for the "line" with slope ~= 1.15 is a(n)~=n(1+1.0/log(n/24.2)), and a good fit for the other "lines" is a(n)~= (c/2)*n(1-0.5/log(n/3.67)), for c = 1,2,3,5,7,11,13. The first of these curves consists of most of the odd terms in the sequence. The second family consists of the primes (c=1), even terms (c=2), and c*prime (c=3,5,7,11,13,...). This functional form for the fit is motivated by the observed pattern (after the first 204 terms) of alternating even and odd terms, except for the sequence pattern 2*p, odd, p, even, q*p when reaching a prime (with q a prime < p). - Jon E. Schoenfield and David Applegate, Dec 15 2014

For a generalization, see the sequence of monomials of primes in the comment in A247225. - Vladimir Shevelev, Jan 19 2015

From Vladimir Shevelev, Feb 24 2015: (Start)

Let P be prime. Denote by S_P*P the first multiple of P appearing in the sequence. Then

1) For P >= 5, S_P is prime.

Indeed, let

a(n-2)=v, a(n-1)=w, a(n)=S_P*P. (*)

Note that gcd(v,P)=1. Therefore, by the definition of the sequence, S_P*P should be the smallest number such that gcd(v,S_P) > 1.

So S_P is the smallest prime factor of v.

2) The first multiples of all primes appear in the natural order.

Suppose not. Then there is a pair of primes P < Q such that S_Q*Q appears earlier than S_P*P. Let

a(m-2)=v_1, a(m-1)=w_1, a(m)=S_Q*Q. (**)

Then, as in (*), S_Q is the smallest prime factor of v_1. But this does not depend on Q. So S_Q*P is a smaller candidate in (**), a contradiction.

3) S_P < P.

Indeed, from (*) it follows that the first multiple of S_P appears earlier than the first multiple of P. So, by 2), S_P < P.

(End)

For any given set S of primes, the subsequence consisting of numbers whose prime factors are exactly the primes in S appears in increasing order. For example, if S = {2,3}, 6 appears first, in due course followed by 12, 18, 24, 36, 48, 54, 72, etc. The smallest numbers in each subsequence (i.e., those that appear first) are the squarefree numbers A005117(n), n > 1. - Bob Selcoe, Mar 06 2015

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(n-1)) is nonempty,

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

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

(Without condition (iii), every prime dividing m might also divide a(n-1), 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 1, since a(n) must contain a prime in a(n-1) and a prime not in a(n-1).)

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.

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(n-1) = x*q^i, a(n) = q*p, where q

= 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

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

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)