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
Examples
a(10)=2 since 8 is closest power of 2 to 10 and |8-10| = 2.
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
Programs
-
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 -
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
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
Comments