login
Smallest possible sum of the digits of a multiple of n.
7

%I #27 Mar 23 2024 21:07:27

%S 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,

%T 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,

%U 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

%N Smallest possible sum of the digits of a multiple of n.

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

%C 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

%C 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

%H A.V.Izvalov, S.T.Kuznetsov, <a href="/A077196/b077196.txt">Table of n, a(n) for n = 1..56000</a>

%H Pavel V. Phedotov, <a href="http://digitsum.narod.ru">Sum of digits of a multiple of a given number</a>, May 2002. (in Russian)

%H Valery P. Phedotov, <a href="http://matholimp.livejournal.com/2009/12/14">Problems from 2002 Math Olympiad "Third Millennium"</a> (in Russian)

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

%F 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.

%o (Python)

%o def dijkstra(dist, start, startValue, traverse): # Dijkstra's algorithm

%o from heapq import heappop, heappush

%o dist[start] = startValue

%o queue = [(startValue, start)]

%o while queue:

%o value, node = heappop(queue)

%o if dist[node] == value:

%o for node2, value2 in traverse(node, value):

%o if dist[node2] > value2:

%o dist[node2] = value2

%o heappush(queue, (value2, node2))

%o return dist

%o def A077196(n):

%o def traverse(remainder, add1):

%o return [((remainder*10)%n, add1), ((remainder+1)%n, add1+1)]

%o return dijkstra([n+1]*n, 1%n, 1, traverse)[0] # _Jason Yuen_, Feb 28 2024

%Y Cf. A077194, A077195, A181862.

%K base,nonn

%O 1,3

%A _Amarnath Murthy_, Nov 01 2002

%E More terms from _Sascha Kurz_, Feb 10 2003

%E Corrected and extended by _Max Alekseyev_, Feb 26 2009