A053646 Distance to nearest power of 2.

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

Offset

1,6

Comments

Sum_{j=1..2^(k+1)} a(j) = A002450(k) = (4^k - 1)/3. - Klaus Brockhaus, Mar 17 2003

Links

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Klaus Brockhaus, Illustration for A053646, A081252, A081253 and A081254

Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.

Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.

Index entries for sequences related to distance to nearest element of some set

Formula

a(2^k+i) = i for 1 <= i <= 2^(k-1); a(3*2^k+i) = 2^k-i for 1 <= i <= 2^k; (Sum_{k=1..n} a(k))/n^2 is bounded. - Benoit Cloitre, Aug 17 2002

a(n) = min(n-2^floor(log(n)/log(2)), 2*2^floor(log(n)/log(2))-n). - Klaus Brockhaus, Mar 08 2003

From Peter Bala, Aug 04 2022: (Start)

a(n) = a( 1 + floor((n-1)/2) ) + a( ceiling((n-1)/2) ).

a(2*n) = 2*a(n); a(2*n+1) = a(n) + a(n+1) for n >= 2. Cf. A006165. (End)

a(n) = 2*A006165(n) - n for n >= 2. - Peter Bala, Sep 25 2022

Example

a(10)=2 since 8 is closest power of 2 to 10 and |8-10| = 2.

Maple

a:= n-> (h-> min(n-h, 2*h-n))(2^ilog2(n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Mar 28 2021

Mathematica

np2[n_]:=Module[{min=Floor[Log[2, n]], max}, max=min+1; If[2^max-n<n-2^min, 2^max-n, n-2^min]]; np2/@Range[90] (* Harvey P. Dale, Feb 21 2012 *)

Prog

(PARI) a(n)=vecmin(vector(n, i, abs(n-2^(i-1))))
(PARI) for(n=1, 89, p=2^floor(0.1^25+log(n)/log(2)); print1(min(n-p, 2*p-n), ", "))
(PARI) a(n) = my (p=#binary(n)); return (min(n-2^(p-1), 2^p-n)) \\ Rémy Sigrist, Mar 24 2018
(Python)
def A053646(n): return min(n-(m := 2**(len(bin(n))-3)), 2*m-n) # Chai Wah Wu, Mar 08 2022

Crossrefs

Cf. A006165, A053188, A060973, A081134, A002450, A081252, A081253, A081254.

Sequence in context: A179765 A004074 A245615 * A080776 A376813 A360659

Adjacent sequences: A053643 A053644 A053645 * A053647 A053648 A053649

Keyword

easy,nonn

Author

Henry Bottomley, Mar 22 2000

Status

approved