login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #30 Mar 02 2023 11:48:55

%S 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,

%T 18,76,25,33,11,21,77,90,89,104,103,118,42,119,134,151,52,169,63,75,

%U 17,135,188,208,88,229,102,117,24,251,133,150,32,168,41,51,16,28,152

%N Inverse of A066884 considered as a permutation of the positive integers.

%H Ivan Neretin, <a href="/A067587/b067587.txt">Table of n, a(n) for n = 1..10000</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F 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.

%t 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

%o (Perl)

%o 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

%o (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

%o (Python)

%o from math import comb

%o def A067587(n):

%o c, k = 0, 0

%o for i,j in enumerate(bin(n)[-1:1:-1]):

%o if j == '1':

%o k += 1

%o c += comb(i,k)

%o return comb(n.bit_count()+c,2)+c+1 # _Chai Wah Wu_, Mar 02 2023

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

%K nonn,look,easy

%O 1,2

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

%E Edited by _Dean Hickerson_, Feb 16 2002

%E Offset changed to 1 by _Ivan Neretin_, Mar 02 2016