Nearest integer with the same Hamming weight

Theorem: For a positive integer n, the nearest integer not equal to n with the same Hamming weight as n is larger than n if and only if n is odd.

Proof: If n is of the form 2ᵏ-1, then n is odd and there are no smaller positive integers with the same Hamming weight as n and the nearest integer not equal to n with the the same Hamming as n is equal to (3n+1)/2 > n.

Let us denote a(n) as the smallest integer > n with the same Hamming weight as n. For n not of the form 2ᵏ-1, let us denote b(n) as the largest integer < n with the same Hamming weight as n. Let us denote c(n) as the nearest integer not equal to n with the same Hamming weight as n.

If n is of the form (2ᵏ-1)*2ᵐ for some k, m>0, then n is even and in binary is of the form 11..1100..00 and a(n) = 2ᵏ⁺ᵐ+2ᵏ⁻¹-1, i.e. 100..0011..11 in binary. On the other hand, b(n) = (2ᵏ⁻¹-1)*2ᵐ⁺¹+2ᵐ⁻¹, i.e. 11..110100..00 in binary. Thus a(n)-n = 2ᵏ⁻¹-1+2ᵐ ≥ 2ᵐ and n-b(n) = 2ᵐ⁻¹ < 2ᵐ. Therefore c(n) = b(n).

If n is not of the form (2ᵏ-1)*2ᵐ, 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ʳ-1, then b(n) must flip one of the '1' bit in xxx...xxx whereas a(n) leaves xxx...xxx unchanged. Thus n-b(n) > a(n)-n. Otherwise a(n) and b(n) will not change the bits xxx...xxx and reduces to the problem for yyy...yyy and thus the result follows by induction.

In particular, this proof shows that c(n) = a(n) if n is odd and c(n) = b(n) if n is even. It also shows that a tie never occurs in determining c(n), i.e. a(n)-n is not equal to n-b(n) for all n>0.

In The On-Line Encyclopedia of Integer Sequences (OEIS), a(n) is given by sequence A057168, b(n) is given by A243109 and c(n) is given by A381764.