A348730 - OEIS

%I #50 Nov 08 2021 13:24:49

%S 0,15,24,31,43,49,58,69,79,86,95,103,114,124,130,142,150,159,169,177,

%T 185,195,203,214,223,231,241,249,259,267,275,286,295,303,312,321,330,

%U 340,349,357,367,375,383,394,403,411,421,429,439,448,456,465,475,482,493,501

%N Largest remainder of an n-digit number when divided by its sum of digits.

%C When dividing a number by N, the remainder can be at most N - 1. The largest sum of digits that an n-digit number can reach is 9*n. According to this, a(n) < 9*n is always the case.

%C Is the sequence strictly increasing? a(n) is achieved by a single n-digit number when n = 2, 3, 5, 19, 24, 27, 32, 38, ... (Cf. A348900) - _Chai Wah Wu_, Nov 02 2021

%H David A. Corneth, <a href="/A348730/b348730.txt">Table of n, a(n) for n = 1..1780</a> (first 820 terms from Chai Wah Wu)

%H David A. Corneth, <a href="/A348730/a348730.gp.txt">PARI program</a>

%H Heinrich Hemme, <a href="https://www.spektrum.de/raetsel/was-ist-der-groesstmoegliche-rest/1939072">Was ist der größtmögliche Rest?</a> Hemmes mathematische Rätsel, Oct 28 2021.

%H Volker Wagner, <a href="https://www.mental-aktiv.de/knobelforum/puzzle/qQoxjRqAFeKd3aXmu">Kleine Rechnerei</a>, Knobelforum, Jan 24 2020.

%e 79 = 15 mod 16

%e 799 = 24 mod 25

%e 9599 = 31 mod 32

%e 98999 = 43 mod 44

%e 599999 = 49 mod 50

%e 8999998 = 58 mod 61

%e etc.

%p sod:=proc(n) # sum of digits

%p   local N;

%p   N:=convert(n,base,10);

%p   add(i,i=N);

%p end;

%p a:=proc(k)local n, i;

%p   for n from 1 to k do

%p     maxR||n:=0: # largest remainder

%p     for i from 10^(n-1) to 10^n-1 do

%p       if i mod sod(i)>maxR||n then

%p          maxR||n:=i mod sod(i);

%p        fi;

%p     od:

%p   od:

%p   return(seq(maxR||n,n=1..k));

%p end;

%t a[n_] := Max[Mod[#, (Plus @@ IntegerDigits[#])] & /@ Range[10^(n - 1), 10^n - 1]]; Array[a, 7] (* _Amiram Eldar_, Oct 31 2021 *)

%o (Python)

%o def sd(n): return sum(map(int, str(n)))

%o def a(n): return max(n%sd(n) for n in range(10**(n-1)+1, 10**n))

%o print([a(n) for n in range(1, 7)]) # _Michael S. Branicky_, Oct 31 2021

%o (PARI) See Corneth link

%o (Python)

%o from functools import lru_cache

%o from sympy.combinatorics.partitions import IntegerPartition

%o from sympy.utilities.iterables import partitions, multiset_permutations

%o @lru_cache(maxsize=None)

%o def intpartition(n,m): return tuple(''.join(str(d) for d in IntegerPartition(p).partition+[0]*(m-s)) for s, p in partitions(n,k=9,m=m,size=True))

%o def A348730(n):

%o     l, c, k = 9*n, 0, 10**(n-1)

%o     while l-1 > c:

%o         c = max(c,max(s % l for s in (int(''.join(q)) for p in intpartition(l,n) for q in multiset_permutations(p)) if s >= k))

%o         l -= 1

%o     return c # _Chai Wah Wu_, Nov 03-08 2021

%Y Cf. A070635, A348900.

%K nonn,base

%O 1,2

%A _Martin Renner_, Oct 31 2021

%E a(8)-a(10) from _Michael S. Branicky_, Oct 31 2021

%E More terms from _David A. Corneth_, Oct 31 2021