cp's OEIS Frontend

This sequence is different from A058061 for n containing 6th, 8th, ..., k-th powers in its prime decomposition, where k runs through the integers missing from A064548.

For n > 1, n is a product of a(n) distinct members of A050376. - Matthew Vandermast, Jul 13 2004

For n > 1: a(n) = length of n-th row in A213925. - Reinhard Zumkeller, Mar 20 2013

Number of Fermi-Dirac factors of n. - Peter Munn, Dec 27 2019

Inverse of sequence A064358 considered as a permutation of the positive integers. - Howard A. Landman, Sep 25 2001

This sequence is not exactly a permutation because it has offset 0 but doesn't contain 0. A052331 is its exact inverse, which has offset 1 and contains 0. See also A064358.

Are there any other values of n besides 4 and 36 with a(n) = n? - Thomas Ordowski, Apr 01 2005

4 = 100 = 4^1 * 3^0 * 2^0, 36 = 100100 = 9^1 * 7^0 * 5^0 * 4^1 * 3^0 * 2^0. - Thomas Ordowski, May 26 2005

Ordering of positive integers by increasing "Fermi-Dirac representation", which is a representation of the "Fermi-Dirac factorization", term implying that each prime power with a power of two as exponent may appear at most once in the "Fermi-Dirac factorization" of n. (Cf. comment in A050376; see also the OEIS Wiki page.) - Daniel Forgues, Feb 11 2011

The subsequence consisting of the squarefree terms is A019565. - Peter Munn, Mar 28 2018

Let f(n) = A050376(n) be the n-th Fermi-Dirac prime. The FDH-number of a strict integer partition (y_1,...,y_k) is f(y_1)*...*f(y_k). A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. Then a(n) is the number whose binary indices are the parts of the strict integer partition with FDH-number n. - Gus Wiseman, Aug 19 2019

The set of indices of odd-valued terms has asymptotic density 0. In this sense (using the order they appear in this permutation) 100% of numbers are even. - Peter Munn, Aug 26 2019

Every positive integer, m, is the product of a unique subset, S(m), of the numbers listed in A050376 (primes, squares of primes etc.) The Fermi-Dirac factors of m are the members of S(m). So T(n,k) is the product of the members of (S(n) U S(k)).

Old name: Table a(i,j) = product prime(k)^(Ei(k) OR Ej(k)) where Ei and Ej are the vectors of exponents in the prime factorizations of i and j; OR is the bitwise operation on binary representation of the exponents.

Analogous to LCM, with OR replacing MAX.

A003418-analog seems to be A066616. - Antti Karttunen, Apr 12 2017

Considered as a binary operation, the result is the lowest common multiple of the squarefree parts of its operands multiplied by the square of the operation's result when applied to the square roots of the square parts of its operands. - Peter Munn, Mar 02 2022

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)

This sequence has connections with A113552 and A281978: each pair of consecutive terms contains a term that divides the other term.

The derived sequence A282304 gives some insights about the fractal nature of this sequence.

Conjectures:

- All prime numbers appear in this sequence, in increasing order,

- the derived sequence A282304 is unbounded,

- this sequence is a permutation of the natural numbers.

From Antti Karttunen, May 17 2018: (Start)

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: either remove some parts from the partition, but with the constraint that if any summand k is removed, then all copies of k present in partition must be removed in too. One may remove all copies of several distinct summands as well. If by such a removal of parts we can find any smaller partitions that have not yet occurred in the sequence, then we choose the one which has the smallest Heinz encoding value to be a(n+1). On the other hand, if all partitions obtained by such removals have already occurred in the sequence, one must then add one or more parts to the current partition, but with the constraint that one is allowed to use only summands that do not already occur in partition (but any number of such summands may be used, also of more than one kind, as long as such summands are not already present in the partition that corresponds to a(n)). Of all such valid new partitions not already encountered, one with the smallest Heinz encoding value is chosen to be a(n+1). Compare this to the rules given for similar A304531 and A303751.

Primes 2 .. 61 occur at: 2, 4, 8, 14, 34, 96, 193, 386, 770, 1538, 3074, 14647, 30533, 60824, 122349, 245225, 688293, 1535694.

Terms just before primes are: 1, 6, 20, 420, 1848, 6552, 556920, 1511640, 6953544, 11090902680, 26447537160, 444799488600, 411767273946600, 1361999444592600, 448097817270965400, 2159016755941924200, 768250528363503385200, 3827047701385526108400.

Primorials (A002110) occur at: 1, 2, 3, 10, 23, 56, 151, 343, 728, 1497, 3034, 6107, 20753, 51285, 112674, 235085, 655721, 1525973, 3151033, ...

Powers of 2: 2 .. 32 occur at: 2, 6, 26, 6531, 1210614, and immediately following terms are: 6, 20, 24, 48, 96.

Immediately preceding terms are: 1, 12, 840, 1163962800, 1479723952477818247200. After 1 these factor as: (2^2 * 3^1), (2^3 * 3^1 * 5^1 * 7^1), (2^4 * 3^2 * 5^2 * 7^1 * 11^1 * 13^1 * 17^1 * 19^1), (2^5 * 3^2 * 5^2 * 7^2 * 11^1 * 13^1 * 17^1 * 19^1 * 23^1 * 29^1 * 31^1 * 41^1 * 43^1 * 47^1 * 53^1).

Observed recurrences: From n>=4 and k>=2 onward, there is a following general pattern:

