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

Question

Моя цель - найти сумму всех чисел от 4 до 666554, которая состоит только из 4,5,6.

SUM = 4+5+6+44+45+46+54+55+56+64+65+66+.....................+666554. 

Простой метод состоит в том, чтобы запустить цикл и добавить числа, состоящие только из 4,5 и 6.

long long sum = 0; 
for(int i=4;i <=666554;i++){ 
    /*check if number contains only 4,5 and 6. 
    if condition is true then add the number to the sum*/ 
} 

Но это кажется неэффективным. Проверка того, что число составило 4,5 и 6, потребует времени. Есть ли способ повысить эффективность. Я пробовал много, но никакого нового подхода я не нашел. Пожалуйста, помогите.

Answer 1

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

4 + 5 + 6 == 5 * 3 

Для 2-цифры номеров:

(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, используя поиск по шаблону достаточно быстро. (example)

Answer 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)) 

Answer 3

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

---

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

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

• условие может не быть тривиальной, чтобы соответствовать: в этом случае простой способ является преобразование в строку (довольно тяжелый по подразделениям и испытаний), а затем string- соответствие
• отношение фильтрации не так уж плохо, чтобы начать с 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 

here is the same in C++ И.

Answer 4

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

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

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

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

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

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

Если это по-прежнему неясно, выписывать п = 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) 

При п = 6

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

---

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

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

Answer 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