A386386: a 2-adic permutation with explicit inverse

[Tomasz Ordowski]

Hello Everyone!

I’d like to mention my recent OEIS permutation A386386. It gives a canonical ordering of the nonnegative integers based on distance from powers of 2 rather than size, and it has an explicit inverse via the decomposition n+1 = u·2^v (u odd).

The inverse position satisfies
P⁻¹(n) = n − n/(log 2 · log n) + O(n/(log n)²), reflecting a logarithmic block structure.

Question: do similar explicit, non-greedy permutations exist for other primes p, or is this phenomenon specific to p = 2?

Best, 

Tom Ordo

[Ruud H.G. van Tol]

Tangential:

The (k - 2^m) * 2^(m-1) - 1 representation of n, reminds me of
the (2*k + 1) * 2^m - 1 representation, where m is the number of
trailing 1-bits in binary, and k is the value before the rightmost 0-bit.

? my(t); [ [n>>((t=valuation(n+1,2))+1), t] |n<-[0..30]]
% [[0, 0], [0, 1], [1, 0], [0, 2], [2, 0], [1, 1], [3, 0], [0, 3], [4,
0], [2, 1], [5, 0], [1, 2], [6, 0], [3, 1], [7, 0], [0, 4], [8, 0], [4,
1], [9, 0], [2, 2], [10, 0], [5, 1], [11, 0], [1, 3], [12, 0], [6, 1],
[13, 0], [3, 2], [14, 0], [7, 1], [15, 0]]

Examples:
11 =  1.0.11 = [1, 2]
19 = 10.0.11 = [2, 2]
27 = 11.0.11 = [3, 2]

A permutation based on the sum of the coordinates is:
0, 1, 2, 3, 5, 4, 7, 11, 9, 6, 15, 23, 19, 13, 8, 31, 47, 39, 27, 17,
10, 63, 95, 79, 55, 35, 21, 12
which is A075300.

-- Ruud

[Tomasz Ordowski]

Thanks, Ruud — that’s a very nice connection. 

Indeed, your (2k+1)2^m−1 decomposition via trailing 1-bits is essentially the same 2-adic valuation structure seen from the "right edge", whereas my (k−2^m)2^(m−1)−1 view measures distance from powers of 2. Both expose the same 2-adic stratification of N, just with different coordinates.

Regarding my question: I believe analogous permutations do exist for odd primes p, via the decomposition n+1=up^v with u coprime to p, but the case p=2 is uniquely simple. Only for p=2 does the valuation induce a total, binary tree–like ordering compatible with a clean logarithmic inverse asymptotic. For p>2, the higher branching and lack of a linear "distance from powers" notion seem to obstruct an equally canonical, non-greedy permutation.

So the phenomenon is not exclusive to p=2, but its elegance and explicitness very likely are.

Maybe someone has a different opinion or sees other connections.

I invite you to discuss... 

Tom Ordo 

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/427bdbc4-8ed8-4917-9c4b-83bf8785f8b1%40isolution.nl.

[Tomasz Ordowski]

PS. For completeness, the inverse permutation admits a fully explicit formula.
Write n+1 = u * 2^v with u odd and v = v2(n+1). Then

P^(-1)(n) = (u − 1) * 2^v + (2^v − 1),

equivalently,

P^(-1)(n) = (u + 1) * 2^v − 1.

Thus the inverse is given directly by the 2-adic decomposition of n+1.

[Tomasz Ordowski]

A386386 Sequence Analysis