cp's OEIS Frontend

This is also "minimal subset/superset bitmask" transform of the nonnegative integers, A001477. In that transform, applicable to any N -> N injection f, we start from a(0) = 0, after which for n > 0, if there are one or more k_i that are not already present in the sequence among terms a(0) .. a(n-1), and for which bitor(k_i,a(n-1)) = a(n-1), then a(n) = that k_i for which f(k_i) is minimized; otherwise, a(n) = that h_i for which f(h_i) is minimized among the infinite set of numbers h_i for which bitand(h_i,a(n-1)) = a(n-1) and that are not yet present in the sequence. In this case f(n) = A001477(n) = n.

The original, equivalent definition is:

a(0) = 0 and for n > 0, if there are one or more k_i that are not already present in the sequence among terms a(0) .. a(n-1), and for which bitor(k_i,a(n-1)) = a(n-1), then a(n) = that k_i which gives minimum value of A019565(k_i) amongst them; otherwise, when no such k_i exists, a(n) = the least number not already present that can be obtained by toggling a single 0-bit of a(n-1) to 1. This is done by trying to toggle successive vacant bits from the least significant end of the binary representation of a(n-1), until such a sum a(n-1) + 2^h (= a(n-1) bitxor 2^h) is found that is not already present in the sequence.

Shares with permutations like A003188, A006068, A300838, A302846, A303765 and A304083 the property that when moving from any a(n) to a(n+1) either a subset of 0-bits are toggled on (changed to 1's), or a subset of 1-bits are toggled off (changed to 0's), but no both kind of changes may occur at the same step.

Also, like A003188, A006068 and many other base-2 representation related permutations, this permutation preserves the binary size of n (A000523(n)), and furthermore, a(n) seems to stay at most points (except at powers of 2) remarkably close to n.

From Antti Karttunen, May 23 2018: (Start)

Outline of the proof that the definition involving A019565 is equivalent to the recurrent formula:

Even though A019565 is nonmonotonic, for example A019565(4) = 5 = p_3 < A019565(3) = 6 = p_1 * p_2, and in general, although there are always primes p_k < p_{i1} * p_{i2} * ... * p_{ih}, with i1, i2, ..., ih < k, it doesn't matter here, because not just the position of the most significant 1-bit is monotonic in this sequence (see the binary representation at A304747), but also in each subrange (2^k)+2 .. (2^(k+1))-1 the position of the second most significant 1-bit moves only leftward, i.e., is monotonic, which follows from the recursive formula.

