A302781 Divisor-or-multiple permutation of natural numbers constructed from two-dimensional Hilbert curve (A163357) and Fermi-Dirac primes (A050376).

1, 2, 6, 3, 15, 5, 10, 30, 120, 40, 20, 60, 12, 24, 8, 4, 28, 84, 168, 56, 14, 7, 21, 42, 210, 105, 35, 70, 280, 840, 420, 140, 1260, 3780, 7560, 2520, 630, 315, 945, 1890, 378, 189, 63, 126, 504, 1512, 756, 252, 36, 72, 216, 108, 540, 180, 360, 1080, 270, 90, 45, 135, 27, 54, 18, 9, 117, 351, 702, 234, 936, 468

Offset

0,2

Comments

Note that the starting offset is 0, to align with A052330 and A207901.

Shares with A064736, A207901, A298480, A302350, A302783, A303771, etc. the property that a(n) is either a divisor or a multiple of a(n+1). Permutations satisfying such property are called "divisor-or-multiple permutations" in the OEIS, although Mazet & Saias call them "chain permutations" in their paper. [Edited by Antti Karttunen, Aug 26 2018]

One way to construct such permutations is by composing A052330 from the right with any such permutation like A003188 or A302846 where the binary expansions of a(n) and a(n+1) always differ by just a single bit-position.

Further permutations satisfying the same condition could be constructed from higher-dimensional versions (i.e., greater than 2) of Hilbert's space-filling curves, where the coordinates of each dimension would be Gray coded separately and then interleaved together. Permutation A207901 is essentially a one-dimensional variant of the same idea, while this is constructed from the 2-dimensional curve A163357, which is a Hamiltonian path on N X N grid.

See Peter Munn's A300012 for another idea for constructing such a permutation. - Antti Karttunen, Aug 26 2018

Links

Antti Karttunen, Table of n, a(n) for n = 0..16383

Pierre Mazet and Eric Saias, Etude du graphe divisoriel 4, arXiv:1803.10073 [math.NT], 2018.

Various, Discussion on SeqFan-list, April 2018.

Index entries for sequences that are permutations of the natural numbers

Formula

a(n) = A052330(A302846(n)), where A302846(n) = A000695(A003188(A059253(n))) + 2*A000695(A003188(A059252(n))).

a(n) = A207901(A302844(n)) = A052330(A064706(A163356(n))).

Prog

(PARI)
up_to_e = 14;
v050376 = vector(up_to_e);
A050376(n) = v050376[n];
ispow2(n) = (n && !bitand(n, n-1));
i = 0; for(n=1, oo, if(ispow2(isprimepower(n)), i++; v050376[i] = n); if(i == up_to_e, break));
A052330(n) = { my(p=1, i=1); while(n>0, if(n%2, p *= A050376(i)); i++; n >>= 1); (p); };
A064706(n) = bitxor(n, n>>2);
A057300(n) = { my(t=1, s=0); while(n>0, if(1==(n%4), n++, if(2==(n%4), n--)); s += (n%4)*t; n >>= 2; t <<= 2); (s); };
A163356(n) = if(!n, n, my(i = (#binary(n)-1)\2, f = 4^i, d = (n\f)%4, r = (n%f)); (((((2+(i%2))^d)%5)-1)*f) + if(3==d, f-1-A163356(r), A057300(A163356(r))));
A302781(n) = A052330(A064706(A163356(n)));

Crossrefs

Cf. A302782 (inverse).

Cf. A003188, A050376, A052330, A059252, A059253, A064706, A163356, A163357, A207901, A298480, A300012, A302844, A302846, A302783, A303771.

Sequence in context: A072647 A100113 A300012 * A303760 A330919 A303770

Adjacent sequences: A302778 A302779 A302780 * A302782 A302783 A302784

Keyword

nonn

Author

Antti Karttunen, Apr 14 2018

Extensions

Name edited by Antti Karttunen, Aug 26 2018

Status

approved