Site icon Neil Sloane Blog

The Two-Up Sequence

The Two-Up sequence is a little-known classic of great interest. There are many conjectures but few theorems. I’m hoping people will help fill in the gaps. Anyone who can help is welcome to contribute to this blog.


1. Introduction

The sequence has a simple definition:

(D1) The Two-Up sequence consists of distinct positive integers, and the n-th term a(n) must be relatively prime to the next n terms. Always pick the smallest possible number.

The OEIS entry is The sequence begins:

Table 1. The first 12 terms of the Two-Up sequence A090252

Explanation: a(1) = 1 (it has to be positive!)

a(2) has to be relatively prime to 1 and can’t be 1, so a(2) = 2.

a(3) and a(4) have to relatively prime to a(2) = 2, so a(3) = 3 and a(4) = 5 work.

Now a(3) = 3 tells us that a(4), a(5), and a(6) have to be relatively prime to 3, and must be numbers we haven’t used. We don’t have to worry about a(4) being relatively prime to a(3), since that was already taken care of at the previous step. So from a(3) = 3 we get a(5) = 4 and a(6) = 7.

The sequence continues in this way. From a(4) = 5 we get a(7) and a(8), and at each subsequent step we get two more terms. This means that we can restate the definition in a simpler and more explicit way:

(D2) Start with a(1) = 1 and a(2) = 2. At each step k >= 2, given a(k), the sequence is extended by adding two terms: a(2k-1) = smallest unused number which is relatively prime to all of a(k), a(k+1), …, a(2k-2), and a(2k) = smallest unused number which is relatively prime to all of a(k), a(k+1), …, a(2k-1).

That is why I call this the Two-Up sequence, because it grows by two steps at a time. (It has nothing to do with the famous Australian coin-tossing game of the same name.)

This is one of the most fascinating sequences in the OEIS, because the definition is simple and classic, but we have almost no hard facts about it. Here are two graphs: first a pin plot of the first 200 terms, then a scatterplot of 34K terms.

Figures 1 and 2: A pin plot of the first 200 terms of the Two-Up sequence A090252, and a scatterplot of the first 35K terms.

You can see that most of the terms lie on a line (these are the prime numbers) , but occasionally there are gaps where (usually smaller) nonprime, terms appear.

2. Remarks

3. Alternative definitions

Here are three further equivalent definitions of the Two-Up sequence (A090252). We omit the easy proofs that all five definitions are equivalent.

(D3) a(n) is the smallest unused positive number that is relatively prime to the previous floor(n/2) terms.

(D4) This is the lexicographically earliest infinite sequence of distinct positive numbers with the property that the n-th term is relatively prime to the following n terms.

(D5) This is the lexicographically earliest infinite sequence of distinct positive numbers with the property that the n-th term is relatively prime to the previous floor(n/2) terms..

Of the five definitions, I find (D2) the simplest to work with for most purposes.

4. What we can prove

We continue to use a(n) to denote the n-th term.

Theorem 1: The sequence is infinite, and there is a function W(k) such that for any positive number k, a(n) >= k for all n >= W(k).

Theorem 1 is a standard beginning for analyzing “lexicographically earliest sequences”. See for example the EKG sequence1 A064413, and the Yellowstone Permutation2 A098550.

The next result follows easily from Theorem 1.

Theorem 2: Every prime appears in the sequence, the primes appear in their natural order; and every prime divides infinitely many terms.

Theorem 3: For n >= 2, a(n) <= prime(n – b(n-1)), where b(k) is the number of nonprime terms among a(1), …, a(k).

Proof: When computing a(n), in the first n-1 terms we have seen n-1-b(n-1) primes, so prime(n-b(n-1)) is a candidate for a(n), and is therefore an upper bound on it.

Corollary 4: For n >= 2, if a(n) is a prime, then a(n) = prime(n – b(n-1)), and if a(n) is composite, a(n) < prime(n – b(n-1)).

Proof by induction.

