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

%I #17 Dec 28 2022 09:04:50

%S 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,

%T 96,11,56,512,26,1024,31,40,192,18,29,2048,384,80,60,4096,52,8192,112,

%U 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

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

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

%C 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

%H Antti Karttunen, <a href="/A253566/b253566.txt">Table of n, a(n) for n = 1..1024</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

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

%F As a composition of other permutations:

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

%F a(n) = A336120(n) + A336125(n). - _Antti Karttunen_, Jul 18 2020

%F 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

%e From _Gus Wiseman_, Dec 23 2022: (Start)

%e 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:

%e 1: () -> ()

%e 2: (1) -> (1)

%e 3: (2) -> (2)

%e 4: (1,1) -> (1,1)

%e 5: (3) -> (3)

%e 6: (2,1) -> (1,2)

%e 7: (4) -> (4)

%e 8: (1,1,1) -> (1,1,1)

%e 9: (2,2) -> (2,1)

%e 10: (3,1) -> (1,3)

%e 11: (5) -> (5)

%e 12: (2,1,1) -> (1,1,2)

%e 13: (6) -> (6)

%e 14: (4,1) -> (1,4)

%e 15: (3,2) -> (2,2)

%e 16: (1,1,1,1) -> (1,1,1,1)

%e (End)

%t primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];

%t stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;

%t stcinv/@Table[Differences[Prepend[primeMS[n],1]]+1,{n,100}] (* _Gus Wiseman_, Dec 23 2022 *)

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

%Y Inverse: A253565.

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

%Y Applying A000120 gives A001222.

%Y A reverse version is A156552, inverse essentially A005940.

%Y The inverse is A253565, triangular form A242628.

%Y The triangular form is A358169.

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

%Y A066099 lists standard compositions, lengths A000120, sums A070939.

%Y A112798 list prime indices, sum A056239.

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

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

%K nonn

%O 1,3

%A _Antti Karttunen_, Jan 03 2015