A382256 Smallest binary number whose run lengths of bits correspond to a partition with Heinz number n.

0, 1, 3, 2, 7, 4, 15, 5, 12, 8, 31, 11, 63, 16, 24, 10, 127, 19, 255, 23, 48, 32, 511, 22, 56, 64, 51, 47, 1023, 39, 2047, 21, 96, 128, 112, 44, 4095, 256, 192, 46, 8191, 79, 16383, 95, 103, 512, 32767, 45, 240, 71, 384, 191, 65535, 76, 224, 94, 768, 1024, 131071, 92, 262143, 2048, 207, 42, 448, 159

Offset: 1

Author

M. F. Hasler, Mar 19 2025

Keywords

• nonn

Comments

This is another way of assigning a canonical representative (natural number and composition) to any partition, and therefore to define an order on the set of all partitions.

Since the binary number corresponding to a partition of n is in the interval [2^(n-1), 2^n-1], it does respect the primary order criterion of all classical partition orderings (Abramowitz and Stegun or Hindenburg order: A036036, "Maple order": A080576, "Mathematica order": A080577, ...) which is the sum of the partitions. This is not the case for the Heinz number, cf. Examples.

Examples

			Heinz number 1 corresponds to the empty product, empty sum and partition which is that of a(1) = 0.
Heinz number 2 = prime(1) corresponds to the partition (1), and run lengths of the binary number a(2) = 1 which has just one bit 1.
Heinz number 3 = prime(2) corresponds to the partition (2), which equals the run lengths of the binary number 11[2] = 3 = a(3) which has two consecutive bits 1.
Heinz number 4 = prime(1)^2 corresponds to the partition (1,1), which equals the run lengths of the binary number 10[2] = 2 = a(4) which has one bit 1, then one bit 0.
Heinz number 5 = prime(3) corresponds to the partition (3), which equals the run lengths of the binary number 111[2] = 7 = a(5) which has three consecutive bits 1.
Heinz number 6 = prime(1)*prime(2) corresponds to the partition (1,2), which equals the run lengths of the binary number 100[2] = 4 = a(6).
Heinz number 7 = prime(4) corresponds to the partition (4), which equals the run lengths of the binary number 1111[2] = 15 = a(7).
Heinz number 8 = prime(1)^3 corresponds to the partition (1,1,1), which equals the run lengths of the binary number 101[2] = 5 = a(8). Here, we have a partition with smaller sum than the previous one, but with a larger Heinz number. This shows that ordering the partitions by their Heinz number puts partitions with smaller sums behind partitions with larger sums. The binary numbers, however, do increase with increasing sum of the partition.
Similarly, Heinz number 14 = 2*7 = prime(1)*prime(4) corresponds to the partition (1,4) of 5, which equals the run lengths of the binary number 10000[2] = 16 = a(14), while the larger Heinz number 16 = 2^4 = prime(1)^4 corresponds to the partition (1,1,1,1) with smaller sum 4, and run lengths of the smaller binary number 1010[2] = 10 = a(16).
		

Crossrefs

Cf. A382255, A036036, A080576, A080577 (partitions in Abramowitz-Stegun, Maple and Mathematica order).

Programs

PARI

apply( {A382256(n)=if(n=factor(n)~, n[1,]=apply(primepi, n[1,]); my(i=1, b, L, R=2^n[1,1]-1); n=Vec(n); while(n[i][2]-- || n=n[^i], R<<=L=n[i=b*#n+!b][1]; b && R+=2^L-1; b=1-b); R)}, [1..66])