cp's OEIS Frontend

This is a self-inverse permutation of the nonnegative integers.

The function "substitute x+1 for x" on polynomials over GF(2) is completely multiplicative.

What is the density of fixed points in this sequence? Do we get a different answer if we look only at irreducible polynomials?

From Antti Karttunen, Dec 27 2013: (Start)

As what comes to the above question, the number of fixed points in range [2^(n-1),(2^n)-1] of the sequence is given by A131575(n). In range [0,0] there is one fixed point: 0, in range [1,1] there is also one: 1, in range [2,3] there are no fixed points, in range [4,7] there are two fixed points: 6 and 7, and so on. (Cf. also the C-code given in A118666.)

Similarly, the number of cycles in such ranges begins as 1, 1, 1, 3, 4, 10, 16, 36, 64, 136, ... which is A051437 shifted two steps right (prepended with 1's): Because the sequence is a self-inverse permutation, the number of its cycles in range [2^(n-1),(2^n)-1] is computed as: cycles(n) = (A011782(n)-number_of_fixedpoints(n))/2 + number_of_fixedpoints(n), which matches with the identity: A051437(n-2) = (A011782(n)-A131575(n))/2 + A131575(n), for n>=2.

In OEIS terms, the above comment about multiplicativeness can be rephrased as: a(A048720(x,y)) = A048720(a(x),a(y)) for all integers x, y >= 0. Here A048720(x,y) gives the product of carryless binary multiplication of x and y.

The permutation conjugates between Gray code and its inverse: A003188(n) = a(A006068(a(n))) and A006068(n) = a(A003188(a(n))) [cf. the identity 1.19-9d: gB = Bg^{-1} given on page 53 of fxtbook].

Because of the multiplicativity, the subset of irreducible (and respectively: composite) polynomials over GF(2) is closed under this permutation. Cf. the following mappings: a(A014580(n)) = A234750(n) and a(A091242(n)) = A234745(n).

(End)

a(0)=0; thereafter if n occurs as a term of A005187, a(n)=its position in A005187, otherwise zero. This works as an "inverse" function for A005187 in a sense that a(A005187(n)) = n for all n.

a(n)*A234017(n) = 0 for all n.

a(0)=0; thereafter if n occurs as a term of A055938, a(n)=its position in A055938, otherwise zero. This works as an "inverse" function for A055938 in a sense that a(A055938(n)) = n for all n.

a(n)*A213714(n) = 0 for all n.

For all n, a(A000079(n)) = A000225(n+1), i.e. a(2^n) = (2^(n+1))-1.

For n>=1, a(A000225(n)) = A000325(n).

This permutation is obtained by "entangling" even and odd numbers with complementary pair A005187 & A055938, meaning that it can be viewed as a binary tree. Each child to the left is obtained by applying A005187(n+1) to the parent node containing n, and each child to the right is obtained as A055938(n):

0

|

...................1...................

3 2

7......../ \........6 4......../ \........5

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

15 14 11 13 8 9 10 12

31 30 26 29 22 24 25 28 16 17 18 20 19 21 23 27

etc.

For n >= 1, A256991(n) gives the contents of the immediate parent node of the node containing n, while A070939(n) gives the total distance to 0 from the node containing n, with A256478(n) telling how many of the terms encountered on that journey are terms of A005187 (including the penultimate 1 but not the final 0 in the count), while A256479(n) tells how many of them are terms of A055938.

Permutation A233278 gives the mirror image of the same tree.

This permutation is obtained by "entangling" even and odd numbers with complementary pair A055938 & A005187, meaning that it can be viewed as a binary tree. Each child to the left is obtained by applying A055938(n) to the parent node containing n, and each child to the right is obtained as A005187(n+1):

0

|

...................1...................

2 3

5......../ \........4 6......../ \........7

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

12 10 9 8 13 11 14 15

27 23 21 19 20 18 17 16 28 25 24 22 29 26 30 31

etc.

For n >= 1, A256991(n) gives the contents of the immediate parent node of the node containing n, while A070939(n) gives the total distance to zero at the root from the node containing n, with A256478(n) telling how many of the terms encountered on that journey are terms of A005187 (including the penultimate 1 but not the final 0 in the count), while A256479(n) tells how many of them are terms of A055938.

Permutation A233276 gives the mirror image of the same tree.

This permutation transforms the enumeration system of positive irreducible fractions A071766/A229742 (HCS) into the enumeration system A007305/A047679 (Stern-Brocot), and the enumeration system A245325/A245326 into A162909/A162910 (Bird). - Yosu Yurramendi, Jun 09 2015

This sequence is one instance of Clark Kimberling's generic dispersion arrays. Paraphrasing his explanation in A191450, mutatis mutandis, we have the following definition:

Suppose that s is an increasing sequence of positive integers, that the complement t of s is infinite, and that t(1)=1. The dispersion of s is the array D whose n-th row is (t(n), s(t(n)), s(s(t(n))), s(s(s(t(n)))), ...). Every positive integer occurs exactly once in D, so that, as a sequence, D is a permutation of the positive integers. The sequence u given by u(n) = {index of the row of D that contains n} is a fractal sequence. In this case s(n) = A055938(n), t(n) = A005187(n) [from term A005187(1) onward] and u(n) = A254112(n).

For other examples of such sequences, see the Crossrefs section. For a general introduction, please follow the Kimberling references.

The main diagonal: 1, 6, 20, 60, 154, 377, 887, 2040, 4598, 10229, 22515, 49139, ...