A227351 Permutation of nonnegative integers: map each number by lengths of runs of zeros in its Zeckendorf expansion shifted once left to the number which has the same lengths of runs (in the same order, but alternatively of runs of 0's and 1's) in its binary representation.

0, 1, 3, 7, 2, 15, 6, 4, 31, 14, 12, 8, 5, 63, 30, 28, 24, 13, 16, 9, 11, 127, 62, 60, 56, 29, 48, 25, 27, 32, 17, 19, 23, 10, 255, 126, 124, 120, 61, 112, 57, 59, 96, 49, 51, 55, 26, 64, 33, 35, 39, 18, 47, 22, 20, 511, 254, 252, 248, 125, 240, 121, 123, 224

Offset: 0

Author

Antti Karttunen, Jul 08 2013

Keywords

• nonn
• base

Comments

This permutation is based on the fact that by appending one extra zero to the right of Fibonacci number representation of n (aka "Zeckendorf expansion") and then counting the lengths of blocks of consecutive (nonleading) zeros we get bijective correspondence with compositions, and thus also with the binary representation of a unique n. See the chart below:

n A014417(n) A014417(A022342(n+1)) Runs of Binary number In dec.

[shifted once left] zeros with same runs = a(n)

0: ......0 ......0 [] .....0 0

1: ......1 .....10 [1] .....1 1

2: .....10 ....100 [2] ....11 3

3: ....100 ...1000 [3] ...111 7

4: ....101 ...1010 [1,1] ....10 2

5: ...1000 ..10000 [4] ..1111 15

6: ...1001 ..10010 [2,1] ...110 6

7: ...1010 ..10100 [1,2] ...100 4

8: ..10000 .100000 [5] .11111 31

9: ..10001 .100010 [3,1] ..1110 14

10: ..10010 .100100 [2,2] ..1100 12

11: ..10100 .101000 [1,3] ..1000 8

12: ..10101 .101010 [1,1,1] ...101 5

13: .100000 1000000 [6] 111111 63

Are there any other fixed points after 0, 1, 6, 803, 407483 ?

Links

• Antti Karttunen, Table of n, a(n) for n = 0..10946
• OEIS Wiki, Run-length encoding
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Inverse permutation: A227352. Cf. also A003714, A014417, A006068, A048679.

Could be further composed with A075157 or A075159, also A129594.

Programs

Scheme

(define (A227351 n) (A006068 (A048679 n)))

Scheme

(define (A227351v2 n) (A006068 (A106151 (* 2 (A003714 n)))))

Formula

a(n) = A006068(A048679(n)) = A006068(A106151(2*A003714(n))).

This permutation effects following correspondences:

a(A000045(n)) = A000225(n-1).

a(A027941(n)) = A000975(n).

For n >=3, a(A000204(n)) = A000079(n-2).