Sum of digits of all 4-digit numbers divisible by 7

Question

What would be the way to approach this problem?

Answer 1

One way to do it is to look at the underlying pattern of when each digit changes as you count up from the first to the last number in the series. I'll do it for the thousands digit, and you can try the rest. You'll need to think about each one separately.

The first one is $1001$, and the last is $9996$.

Doing this with a computer is easy. Doing this by hand is straightforward but you'll need to watch details. There are lots of opportunities to be off by one.

The first number divisible by $7$ in each thousand is:

$$1001, 2002, 3003, 4004, 5005, 6006, 7000, 8001, 9002,$$

and the last is just seven minus the first of the next thousand:

$$1995, 2996, 3997, 4998, 5999, 6993, 7994, 8995, 9996.$$

There are $143$ terms in the series from $1001$ to $1995$. Similarly for all of the other thousands except the $6000$'s, where there are $142$ terms. (This should be clear from inspection of the difference of the first and last in each thousand. This difference in all but the $6000$'s is $994$ but in the $6000$'s the difference is $987$.)

So, the sum of all of the thousands digits is $(143 \times 45) - 6 = 6429.$

Work out a similar analysis for the other three digits. Each one has a pattern.

Answer 2

There are 9 1-digit decimal numbers. Partition them on their residue modulo 7 and you get:

$$(0,\{7\}), (1,\{1,8\}), (2,\{2,9\}), (3,\{3\}), (4,\{4\}), (5,\{5\}), (6,\{6\})$$

We can extetnd this to 2-digit numbers. First we multiply all the 1-digit numbers by 10, which has the effect of shuffling all the residues, but in a fixed way: 0 goes to 0, and $n \neq 0$ goes to $3n \mod 7$. So all the 2-digit multiples of 10 can be paetitioned like this:

$$(0, \{70\}), (3,\{10,80\}), (6,\{20,90\}), (2,\{30\}), (5, \{40\}), (1,\{50\}), (4,\{60\})$$

There are 10 decimal digits. They can be partitioned by residue modulo 7 like this:

$$(0,\{0,7\}), (1,\{1,8\}), (2,\{2,9\}), (3,\{3\}), (4,\{4\}), (5,\{5\}), (6,\{6\})$$

We can now do a kind of cartesian product between these two partitions to calculate the partition of all 2-digit numbers by residue. Here is the residue-0 entry of that partition:

$$(0,\{70,77,14,84,21,91,35,42,49,56,63\})$$

This was created by combining the $(0,\{70\})$ entry with the $(0,\{0,7\})$, entry, the $(3,\{10,80\})$ entry with the $(4,\{4\})$, and so on. You can see that this is going to get very verbose.

In the end we only care about digit sums, so we don't really need to keep track of every single number in every residue class. We only need to keep track of the set's size and digit sum.

When combining two partition entries together, with residue, counts and sums $(r_1,c_1,s_1)$ and $(r_2,c_2,s_2)$, their combined entry will be $(r_1r_2 \mod 7, c_1c_2, c_1s_2 + c_2s_1)$.

For instance, consider combining $(3,\{10,80\})$ and $(2,\{2,9\})$. Their converted versions are $(3,2,9)$ and $(2,2,11)$. Combining them results in $(5,4,40)$. Doing it the long way results in $(t,\{12,19,82,89\})$, which also has 4 entries and digit sum 40.

So, starting over with the abbreviated versions of the sets.

9 1-digit decimal numbers:

$$(0,1,7), (1,2,9), (2,2,11), (3,1,3), (4,1,4), (5,1,5), (6,1,6)$$

Multiply them by 10, which doesn't change the digit sum.

$$(0,1,7), (3,2,9), (6,2,11), (2,1,3), (5,1,4), (1,1,5), (4,1,6)$$

10 decimal digits:

$$(0,2,7),(1,2,9),(2,2,11),(3,1,3),(4,1,4),(5,1,5),(6,1,6)$$

After an annoying, but feasable amount of work you can get the 2-digit numbers:

$$(0,13,125),(1,13,129),(2,12,114),(3,13,118),(4,13,122),(5,13,126),(6,13,121)$$

The 3-digit numbers:

$$(0,128,1792),(1,128,1794),(2,129,1806),(3,129,1809),(4,129,1803),(5,129,1806),(6,128,1790)$$

And the 4-digit numbers:

$$(0,1286,23792),(1,1286,23791),(2,1286,23790),(3,1286,23798),(4,1285,23778),(5,1285,23767),(6,1286,23784)$$

Looking at the entry for residue 0 we know there are 1286 4-digit numbers divisible by 7, and their digit sum is 23792.

Answer 3

Programmatically this can be solved as follows:

long sum = 0;

for (int i = 1000; i < 9999; i++)
    if (i % 7 == 0) {
        print(" "+i);
        sum+=i;
    }

which gives the following result: 7071071

where % suppose to mean $modulo$

---

Edit: Sorry, you are right @John

For given problem, this is correct computation:

long sum = 0;

for (int n = 1000; n <= 9999; n++)
    if (n % 7 == 0)
        sum += digitSum(n);

the recursive digitSum method:

static int digitSum(int n) {
    if (n == 0)
        return 0;
    return n%10 + digitSum(n/10);
}

the result is: 23792