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)

A permutation of the positive integers (but please note the starting offset: 0-indexed).

This sequence is a variant of A052330.

Shares with A064736, A302350, etc. the property that a(n) is either a divisor or a multiple of a(n+1). - Peter Munn, Apr 11 2018 on SeqFan-list. Note: A302781 is another such "divisor-or-multiple permutation" satisfying the same property. - Antti Karttunen, Apr 14 2018

The offset is 0 since S_0 = {1} denotes the first 2^0 = 1 terms. - Daniel Forgues, Apr 13 2018

This is "Fermi-Dirac piano played with Gray code", as indicated by Peter Munn's Apr 11 2018 formula. Compare also to A303771 and A302783. - Antti Karttunen, May 16 2018

Note that the starting offset is 0, to align with A052330 and A207901.

Shares with A064736, A207901, A298480, A302350, A302783, A303771, etc. the property that a(n) is either a divisor or a multiple of a(n+1). Permutations satisfying such property are called "divisor-or-multiple permutations" in the OEIS, although Mazet & Saias call them "chain permutations" in their paper. [Edited by Antti Karttunen, Aug 26 2018]

One way to construct such permutations is by composing A052330 from the right with any such permutation like A003188 or A302846 where the binary expansions of a(n) and a(n+1) always differ by just a single bit-position.

Further permutations satisfying the same condition could be constructed from higher-dimensional versions (i.e., greater than 2) of Hilbert's space-filling curves, where the coordinates of each dimension would be Gray coded separately and then interleaved together. Permutation A207901 is essentially a one-dimensional variant of the same idea, while this is constructed from the 2-dimensional curve A163357, which is a Hamiltonian path on N X N grid.

See Peter Munn's A300012 for another idea for constructing such a permutation. - Antti Karttunen, Aug 26 2018

The greedy algorithm which constructs this sequence can be understood also in terms of Heinz encodings of partitions (see A215366): Any term a(n) corresponds to a particular integer partition {s1+...+sk} via mapping a(n) = prime(s1) * ... * prime(sk), where s1 .. sk are the summands of an integer partition. The choices for constructing the next partition are: If by removing any parts from the partition we can find any smaller partitions that have not already occurred in the sequence, then we choose the one which has the smallest Heinz encoding value. On the other hand, if all partitions obtained by such removals have already occurred in the sequence, then we add to the current partition the least number of copies of the least positive integer that is not yet a part of the partition (A257993), until a partition is found which is not yet in the sequence.

From Antti Karttunen & David A. Corneth, May 01 - 04 2018: (Start)

No two successive descending terms, that is, a(n) > a(n+1) > a(n+2) never occurs.

For n > 1, if a(n) is odd then a(n-1) = 2^h * k * a(n) and a(n+1) = 2^j * a(n) for some h, k and j, that is, odd terms occur between two larger even numbers.

If a(n) < a(n+1) < a(n+2) then (a(n+1) / a(n)) is a divisor of a(n+2).

However, when a(n) < a(n+1) > a(n+2) then (a(n+1) / a(n)) might not be a divisor of a(n+2). The first such case occurs at n=64..66, as a(64) = 280 = 2^3 * 5 * 7, a(65) = 7560 = 2^3 * 3^3 * 5 * 7, and a(66) = 72 = 2^3 * 3^2. We have 7560/280 = 27, which is not a divisor of 72 (72/27 = 8/3).

In most cases, when a(n+1) < a(n) then gcd(a(n+1), a(n)/a(n+1)) = 1 (about 87% for the first 100000 descents). However, there are many exceptions to this, the first case occurring at a(65) = 7560 = 2^3 * 3^3 * 5 * 7 and a(66) = 72 = 2^3 * 3^2, with gcd(72,7560/72) = 3.

(End)

From David A. Corneth, May 04 2018: (Start)

The sequence can be partitioned into a tabf sequence with rows having the first element odd and the others even. It would give (1, 2, 6), (3, 12, 4, 36), (9, 18, 90), (5, 10, 30), (15, 60, 20, 180), (45, 360, 8, 24, 120, 40, 1080), (27, 54, 270), ...

It turns out that some rows are multiples of others; for example, the row (5, 10, 30) is five times the row (1, 2, 6). (End)

See also "observed scaling patterns" in the Formula section.

A303750 gives the positions of odd terms.

A282291 and A304531 are unitary divisor variants that satisfy the condition gcd(a(n+1), a(n)/a(n+1)) = 1, whenever a(n) > a(n+1).

The primes 2, 3, 5, 7, 11, 13, 19, 23 and 29 occur at positions 2, 4, 11, 42, 176, 1343, 8470, 57949, 302739, 1632898, thus after 7 and except for 13, a little earlier than they occur in variant A304531.

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

If a(n+1) > a(n), then A001222(a(n+1)) = 1 + A001222(a(n)).

From Antti Karttunen, May 23 2018: (Start)

For n >= 1, A006530(a(n)) = A000040(A070939(n)), thus the greatest prime dividing n, or equally, its index (A061395), is monotonic and follows the length of binary representation of n. This follows by induction on the size of the binary representation of n, and the fact that the "least possible unused divisor" part of a greedy rule can find all the unused divisors of A002110(k) before the next larger prime A000040(1+k) is needed as a factor.

For n >= 1, a((2^k)+1) = A000040(k+1), that is, after the first term with the next larger prime factor, which always occurs at 2^k, the next term is that prime itself, which is prime(k+1).

(A) For r in range 1 .. (2^(k-1)), a((2^k)+r) = A000040(k+1) * a(r-1), and prime A000040(k) is not present in the factorization. Because we cannot divide prime(k+1) out, as that would give a term already encountered, and because every term in this range has it as a largest prime factor, the relative magnitude-wise order of the terms in this range follows the relative magnitude-wise order of terms in a(0) .. a((2^(k-1))-1).

(B) For r in range (2^(k-1))+1 .. (2^k)-1, a((2^k)+r) = A000040(k+1) * a(r-1), and prime A000040(k) is present in the factorization.

Now it might be case that prime(k) > a product m of some subset of primes prime(k-1) .. prime(1). Even though the algorithm in those cases "would like" to divide by prime(k) instead of dividing by that product m, because then the divisor would be smaller, it cannot, because dividing by prime(k) (or by any other divisor containing it) would give an already used term.

(End)

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

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.