Сумма всех чисел, записанных с определенными цифрами в заданном диапазоне

Ответ 1

Для 1-значных цифр обратите внимание, что

4 + 5 + 6 == 5 * 3

Для двухзначных чисел:

(44 + 45 + 46) + (54 + 55 + 56) + (64 + 65 + 66)
== 45 * 3 + 55 * 3 + 65 * 3
== 55 * 9

и т.д.

В общем случае для чисел n -digits их 3 ⁿ из них состоят только из 4, 5, 6, их среднее значение точно 5...5 (n цифр). Используя код, их сумма равна ('5' * n).to_i * 3 ** n (Ruby) или int('5' * n) * 3 ** n (Python).

Вы вычисляете до 6 цифр цифр, затем вычитаете сумму от 666555 до 666666.

P.S: для небольших чисел, таких как 666554, использование сопоставления шаблонов достаточно быстро. (пример)

Ответ 2

Внедрить счетчик в базе 3 (количество цифровых значений), например. 0,1,2,10,11,12,20,21,22,100.... и затем перевести номер базы-3 в десятичную цифру с цифрами 4,5,6 (0- > 4, 1- > 5, 2- > 6) и прибавить к общей сумме. Повторяйте до предела.

def compute_sum(digits, max_val):

  def _next_val(cur_val):
    for pos in range(len(cur_val)):
      cur_val[pos]+=1
      if cur_val[pos]<len(digits):
        return
      cur_val[pos]=0
    cur_val.append(0)

  def _get_val(cur_val):
    digit_val=1
    num_val=0
    for x in cur_val:
      num_val+=digits[x]*digit_val
      digit_val*=10
    return num_val

  cur_val=[]
  sum=0
  while(True):
    _next_val(cur_val)
    num_val=_get_val(cur_val)
    if num_val>max_val:
      break
    sum+=num_val
  return sum

def main():
  digits=[4,5,6]
  max_val=666554
  print(digits, max_val)
  print(compute_sum(digits, max_val))

Ответ 3

Математика хороша, но не все проблемы тривиально "сжимаемы", поэтому знать, как справляться с ними без математики, может быть полезно.

В этой задаче суммирование тривиально, трудность эффективно перечисляет числа, которые необходимо добавить, на первый взгляд.

Маршрут "фильтр" - возможность: генерировать все возможные числа, постепенно и отфильтровывать те, которые не совпадают; однако он также весьма неэффективен (в общем):

• условие не может быть тривиальным, чтобы соответствовать: в этом случае более простым способом является преобразование в строку (довольно тяжелое для делений и тестов), за которым следует соответствие строк
• отношение фильтрации не так уж плохо, чтобы начать с 30% на цифру, но оно очень мало масштабируется, поскольку gen-y-s отметил: для 4-значного числа он составляет 1%, или генерирует и проверяет 100 номеров, чтобы получить только 1 из них.

Поэтому я бы посоветовал подход "поколений": генерировать числа, которые соответствуют условию (и всем из них).

Я хотел бы отметить, что генерация всех чисел, состоящих из 4, 5 и 6, подобна подсчету (в тройном):

• начинается с 4
• 45 становится 46 (остерегайтесь переноса)
• 66 становится 444 (крайний перенос)

Отпустите в Python в качестве генератора:

def generator():
    def convert(array):
        i = 0
        for e in array:
            i *= 10
            i += e
        return i

    def increment(array):
        result = []
        carry = True

        for e in array[::-1]:
            if carry:
                e += 1
                carry = False
            if e > 6:
                e = 4
                carry = True
            result = [e,] + result

        if carry:
            result = [4,] + result

        return result

    array = [4]
    while True:
        num = convert(array)
        if num > 666554: break

        yield num
        array = increment(array)

Его результат можно напечатать с помощью sum(generator()):

$ time python example.py
409632209
python example.py  0.03s user 0.00s system 82% cpu 0.043 total

И здесь то же самое в С++.

Ответ 4

"Начните с более простой проблемы". -Polya

Суммируйте n-значные числа, которые состоят только из цифр 4,5,6

Как объясняет Ю. Хао, существуют 3**n числа, а их средняя по симметрии, например. 555555, поэтому сумма 3**n * (10**n-1)*5/9. Но если вы этого не заметили, вот как вы могли бы решить проблему по-другому.

Задача имеет рекурсивную конструкцию, поэтому попробуем рекурсивное решение. Пусть g (n) - сумма всех 456-чисел ровно n цифр. Тогда мы имеем рекуррентное отношение:

