A353157 a(n) is the distance from n to the nearest integer whose binary expansion has no common 1-bits with that of n.

0, 1, 1, 1, 1, 3, 2, 1, 1, 3, 5, 5, 4, 3, 2, 1, 1, 3, 5, 7, 9, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25

Offset: 0

Author

Rémy Sigrist, Apr 27 2022

Keywords

• nonn
• base

Comments

Equivalently the distance to the nearest integer that can be added without carries in base 2.

Examples

			For n = 42 ("101010" in binary):
- 21 ("10101") is the greatest number <= 42 that has no common 1-bits with 42,
- 128 ("1000000") is the least number >= 42 that has no common 1-bits with 42,
- so a(42) = min(42-21, 128-42) = min(21, 86) = 21.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8192
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A006257, A020988, A097110, A080079, A108019, A353158.

Programs

PARI

a(n) = { my (high=2^#binary(n), low=high-1-n); min(n-low, high-n) }

Formula

a(n) = min(A006257(n), A080079(n)) for any n > 0.

a(n) = 1 iff n belongs to A097110.

a(n) = n/2 iff n belongs to A020988.

a(n) = n/4 iff n belongs to A108019.

2*a(n) - a(2*n) = 0 or 1.