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 https://oeis.org/A090252. The sequence begins:

n123456789101112
a(n)1235479111317819
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

  • 1. There are several other, equivalent, definitions of this sequence – see Section 3. This sequence belongs to the family of Lexicographically Earliest (or LES) sequences. It is the simplest of a trio of very similar sequences, the other two being the “Strangers on a Train” sequence A247665, and A353730. Two further similar sequences are A084937 and A249064. There are a great many LES sequences in the OEIS, and if we could crack this one it might help in studying more complicated versions. I have a hunch that by concentrating on the “exceptions” (see Section 5) it may be possible to analyze this sequence.
  • 2. What we can prove (see Section 4): Every prime appears, the primes appear in their natural order; and every prime divides infinitely many terms. Also a(n) <= prime(n-1) for n >= 2, and (a stronger bound) a(n) <= prime(n – b(n-1)), where b(k) = A354166(k) is the number of nonprime terms among a(1),…,a(k). It seems that almost always a(n) = prime(n – b(n-1)), and that this is the equation to the heavy line in the graph.
  • 3. The following are the main open problems: Conjecture 1: Every term is either a prime, a power of a prime, or the product of two distinct primes.

  • 4. Conjecture 2: a(n) is even iff n = 3*2^k – 1 for some k >= 0, and a(n) is a multiple of 3 iff n = 2^k – 1 for some k >= 2. More generally, for any prime p, there is a constant M_p such that for n >= n_0, a(n) is a multiple of p but not equal to p iff n = M_p*2^k – 1 for some k >= k_0. See Section 5.
  • 5. Conjecture 3: The numbers 6, 10, 14, 15, 22, 33, 34, 35, 38, 39, 46, … do not appear. See Section 5.
  • 6. What is the rate of growth of the upper-bound line shown in the graphs? This is the line U(n) = prime(n – b(n-1)) where b(k) = A354166(k) is the number of nonprime terms among a(1),…,a(k). See Section 6.
  • 7. Thanks to Russ Cox, A090252 has a table giving the first 5.7 million terms (more precisely, N = 5764982 terms). This was obtained with a Go program analogous to that for A247665. It can compute 5.7 million terms in 5 minutes. It would be useful to have equally efficient programs in Maple, Mathematica, PARI, or Python. [June 20 2022: Hugo van der Sanden has now written a Perl program that has computed 10^9 terms. See Comments.]
  • 8. Russ Cox’s table in fact gives the first N = 5764982 terms, which consist of 5761455 primes, 1009 prime powers p^k, k >= 2, and 2517 semiprimes pq, 2 <= p < q, and the initial a(1)=1. The total number of nonprime terms is 1009+2517+1 = 3527 = b(N). This supports the conjecture that almost all terms are primes.
  • 9. I am hoping that this blog will lead to a collaborative attack that will answer the above questions. Anyone who can help is encouraged to add a comment.  (I don’t know if other people can add figures or graphs, but if not I will be glad to add them.  I can be reached at njasloane at gmail.)
  • 10. Amarnath Murthy submitted the sequence to the OEIS in 2003. Here is a partial list of people who have recently contributed to this entry or the set theory version A354169: Michael S. Branicky, Russ Cox, Michael De Vlieger, Thomas Scheuerle, Rémy Sigrist, Hugo van der Sanden, Walter Trump, and the present author.
  • 11. Notation: a(n) denotes A090252(n) (except in Section 7), log is natural log, and log_2 is log to base 2.
  • 12. Brief summary of the Comments. The first seven comments are from Hugo van der Sanden (and me). Hugo discusses the mechanism that controls the next term, and how he used this analysis to greatly speed up the calculations, enabling him to reach 10^9 terms. The eighth comment, from Hugo van der Sanden on June 16 2022, discusses the possibility that there could be a term that is divisible by three different primes. Comments 9, 10, 11, from Thomas Scheuerle, deal with the set-theory version A354169 defined in Section 7.

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.

n123456789101112
a(n)1235479111317819
b(n-1)11112233334
p(n-b(n-1))23577111113171919
difference000302000110
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 https://oeis.org/A354164/a354164.txt

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&#8221;>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.

