[Tutor] New at Python

[Steven D'Aprano]

On Sun, Oct 05, 2014 at 06:40:39PM -0400, Mike Spaulding wrote:
> Given that n refers to a positive int use a while loop to compute the sum of
> the cubes of the first n counting numbers, and associate this value with
> total . Use no
> <http://pearson.turingscraft.com/codelab/jsp/tutor.jsp?glIndex=1&lang=PYTHON
> 3> variables  other than n , k , and total . 


Here is the thought process I would use to convert this into code. 
Actually writing code happens quite late in the process, first I try to 
understand the problem, and then and only then do I write code.

We want to "compute the sum of ...", associating that value with total. 
So write it out in English (or whatever your native language is):

    total = sum of ...

What do the ... represent? The cubes of the first n counting numbers. Do 
you remember the definition of "counting numbers"? If not, google for 
it. Understanding the problem, and the language used in the problem, is 
critical to solving the problem.

https://duckduckgo.com/html/?q=counting+numbers

The counting numbers are simply 1, 2, 3, 4, 5, ... which goes on 
forever, but fortunately for this problem we only want "the first n" 
of them. If you're familiar with mathematics, that's obvious, but what 
if you're not? Let's reason inductively.

If we wanted the first *three* numbers, we would have:

    1, 2, 3.

If we wanted the first *four* numbers, we would have:

    1, 2, 3, 4.

If we wanted the first *ten* numbers, we would have:

    1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

I'm seeing a pattern here. So if you use a pronumeral "n" to represent 
the, er, number of numbers we want, we'll have something like this:

    1, 2, 3, 4, ... n.

and we want the *cubes* of those numbers:

    1**3, 2**3, 3**3, 4**3, ... n**3.

and they go into our sum:

    total = sum of 1**3, 2**3, 3**3, 4**3, ... n**3

We're told to solve this with a while loop, using variables n, k and 
total. Let's ignore the part about the while loop for now, and 
concentrate on the variables. n and total are obviously the input and 
the output: n is the number we're working on, total is the number we 
calculate. What's k? That gives us a strong hint that we need a third 
variable.

What could it be? Since we can only add two numbers at a time (a + b) 
and we know that total is going to be one of them (total + ???) and n is 
*not* going to be the other one, that gives us a clue that k will be the 
other one:

    k = 1
    total = total + k**3
    k = 2
    total = total + k**3

etc.

Let's start with a simpler problem: ignore the requirement to cube the 
numbers, and let's just sum the natural numbers themselves:

    total = sum of 1, 2, 3, 4, ... n

We can write that as:

total = 0  # We start with nothing.
total = total + 1  # Add the first number.
total = total + 2  # Add the second number.
total = total + 3  # Add the third number.
total = total + 4  # I'm starting to see a pattern here.

and so on. Whenever you see repeated code like that, you should think of 
a loop. A for loop is actually the right solution here, but the question 
insists you use a while loop, so let's start with a little bit of 
almost-but-not-quite Python code. We use k as the loop variable, it will 
start at the first number we want to add, and increase by one each time 
through the loop:


total = 0
k = 1  # The number we're going to add to the total, starting at 1.
while there are still numbers to be added:
    total = total + k
    k = k + 1  # Go on to the next number to be added.


There's a shorter way to add an increment to a variable:

total = 0
k = 1
while there are still numbers to be added:
    total += k
    k += 1


Obviously "while there are still numbers to be added" is not Python 
code. In Python, we need "while condition". What is the condition that 
decides whether there are still numbers to be added or not?

Let's take a concrete example: n = 4. We're going to loop with:

k = 1 is used.
k = 2 is used.
k = 3 is used.
k = 4 is used.  <-- n = 4
k = 5 is NOT used.

So our condition is that k is less than or equal to n. So now we can 
insert that condition into the Python code:

total = 0
k = 1
while k <= n:
    total += k
    k += 1


Don't forget that we actually want to sum the cubes!

total = 0
k = 1
while k <= n:
    total += k**3
    k += 1


And we're done here and can move on to the next exercise. Or, we can 
continue on this one and do it *right*.


Earlier, I said that a for loop was the right solution for this, rather 
than a while loop. Using a for loop simplifies the management of the k 
variable:

total = 0
for k in (1, 2, 3, 4, ..., n)  # not quite legal Python!
    total = total + k**3


To get the values (1, 2, 3, 4, ..., n) we use the built-in Python 
function "range", which returns a sequence of numbers, given an optional 
starting value, a stopping value, and an optional stepsize or stride:

range(6) -> 0, 1, 2, 3, 4, 5
range(1, 6) -> 1, 2, 3, 4, 5
range(1, 6, 2) -> 1, 3, 5

So in this case, we want to start at 1, and end with n *included*, so 
our stopping value is n+1, and the step is just the default 1:

total = 0
for k in range(1, n+1):
    total = total + k**3


That can be simplified using a generator expression and the built-in 
sum() function:

total = sum(k**3 for k in range(1, n+1))


only you probably haven't learned about them yet. But you can probably 
see the similarity between the explicit for-loop and the generator 
expression:

for k in range(1, n+1):
    <blah blah blah> k**3

vs.

<blah blah blah>(k**3 for k in range(1, n+1))

The order is slightly different, but I hope you can see the similarity.

Can we improve this solution? Here it is again:

total = sum(k**3 for k in range(1, n+1))


Yes, we can improve it, thanks to mathematics! Can we find a simple 
equation that gives us the sum of the first n cubes? Googling for 
"sum of first n cubes" gets me to here:

https://en.wikipedia.org/wiki/Squared_triangular_number

which simplifies my code to:

total = sum(k for k in range(1, n+1))**2

I can simplify that even more, since there is a marvelous 
equation that gives the sum of the first n counting numbers. These two 
pages will give you a good feel for how to think like a mathematician 
and find patterns, which is an excellent skill for programmers too:

http://www.comfsm.fm/~dleeling/math/cogapp/sumofn.html
http://proofsfromthebook.com/2013/01/29/first-n-positive-integers/

Using that formula gives us:

total = (n*(n+1)//2)**2  # sum of the first n cubes.

which requires no other variables, no loops, and only four maths 
operations: one each addition, multiplication, division and power. For 
large values of n it will be *much* faster than summing them by hand. 
The only downside is that it isn't *obvious* that it is the sum of the 
first n cubes, but that's why # comments are available.



-- 
Steven