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

Author

Altug Alkan and Rémy Sigrist, Mar 23 2018

Keywords

• nonn
• look

Comments

This sequence is unbounded.

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

Examples

			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.
		

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

Crossrefs

Cf. A000079, A003586, A053646.

Programs

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

Formula

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

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

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