login
A067587
Inverse of A066884 considered as a permutation of the positive integers.
4
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,2
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.
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
PROG
(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
(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
(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
CROSSREFS
KEYWORD
nonn,look,easy
AUTHOR
Jared Ricks (jaredricks(AT)yahoo.com), Jan 31 2002
EXTENSIONS
Edited by Dean Hickerson, Feb 16 2002
Offset changed to 1 by Ivan Neretin, Mar 02 2016
STATUS
approved