For n = x .. x+(y-1), a(n) = prime(1+k)*a(n-(x-1)),

where y is the k-th record in A282304, and x is the position of that record in A282304, starting from the k = 2nd record in that sequence:

For n = 8 .. 8+4, a(n) = 5*a(n-7).

For n = 14 .. 14+10, a(n) = 7*a(n-13).

For n = 34 .. 34+30, a(n) = 11*a(n-33).

For n = 96 .. 96+89, a(n) = 13*a(n-95).

For n = 193 .. 193+184, a(n) = 17*a(n-192).

For n = 386 .. 386+382, a(n) = 19*a(n-385).

For n = 770 .. 770+766, a(n) = 23*a(n-769).

For n = 1538 .. 1538+1534, a(n) = 29*a(n-1537).

For n = 3074 .. 3074+3070, a(n) = 31*a(n-3073).

For n = 14647 .. 14647+11104, a(n) = 37*a(n-14646).

For n = 30533 .. 30533+29454, a(n) = 41*a(n-30532).

For n = 60824 .. 60824+30061, a(n) = 43*a(n-60823).

For n = 122349 .. 122349+91330, a(n) = 47*a(n-122348).

For n = 245225 .. 245225+121950, a(n) = 53*a(n-245224).

For n = 688293 .. 688293+367237, a(n) = 59*a(n-688292).

For n = 1535694 .. 1535694+596154, a(n) = 61*a(n-1535693).

Note how this forces values like prime powers to gaps between. E.g. 49 = a(367278) occurs 103 steps after the subsection a(n) = 53*a(n-245224) has ended at 245225+121950 (= 367175), but before the next regular subsection a(n) = 59*a(n-688292) starts at 688293.

(End)

The greedy algorithm which constructs the sequence is easiest to grasp in terms of Heinz encodings of partitions (see A215366): Any term a(n) corresponds to a particular integer partition. The choices for constructing the next partition are: either remove some parts from the partition, but with the condition that if any summand k is removed, then all copies of k present in partition must be removed in toto. One may remove all copies of several distinct summands as well. If by such a removal of parts we can find any smaller partitions that have not yet 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 one adds to the current partition the least number of copies of the least positive integer that is not yet a part of the partition (see A257993), until a partition is found which is not yet in the sequence. This process also implies that one never removes the summand(s) that was/were just added in the previous step.

It has not yet been rigorously proved that all partitions can be reached this way, i.e., that this sequence is a permutation of natural numbers.

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

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) then (a(n+1) / a(n)) is a divisor of a(n+2). This follows because clearly (in case A) when a(n) < a(n+1) < a(n+2) then (a(n+1) / a(n)) is a divisor of a(n+2) because on ascending subsections each successive term is obtained by multiplying by some prime (or its power) not already present. But it is also true (in case B) when a(n) < a(n+1) > a(n+2), as:

In contrast to A303751, this permutation is specified with an additional constraint that gcd(a(n+1), a(n)/a(n+1)) = 1, whenever a(n) > a(n+1). From this then follows that also when a(n) < a(n+1) > a(n+2) then (a(n+1) / a(n)) is guaranteed to be a divisor of a(n+2). It also follows from this that also the squarefree version A304537(n) = A019565(A052331(a(1+n))) satisfies the divisor-or-multiple property.

Odd numbers occur at A304530.

Primes occur at : 2, 4, 11, 42, 237, 1798, 7192, 69611, 431203, 2401568, ...

Primorials (A002110) occur at: 1, 2, 3, 13, 54, 290, 2087, 11333, 118777, 934737, ...

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)

Note that this is not equal to the smallest Fermi-Dirac prime (A050376) dividing n, which is always A020639(n). - Antti Karttunen, Apr 15 2018

Because "Fermi-Dirac factorization" is fundamentally different from ordinary prime factorization (as no exponents larger than 1 are allowed) this pair of permutations mapping between them is not always very intuitive. For example, we have ("as expected") A302776(n) = A302023(A052126(A302024(n))), while on the other hand, we have A302792(n) = A300841(A302023(A032742(A302024(n)))), where an additional shift-operator A300841 is needed for "correction".

For n > 0, with prime factorization Product_{i=1..k} p_i ^ e_i (all p_i distinct and all e_i > 0):

- let S_n = A000961 \ { p_i ^ (e_i + j) with i=1..k and j > 0 },

- a(n) = Sum_{i=1..k} 2^#{ s in S_n with 1 < s < p_i ^ e_i }.

In an informal way, we encode the prime powers > 1 that are unitary divisors of n as 1's in binary, while discarding the 0's corresponding to their "proper" multiples.

a(A002110(n)) = 2^n-1 for any n >= 0.

a(A000961(n+1)) = 2^(n-1) for any n > 0.

A000120(a(n)) = A001221(n) for any n > 0 (each prime divisor p of n (alongside the p-adic valuation of n) is encoded as a single 1 bit in the base-2 representation of a(n)).

A000961(2+A007814(a(n))) = A034684(n) for any n > 1 (the least significant bit of a(n) encodes the smallest unitary divisor of n that is larger than 1).

This sequence establishes a bijection between the positive numbers and the nonnegative numbers; see A289272 for the inverse of this sequence.

The numbers 4, 36, 40 and 532 equal their image; are there other such numbers?

This sequence has connections with A034729 (which encodes the divisors of a number, and is not surjective) and A087207 (which encodes the prime divisors of a number, and is not injective).