g(n) = (4+5+6)*10**(n-1)*3**(n-1) + 3*g(n-1)

Чтобы увидеть это, отделите первую цифру каждого числа в сумме (например, для n = 3, столбец сотен). Это дает первый термин. Второй член представляет собой сумму оставшихся цифр, один счетчик g (n-1) для каждого префикса 4,5,6.

Если это еще неясно, выпишите сумму n = 2 и отдельные десятки единиц:

g(2) = 44+45+46 + 54+55+56 + 64+65+66
     = (40+50+60)*3 + 3*(4+5+6)
     = (4+5+6)*10*3 + 3*g(n-1)

Круто. На этом этапе острый читатель может захотеть проверить формулу Ю Хао для g (n), которая удовлетворяет нашему рекуррентному соотношению.

Чтобы решить проблему OP, сумма всех 456-чисел от 4 до 666666 равна g(1) + g(2) + g(3) + g(4) + g(5) + g(6). В Python с динамическим программированием:

def sum456(n):
    """Find the sum of all numbers at most n digits which consist of 4,5,6 only"""
    g = [0] * (n+1)
    for i in range(1,n+1):
        g[i] = 15*10**(i-1)*3**(i-1) + 3*g[i-1]
    print(g) # show the array of partial solutions
    return sum(g)

При n = 6

>>> sum456(6)
[0, 15, 495, 14985, 449955, 13499865, 404999595]
418964910

Изменить: я отмечаю, что ОП урезал свою сумму на 666554, чтобы он не соответствовал общей схеме. Это будет меньше последних нескольких терминов

>>> sum456(6) - (666555 + 666556 + 666564 + 666565 + 666566 + 666644 + 666645 + 666646 + 666654 + 666655 + 666656 + + 666664 + 666665 + 666666)
409632209

Ответ 5

Сумма от 4 до 666666 равна:

total = sum([15*(3**i)*int('1'*(i+1)) for i in range(6)])
>>> 418964910

Сумма нескольких чисел между 666554 и 666666:

rest = 666555+666556+666564+666565+666566+
666644+666645+666646+
666654+666655+666656+
666664+666665+666666
>>> 9332701

total - rest
>>> 409632209

Ответ 6

Реализация вопроса на Java: - Для ответа используется модуль (10 ^ 9 +7).

public static long compute_sum(long[] digits, long max_val, long count[]) {
    List<Long> cur_val = new ArrayList<>();
    long sum = 0;
    long mod = ((long)Math.pow(10,9))+7;
    long num_val = 0;
    while (true) {
        _next_val(cur_val, digits);
        num_val = _get_val(cur_val, digits, count);
        sum =(sum%mod + (num_val)%mod)%mod;
        if (num_val == max_val) {
            break;
        }

    }
    return sum;
}

public static void _next_val(List<Long> cur_val, long[] digits) {
    for (int pos = 0; pos < cur_val.size(); pos++) {
        cur_val.set(pos, cur_val.get(pos) + 1);
        if (cur_val.get(pos) < digits.length)
            return;
        cur_val.set(pos, 0L);
    }

    cur_val.add(0L);
}

public static long _get_val(List<Long> cur_val, long[] digits, long count[]) {
    long digit_val = 1;
    long num_val = 0;
    long[] digitAppearanceCount = new long[]{0,0,0};
    for (Long x : cur_val) {
        digitAppearanceCount[x.intValue()] = digitAppearanceCount[x.intValue()]+1;
        if (digitAppearanceCount[x.intValue()]>count[x.intValue()]){
            num_val=0;
            break;
        }
        num_val = num_val+(digits[x.intValue()] * digit_val);
        digit_val *= 10;
    }
    return num_val;
}


public static void main(String[] args) {

    long [] digits=new long[]{4,5,6};
    long count[] = new long[]{1,1,1};
    long max_val= 654;

    System.out.println(compute_sum(digits, max_val, count));
}

Ответ @gen-ys (fooobar.com/info/195767/...) неправильный (он включает 55,66,44 для x = y = z = 1, что превышает доступные значения 4s, 5s, 6s). Это дает выходные данные как 12189, но это должно быть 3675 для x = y = z = 1.

Логика @Yu Hao (fooobar.com/info/195767/...) имеет ту же ошибку, что и упомянутая выше. Это дает выходные данные как 12189, но это должно быть 3675 для x = y = z = 1.