login
The a(n)-th composition in standard order (A066099) is the first differences plus one of the prime indices of n (A112798).
1

%I #12 Jul 15 2023 10:36:27

%S 0,0,0,1,0,2,0,3,1,4,0,6,0,8,2,7,0,5,0,12,4,16,0,14,1,32,3,24,0,10,0,

%T 15,8,64,2,13,0,128,16,28,0,20,0,48,6,256,0,30,1,9,32,96,0,11,4,56,64,

%U 512,0,26,0,1024,12,31,8,40,0,192,128,18,0,29,0

%N The a(n)-th composition in standard order (A066099) is the first differences plus one of the prime indices of n (A112798).

%C The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

%C A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

%H Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vTCPiJVFUXN8IqfLlCXkgP15yrGWeRhFS4ozST5oA4Bl2PYS-XTA3sGsAEXvwW-B0ealpD8qnoxFqN3/pub">Statistics, classes, and transformations of standard compositions</a>

%e The prime indices of 36 are {1,1,2,2}, with first differences plus one (1,2,1), which is the 13th composition in standard order, so a(36) = 13.

%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 Table[stcinv[Differences[primeMS[n]]+1],{n,100}]

%Y See link for sequences related to standard compositions.

%Y Prepend 1 to indices: A253566 (cf. A358169), inverse A253565 (cf. A242628).

%Y Taking Heinz number instead of standard composition number gives A325352.

%Y These compositions minus one are listed by A355536, sums A243055.

%Y A001222 counts prime indices, distinct A001221.

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

%Y A112798 lists prime indices, sum A056239.

%Y A355534 = augmented diffs. of rev. prime indices, Heinz numbers A325351.

%Y Cf. A000720, A005940, A055932, A057335, A066312, A286470, A287352, A325390.

%K nonn

%O 1,6

%A _Gus Wiseman_, Dec 21 2022