The {b(n)} sequence is A354166. The initial values of a(n), b(n-1), prime(n-b(n-1)), and the difference a(n) – prime(n-b(n-1) are shown in Table 2. By the corollary, the difference is zero iff a(n) is a prime. Since b(n) >= 1, Theorem 3 implies a(n) <= prime(n-1) for n >= 2. We will say more about b(n) in Section 6.

Table 2. For n >= 2, the sequence a(n) is upper-bounded by prime(n-b(n-1)), where b(k) (A354166(n)) is the number of nonprime terms among a(1), …, a(k).

5. Which numbers appear?

As mentioned in Remark 8, the first 5.7 million terms of the sequence are mostly primes, together with a relatively small number of prime powers p^k, k >= 2, and semiprimes pq, 2 <= p < q. It seems plausible that this property will hold in general, so we state this as the first conjecture.

Conjecture 1: Every term is either a prime, a power of a prime or the product of two distinct primes.

We now discuss why this conjecture may be true, but we will also point out that there is a small chance that it is false and that eventually numbers with three or more distinct prime factors may appear.

Suppose a term a(n) is divisible by a prime p but is not equal to p. By definition D2, p cannot divide the terms a(n+1), …, a(2n), but may divide a(2n+1). Since most terms are primes, and the primes appear in the natural order, and a(n) was not prime, most of the terms immediately following a(n) will be much bigger than a(n). By the time we reach a(2n+1), therefore, there is a good chance that there will be another multiple of p that will be the smallest missing number and be a good candidate for a(2n+1).

Let S(p) denote the set of indices k such that a(k) is divisible by p but is not equal to p. The above handwaving argument suggests that if k is an element of S(p), then the next largest element will be 2k+1. The general solution to the recurrence f(k+1) = 2 f(k) + 1 is f(k) = M*2^k + 1 for k >= k_0, for some constants M and k_0. Indeed, this is exactly what S(p) looks like for the initial primes p.

We state this formally as follows:

Conjecture 2: For any prime p, there are constants M_p, n_0, k_0 such that, for n >= n_0, a(n) != p is a multiple of p iff n = M_p*2^k – 1 for some k >= k_0.

We deliberately exclude from S(p) the index where p itself appears in the sequence, because the primes and nonprimes have a totally different behavior. For the indices of the primes see A354148. Note that we can assume M(p) is odd.

Consider first the prime p = 2. In the first 5.7 million terms, we find that a(n) is even precisely for n = 3*2^k – 1, for 1 <= k <= 20 (cf. A083329). These 20 even values themselves, however, are mysterious. They are 2, 4, 8, 16, 26, 32, 64, 128, 206, 256, 478, 512, 998, 1024, 2048, 3134, 4096, 6514, 8192, 13942, 16384 (A354255), and consist of powers of 2 together with the semiprimes 2p for p = 2, 13, 103, 239, 499, 1567, 3257, 6971 (A354159). At present we do not have any other characterization of these primes. June 14 2022: Hugo van der Sanden has found three more terms in the latter sequence. After 6971, we get 14447, 30259, and 63317.

Notice that many even semiprimes, like 6 and 10, seem to be missing. In fact there appear to be infinitely many semiprimes that never appear. We list those that are less than 100 in the next conjecture:

Conjecture 3. The semiprimes 6, 10, 14, 15, 22, 33, 34, 35, 38, 39, 46, 51, 58, 62, 65, 69, 74, 77, 82, 86, 87, 91, 93, 94, 95 never appear.

The structure for multiples of p = 3 is similar to that for p = 2. In the first 5.7 million terms, a(n) is a multiple of 3 precisely when n = 2^k – 1 for k = 2, …, 20. Likewise, a(n) is a multiple of 5 precisely when n = 15*2^k – 1 for k = 0, …, 18.

For primes p >= 7, however, there are usually irregularities at the start. That is, the set S(p) consists of certain exceptional values, followed by terms M(p)*2^k – 1 for k >= some k_0. For example, S(7) = { 15; 33*2^k – 1 for k >= 0}, S(13) = { 47; 97*2^k – 1 for k >= 0}. These exceptional values, as we will see, are the key to understanding the sequence. Table 3 shows the sets S(p) for p <= 53, which is the first prime for which there appears to be more than one exception.

Table 3: The sets S(p) for primes p <= 53

Notes on Table 3. The exceptions roughly correspond to taking k = -1, -2, -3, … in the formula M(p)*2^k – 1. E.g. for p = 13, the exception 47 is close to 97/2 – 1. The sequence of the M(p) values, 3, 1, 15, 33, 61, 97, 121, …, is at present a mystery. It is not yet in the OEIS, and cannot be added since all its terms are conjectural. In the final column, is k_0 always 0 for p >= 7 ? The number of exceptions remains small for a long time. For example, the primes p = 1201, 1213, 1217 all have a single exception, namely 61441, 61443, 61447, and the M(p) values are 122884, 122888, 122896.

Let us assume for the following discussion that the sets S(p) really are as described above. Then we can explain much of the structure of the sequence. To start with, notice that if M(p) and M(q) are distinct odd numbers, then the sequences { M(p)*2^i – 1, i >= 0} and { M(q)*2^j – 1, j >= 0} are disjoint. So if a semiprime pq, 2 <= p < q belongs to the sequence, with say a(n) = pq, then n is in the intersection of S(p) and S(q), and so n must be an exceptional terms in S(p) or S(q) (or both).

But S(2), S(3), and S(5) have no exceptional elements, so the sequence does not contain any multiple of 6, 10, or 15, which would establish part of Conjecture 3.

On the other hand the sequence contains many semiprimes pq, 2 <= p < q. The first few are a(15) = 21, a(29) = 55, a(47) = 26, a(59) = 85, and a(63) = 57 (see A354160 and A354161 for further examples). Their existence corresponds to the exceptional values 15 in S(7), 29 in S(11), 47 in S(13), 59 in S(17), and 63 in S(19) (see Table 3).

There are very few exceptions, so there are relatively few semiprimes compared with the number of primes.

Could there be a term a(n) = pqr, a product of three distinct primes? This could only happen if n is an exception for two out of three of the sets S(p), S(q), S(r). This seems possible. It would be worth extending Russ Cox’s table of 5.7 million terms to see if this happens. (Only the nonprime terms need to be recorded, which means – as we will see in the next section – that to get n terms we need only save on the order of sqrt(n) terms.)

Of course if there does exist a term pqr, this will invalidate most of the above conjectures. So as a sanity check it would be worth trying to get say 10^12 terms of our sequence.

[Added June 20 2022: Hugo van der Sanden has checked 10^9 terms, and no term pqr has appeared. See his comments below.]

6. The rate of growth

From Section 4 we know that the upper envelope is given by the equation

U(n) = prime(n – b(n-1)),

the prime terms lie on this line, and the composite terms lie below it. But how fast does this curve grow as a function of n? There are three sequences that are relevant to this question: A354164, which lists the indices of the nonprimes in the sequence A090252, A354165, which lists the nonprimes themselves in order of appearance, and A354166, which gives b(n), the number of nonprimes in the first n terms.

Figure 3 shows the first 38K terms of b(n).

Fig. 3: The first 38K terms of b(n).

Using the data from A090252 one can easily obtain 5.7 million terms of b(n). I tried several methods to estimate the growth rate. Figure 3 suggests that b(n) might grow like sqrt(n), so I looked for an approximation of the form b(n) = C n^t, or log b(n) = log C + t log n. After 5.7M terms, log b(n) / log n has slowly increased to about 0.525, suggesting t might be about 0.53. Then I tried a least squares fit using Maple’s Fit command from its Statistics package. This did not work too well – the best result I obtained suggested that b(n) is about 4 n^0.463.

To summarize, perhaps b(n) grows like 4 sqrt(n). This would imply that the curve U(n) is about prime(n – 4 sqrt(n)), i.e.

U(n) is approximately (n – 4 sqrt(n)) log n.

Given that we have 5.7 million terms of b(n), it should be possible to find a better estimate. In case someone is willing to help, here is the data. Start with Russ Cox’s table

This file is a table containing 3527 rows. Here are rows 1 through 6 and 3527:

Table 4: Part of Russ Cox’s table of the nonprimes in the first 5.7 million terms of A090252. The last column gives the number of distinct prime factors of A354165(i).

To extract a table of b(n) from this, note that row i = 3 says that b(n) = 3 for all n in the range 7 to 10 (compare Table 2 above). In general, row i says that b(n) = i for all n in the range A354164(i) <= n < A354164(i+1).

I also tried to estimate b(n) by separately counting the prime powers and the semiprimes among the first n terms. For a prime p, the number of powers p^k, k >= 2, among a(1),..,a(n) is at most floor( log n / log p), and then we must sum this over p <= sqrt(n). To count the semiprimes pq, 2 <= p < q, we can use the conjectural discussion in Section 5. For a fixed prime p, the number of pq in the first n terms is at most floor( log_2 (n/M(p))), and then this must be summed over p <= sqrt(n) and divided by 2 since each semiprime is counted twice. But since we don’t know how the M(p) grow, this attack did not lead anywhere.

A final remark about the graph of the sequence shown in Fig. 2. There are conspicuous clusters of nonprimes at regular intervals. I am referring to the nearly vertical columns of dots that start at about n = 1919, 3839, 7679, 15359, etc. These numbers are essentially doubling at each step, and are in fact terms of S(5) = { 15.2^k – 1, k >= 0}: a(1919) = 625, a(3839) = 1315, a(7679) = 1895, a(15359) = 2885. For some reason the multiples of 5 are the record low values (or the slowest to appear), and once one of them appears, it is soon followed by a string of other small missing numbers.

7. The set-theory version

Any “lexicographically earliest sequence” in which the definition imposes constraints on the common factors between terms has a set-theory analog, obtained by replacing “a(i) has a common factor with a(j)” with “there is a coordinate position where the binary expansions of a(i) and a(j) both have a 1”, and “a(i) and a(j) are relatively prime” with “there is no coordinate position where the binary expansions of a(i) and a(j) both have a 1”.

The difference is that in the number-theory version we consider the primes that divide each term, whereas in the set-theory version we look at the set of coordinate positions where the binary expansion of the term has a 1. The number-theory versions usually begin with a(1) = 1, whereas the set-theory versions usually begin with a(0) = 0.

Some interesting examples of pairs (number-theory version and set-theory version) are (the EKG sequence A064413 and A115510), (the Yellowstone Permutation A098550 and A252867), (the Enots Wolley sequence and A338833), and (Grant Olson’s sequence A347113 and A353712).

I particularly like the following pair. If the rule for the number-theory version is simply that a(n) should be relatively prime to the previous term we get the sequence 1,2,3,4,5,…, the natural numbers A000027. The set-theory version of that is the surprisingly complicated Tetris Sequence A109812 that a number of us have been working in the Spring of 2022. I am planning to make that the subject of my next blog.

The set-theory version of the Two-Up sequence is the fairly new sequence A354169. It is slightly less interesting than the set-theory versions mentioned in the previous paragraphs, because it grows extremely rapidly: it essentially doubles at each step. Even so, Rémy Sigrist has created a b-file of 4941 terms. The terms that are not powers of 2 are (in order of appearance) 0, 3, 12, 17, 34, 68, 136, 768, 1025, 18, 2080, 12288, 16388, 72, 32896, … (A354680). There is no other explanation known for these terms. Thomas Scheuerle asked me if all the terms of the set-theory version have Hamming weight at most 2. I checked the first 4941 terms, and it is true. This is the natural analog of Conjecture 1 (see Section 5).

June 16 2022: Rémy Sigrist reports that in the first 477684 terms of A354169 all have Hamming weight 0, 1, or 2. In fact 318457 terms have weight 1, 159226 have weight 2, and one has weight 0.

June 20 2022: Walter Trump reports Hamming weight <= 2 holds for 32*10^7 terms.

7a. Update concerning the Set-Theory Version (A354169), July 12 2022

In the past month there has been a lot of activity concerning A354169 and the derived sequences A354680, A354767, A354773, A354774, A354775, A354780, A354781, A354783, A354798, A355150, especially from F. Michel Dekking, Thomas Scheuerle, Walter Trump, Hugo van der Sanden, and the present author.

In particular, Thomas Scheuerle has added a number of theorems and conjectures to the OEIS entry A354169, which are presently being reviewed. Walter Trump has written a lengthy analysis of this sequence. The latest version can be found [where?].

The rest of this section gives an outline of my own plan for proving the theorem that all weights in A354169 are 2 or less.  (It is not finished, and I could use some help.)

I began by making a large table showing the first 190 terms of A354169 and their binary expansions: See

N. J. A. Sloane, <a href=”https://A354169/a354169_1.pdf”>Table showing first 190 terms</a> (pdf file of scan of large table), and

N. J. A. Sloane, <a href=”https://A354169/a354169_2.pdf”>Left-hand portion of rows 97-135 of preceding table</a>, showing columns 67-96, rotated counter-clockwise by 90 degrees. The red line in this table should be aligned with the red line between rows 135 and 136 in the preceding table. [This portion of the table was too wide to fit through the scanner.]

I divide A354169 into blocks, indicated by the red lines in the table. The zeroth block, terms 0 to 39 is special, and we regard it as the initial terms for the recurrences.

Then blocks 1, 2, 3, … consist of terms 40 to 63, 64 to 87, 88 to 135, 136 to 183, and so on.

The blocks start at these “fence posts”:

 40, 64, 88, 136, 184, 280, 376, 568, 760, 1144, 1528, 2296, 3064, 4600, … (essentially 8*(A354785 – 1)).

The table shows a great deal of regularity. In fact, from entry 40 onwards, everything (including the slight irregularities at the starts of the blocks) can be described by quite simple recurrences.  There are recurrences that specify the indices of the weight 1 terms (see A354767), the indices of the weight 2 terms (A354798), the high order bit of the weight 2 terms (A354774), the low order bit of the weight 2 terms (A354773), and the indices where there is the possibility of a weight 3 term (Remy Sigrist’s A354757 and my A354783).

None of these recurrences have been proved, but they are precise: they say exactly how A354169 grows.  Think of this as a machine that acts like the famous Munich Glockenspiel clock. The blocks in the sequence are like days, only in this machines the days get longer every two days.

The proof that weight 3 never happens will be by induction on the blocks.  We verify that the first block from n=40 to n=63 satisfies the recurrences. The induction step will show that if the recurrences hold for block N, they also hold for block N+1.

The crucial step in the proof – which I have not fully worked out – is to understand exactly how the next term a(n) in A354169 is constructed.

Suppose block 1, entries a(40)-a(63), is as claimed. We have to show that block 2 is given by the same recurrences. The first thing is a(64). To illustrate the procedure, let’s go back to the start of block 1, and ask how is a(40) determined?

The definition tells us that a(40) has to be disjoint from a(20) through a(39), and must be the smallest such number that is not yet in the sequence.

 The logical OR of a(20) through a(39) is A354757(40) which is 268435387 (from the b-file for A354757, or from the recurrence when we are doing the general case).

In binary this is

 1^14 1^7 0 111 0 11  (the bits here are in human order)   (*****)

and the binary complement is

 000000000 1 000 1 00 = 68    This is by definition A354783(40)

This has weight 2 so there is no choice for it to be a(40) – all the powers of 2 have already been used, and 68 has already appeared at a(19).  So a(40) is the next power of 2.

 Let me make some remarks about the “OR” vector (*****).

 Here it has two 0’s.  In general experiment shows that it has 0, 1, 2, or 3 0’s.

The only places where it has 3 zeros are

13, 19, 29, 31, 41, 43, 53, 59, 65, 67, 77, 83, 89, 91, 101, 107, 113, 119, 125, 131, 137, 139, 149, 155, 161, 167, 173, 179, 185, 187, 197, 203, 209, 215, 221, 227, 233, 239, 245, 251, …

, a sequence which has a simple structure: take first differences, which produces

6, 10, 2, 10, 2, 10, 6, 6, 2, 10, 6, 6, 2, 10, 6, 6, 6, 6, 6, 6, 2, 10, 6, 6, 6, 6, 6, 6, 2, 10, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 10, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 10, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 10, 6, 6, 6, 6, 6, 6, …

and then take the RUNS transform, getting

1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 6, 1, 1, 6, 1, 1, 14, 1, 1, 14, 1, 1, 30, 1, 1, 30, 1, 1, 62, 1, 1, 62, 1, 1, 126, 1, 1, 126, 1, 1, 254, 1, 1, …

If you look at my huge table, mentioned above, and put a red dot at the rows where weight 3 appears, you see there is an obvious pattern to the red dots. (Basically they appear after each run of three powers of 2.)

However, we don’t really need to know much about these  terms.

Now I can talk about what is really going on.

First , in the huge table, there are basically three columns of 1’s. The third column has some stray 1’s to its right, but they are explained by the recurrences.

On the left-hand edge, there are the 1’s from the powers of 2.  Next, there is a column of 1’s from the high-order bits in the weight 2 terms. This has an obvious regular structure. Then on the right of the graph, there is another easy column of 1’s from the low order bits, plus on the extreme right there are some further 1’s.  Note that these are all controlled by the recurrences. The recurrence for the low order bits is very interesting, for it basically is L(2t) = L(t-1), L(2t-1) = t, where L(t) denotes the t-th low order bit. This gives the slightly fractally appearance to the right side of the graph.

Now let us return to the binary vector (*****), which is:

 1^14 1^7 0 111 0 11

The first group of 1’s is from the powers of 2, the next group is from the high order bits of the weight 2 words, and the rest is from the low order bits.

In general (*****) looks like

 111111111111  0’s maybe  1111111111 0’s maybe   111111111111111111 0’s maybe 111111

  powers of 2              high bits           low bits with maybe an internal 0

(a solid block of 1’s)  (a solid block of 1’s)

In practice it seems that (*****) always has 0, 1, 2, or 3 0’s, and so the complement (A354783) has weight at most 3.

To be continued.

8. Figures to go with the Comments below

Perhaps people who send comments are not allowed to include figures?? I do not know. But I will be happy to add them here.

Thomas Scheuerle emailed me two figures on June 16 and 17, 2022. For the first one, he said:

I have a svg file attached here. [I had to convert it to .png – njas]
The X axis is n.
The Y axis identifies the bits 1 -> 2^0; 2 -> 2^1 …
Red dots are the bits used by A354169(n).
Blue circles are bit positions below the record powers of 2^m
which may be used by new values in the sequence.

We observe if a new value of the sequence uses bit position below the records then always the lowest possible position is part of this usage too.

This is in my opinion very important for understanding all the other effects.

For the second figure, he (Thomas Scheuerle) said:

I did another graph, for A090252
Red dots are the prime factors of A090252(n).
Y is the prime(y) with Y=0 -> 1.
The blue circles show primes which are below the record primes and
are available for use in the actual step.
The arrows with numbers show the exponent of the prime number that was used.
We observe a much less saturated situation than in A354169,
but the rules found in A354169 still hold fine.

9. A final remark

It would be nice to know more about the sequences mentioned in this blog. I encourage people to send in comments, proofs, etc. Or send them to me (njasloane at gmail) and I will add them.

Chronology (of major changes; does not mention Comments):

June 13 2022: Blog started.

June 14 2022: Mentioned Hugo van der Sanden’s extension of S(2) in Section 5.

June 16 2022: Mentioned Rémy Sigrist’s work on Hamming weight of A354169 in Section 7.

June 17 2022: Added Thomas Scheuerle’s two figures to Section 8.

June 20 2022: Added this Chronology. Added notes [in brackets] to Remark 7 and Section 5, pointing to updates to be found in the Comments. Added note to Section 7 about Walter Trump’s work on Hamming weight of A354169.

June 25 2022: Added Remark 12, giving a brief summary of the Comments.

July 12 2022: Added Section 7a reporting on recent work on the Set-Theory version.

Neil J. A. Sloane, last modified July 12 2022

  1. J. C. Lagarias, E. M. Rains and N. J. A. Sloane, The EKG sequence, arXiv:math/0204011 [math.NT], 2002; Exper. Math. 11 (2002), 437-446.
  2. 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; J. Int. Seq. 18 (2015) 15.6.7.
Exit mobile version