A067587 Inverse of A066884 considered as a permutation of the positive integers.

1, 3, 2, 6, 5, 9, 4, 10, 14, 20, 8, 27, 13, 19, 7, 15, 35, 44, 26, 54, 34, 43, 12, 65, 53, 64, 18, 76, 25, 33, 11, 21, 77, 90, 89, 104, 103, 118, 42, 119, 134, 151, 52, 169, 63, 75, 17, 135, 188, 208, 88, 229, 102, 117, 24, 251, 133, 150, 32, 168, 41, 51, 16, 28, 152

Offset: 1

Author

Jared Ricks (jaredricks(AT)yahoo.com), Jan 31 2002

Keywords

• nonn
• look
• easy

Links

• Ivan Neretin, Table of n, a(n) for n = 1..10000
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A066884, A000120, A068076, A263017, A356419.

Programs

Mathematica

w[n_] := Plus@@IntegerDigits[n, 2]; p[n_] := Plus@@MapThread[Binomial, {Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]]-1, Range[w[n]]}]; a[n_] := Binomial[w[n]+p[n], 2]+p[n]+1

PARI

a(n)=my(w=hammingweight(n), p=sum(i=1, n-1, hammingweight(i)==w)); binomial(w+p, 2) + p + 1 \\ Jianing Song, Aug 06 2022

Perl

foreach(1..10_000){$i=eval join "+", split //, sprintf "%b", $; $j=$r[$i]++; print "$ ",$j+1+($i+$j)*($i+$j-1)/2,"\n"} # Ivan Neretin, Mar 02 2016

Python

from math import comb
def A067587(n):
    c, k = 0, 0
    for i,j in enumerate(bin(n)[-1:1:-1]):
        if j == '1':
            k += 1
            c += comb(i,k)
    return comb(n.bit_count()+c,2)+c+1 # Chai Wah Wu, Mar 02 2023

Formula

Let w(n) = A000120(n) be the 'weight' of n; i.e. the number of 1's in the binary expansion of n. Let p(n) = A068076(n) be the number of positive integers < n with the same weight as n. Then a(n) = binomial(w(n)+p(n),2) + p(n) + 1.

Extensions

Edited by Dean Hickerson, Feb 16 2002

Offset changed to 1 by Ivan Neretin, Mar 02 2016