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
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)
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
Extensions
More terms from Sascha Kurz, Feb 10 2003
Corrected and extended by Max Alekseyev, Feb 26 2009
Comments