A209268 Inverse permutation A054582.

1, 2, 3, 4, 6, 5, 10, 7, 15, 9, 21, 8, 28, 14, 36, 11, 45, 20, 55, 13, 66, 27, 78, 12, 91, 35, 105, 19, 120, 44, 136, 16, 153, 54, 171, 26, 190, 65, 210, 18, 231, 77, 253, 34, 276, 90, 300, 17, 325, 104, 351, 43, 378, 119, 406, 25, 435, 135, 465, 53, 496, 152

Offset: 1

Author

Boris Putievskiy, Jan 15 2013

Keywords

• nonn

Comments

Permutation of the natural numbers.

a(n) is a pairing function: a function that reversibly maps Z^{+} x Z^{+} onto Z^{+}, where Z^{+} is the set of integer positive numbers.

Examples

			The start of the sequence for n = 1..32 as table, distributed by exponent of highest power of 2 dividing n:
   |   Exponent of highest power of 2 dividing n
n  |--------------------------------------------------
   |    0      1      2       3      4         5    ...
------------------------------------------------------
1  |....1
2  |...........2
3  |....3
4  |..................4
5  |....6
6  |...........5
7  |...10
8  |..........................7
9  |...15
10 |...........9
11 |...21
12 |..................8
13 |...28
14 |..........14
15 |...36
16 |................................11
17 |...45
18 |..........20
19 |...55
20 |.................13
21 |...66
22 |..........27
23 |...78
24 |................................12
25 |...91
26 |..........35
27 |..105
28 |.................19
29 |..120
30 |..........44
31 |..136
32 |.........................................16
. . .
Let r_c be number row inside the column number c.
r_c = (n+2^c)/2^(c+1).
The column number 0 contains numbers r_0*(r_0+1)/2,     A000217,
The column number 1 contains numbers r_1*(r_1+3)/2,     A000096,
The column number 2 contains numbers r_2*(r_2+5)/2 + 1, A034856,
The column number 3 contains numbers r_3*(r_3+7)/2 + 3, A055998,
The column number 4 contains numbers r_4*(r_4+9)/2 + 6, A046691.
		

Links

• Boris Putievskiy, Table of n, a(n) for n = 1..10000
• Boris Putievskiy, Transformations [of] Integer Sequences And Pairing Functions, arXiv:1212.2732 [math.CO], 2012.
• R. J. Mathar, oeisPy
• Eric W. Weisstein, MathWorld: Pairing functions
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A054582, A003602, A007814, A000217, A000096, A034856, A055998, A046691, A014132.

Programs

Mathematica

a[n_] := (v = IntegerExponent[n, 2]; (1/2)*(((1/2)*(n/2^v + 1) + v)^2 + (1/2)*(n/2^v + 1) - v)); Table[a[n], {n, 1, 55}] (* Jean-François Alcover, Jan 15 2013, from 1st formula *)

Python

f = open("result.csv", "w")
def A007814(n):
### author        Richard J. Mathar 2010-09-06 (Start)
### http://oeis.org/wiki/User:R._J._Mathar/oeisPy/oeisPy/oeis_bulk.py
        a = 0
        nshft = n
        while (nshft %2 == 0):
                a += 1
                nshft >>= 1
        return a
###(End)
for  n in range(1,10001):
     x = A007814(n)
     y = (n+2**x)/2**(x+1)
     m = ((x+y)**2-x+y)/2
     f.write('%d;%d;%d;%d;\n' % (n, x, y, m))
f.close()

Formula

a(n) = (((A003602)+A007814(n))^2 - A007814(n) + A003602(n))/2.

a(n) = ((x+y)^2-x+y)/2, where x = max {k: 2^k | n}, y = (n+2^x)/2^(x+1).