A243109 -id:A243109 - cp's OEIS frontend

A037870 a(n) = (1/2)Sum{|d(i)-e(i)|}, where Sum{d(i)2^i} is base 2 representation of n and e(i) are digits d(i) in nonincreasing order, for i=0,1,...,m.

0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 2, 2

Offset: 1

Clark Kimberling

a(n) is also the minimum number of bit swap operations that needs to be performed to pack all the bits of n to the right. - Philippe Beaudoin, Aug 20 2014
a(n) = 0 if A243109(n) = n; 1 + a(A243109(n)) otherwise. - Philippe Beaudoin, Aug 20 2014
The index of the k-th record of this sequence is A020522(k) and corresponds to k ones followed by k zeros. - Philippe Beaudoin, Aug 20 2014

Philippe Beaudoin, Table of n, a(n) for n = 1..10000

Cf. A007088, A020522, A243109.

a:= proc(n) local L,m;
L:= convert(n,base,2);
m:= convert(L,`+`);
m - convert(L[1..m],`+`);
end proc:
seq(a(n),n=1..100); # Robert Israel, Aug 20 2014

A037870[n_] := Total[Abs[# - Sort[#]]/2] & [IntegerDigits[n, 2]];
Array[A037870, 100] (* Paolo Xausa, Mar 07 2025 *)

a(n) = {d = binary(n); e = vecsort(d); sum(i=1, #d, abs(d[i]-e[i]))/2;} \\ Michel Marcus, Aug 20 2014

Definition swapped with A037879. - R. J. Mathar, Oct 19 2015

A381764 Nearest integer not equal to n with the same Hamming weight (number of 1 bits) as n.

Original entry on oeis.org

2, 1, 5, 2, 6, 5, 11, 4, 10, 9, 13, 10, 14, 13, 23, 8, 18, 17, 21, 18, 22, 21, 27, 20, 26, 25, 29, 26, 30, 29, 47, 16, 34, 33, 37, 34, 38, 37, 43, 36, 42, 41, 45, 42, 46, 45, 55, 40, 50, 49, 53, 50, 54, 53, 59, 52, 58, 57, 61, 58, 62, 61, 95, 32, 66, 65, 69, 66

Offset: 1

Chai Wah Wu, Mar 06 2025

nonn

a(n) = integer m nearest to n such that m <> n and A000120(n) = A000120(m).
Theorem: a tie does not occur for n>0, i.e. A057168(n)-n <> n-A243109(n).
Proof: If n is of the form 2^k-1, then there are no smaller numbers with the same Hamming weight as n and a(n) = A057168(n) = (3n+1)/2.
If n is of the form (2^k-1)*2^m for some k,m>0, then n in binary is of the form 11..1100..00 and A057168(n) = 2^(k+m)+2^(k-1)-1, i.e. 100..0011..11 in binary. On the other hand, A243109(n) = (2^(k-1)-1)*2^(m+1)+2^(m-1), i.e. 11..110100..00 in binary. Thus A057168(n)-n = 2^(k-1)-1+2^m >= 2^m and n-A243109(n) = 2^(m-1) < 2^m. There is no tie and a(n) = A243109(n).
If n is not of the form (2^k-1)*2^m, then n in binary is of the form xxx...xxx0yyy...yyy, where xxxxxx and yyyyy are both not all zeros. If yyy...yyy is of the form 2^r-1, then A243109(n) must flip one of the '1' bit in xxx...xxx whereas A057168(n) leaves xxx...xxx unchanged. Thus n-A243109(n) > A057168(n)-n. Otherwise A057168(n) and A243109(n) will not change the bits xxx...xxx and reduces to the problem for yyy...yyy and thus the result follows by induction.
The above also gives a procedure to determine when a(n) = A057168(n) and when a(n) = A243109(n) or more succinctly a(n) = A243109(n) if n is even and a(n) = A057168(n) otherwise.

			For n = 2, A057168(2) = 4 and A243109(2) = 1 and 1 is closer to 2 than 4, thus a(2) = 1.

Robert Israel, Table of n, a(n) for n = 1..10000
Marc B. Reynolds, Popcount walks: next, previous, toward and nearest (2023).

Cf. A000120, A055010, A057168, A243109.

f:= proc(n) local t,k,d;
  if n::even then d:=-1 else d:= 1 fi;
  t:= convert(convert(n,base,2),`+`);
  for k from n+d by d do
    if convert(convert(k,base,2),`+`) = t then return k fi
  od
end proc:
map(f, [$1..100]); # Robert Israel, Jun 20 2025

def A381764(n): return n^((a:=-n&n+1)|(a>>1))

a(n) = A243109(n) if n is even and a(n) = A057168(n) otherwise.
a(2^k-1) = A055010(k).
For k,m > 0, a((2^k-1)*2^m) = 2^(m-1)*(2^(k+1)-3).

cp's OEIS Frontend

A037870 a(n) = (1/2)Sum{|d(i)-e(i)|}, where Sum{d(i)2^i} is base 2 representation of n and e(i) are digits d(i) in nonincreasing order, for i=0,1,...,m.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A381764 Nearest integer not equal to n with the same Hamming weight (number of 1 bits) as n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

cp's OEIS Frontend

A037870 a(n) = (1/2)*Sum{|d(i)-e(i)|}, where Sum{d(i)*2^i} is base 2 representation of n and e(i) are digits d(i) in nonincreasing order, for i=0,1,...,m.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A381764 Nearest integer not equal to n with the same Hamming weight (number of 1 bits) as n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

A037870 a(n) = (1/2)Sum{|d(i)-e(i)|}, where Sum{d(i)2^i} is base 2 representation of n and e(i) are digits d(i) in nonincreasing order, for i=0,1,...,m.