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

Java implementation of question:- This uses the modulo(10^9 +7) for the answer.

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

The Answer by @gen-y-s (https://stackoverflow.com/a/31286947/8398943) is wrong (It includes 55,66,44 for x=y=z=1 which is exceeding the available 4s, 5s, 6s). It gives output as 12189 but it should be 3675 for x=y=z=1.

The logic by @Yu Hao (https://stackoverflow.com/a/31285816/8398943) has the same mistake as mentioned above. It gives output as 12189 but it should be 3675 for x=y=z=1.

Answer 2

Mathematics are good, but not all problems are trivially "compressible", so knowing how to deal with them without mathematics can be worthwhile.

---

In this problem, the summation is trivial, the difficulty is efficiently enumerating the numbers that need be added, at first glance.

The "filter" route is a possibility: generate all possible numbers, incrementally, and filter out those which do not match; however it is also quite inefficient (in general):

• the condition might not be trivial to match: in this case, the easier way is a conversion to string (fairly heavy on divisions and tests) followed by string-matching
• the ratio of filtering is not too bad to start with at 30% per digit, but it scales very poorly as gen-y-s remarked: for a 4 digits number it is at 1%, or generating and checking 100 numbers to only get 1 out of them.

I would therefore advise a "generational" approach: only generate numbers that match the condition (and all of them).

I would note that generating all numbers composed of 4, 5 and 6 is like counting (in ternary):

• starts from 4
• 45 becomes 46 (beware of carry-overs)
• 66 becomes 444 (extreme carry-over)

---

Let's go, in Python, as a generator:

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)

Its result can be printed with sum(generator()):

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

And here is the same in C++.

Answer 3

The sum of 4 through 666666 is:

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

The sum of the few numbers between 666554 and 666666 is:

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

total - rest
>>> 409632209

Answer 4

"Start with a simpler problem." —Polya

Sum the n-digit numbers which consist of the digits 4,5,6 only

As Yu Hao explains above, there are 3**n numbers and their average by symmetry is eg. 555555, so the sum is 3**n * (10**n-1)*5/9. But if you didn't spot that, here's how you might solve the problem another way.

The problem has a recursive construction, so let's try a recursive solution. Let g(n) be the sum of all 456-numbers of exactly n digits. Then we have the recurrence relation:

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

To see this, separate the first digit of each number in the sum (eg. for n=3, the hundreds column). That gives the first term. The second term is sum of the remaining digits, one count of g(n-1) for each prefix of 4,5,6.

If that's still unclear, write out the n=2 sum and separate tens from units:

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)

Cool. At this point, the keen reader might like to check Yu Hao's formula for g(n) satisfies our recurrence relation.

To solve OP's problem, the sum of all 456-numbers from 4 to 666666 is g(1) + g(2) + g(3) + g(4) + g(5) + g(6). In Python, with dynamic programming:

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)

For n=6

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

---

Edit: I note that OP truncated his sum at 666554 so it doesn't fit the general pattern. It will be less the last few terms

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

Answer 5

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 6

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