3  A Small Example Program

3.1 What Skills Are Needed for Programming?

  • Thinking in algorithms:
    What steps are required to solve the problem? What data must be stored, what data structures must be created? What cases can occur and must be recognized and handled?
  • Implementing the algorithm in a program:
    What data structures, constructs, functions… does the programming language provide?
  • Formal syntax:
    Humans understand ‘broken English’; computers don’t understand ‘broken C++’ or ‘broken Julia’. The syntax must be mastered.
  • The “ecosystem” of the language:
    How do I run my code? How do the development environments work? What options does the compiler understand? How do I install additional libraries? How do I read error messages? Where can I get information?
  • The art of debugging:
    Programming beginners are often happy when they have eliminated all syntax errors and the program finally ‘runs’. For more complex programs, the work only just begins, as testing, finding, and fixing errors in the algorithm must now be done.
  • Intuition for the efficiency and complexity of algorithms
  • Specifics of computer arithmetic, especially floating point numbers

These cannot all be mastered at once. Be patient with yourself and ‘play’ with the language.

The following examples should serve as inspiration.

3.2 Project Euler

A nice source for programming tasks with mathematical character and very different levels of difficulty is Project Euler. The tasks are designed so that no inputs are necessary and the desired result is a single number. This allows you to fully concentrate on programming the algorithm.

3.2.1 Example 1

NoteProject Euler Problem No. 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

  1. Algorithm:

    • Test all natural numbers <1000 for divisibility by 3 or 5 and
    • sum the divisible numbers.

  2. Implementation:

    How does Julia provide the remainder of integer division? Functions like this are typically called rem() (for remainder) or mod(). You can look it up in the documentation or try ?rem and ?mod in the Julia REPL. Both functions exist; the difference lies in the treatment of negative integers. For natural numbers n,m, mod(n,m) and rem(n,m) give the same result, and the latter also has the infix form n % m.

    How does one test a sequence of values and sum them up? There is a standard pattern: for loop and accumulator variable:

s = 0                               # initialize accumulator variable
for i in 1:999                      # loop   
    if i % 3 == 0 || i % 5 == 0     # test
        s += i                      # add to accumulator 
    end                             # end test
end                                 # end loop
println("The answer is: $s")        # output result
The answer is: 233168

Of course, this can also be done a bit shorter:

sum([i for i in 1:999 if i%3==0||i%5==0])
233168

3.2.2 Example 2

NoteProject Euler Problem No. 92

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

Programs can be developed top-down and bottom-up. Top-down would probably mean here: “We start with a loop for i = 1:9999999.” The other approach works through individually testable components and is often more effective. (And with a certain project size, one approaches the goal from both ‘top’ and ‘bottom’ simultaneously.)

Function No. 1

We want to investigate how numbers behave under repeated calculation of the ‘square digit sum’ (sum of squares of digits). Therefore, write and test a function that calculates this ‘square digit sum’.

function q2sum(n)
    s = 0                         # accumulator for the sum
    while n > 9                   # as long as n is still multi-digit...
       q, r = divrem(n, 10)       # calculate integer quotient and remainder of division by 10
       s += r^2                   # add squared digit to accumulator
       n = q                      # continue with the number divided by 10
    end
    s += n^2                      # add the square of the last digit
    return s
end

Let’s test it now:

for i in [1, 7, 33, 111, 321, 1000, 73201]
   j = q2sum(i)
   println("Square digit sum of $i = $j")
end
Square digit sum of 1 = 1
Square digit sum of 7 = 49
Square digit sum of 33 = 18
Square digit sum of 111 = 3
Square digit sum of 321 = 14
Square digit sum of 1000 = 1
Square digit sum of 73201 = 63

In the spirit of the task, we apply the function repeatedly:

n = 129956799
for i in 1:14
    n = q2sum(n)
    println(n)
end
439
106
37
58
89
145
42
20
4
16
37
58
89
145

… and we have now hit one of the ‘89-cycles’.

Function No. 2

We need to test whether repeated application of the function q2sum() finally leads to 1 or ends in this 89-cycle.

function q2test(n)
    while n !=1 && n != 89       # as long as we have not reached 1 or 89...
        n = q2sum(n)             # repeat 
    end
    if n == 1 return false end   # not an 89 cycle
    return true                  # 89 cycle found
end

… and with this, we can solve the task:

c = 0                        # once again an accumulator
for i = 1 : 10_000_000 - 1   # this is how you can separate thousands for better readability
    if q2test(i)             # q2test() returns a boolean, no further test needed 
        c += 1               #    'if x == true' is redundant, 'if x' is perfectly sufficient 
    end     
end
println("$c numbers below ten million arrive at 89.")
8581146 numbers below ten million arrive at 89.

Numbers for which the iterative square digit sum calculation ends at 1 are called happy numbers; all other numbers eventually reach the 89-cycle.

Here is the complete program again:

function q2sum(n)
    s = 0                      
    while n > 9                 
       q, r = divrem(n, 10)
       s += r^2                 
       n = q                    
    end
    s += n^2                    
    return s
end

function q2test(n)
    while n !=1 && n != 89      
        n = q2sum(n)           
    end
    if n==1 return false end   
    return true                 
end

c = 0
for i = 1 : 10_000_000 - 1   
    if q2test(i)
        c += 1
    end     
end
println("$c numbers below ten million arrive at 89.")
8581146 numbers below ten million arrive at 89.