To see this, consider the first time in this sequence when in a batch of terms (of equal binary width) we have bits in position k (the most significant position) and (k-1) on (that is, both are 1's), the latter corresponding to prime p_k: while in principle a bit-based rule could choose to subtract 2^(k-1), in preference to any 1-bits to the right of it (that correspond to primes p_{i1} .. p_{ih}), it cannot do so at this stage, because it is the second most significant 1-bit, and then it would not move only leftward, contradicting what was said above. Neither this can occur later when more 1-bits have appeared to their left: the recursive formula guarantees it.

Also conversely, even though p_4 = 7 > 6 = p_1 * p_2, and in general, we always have such prime p_k > p_{i1} * p_{i2} * ... * p_{ih}, with i1, i2, ..., ih < k, and while here A019565-based rule (see comments in A303760) would prefer dividing p_k out instead of any subset of p_{i1} .. p_{ih}, it happens that in that rule, the index of the largest prime (A061395) grows monotonically, so at the stage where p_k is the largest prime of the batch of length 2^(k-1), p_k just cannot be divided out, and also here the structure of the later batches is strictly determined by recursion.

(End)

Consider A019565. Imagine that it is an automatic piano that "plays sequences" when an appropriate punched "tape" is fed to it (as its input), i.e., when it is composed from the right with an appropriate sequence p, as A019565(p(n)). The 1-bits in the binary expansion of each p(n) are the "holes" in the tape, and they determine which "tunes" are present on beat n. The "tunes" are actually primes that are multiplied together. Of course only "squarefree music" (sequences containing only squarefree numbers, A005117) is possible to generate this way, thus we call A019565 a "squarefree piano".

There is a more sophisticated instrument, called "Fermi-Dirac piano" (A052330), with which it is possible to produce sequences that may contain any numbers.

If the tape is constructed in such a way that between the successive beats (when moving from p(n) to p(n+1)), either a subset of 0-bits are toggled on (changed to 1's), or a subset of 1-bits are toggled off (changed to 0's), but no both kind of changes occur simultaneously, then when fed as an input to either of these pianos, the resulting sequence "s" (the output) is guaranteed to satisfy the condition that s(n+1) is either a multiple or a divisor of s(n). For example, Gray code A003188 and its inverse A006068 are examples of such tapes, and they produce sequences A302033, A207901 and A284003, A302783.

This divisor-or-multiple permutation is obtained by playing "Fermi-Dirac piano" with the same tape which yields A303760 when "squarefree piano" is played with it. Note that A303760 is not a subsequence of this sequence, as its terms occur in different order than the squarefree terms here.

See also Peter Munn's Apr 11 2018 message on SeqFan-mailing list and comments in A304537.

Each a(n+1) is either a divisor or a multiple of a(n).

The primorials (A002110) occur in ascending order, in positions given by A300829, and each is then followed by the least unused term up to that point. For n = 2 .. 79 this is the highest prime factor of the said primorial, but note that for A300829(80) = 4965, a(4965) = A002110(80), but a(4966) = 407 = 11*37, instead of prime(80) = 409. Note that 409 occurs at a(5043), where 5043 = 1+A300829(81).

For example, 11 comes after a(A300829(5)) = a(12) = 2310 = 2*3*5*7*11, and all squarefree numbers < 11: {1, 2, 3, 5, 6, 7, 10} occur before a(13).

Each a(n+1) is either a divisor or a multiple of a(n).

The construction is otherwise like that of A303760, except here we choose the largest divisor instead of the smallest one. In contrast to A303760, this sequence is NOT permutation of A005117: 70 = A019565(13) is the first missing squarefree number. See also comments in A303769, A303749 and A302775.

Index of greatest prime factor of a(n) is monotonic and increments at n = {0, 1, 2, 4, 8, 15, 31, 50, 102, 157, 317, 480, 964, 1451, 2907, 4366, 8738, 13113, 26233, 39356, ...} - Michael De Vlieger, May 22 2018

Each a(n) is always either a divisor or a multiple of a(n+1).

Consider A052330. Imagine that it is an automatic piano that "plays sequences" when an appropriate punched "tape" is fed to it (as its input), i.e., when it is composed from the right with an appropriate sequence p, as A019565(p(n)). The 1-bits in the binary expansion of each p(n) are the "holes" in the tape, and they determine which "tunes" are present on beat n. The "tunes" are actually "Fermi-Dirac primes" (A050376) that are multiplied together.

If the tape is constructed in such a way that between the successive beats (when moving from p(n) to p(n+1)), either a subset of 0-bits are toggled on (changed to 1's), or a subset of 1-bits are toggled off (changed to 0's), but no both kind of changes occur simultaneously, then when fed as an input to this piano, the resulting sequence "s" (the output) is guaranteed to satisfy the condition that s(n+1) is either a multiple or a divisor of s(n). Furthermore, if the given sequence p is itself a permutation of natural numbers, then also the produced sequence is. For example, Gray code A003188 and its inverse A006068 are such sequences, and when given as an "input tape" for A052330, they produce permutations A207901 and A302783.

There is a simpler instrument, called "squarefree piano" (A019565), with which it is possible to produce similar divisor-or-multiple sequences, but that contain only squarefree numbers. Given A003188 or A006068 as an input tape for it produces correspondingly sequences A302033 and A284003.

This sequence is obtained by playing "squarefree piano" with the same tape which yields A304531 when "Fermi-Dirac piano" is played with it. However, in this case the sequence A304531 is produced by a greedy algorithm, and thus its tape (A304533) is actually a back-formation, obtained from the "music" (A304531) by applying "tape-recorder" (A052331) to it. Note that this in not a subsequence of A304531, as the terms occur in different order than the squarefree terms of A304531.

See also Peter Munn's Apr 11 2018 message on SeqFan-mailing list.

Each a(n+1) is either a divisor or a multiple of a(n).