cp's OEIS Frontend

A081134 Distance to nearest power of 3.

%I A081134 #43 Oct 13 2022 13:02:27
%S A081134 0,1,0,1,2,3,2,1,0,1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,
%T A081134 8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,26,25,24,
%U A081134 23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7
%N A081134 Distance to nearest power of 3.
%H A081134 Rémy Sigrist, <a href="/A081134/b081134.txt">Table of n, a(n) for n = 1..10000</a>
%H A081134 Klaus Brockhaus, <a href="/A081134/a081134.gif">Illustration for A081134, A081249, A081250 and A081251</a>
%H A081134 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 A081134 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 A081134 <a href="/index/Di#distance_to_the_nearest">Index entries for sequences related to distance to nearest element of some set</a>
%F A081134 a(n) = min(n-3^floor(log(n)/log(3)), 3*3^floor(log(n)/log(3))-n).
%F A081134 From _Peter Bala_, Sep 30 2022: (Start)
%F A081134 a(n) = n - A006166(n); a(n) = 2*n - A003605(n).
%F A081134 a(1) = 0, a(2) = 1, a(3) = 0; thereafter, a(3*n) = 3*a(n), a(3*n+1) = 2*a(n) + a(n+1) and a(3*n+2) = a(n) + 2*a(n+1). (End)
%e A081134 a(7) = 2 since 9 is closest power of 3 to 7 and 9 - 7 = 2.
%p A081134 a:= n-> (h-> min(n-h, 3*h-n))(3^ilog[3](n)):
%p A081134 seq(a(n), n=1..100);  # _Alois P. Heinz_, Mar 28 2021
%t A081134 Flatten[Table[Join[Range[0,3^n],Range[3^n-1,1,-1]],{n,0,4}]] (* _Harvey P. Dale_, Dec 31 2013 *)
%o A081134 (PARI) a(n) = my (p=#digits(n,3)); return (min(n-3^(p-1), 3^p-n)) \\ _Rémy Sigrist_, Mar 24 2018
%o A081134 (Python)
%o A081134 def A081134(n):
%o A081134     kmin, kmax = 0,1
%o A081134     while 3**kmax <= n:
%o A081134         kmax *= 2
%o A081134     while True:
%o A081134         kmid = (kmax+kmin)//2
%o A081134         if 3**kmid > n:
%o A081134             kmax = kmid
%o A081134         else:
%o A081134             kmin = kmid
%o A081134         if kmax-kmin <= 1:
%o A081134             break
%o A081134     return min(n-3**kmin, 3*3**kmin-n) # _Chai Wah Wu_, Mar 31 2021
%Y A081134 Cf. A002452, A003605, A006166, A053646, A062153, A081249, A081250, A081251.
%K A081134 easy,nonn
%O A081134 1,5
%A A081134 _Klaus Brockhaus_, Mar 08 2003