login
Distance to nearest power of 2.
16

%I #50 Sep 25 2022 15:49:01

%S 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,

%T 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,

%U 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

%N Distance to nearest power of 2.

%C Sum_{j=1..2^(k+1)} a(j) = A002450(k) = (4^k - 1)/3. - _Klaus Brockhaus_, Mar 17 2003

%H Rémy Sigrist, <a href="/A053646/b053646.txt">Table of n, a(n) for n = 1..10000</a>

%H Klaus Brockhaus, <a href="/A053646/a053646.gif">Illustration for A053646, A081252, A081253 and A081254</a>

%H Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.

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

%H <a href="/index/Di#distance_to_the_nearest">Index entries for sequences related to distance to nearest element of some set</a>

%F 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

%F a(n) = min(n-2^floor(log(n)/log(2)), 2*2^floor(log(n)/log(2))-n). - _Klaus Brockhaus_, Mar 08 2003

%F From _Peter Bala_, Aug 04 2022: (Start)

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

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

%F a(n) = 2*A006165(n) - n for n >= 2. - _Peter Bala_, Sep 25 2022

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

%p a:= n-> (h-> min(n-h, 2*h-n))(2^ilog2(n)):

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Mar 28 2021

%t 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 *)

%o (PARI) a(n)=vecmin(vector(n,i,abs(n-2^(i-1))))

%o (PARI) for(n=1,89,p=2^floor(0.1^25+log(n)/log(2)); print1(min(n-p,2*p-n),","))

%o (PARI) a(n) = my (p=#binary(n)); return (min(n-2^(p-1), 2^p-n)) \\ _Rémy Sigrist_, Mar 24 2018

%o (Python)

%o def A053646(n): return min(n-(m := 2**(len(bin(n))-3)),2*m-n) # _Chai Wah Wu_, Mar 08 2022

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

%K easy,nonn

%O 1,6

%A _Henry Bottomley_, Mar 22 2000