cp's OEIS Frontend

A pseudo-logarithmic function in the sense that a(b*c) = a(b)+a(c) and so a(b^c) = c*a(b) and f(n) = k^a(n) is a multiplicative function. [Cf. A248692 for example.] Essentially a function from the positive integers onto the partitions of the nonnegative integers (1->0, 2->1, 3->2, 4->1+1, 5->3, 6->1+2, etc.) so each value a(n) appears A000041(a(n)) times, first with the a(n)-th prime and last with the a(n)-th power of 2. Produces triangular numbers from primorials. - Henry Bottomley, Nov 22 2001

Michael Nyvang writes (May 08 2006) that the Danish composer Karl Aage Rasmussen discovered this sequence in the 1990's: it has excellent musical properties.

All A000041(a(n)) different n's with the same value a(n) are listed in row a(n) of triangle A215366. - Alois P. Heinz, Aug 09 2012

a(n) is the sum of the parts of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} (p_j-th prime) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(33) = 7 because the partition with Heinz number 33 = 3 * 11 is [2,5]. - Emeric Deutsch, May 19 2015

From Antti Karttunen, May 12 2014: (Start)

a(A003961(n)) = n for all n. [This is a left inverse function for the injection A003961.]

Bisections are A064216 (the terms at odd indices) and A064989 itself (the terms at even indices), i.e., a(2n) = a(n) for all n.

(End)

From Antti Karttunen, Dec 18-21 2014: (Start)

When n represents an unordered integer partition via the indices of primes present in its prime factorization (for n >= 2, n corresponds to the partition given as the n-th row of A112798) this operation subtracts one from each part. If n is of the form 2^k (a partition having just k 1's as its parts) the result is an empty partition (which is encoded by 1, having an "empty" factorization).

For all odd numbers n >= 3, a(n) tells which number is located immediately above n in square array A246278. Cf. also A246277.

(End)

Alternatively, if numbers are represented as the multiset of indices of prime factors with multiplicity, this operation subtracts 1 from each element and discards the 0's. - M. F. Hasler, Dec 29 2014

a(n) is the Matula number of the rooted tree obtained from the rooted tree T having Matula number n, by contracting its edges that emanate from the root. Example: a(49) = 16. Indeed, the rooted tree with Matula number 49 is the tree obtained by merging two copies of the tree Y at their roots. Contracting the two edges that emanate from the root, we obtain the star tree with 4 edges having Matula number 16. - Emeric Deutsch, May 01 2015

The Matula (or Matula-Goebel) number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T. - Emeric Deutsch, May 01 2015

a(n) is the product of the parts of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} (p_j-th prime) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(75) = 18; indeed, the partition having Heinz number 75 = 3*5*5 is [2,3,3] and 2*3*3 = 18. - Emeric Deutsch, Jun 03 2015

Let T be the free-commutative-monoid monad on the category Set. Then for each set N we have a canonical function m from TTN to TN. If we let N = {1, 2, 3, ...} and enumerate the primes in the usual way (A000040) then unique prime factorization gives a canonical bijection f from N to TN. Then the sequence is given by a(n) = f^-1(m(T(f)(f(n)))). - Oscar Cunningham, Jul 18 2019

Factor n; replace each prime(i) with i, take the conjugate partition, replace parts i with prime(i) and multiply out.

From Antti Karttunen, May 12-19 2014: (Start)

For all n >= 1, A001222(a(n)) = A061395(n), and vice versa, A061395(a(n)) = A001222(n).

Because the partition conjugation doesn't change the partition's total sum, this permutation preserves A056239, i.e., A056239(a(n)) = A056239(n) for all n.

(Similarly, for all n, A001221(a(n)) = A001221(n), because the number of steps in the Ferrers/Young-diagram stays invariant under the conjugation. - Note added Apr 29 2022).

Because this permutation commutes with A241909, in other words, as a(A241909(n)) = A241909(a(n)) for all n, from which follows, because both permutations are self-inverse, that a(n) = A241909(a(A241909(n))), it means that this is also induced when partitions are conjugated in the partition enumeration system A241918. (Not only in A112798.)

(End)

From Antti Karttunen, Jul 31 2014: (Start)

Rows in arrays A243060 and A243070 converge towards this sequence, and also, assuming no surprises at the rate of that convergence, this sequence occurs also as the central diagonal of both.

Each even number is mapped to a unique term of A102750 and vice versa.

Conversely, each odd number (larger than 1) is mapped to a unique term of A070003, and vice versa. The permutation pair A243287-A243288 has the same property. This is also used to induce the permutations A244981-A244984.

Taking the odd bisection and dividing out the largest prime factor results in the permutation A243505.

Shares with A245613 the property that each term of A028260 is mapped to a unique term of A244990 and each term of A026424 is mapped to a unique term of A244991.

Conversely, with A245614 (the inverse of above), shares the property that each term of A244990 is mapped to a unique term of A028260 and each term of A244991 is mapped to a unique term of A026424.

(End)

The Maple program follows the steps described in the first comment. The subprogram C yields the conjugate partition of a given partition. - Emeric Deutsch, May 09 2015

The Heinz number of the partition that is conjugate to the partition with Heinz number n. The Heinz number of a partition p = [p_1, p_2, ..., p_r] is defined as Product(p_j-th prime, j=1...r). Example: a(3) = 4. Indeed, the partition with Heinz number 3 is [2]; its conjugate is [1,1] having Heinz number 4. - Emeric Deutsch, May 19 2015

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

