Week 8: Loops and Digits

Counting and Peeling

Week 8 is chapter 6 at work. Two of its programs are counted loops with accumulators: the sums of the natural, odd, and even numbers up to N, and the first N Fibonacci numbers. The other two are the loop that every number-theory exercise in the syllabus is built on, the digit-peeling loop: n % 10 is the last digit, n / 10 is the number without it, and repeating those two operations until nothing is left visits every digit in turn. Learn that loop this week and the palindrome, the digit sum, the Armstrong number, and every cousin of theirs on an exam paper become the same program with a different body.

All four programs refuse inputs that would overflow. That looks like fussiness in a lab program; it is the difference between a loop whose every iteration is defined and one that stops being C part way through.

Program 1: Sums of the Natural, Odd, and Even Numbers up to N

Algorithm:

1. Start.
2. Read N; if it is below 1 or above 60000, print a message and stop.
3. Set three sums to 0.
4. For i from 1 to N: add i to the natural sum, and to the even sum if i is even, otherwise to the odd sum.
5. Print the three sums.
6. Stop.

10 gives 55, 25, and 30, and the three always satisfy natural = odd + even, which is the check to run in your head on any input. The shape is the chapter 6 accumulator: a total that starts at 0 and a loop that adds one term per pass. One loop does all three sums, because the if inside it routes each i to one of the two smaller totals as well as the big one; three separate loops would be correct and three times the work.

The sums are long and N is capped at 60000 for one reason: the sum of 1 to 60000 is a little over 1.8 billion, which fits in the 32 bits C89 guarantees a long, and 1 to 70000 would not. On this platform long is 64 bits and the loop could run to N in the billions, but the program is written to the standard, not the laptop, and signed overflow is undefined behaviour rather than a wrong answer.

Program 2: The First N Fibonacci Numbers

The sequence starts 0, 1, and every later term is the sum of the two before it.

Algorithm:

1. Start.
2. Read N; if it is below 1 or above 45, print a message and stop.
3. Set first to 0 and second to 1.
4. Repeat N times: print first, then set next = first + second, first = second, second = next.
5. Stop.

10 prints 0 1 1 2 3 5 8 13 21 34. The three assignments at the bottom of the loop are week 2's rotation again: the window of two terms slides one place along the sequence each pass, with next as the temporary. Printing first before the shuffle is what makes term 1 come out as 0; shuffle first and the sequence starts at 1, which is the commonest wrong output.

The separator is handled by printing a space before every term except the first, so there is no trailing space at the end of the line. That detail decides whether an automatic checker accepts the output, and it is a habit worth having before the checker is a person. The cap of 45 comes from the shuffle computing two terms beyond the one just printed: after printing the 45th term it forms the 47th, 1836311903, which is the largest Fibonacci number that fits in 32 bits. One more and the addition overflows.

Program 3: Sum of Digits, Reduced to a Single Digit

Add the digits of a number; if the result has more than one digit, add its digits; repeat until one digit remains. 9875 becomes 29, then 11, then 2.

Algorithm:

1. Start.
2. Read N; if it is below 1, print a message and stop.
3. Print N.
4. While N has more than one digit: set sum to 0; while N is not 0, add N % 10 to sum and set N to N / 10; set N to sum and print it.
5. Stop.

9875 prints 9875 -> 29 -> 11 -> 2, and 7 prints just 7, since a single digit is already the answer and the outer loop never runs. The inner loop is the digit peeler: n % 10 is 5, then n / 10 leaves 987, and four passes later n is 0 and the loop ends. The outer loop's test, n >= 10, is the plain way to say "has more than one digit". Note that the inner loop consumes n, which is why the sum is copied back into it before the next round, and why sum is reset to 0 at the top of each outer pass rather than once before the loop. Forgetting that reset is the bug that prints 40 where 11 should be, and then never stops, because a running total that is never cleared only grows.

Program 4: Reverse a Four-Digit Number and Test for a Palindrome

Algorithm:

1. Start.
2. Read N; if it is not between 1000 and 9999, print a message and stop.
3. Save N and set reversed to 0.
4. While N is not 0: set reversed to reversed × 10 + N % 10, and N to N / 10.
5. Print the saved number and reversed.
6. If reversed equals the saved number, print that it is a palindrome; otherwise print that it is not.
7. Stop.

1221 is a palindrome and 1234 is not. The reversal is the digit peeler with a builder on the front: each peeled digit is appended to reversed by multiplying what is there by 10 first, so the last digit of the input becomes the first digit of the result. The copy into original is needed for the same reason as in program 3: the loop destroys n.

Try 1200. It prints 1200 reversed is 21, not 0021, because 21 is the integer the loop builds and integers have no leading zeros, and it is not a palindrome, which is correct. An answer key that expects 0021 is thinking of the digits as a string; this program is working with a number, and the range check on step 2 is what stops that distinction from mattering for the input the syllabus specifies.

Key Takeaways

• An accumulator starts at 0 and a counted for adds one term per pass; one loop can feed several accumulators through an if.
• Cap the input so that every sum stays inside the 32 bits C89 guarantees a long; overflow is undefined behaviour, not a wrong number.
• Fibonacci is a two-term window slid along by three assignments; print before the shuffle, and separate terms with a space before every term but the first.
• The digit peeler: n % 10 is the last digit, n / 10 drops it, loop until n is 0. It destroys n, so copy n first if you need it later.
• Reset an inner accumulator at the top of every outer pass, not once before the outer loop.
• Reversing builds a number with reversed * 10 + digit; trailing zeros vanish because the result is a number, not a string.