Эффективный способ найти сумму цифр целой последовательности

Question

В следующем фрагменте кода я найти сумму цифр все нечетного числа между интервалом [а, Ь]

def SumOfDigits(a, b): 
    s = 0 
    if a%2 == 0: 
     a+=1 
    if b%2 == 0: 
     b-=1 
    for k in range(a,b+1,2): 
     s+= sum(int(i) for i in list(str(k))) 
    return s 

Есть ли эффективный способ выполнить то же самое? Любые узоры, которые приводят к формуле четкого разреза.

Я сделал поиск в https://oeis.org

Answer 1

Конечно есть образец. Давайте рассмотрим проблему суммирования цифр всех – нечетных и даже – номеров между a и b включительно.

Например: от 17 до 33

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 

В средней части дает сумму всех цифр от 0 до 9 (45) плюс десять раз 2. Левая секция 7 + 8 + 9 плюс три 1 и справа сумма 0 + 1 + 2 + 3 плюс четыре раза 3.

Средняя часть может состоять из нескольких блоков из десяти, например, если вы рассчитываете диапазон между 17 и 63, вы получаете 40 раз 45 плюс десять симов в цифрах от 2 до 5.

Это дает вам рекурсивный алгоритм:

def ssum(n): 
    return n * (n + 1) // 2 

def dsum(a, b): 
    res = 0 

    if a == b: 
     while a: 
      res += a % 10 
      a //= 10 

    elif a < b: 
     aa = a // 10 
     bb = b // 10 

     ra = a % 10 
     rb = b % 10 

     if aa == bb: 
      res += ssum(rb) - ssum(ra - 1) 
      res += (rb - ra + 1) * dsum(aa, bb) 

     else: 
      if ra > 0: 
       res += 45 - ssum(ra - 1) 
       res += (10 - ra) * dsum(aa, aa) 
       aa += 1 

      if rb < 9: 
       res += ssum(rb) 
       res += (rb + 1) * dsum(bb, bb) 
       bb -= 1 

      if aa <= bb: 
       res += 45 * (bb - aa + 1) 
       res += 10 * dsum(aa, bb) 

    return res 

Теперь давайте продолжим это, чтобы включить только нечетные числа. Adkust a так, что он ровный и b так, что это странно. Ваша сумма сумм цифр теперь выполняется над парами четных и нечетных чисел, где even + 1 == odd. Это означает, что цифра нечетного числа id больше, чем четное число, потому что все, кроме последних цифр, одинаковы, а последняя нечетная цифра - больше, чем четная цифра.

Поэтому:

dsum(a, b) == oddsum + evensum 

и:

oddsum - evensum == (b - a + 1) // 2 

Функция для просуммировать digitsums всех нечетных чисел, то:

def oddsum(a, b): 
    if a % 2: a -= 1 
    if b % 2 == 0: b -= 1 

    d = (b - a + 1) // 2 

    return (dsum(a, b) + d) // 2 

Когда я смотрел на ваш комментарий о OEIS , Я заметил, что алгоритм, вероятно, можно упростить, написав функцию, чтобы суммировать цифры от всех nu mbers от нуля до n, а затем вычислить разницу dsum(b) - dsum(a). Вероятно, есть больше возможностей для оптимизации.

Answer 2

Избегайте накладных расходов преобразования и из строк и работать непосредственно с номерами сами:

def SumOfDigits(a, b): 
    result = 0 
    for i in range(a + (not a % 2), b + 1, 2): 
     while i: 
      result += i % 10 
      i //= 10 
    return result