From Antti Karttunen, Dec 20 2014: (Start)

Permutation of natural numbers obtained by replacing each prime divisor of n with the next prime and mapping the generated odd numbers back to all natural numbers by adding one and then halving.

Note: there is a 7-cycle almost right in the beginning: (6 8 14 17 10 11 7). (See also comments at A249821. This 7-cycle is endlessly copied in permutations like A250249/A250250.)

The only 3-cycle in range 1 .. 402653184 is (2821 3460 5639).

For 1- and 2-cycles, see A245449.

(End)

The first 5-cycle is (1410, 2783, 2451, 2703, 2803). - Robert Israel, Jan 15 2015

From Michel Marcus, Aug 09 2020: (Start)

(5194, 5356, 6149, 8186, 10709), (46048, 51339, 87915, 102673, 137205) and (175811, 200924, 226175, 246397, 267838) are other 5-cycles.

(10242, 20479, 21413, 29245, 30275, 40354, 48241) is another 7-cycle. (End)

From Antti Karttunen, Feb 10 2021: (Start)

Somewhat artificially, also this permutation can be represented as a binary tree. Each child to the left is obtained by multiplying the parent by 3 and subtracting one, while each child to the right is obtained by applying A253888 to the parent:

1

|

................../ \..................

2 3

5......../ \........4 8......../ \........6

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

14 13 11 7 23 9 17 18

41 10 38 12 32 28 20 15 68 25 26 63 50 16 53 19

etc.

Each node's (> 1) parent can be obtained with A253889. Sequences A292243, A292244, A292245 and A292246 are constructed from the residues (mod 3) of the vertices encountered on the path from n to the root (1).

(End)

a((A003961(n) + 1) / 2) = n and A003961(a(n)) = 2*n - 1 for all n. If the sequence is indexed by odd numbers only, it becomes multiplicative. In this variant sequence, denoted b, even indices don't exist, and we get b(1) = a(1) = 1, b(3) = a(2) = 2, b(5) = 3, b(7) = 5, b(9) = 4 = b(3) * b(3), ... , b(15) = 6 = b(3) * b(5), and so on. This property can also be stated as: a(x) * a(y) = a(((2x - 1) * (2y - 1) + 1) / 2) for x, y > 0. - Reinhard Zumkeller [re-expressed by Peter Munn, May 23 2020]

Not multiplicative in usual sense - but letting m=2n-1=product_j (p_j)^(e_j) then a(n)=a((m+1)/2)=product_j (p_(j-1))^(e_j). - Henry Bottomley, Apr 15 2005

From Antti Karttunen, Jul 25 2016: (Start)

Several permutations that use prime shift operation A064989 in their definition yield a permutation obtained from their odd bisection when composed with this permutation from the right. For example, we have:

A243505(n) = A122111(a(n)).

A243065(n) = A241909(a(n)).

A244153(n) = A156552(a(n)).

A245611(n) = A243071(a(n)).

(End)

For other numbers than the powers of 2 (that are fixed), this permutation reverses the sequence of exponents in the prime factorization of n from the exponent of 2 to that of the largest prime factor, except that the exponents of 2 and the greatest prime factor present are adjusted by one. Note that some of the exponents might be zeros.

Self-inverse permutation of natural numbers, composition of A122111 & A241909 in either order: a(n) = A122111(A241909(n)) = A241909(A122111(n)).

This permutation preserves both bigomega and the (index of) largest prime factor: for all n it holds that A001222(a(n)) = A001222(n) and A006530(a(n)) = A006530(n) [equally: A061395(a(n)) = A061395(n)].

From the above it follows, that this fixes both primes (A000040) and powers of two (A000079), among other numbers.

Even positions from n=4 onward contain only terms of A070003, and the odd positions only the terms of A102750, apart from 1 which is at a(1), and 2 which is at a(2).

Let's define "property S" for sequences as follows: If s is any sequence of positive natural numbers, normalized to begin with offset 1, then it satisfies the S-property if LCM-transform(s) is equal to the sequence obtained by applying A014963 to sequence s, or in other words, when for all n >= 1, lcm {s(1)..s(n)} / lcm {s(1)..s(n-1)} = A014963(s(n)). This holds if and only if, for all n >= 1, when, either (case A): s(n) is of the form p^k, p prime, then gcd(s(n), lcm {s(1)..s(n-1)}) must be equal to p^(k-1), or (case B): when s(n) is not a prime power, then gcd(s(n), lcm {s(1)..s(n-1)}) must be equal to s(n). Together the cases (A) and (B) reduce to the condition that each prime power should appear in s before any of its multiples do.

Clearly the Doudna-sequence satisfies the property by the way of its construction, as do many of its variants like A356867 (see A369060).

Also, for any base-2 related permutation b that keeps all the numbers of range [2^k, 2^(1+k)[ in the same range, i.e., if for all n >= 1, A000523(b(n)) = A000523(n), then the above property is automatically satisfied.

Furthermore, because in Doudna-sequence no multiple of any term is located on the same row as the term itself (see the tree-illustration in A005940), it follows that any composition of A005940 with any such base-2 related permutation as mentioned above also automatically satisfies the S-property, for example, the permutations A163511, A243353, A253563, A253565, A366260, A366263 and A366275.

Note: Like A005940 itself, also this sequence might be more logical with the starting offset 0 instead of 1, to better align with the underlying mapping from the binary expansion of n to the prime factorization. - Antti Karttunen, Jan 24 2024