A253566 Permutation of natural numbers: a(n) = A243071(A122111(n)).

0, 1, 2, 3, 4, 6, 8, 7, 5, 12, 16, 14, 32, 24, 10, 15, 64, 13, 128, 28, 20, 48, 256, 30, 9, 96, 11, 56, 512, 26, 1024, 31, 40, 192, 18, 29, 2048, 384, 80, 60, 4096, 52, 8192, 112, 22, 768, 16384, 62, 17, 25, 160, 224, 32768, 27, 36, 120, 320, 1536, 65536, 58, 131072, 3072, 44, 63, 72, 104, 262144, 448, 640, 50, 524288, 61, 1048576, 6144, 21

Offset

1,3

Comments

Note the indexing: domain starts from one, while the range includes also zero. See also comments in A253564.

The a(n)-th composition in standard order (graded reverse-lexicographic, A066099) is one plus the first differences of the weakly increasing sequence of prime indices of n with 1 prepended. See formula for a simplification. The triangular form is A358169. The inverse is A253565. Not prepending 1 gives A358171. For Heinz numbers instead of standard compositions we have A325351 (without prepending A325352). - Gus Wiseman, Dec 23 2022

Links

Antti Karttunen, Table of n, a(n) for n = 1..1024

Index entries for sequences that are permutations of the natural numbers

Formula

a(n) = A243071(A122111(n)).

As a composition of other permutations:

a(n) = A054429(A253564(n)).

a(n) = A336120(n) + A336125(n). - Antti Karttunen, Jul 18 2020

If 2n = Product_{i=1..k} prime(x_i) then a(n) = Sum_{i=1..k-1} 2^(x_k-x_{k-i}+i-1). - Gus Wiseman, Dec 23 2022

Example

From Gus Wiseman, Dec 23 2022: (Start)
This represents the following bijection between partitions and compositions. The reversed prime indices of n together with the a(n)-th composition in standard order are:
   1:        () -> ()
   2:       (1) -> (1)
   3:       (2) -> (2)
   4:     (1,1) -> (1,1)
   5:       (3) -> (3)
   6:     (2,1) -> (1,2)
   7:       (4) -> (4)
   8:   (1,1,1) -> (1,1,1)
   9:     (2,2) -> (2,1)
  10:     (3,1) -> (1,3)
  11:       (5) -> (5)
  12:   (2,1,1) -> (1,1,2)
  13:       (6) -> (6)
  14:     (4,1) -> (1,4)
  15:     (3,2) -> (2,2)
  16: (1,1,1,1) -> (1,1,1,1)
(End)

Mathematica

primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
stcinv/@Table[Differences[Prepend[primeMS[n], 1]]+1, {n, 100}] (* Gus Wiseman, Dec 23 2022 *)

Prog

(Scheme) (define (A253566 n) (A243071 (A122111 n)))

Crossrefs

Inverse: A253565.

Cf. A122111, A243071, A253564, A054429, A336120, A336125.

Applying A000120 gives A001222.

A reverse version is A156552, inverse essentially A005940.

The inverse is A253565, triangular form A242628.

The triangular form is A358169.

A048793 gives partial sums of reversed standard comps, Heinz number A019565.

A066099 lists standard compositions, lengths A000120, sums A070939.

A112798 list prime indices, sum A056239.

A358134 gives partial sums of standard compositions, Heinz number A358170.

Cf. A029837, A241916, A243055, A287352, A325390, A355534, A358171, A359042.

Sequence in context: A342266 A082320 A285111 * A333220 A176798 A067118

Adjacent sequences: A253563 A253564 A253565 * A253567 A253568 A253569

Keyword

nonn

Author

Antti Karttunen, Jan 03 2015

Status

approved