cp's OEIS Frontend

A301574 a(n) = distance from n to nearest 3-smooth number (A003586).

%I A301574 #22 Oct 23 2024 00:43:27
%S A301574 0,0,0,0,1,0,1,0,0,1,1,0,1,2,1,0,1,0,1,2,3,2,1,0,1,1,0,1,2,2,1,0,1,2,
%T A301574 1,0,1,2,3,4,5,6,5,4,3,2,1,0,1,2,3,2,1,0,1,2,3,4,5,4,3,2,1,0,1,2,3,4,
%U A301574 3,2,1,0,1,2,3,4,4,3,2,1,0,1,2,3,4,5,6
%N A301574 a(n) = distance from n to nearest 3-smooth number (A003586).
%C A301574 This sequence is unbounded.
%C A301574 A053646 is the corresponding sequence for 2-smooth numbers (A000079).
%H A301574 Altug Alkan, <a href="/A301574/b301574.txt">Table of n, a(n) for n = 1..10000</a>
%H A301574 Rémy Sigrist, <a href="/A301574/a301574.gp.txt">PARI program for A301574</a>
%H A301574 <a href="/index/Di#distance_to_the_nearest">Index entries for sequences related to distance to nearest element of some set</a>
%F A301574 a(n) = 0 iff n belongs to A003586.
%F A301574 2 * a(n) >= a(2 * n).
%F A301574 3 * a(n) >= a(3 * n).
%e A301574 a(20) = a(22) = 2 because 18 is the nearest 3-smooth number to 20 and 24 is the nearest 3-smooth number to 22.
%o A301574 (PARI) \\ See Links section.
%o A301574 (Python)
%o A301574 from sympy import integer_log
%o A301574 def A301574(n):
%o A301574     def bisection(f,kmin=0,kmax=1):
%o A301574         while f(kmax) > kmax: kmax <<= 1
%o A301574         while kmax-kmin > 1:
%o A301574             kmid = kmax+kmin>>1
%o A301574             if f(kmid) <= kmid:
%o A301574                 kmax = kmid
%o A301574             else:
%o A301574                 kmin = kmid
%o A301574         return kmax
%o A301574     def f(x): return x-sum((x//3**i).bit_length() for i in range(integer_log(x,3)[0]+1))
%o A301574     k = n-f(n)
%o A301574     return min(n-bisection(lambda x:f(x)+k,k,k),bisection(lambda x:f(x)+k+1,n,n)-n) # _Chai Wah Wu_, Oct 22 2024
%Y A301574 Cf. A000079, A003586, A053646.
%K A301574 nonn,look
%O A301574 1,14
%A A301574 _Altug Alkan_ and _Rémy Sigrist_, Mar 23 2018