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

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, 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, 3, 2, 1, 0, 1, 2, 3, 4, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6

Offset

1,14

Comments

This sequence is unbounded.

A053646 is the corresponding sequence for 2-smooth numbers (A000079).

Links

Altug Alkan, Table of n, a(n) for n = 1..10000

Rémy Sigrist, PARI program for A301574

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

Formula

a(n) = 0 iff n belongs to A003586.

2 * a(n) >= a(2 * n).

3 * a(n) >= a(3 * n).

Example

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.

Prog

(PARI) \\ See Links section.
(Python)
from sympy import integer_log
def A301574(n):
    def bisection(f, kmin=0, kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return x-sum((x//3**i).bit_length() for i in range(integer_log(x, 3)[0]+1))
    k = n-f(n)
    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

Crossrefs

Cf. A000079, A003586, A053646.

Sequence in context: A360676 A334107 A346700 * A272728 A174695 A337622

Adjacent sequences: A301571 A301572 A301573 * A301575 A301576 A301577

Keyword

nonn,look

Author

Altug Alkan and Rémy Sigrist, Mar 23 2018

Status

approved