THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  Cont_Dig_Sum().  This function takes an integer as its argument and returns the CDS (Contiguous Digit Sum) of that integer.

The CDS (contiguous digit sum) of any integer is the sum of all the smaller integers that can be formed from it, using only contiguous digits.

For example, CDS(8358) is 1393, the sum of 8,83,835,3,35,358,5,58,8.

This code will only find CDS's up to a maximum possible value of an int64 integer.  You can change this in the declarations to a uint64 if you want.  See the table below for the limits.

Type

Exponent of 2
Value

int 230 1073741824
uint 231 2147483648
int64 261 2305843009213693952
uint64 262 4611686018427387904

Declaring the function must be done like this:

declare Cont_Dig_sum (c: int).

Here's the code itself:

sub Cont_Dig_Sum(c)
' Returns the CDS (contiguous digit sum)
' of argument c, that is, the sum of all
' the smaller integers that can be formed
' from it, using only contiguous digits.
def i, loop, temp, sum: int
loop = log10(c): 'get loop size
sum = 0: 'initialise sum to zero
for i = 1 to loop
    temp = c: 'copy argument
    do
        sum = sum + temp % 10^i: 'new sum
        temp = temp/10: 'chop off temp LSD
    until temp < 10^(i - 1)
next i
return sum

Overview:  The output will be stored in variable sum, which is initialised to zero.  A simple FOR-NEXT loop uses variable i to iterate over each digit of the argument in order, from left to right (MSD to LSD).

For each iteration of variable i, the argument c, that is, the integer whose CDS is required, is saved in variable temp.  This is because the process would at this stage change the value of the argument, making it impossible to complete the rest of the FOR-NEXT loop correctly.

An inner DO loop is now opened.  It repeatedly chops off the LSD of the integer stored in temp, saving the resultant in variable sum.  When all of temp's digits have been "chopped off" the outer FOR-NEXT loop moves on to the next digit of the original argument and the process is repeated.

You will see below how this extracts all the contiguous digits of the arguments, totalising them into variable sum as it goes along.

When the process is complete, the value now stored in variable sum is returned to the calling routine.


The following few lines of code do all the work.  I've numbered them to make explanations simpler.

1
2
3
4
5
6
7
8
9
10
11

def i, loop, temp, sum: int
loop = log10(c): 'get loop size
sum = 0: 'initialise sum to zero
for i = 1 to loop
    temp = c: 'copy argument
    do
        sum = sum + temp % 10^i: 'new sum
        temp = temp/10: 'chop off temp LSD
    until temp < 10^(i - 1)
next i
return sum

Let's look at the above code in detail now. 

1

def i, loop, temp, sum: int.  Line 1 sets up the local variables. loop holds one less than the length of the argument.  temp stores the argument temporarily.  sum holds the sum of the CDS's.

2

loop = log10(c).  Taking logs to the base 10 of any integer returns the logarithm of that integer.  For example, log10(8358) returns 3.9221.  However, variable loop has been declared as an integer, so the mantissa is discarded.  This means that the value stored in loop for this example, is 3, one less than the actual length of (or number of digits in) 8358. This is exactly what we need for the code that follows, as you will shortly see.

3

sum = 0.  Variable sum is going to be used to totalise the contiguous digits, adding each one to the total as it's found.  Therefore it's very important to initialise sum to zero to avoid errors.

4

for i = 1 to loop.  Opens the main FOR-NEXT loop.  This loop is used to iterate over each digit of the argument.  It doesn't actually process the argument in any way or produce any of the contiguous digits.  The inner DO loop which follows takes care of that.  Notice that the iteration will go up to one less than the length of the function's argument.  In the example given, 8358, the FOR-NEXT loop will run from 1 to 3.

5

temp = c.  This stores the value of argument c in variable temp.  This retains that value for future use, as it will be corrupted in the next few lines.

6

do.  Opens the inner DO loop.  This is where the real work of producing the contiguous digits takes place.

7

sum = sum + temp % 10^i.  Line 7 is the heart of the program.  It's easier to understand if we start at the right-hand end of the expression. 

10^i means that we raise the power of 10 the same value as is currently stored in the outer FOR-NEXT loop iterator i.  For the argument example given, 8358, i will range from 1 to 3, as explained in the line 4 comments above.  So for successive values of i, 10^i will have values of 10, 100, 1000.

The successive values are used in integer arithmetic with temp, as in
temp % 10^i.  The expression means "divide the value in temp by the value represented by 10^i and keep only the remainder."  So the three values of i for the example argument 8358 produce 8, 58, and 358 in turn for this part of the expression.

So the first run of the inner DO loop extracts 8 as its first
contiguous digit and adds it to whatever is already stored in variable sum, over-writing what was in there.  Thus, if the value in sum was initially zero, it would now read 8.

8

temp = temp/10.  The value in temp for the current example is 8358.  This division should produce 835.8.  However, temp was declared to be an integer, so the decimal part is discarded and temp now holds 835.  The real purpose of line 8, then, is simply to discard or "chop off" the rightmost digit of temp.  Line 8 can be paraphrased as "divide the value stored in variable temp by 10, discard the decimal part, and store the result back into variable temp, over-writing whatever was already stored in there.

The reason for doing this is that the DO loop can be executed again.  This time, line 7 will start with a temp value of 835.  For a value of 1 in FOR-NEXT loop iterator i, line 7 will produce a new
contiguous digit of 5.

The inner DO loop keeps going round, isolating the rightmost
contiguous digit, adding it to sum, then chopping it off, until all the digits have been dealt with.

9

until temp < 10^(i - 1).  Each time the end of the inner DO loop is reached, a decision has to be made: execute the loop again, or quit?  The time to quit is when all the digits to the right of that pointed to iterator i have been dealt with, and the expression temp < 10^(i - 1) picks that out.

10

next i.  Housekeeping - completes FOR-NEXT loop opened in line 4.

11

return sum.  When line 11 is reached, all the contiguous digits have been extracted one at a time and totalised into variable sum.  All that remains now is to pass that value back to the calling routine, and this line does just that.

I can sum up the description above in a table of results, shown below. This makes it a little easier to follow what's happening.  You will see that, when i = 1, temp gets truncated 4 times, and each time the four single-digits contiguous digits are extracted and totalised into sum.

When i = 2, temp only gets truncated 3 times.  This time, each double-digit
contiguous digit is extracted and totalised into sum.

Finally, when
i = 3, temp only gets truncated twice.  Each treble-digit contiguous digit is extracted and totalised into sum.

As required, the final value in sum is correct at 1393.

i temp temp % 10^i sum 
1
8358
835
83
8
8
5
3
8
8
13
16
24
2
8358
835
83
58
35
83
82
117
200
3
8358
835
358
835
558
1393

MAIN MENU
HOW DOES IT WORK?

Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 3rd, 2010.