11 responses to “The Two-Up Sequence”

  1. Hugo van der Sanden Avatar
    Hugo van der Sanden

    Gosh, it’s been a while since I thought about this.

    It is interesting to tabulate [ new, a(n), available ] to show 1) any primes that just become available, because at a(n) they are no longer suppressed, 2) a(n) itself (factorized), 3) the list of available primes <= m(n), the highest prime used up to a(n). A fragment would look like this:


    new........a(n)......available
    5..........5*11.........13--23
    ............79..........13--23
    3,7.........3^3.......7,13--23
    ............7^2.........13--23
    29..........83..........13--29

    (I hope that shows up all right, I’m guessing based on this post that it should show as fixed-width font.)

    Most of the time, the “available” list will consist of a range of consecutive primes p_e..p_f from sqrt(m(n)) to m(n/2), with the occasional outlier.

    The ways for this to change are a) m(n) increases past p^2, and we emit p^2 (eg a(14)=25); b) the effect of a(n)=pq expires, we immediately reuse p but q stays on the list (eg the 7 in the third row of the fragment above, when the effect of a(15)=21 expires) usually for just one more step; c) the effect of composite a(n) = px expires, p^k < p.p_e sqrt(m(n)), I’d expect the next entry after 2^k to be the lesser of 2^{k+1} and 2P_n.

    (However it’s possible that (c) occurs often enough that p_e values are consumed faster than increasing sqrt(m(n)) moves the threshold; in that case we’d see cases of 2p with (p – P_n) gradually increasing.)

    The main plausible route to proof that suggests itself to me would be if one could show that when the effect of p^k expires, p is always immediately reused (ie that always either p^{k+1} or pP_n are available and < m(n)); and that when the effect of pq expires, one of p or q is always immediately reused, and the other always reused in the next step.

  2. Hugo van der Sanden Avatar
    Hugo van der Sanden

    Well the type (c) composites do indeed come often enough that p_e grows consistently further away from sqrt(m(n)), and as a result we do find primes > sqrt(m(n)) returning to availability that are not part of the contiguous set. The first example is at a(515) when we free up 19 * 59 with m(n)=3323 and the contiguous range starting at 89, but they start to show up very regularly for n>1000. So if we define p_e as the least available prime > sqrt(m(n), I think S(2) is still interleaving 2p_e with 2^k, but the actual values those p_e take on will not be as easy to predict as I had imagined.

    Neither are small primes always used immediately: at a(2051) we have just made 53 and 167 available, but we get to use neither of them since we have already used both 53^2 = a(512) and 53 * 167 = a(1025) (the one we just freed up), with m(n)=16843. (I think this also explains why S(53) is the first example with multiple exceptions.)

    Nonetheless, I anticipate that a high proportion of the available primes will continue to be in a contiguous range, so that should make it possible to implement code that will generate values quickly without the explosive growth in memory use of my previous attempts. I’ll have a go at that tomorrow, with an initial target of a(10^8).

    1. Hugo van der Sanden Avatar
      Hugo van der Sanden

      that should make it possible to implement code that will generate values quickly without the explosive growth in memory use of my previous attempts. I’ll have a go at that tomorrow, with an initial target of a(10^8).

      Now done as A249064/A090252. This manages 10^8 values in about 4.5 minutes on my machine, even when heavily loaded.

  3. Thank you. Indeed, there was a typo, which I have corrected.

  4. Hugo van der Sanden Avatar
    Hugo van der Sanden

    My new code keeps a stack of “small primes” that are available for use, and have been used in at least one composite value before, and a range of “large primes” that are available for use, and have never been used in a composite value before – since no previously used composite is divisible by any of the large primes, we can only ever use the first prime in the range at any step, and only ever add the next prime to the end of the range, so it is guaranteed to remain a single set of consecutive primes.

    So I measured how large that stack of small primes gets. The order of events is:
    – release primes that are newly available, if any
    – determine the next value, mark used primes as no longer available
    – measure the stack size

    With this, the first time the stack reached size 1 was at n=31: 3 and 7 were released, a(31) = 27 immediately used the 3, leaving the stack as (7), and the range of large primes as (13 .. 23).

    The first time the stack reached size 2 was at n=16895: 7 and 313 were released, while 461 was already available; a(16895) = 2401 immediately used the 7, leaving the stack as (313, 461) and the range of large primes as (709 .. 84751).

    The stack did not reach size 3, checked up to n=10^9.

    I had guessed that either the stack of small primes would grow slowly but inexorably, or that it would tend to stay relatively small. I didn’t expect it to stay that small though.

    I note also that no exception was seen to the “prime power or semiprime” conjecture up to n=10^9.

    1. As a follow-up to the above comment, Hugo van der Sanden sent me an email on June 16 2022, saying:
      (Start)
      I’ve generated a file up to A090252(10^9) that lists all the composite terms. Here are the details:

      # Table showing n, a(n), f, s, r, u for composite a(n)
      # where a(n) = A090252(n); f is the list of primes freed at this step;
      # s is the list of available “small” primes (which have been used in at
      # least one previous composite a(n)); r is the range of available “large”
      # primes (which have been used as a prime a(n), but not as a composite);
      # and u is the least unused prime.

      which, for example, starts and ends so:
      1 1 f= s= r= u=2
      5 4 f= s= r= u=7
      7 9 f= s= r= u=11
      11 8 f=2 s= r=5..5 u=19
      14 25 f= s= r=7..7 u=29
      15 21 f=3 s= r= u=29
      23 16 f=2 s= r=11..17 u=59
      29 55 f=5 s= r=13..23 u=79

      944476044 21231112681 f= s= r=209549..10395426703 u=21478250809
      1006632959 1047745 f=5,145721 s=145721 r=209563..11113309813 u=22959060791

      The whole file is about 2.6MB.

      There are 39089 composite terms.
      A090252(1006632959) = 1047745 is the 39089’th composite (obviously a semiprime).
      Of these, 11122 are prime powers, 27967 are semiprimes.

      The frequency of powers among the prime powers is (starting from 2):
      11000 75 16 7 4 4 3 2 2 2 1 1 1 1 1 1 1

      (End)
      This file (about 39000 lines) has now been added to the OEIS entry A090252. It is a sequel to Russ Cox’s file that gave the first 3527 entries (in a more abbreviated form), which can also be seen in A090252.

    2. I mentioned to Hugo that I was studying his Perl program for computing the Two-Up sequence A090252. It is available from github:

      https://github.com/hvds/seq/blob/master/A249064/A090252

      There is also a link to the program from the A090252 entry in the OEIS.

      Hugo then kindly provided the following explanatory notes:

      1. Precision: Perl’s native integers will lose precision for values greater than MAX_INT (typically 2^32-1 or 2^64-1, depending on the build). So all integer calculations go via the functions square(), prod() and trypow(); in those functions I check the range, and if needed upgrade the (fast) native integers to (slower) big-integer objects (“Math::GMP”) that use the Gnu multi-precision library.

      Once upgraded, those objects can be used exactly as if they were simple integers.

      The calculation of MAX_INT works by taking the bitwise-complement of zero (~0), which automatically gives the appropriate power of 2.

      2. Making primes available (lines 97-109):

      When n is odd (tested by checking the bitwise calculation n & 1 in a boolean context), we want to make available any prime factors used at index floor(n/2), calculated as n >> 1 (n bitwise shifted right by one place).

      We store only composite values of a(n), so we check (line 99) whether we had a composite value, and delete it from the lookup to save memory. If we did, we recover the prime factors of that value by factorizing it,
      and combine those with any outstanding “small” primes in the @small array, in ascending order (lines 101-102).

      If we had not recorded a composite value at that index, it must have been a prime; and since the primes are known to be used in ascending order, the prime to be freed must be the next one that has not already been freed before. So we set the end of the range to the first unfreed prime; if the range was previously empty we also set the start of the range to the same value; and we advance the variable holding the next unfreed prime to be the next prime (lines 105-107).

      3. Calculating the next value (lines 113-132):

      We will try various possible candidates for the next value, the function try() will keep track of which is the best of those, and record associated information so we know what the knock-on effects of our eventual choice will be.

      Let S_i be the elements in our list of small primes (starting i=0), R be the first in our large prime range, and U be the first prime that has never yet been used, then the candidates are:

      – U (line 113);
      – R^2 (line 115);
      – S_i^k for all i, k (line 116);
      – trypow() looks for the first power that hasn’t already been used
      – S_0 * R (line 117);
      – S_i * S_j for all i, j (lines 120-128);
      – we skip some (i, j) combinations if we know they cannot improve on what we have
      – S_0^2 * S_1 (line 130).
      – if this would be chosen as the best value, we treat it as an error and stop immediately

      Note that U and any multiple of R are guaranteed never to have been used, so we do not need to consider R_1^2, or S_1 * R, or S_0 * R_1. For the same reason the first value not a prime power or semiprime
      can only be S_0^2 * S_1.

      4. Handle the knock-on effects of the value chosen (lines 136-157):

      $r = $best->{free} is a set of flag bits describing what primes were involved in our choice.

      – if we used R, we advance the start of the range of large primes, with a check for the range becoming empty (lines 138-142).
      – if we used any S, we will have stored in $best->{small} a list of indices within @small of the affected prime(s). We now use that list to remove those primes from @small (line 145).
      – if we used U, we advance the variable holding the first never-used prime (line 150)
      – else if we did _not_ use U, we know we have a composite value. We double-check that this isn’t one we used before (line 152); record that this value has been used (line 152); and record that this index
      had this composite value (line 153).

  5. Hugo van der Sanden Avatar
    Hugo van der Sanden

    A bit of detail for conjecture 1: any counterexample must be of the form p^2q, and we must previously have seen pq and any power p^k or q^k that are less than p^2q (so at least p^2, p^3; and p, q class as “small” primes in my previous comment above); additionally, letting r be the least prime that has never appeared in a composite value (the least “large” prime), we need pq < r (else we would take pr, which we know has not been used).

    p and q may become available either simultaneously after the effect of pq expires, or separately. In the simultaneous case we get only one shot at it, and all p^k, q^k < p^2q must have been used before pq. In the separate case, the first of p or q to become available must stay unused for enough steps (at least 2) for the other to become available, and the 2^k pattern for S(p) and S(q) suggests this will become a significant constraint after very few iterations.

    I'll aim to get some statistics on how long small primes can remain unused, which may help towards ruling out the second case. I'm not sure what could rule out the first case.

  6. Thomas Scheuerle Avatar
    Thomas Scheuerle

    ” Thomas Scheuerle asked me if all the terms of the set-theory version have binary weight at most 2. I checked the first 4941 terms, and it is true. ”

    A possibly incorrect and certainly very incomplete start for developing a possible proof:

    Let C be the cumulative binary OR over A354169.
    C = BitOR{ k = floor(n/2)..n-1}a(k).
    Then we see that C is soon in a state of saturation where it contains only
    these zeros where previously in a(floor(n/2)-1) and a(floor(n/2)-2) where occupied by ones.
    In most cases the binary expansion of C looks like (2^m-1) – (a(floor(n/2)-1) AND a(floor(n/2)-2)).

    Conjecture:
    The pattern of zero bits in C below the MSB will never repeat if the number of zeros below MSB in C is greater than 2. Why? These bits will not all be set again in synchronicity by adding a new a(n), so they will never again appear set to zero in synchronicity again. Condition that this will be true: All new a(n) have Hamming-weight <= 2.

    Idea for why no Hamming-weight = 3:
    If the condition of saturation of C was already reached and we have already some sequence a(0..n-1) with all values having Hamming weight <= 2, then to be able to add a number a(n) with a Hamming weight = 3 all the HW = 2 bit sub pattern of this number must be already part of the sequence, otherwise they would precede because of having a smaller numeric value.
    And also of course there must be at least 3 zeros in C which are not part of a record-power of 2 available in C.
    Here we will now face a contradiction this would mean we see now 3 bits in C simultaneously set to zero, which where previously already zero at 3 different times but as overlapping groups of only two bits. (Because to enter the three HW = 2 sub pattern into the sequence we need zeros in C there.) To get three bits at the same time with state zero in C, the numbers which would have previously occupied these same bits at a(floor(n/2)-x) would need small and relatively similar x values (need to be in close proximity in the sequence and close proximity to floor(n/2)) to allow synchronicity in the appearance of these zeros.

  7. Thomas Scheuerle Avatar
    Thomas Scheuerle

    If some features of what I mentioned about A354169 are true for A090252 too, then I would expect some property regarding the semiprimes in A090252:
    Let P_a, P_b, P_c, P_d be some distinct prime numbers, then I expect that if P_a*P_b is part of A090252 and P_a*P_c and P_b*P_d are in A090252 too, then P_c*P_d will not be in A090252 because P_a and P_b will not again become usable in the same step.
    But maybe this is wrong, as the additional freedom provided by prime exponents may provide further relevant aspects compared to A354169.

  8. Thomas Scheuerle Avatar
    Thomas Scheuerle

    I try to shorten my last two comments here:

    We know:
    Se set of bits allowed for usage the records of powers of two + a union of bit values in the binary expansion of sequence members past floor(n/2) which are disjoint to each other.

    Attempt for a shortened prove concept regarding A354169:
    Let us call this union of allowed bits C. If C contains more than two bits,
    but we know that the past of our sequence contains only values up to a Hamming-weight 2, then we know that C is a union of at least 2 disjoint members of our past sequence.
    If this is the case than we know that there is at least a two bit value numerically smaller or equal to the full set of bits in C which is not yet already in our sequence. This is because the values contributing to C are in sequence disjoint and with priority less value first.

    Please help to find the problems and missing parts here if possible 🙂

    Thank you.

Leave a Reply to Hugo van der Sanden Cancel reply

%d bloggers like this: