A077196 Smallest possible sum of the digits of a multiple of n.

1, 1, 3, 1, 1, 3, 2, 1, 9, 1, 2, 3, 2, 2, 3, 1, 2, 9, 2, 1, 3, 2, 2, 3, 1, 2, 9, 2, 2, 3, 3, 1, 6, 2, 2, 9, 3, 2, 3, 1, 5, 3, 3, 2, 9, 2, 2, 3, 2, 1, 3, 2, 3, 9, 2, 2, 3, 2, 2, 3, 2, 3, 9, 1, 2, 6, 3, 2, 3, 2, 3, 9, 2, 3, 3, 2, 2, 3, 4, 1, 9, 5, 3, 3, 2, 3, 3, 2, 2, 9, 2, 2, 3, 2, 2, 3, 2, 2, 18, 1, 2, 3, 2, 2, 3

Offset: 1

Author

Amarnath Murthy, Nov 01 2002

Keywords

• base
• nonn

Comments

a(n) is not bounded since a(10^n-1)=9n. (Rustem Aidagulov)

In May 2002, this sequence (up to n=1000 with some useful remarks) was constructed by Pavel V. Phedotov. Some problems at the Second International Distant School Olympiad in Math "Third Millennium" (January 2002) asked to find a(n) for n = 5, 6, 7, 8, 9, 55, 66, 77, 88, 99, 555, 666, 777, 888, 999, and 2002^2002 . - Valery P. Phedotov (vphedotov(AT)narod.ru), May 05 2010

Start at 0 and perform a series of "multiply by 10" and "add 1" operations. a(n) is the minimum number of "add 1" operations needed to reach a positive multiple of n. - Jason Yuen, Feb 28 2024

Links

• A.V.Izvalov, S.T.Kuznetsov, Table of n, a(n) for n = 1..56000
• Pavel V. Phedotov, Sum of digits of a multiple of a given number, May 2002. (in Russian)
• Valery P. Phedotov, Problems from 2002 Math Olympiad "Third Millennium" (in Russian)

Crossrefs

Cf. A077194, A077195, A181862.

Programs

Python

def dijkstra(dist, start, startValue, traverse):  # Dijkstra's algorithm
    from heapq import heappop, heappush
    dist[start] = startValue
    queue = [(startValue, start)]
    while queue:
        value, node = heappop(queue)
        if dist[node] == value:
            for node2, value2 in traverse(node, value):
                if dist[node2] > value2:
                    dist[node2] = value2
                    heappush(queue, (value2, node2))
    return dist
def A077196(n):
    def traverse(remainder, add1):
        return [((remainder*10)%n, add1), ((remainder+1)%n, add1+1)]
    return dijkstra([n+1]*n, 1%n, 1, traverse)[0]  # Jason Yuen, Feb 28 2024

Formula

a(n) = A007953(A077194(n)).

a(2n)=a(n) and a(5n)=a(n) for any n. In particular, a(2^a*5^b) = a(1) = 1 where a or b are nonnegative integer.

Extensions

More terms from Sascha Kurz, Feb 10 2003

Corrected and extended by Max Alekseyev, Feb 26 2009