Sum of all numbers written with particular digits in a given range

Question

My objective is to find the sum of all numbers from 4 to 666554 which consists of 4,5,6 only.

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

Simple method is to run a loop and add the numbers made of 4,5 and 6 only.

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*/ } 

But it seems to be inefficient. Checking that the number is made up of 4,5 and 6 will take time. Is there any way to increase the efficiency. I have tried a lot but no new approach i have found.Please help.

Answer 1

For 1-digit numbers, note that

4 + 5 + 6 == 5 * 3 

For 2-digits numbers:

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

and so on.

In general, for n-digits numbers, there are 3ⁿ of them consist of 4,5,6 only, their average value is exactly 5...5(n digits). Using code, the sum of them is ('5' * n).to_i * 3 ** n (Ruby), or int('5' * n) * 3 ** n (Python).

You calculate up to 6-digits numbers, then subtract the sum of 666555 to 666666.

---

P.S: for small numbers like 666554, using pattern matching is fast enough. (example)

Answer 2

Implement a counter in base 3 (number of digit values), e.g. 0,1,2,10,11,12,20,21,22,100.... and then translate the base-3 number into a decimal with the digits 4,5,6 (0->4, 1->5, 2->6), and add to running total. Repeat until the limit.

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