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

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


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

Tags:

Algorithm

Math