Floyd's triangle with Python loops

Why this matters

Floyd's triangle is a number pattern. The first row has one number, the second row has two, the third row has three, and so on. The numbers count up from 1. They never skip and never repeat, so each row starts right after the last number of the row above it.

The pattern is small, but it teaches a skill that many programs need: keeping a value that carries from one loop pass to the next. In the other shapes in this module, the loop position alone decides what to print, such as the row number or the column number. Floyd's triangle also needs a counter, a variable that goes up by one each time a number is printed and is never set back to its start value. Forgetting to keep the counter running is the main mistake this lesson is about.

Pascal's triangle, the lesson before this one, builds each number from the numbers above it. Floyd's triangle needs no such rule. The next lesson in this module, Building rows as strings, changes how each row is printed.

Terms used here

A row is one horizontal line of the triangle. A column is a position inside a row, counted from 1 at the left.

A variable is a name that points to a value, such as next_number = 1. Python does not ask you to declare the type of a variable first, so that one line is the whole declaration.

A counter is a variable that changes by one each time something happens. In this lesson the counter is called next_number, because it holds the next number to print. The name next would also work, but Python has a built-in function called next, and a variable with that name would hide it.

A range is what range(1, 5) makes: the numbers 1, 2, 3 and 4. It starts at the first number and stops before the second. So range(1, rows + 1) gives the numbers 1 to rows, and a loop over it runs rows times.

A right-angled triangle here means a triangle that is flat on the left and has a square corner at the bottom left. Every row starts at the left edge, and each row is one number longer than the row above it.

The idea from first principles

Here is a Floyd's triangle with four rows:

1
2 3
4 5 6
7 8 9 10

Look at the shape first. Row 1 has 1 number, row 2 has 2, row 3 has 3, and row 4 has 4. Row number r has exactly r numbers. That tells you how far the inner loop runs: from column 1 up to the row number. In Python, that is range(1, row + 1).

Now look at the numbers. Row 2 starts at 2, one more than the last number of row 1. Row 3 starts at 4, one more than the last number of row 2. Nothing is reset between rows. So one variable has to hold the next number to print. It starts at 1 and goes up by one every time a number is printed.

Put together, the program has three parts:

1. An outer loop for the rows, for row in range(1, rows + 1).
2. An inner loop for the columns, for col in range(1, row + 1).
3. The variable next_number, set to 1 before the outer loop starts and changed only inside the inner loop.

The counter is set before the loops, not inside them. If it were set inside the outer loop, every row would start again at 1. The mistakes section shows exactly that.

Worked example 1: the first triangle

This program prints a triangle with 4 rows. It puts a space between numbers, but not before the first number in a row or after the last one.

The output is:

1
2 3
4 5 6
7 8 9 10

Trace the program. rows is 4 and next_number is 1. The outer loop starts with row 1. The inner loop runs once, because range(1, 2) holds only the number 1. The if does nothing, because col is not greater than 1. The program prints next_number, which is 1. The end="" part tells print to end the line with nothing, instead of its usual newline, so the next output stays on the same line. Then next_number becomes 2. The inner loop ends, and print() with no value moves the cursor to a new line.

Row 2 runs the inner loop twice. In the first pass, col is 1, so no space is printed, and the program prints 2. Then next_number becomes 3. In the second pass, col is 2, so the if prints a space, and the program prints 3. Then next_number becomes 4. The row ends.

The if col > 1 check is there so the first number in each row has no space in front of it. The other way to get the same output is to print a space after every number. That leaves a space at the end of each line. A space at the end of a line is invisible, but a program that compares output word for word will see it as a difference.

Count the work. Row row runs the inner body row times, so four rows print 1 + 2 + 3 + 4 = 10 numbers. The counter ends at 11 after the loops, one more than the last number printed. Worked example 3 uses that fact.

Worked example 2: where is a given number?

The next problem runs in the other direction. Given a number such as 50, which row and which column hold it? You could print the whole triangle and look, but a triangle with a hundred thousand rows is too large to print. The better method is to walk down the rows without printing anything.

Each row starts at a known number. Row 1 starts at 1. Row 2 starts at 2, because row 1 has one number. Row 3 starts at 4, because rows 1 and 2 have 1 + 2 = 3 numbers. In general, a row of length row that starts at first_of_row ends at first_of_row + row - 1. The next row starts one number after that.

So the method is:

1. Start with row 1 and its first number, 1.
2. Find the last number of the current row, which is first_of_row + row - 1.
3. If the target is larger than that last number, the target is in a later row. Skip this row by adding its length to first_of_row and adding 1 to row. Go back to step 2.
4. If the target is not larger, it is in this row. Its column is target - first_of_row + 1.

The code uses a while loop for step 3. A while loop repeats its body as long as its condition is true, so it suits this case, where the number of rows to skip is not known in advance.

The output is:

1 is in row 1, column 1
2 is in row 2, column 1
3 is in row 2, column 2
7 is in row 4, column 1
10 is in row 4, column 4
11 is in row 5, column 1
21 is in row 6, column 6
50 is in row 10, column 5

The first line, def find_position(target):, starts a function. A function is a named block of code that you can call with a value and get a result back. The text in triple quotes under the first line is a docstring, a short note that tools such as help() show to the reader. return row, column sends two values back at once, as a tuple. A tuple is an ordered group of values. The line row, column = find_position(t) splits the tuple into two names.

Trace the number 10. The loop starts with row 1 and first_of_row 1, whose last number is 1. Since 1 is less than 10, the loop skips row 1. It sets first_of_row to 2 and row to 2. Row 2 ends at 2 + 2 - 1 = 3, which is still less than 10, so it skips row 2. It sets first_of_row to 4 and row to 3. Row 3 ends at 4 + 3 - 1 = 6, so it skips row 3 too. Now first_of_row is 7 and row is 4. Row 4 ends at 7 + 4 - 1 = 10. The test 10 < 10 is false, so the loop stops. The column is 10 - 7 + 1 = 4.

The number 50 shows the same method over more rows. Row 10 starts at 46, because rows 1 to 9 hold 45 numbers. It ends at 55. The column is 50 - 46 + 1 = 5, which matches the output.

The loop does one step per row it skips. To reach a number near n, it must skip about the square root of 2 times n rows, because the rows up to row r hold about r times r divided by 2 numbers. For a number near one million, that is about 1,400 steps. When this program was run with 1,000,000 as the target, the loop took 1,413 steps. For a number near one billion, it takes about 44,700 steps. The method is fast enough for numbers in the billions, and it never builds the triangle in memory.

Worked example 3: sums and the counter after the triangle

The third example uses the counter in two more ways. It adds up each row, and it prints the counter after the triangle is finished. The counter is the same variable as before. It is not reset between rows.

The output is:

row 1: starts at 1, sum 1
row 2: starts at 2, sum 5
row 3: starts at 4, sum 15
row 4: starts at 7, sum 34
row 5: starts at 11, sum 65
total of all numbers: 120
next value after the triangle: 16

There are two new details here.

The first is that first_of_row is copied from next_number before the inner loop starts. The inner loop changes next_number many times, so the copy is the only way to remember where the row began. Row 3 starts at 4, which is the value of next_number when row 3 began.

The second is the order of the two lines inside the inner loop. row_sum += next_number comes before next_number += 1. The sum uses the current value of next_number, and then the counter moves on. If the two lines were swapped, every number in the sum would be one too big.

The inner loop uses for _ in range(row):. The name _ marks a loop value that the body does not use. The loop only needs to run row times, so the value itself is not needed.

The total is 120. That equals the sum of the numbers 1 to 15, which is 15 times 16 divided by 2. The final counter value is 16. The counter is always one more than the last number printed, so the printed numbers run from 1 to 15. The triangle with 5 rows has 1 + 2 + 3 + 4 + 5 = 15 numbers.

Common mistakes

Resetting the counter inside the outer loop

The counter must start once, before the rows. Moving it into the outer loop makes each row start at 1.

The output is:

1 
1 2 
1 2 3 
1 2 3 4 

Every row starts at 1 because next_number = 1 runs again at the start of each row. The fix is to move that line above the outer loop.

Forgetting to move the counter

If next_number += 1 is missing, the counter never changes.

The output is:

1 
1 1 
1 1 1 
1 1 1 1 

No error is reported. The program runs and prints the wrong numbers. When a pattern prints the wrong values but no error, check each variable that should change, and find the line that changes it.

Using the wrong inner bound

The inner loop must run row times, so its range must be range(1, row + 1). With range(1, row), the range stops one step earlier, and the inner loop runs one time fewer in each row. Row 1 runs zero times.

The output is:

 
1 
2 3 
4 5 6 

The first line is empty, because row 1 prints nothing. Every other row is one number short, so the triangle has the wrong shape. Each row also has one fewer number than its row number, which breaks the counting rule from the start of the lesson.

Stopping the outer loop one row early

The end of a range is not included. range(1, rows) gives the numbers 1 up to rows - 1. This is the same off-by-one mistake as the inner bound, but in the outer loop.

The output is:

1
2 3
4 5 6

Row 4 is missing. The fix is range(1, rows + 1).

Integers do not wrap around

Some languages store whole numbers in a fixed number of bits. When such a counter goes past its largest value, it wraps around to the most negative value and keeps counting from there, and no error is shown. Python does not do this. A Python int grows to hold any whole number, so the counter keeps going.

The output is:

9223372036854775807
9223372036854775808
9223372036854775809

Python keeps going past 2**63 - 1, the largest value a signed 64-bit counter can hold. A very large number takes more memory and more time to work with, but it is never wrong.

A missing colon

Python needs a colon at the end of each line that starts a block, such as a for line. Leaving it out stops the program before it runs. Python reports the line where it expected the colon.

rows = 4
next_number = 1
for row in range(1, rows + 1)
    for col in range(1, row + 1):
        print(next_number, end=" ")
    print()

Running this file gives:

  File "<folder>/main.py", line 3
    for row in range(1, rows + 1)
                                 ^
SyntaxError: expected ':'

The path in the first line depends on where the file is saved. The caret points just past the ), which is where the colon belongs. The error names line 3, so that is the first place to look. Add the colon and the error goes away.

Practice

Exercise 1: Five rows

Print a Floyd's triangle with 5 rows. Use the same two loops as worked example 1, with a space between numbers and none at the ends of a row.

Show the answer

The output is 1, then 2 3, then 4 5 6, then 7 8 9 10, then 11 12 13 14 15, each on its own line.

Exercise 2: The sum of each row

For a triangle with 5 rows, print the sum of the numbers in each row. Use the counter. Do not use a formula.

Show the answer

The output is:

row 1 sum 1
row 2 sum 5
row 3 sum 15
row 4 sum 34
row 5 sum 65

Exercise 3: Find the number 100

Change worked example 2 so that it finds the row and column of 100. Work out the answer by hand first, then run the program to check it.

Show the answer

Row 13 ends at 91, and row 14 starts at 92 and ends at 105. So 100 is in row 14, column 100 - 92 + 1 = 9.

The output is:

row 14, column 9

Exercise 4: Count the numbers

For a triangle with n rows, count how many numbers it prints using two nested loops. Print the count, then print n times n + 1 divided by 2 for the same n. The two values should match. Use n equal to 5.

Show the answer

The output is:

numbers printed: 15
formula n(n+1)/2: 15

The inner loop runs row times for each row, so the total is 1 + 2 + ... + n. The formula gives the same answer, and that matches the check in worked example 3. The formula uses //, which divides and keeps only the whole part of the result. With / in its place, Python gives a number with a decimal point, and the last line would print 15.0.

Exercise 5: Reverse each row

Change the triangle so each row prints its numbers from largest to smallest. Row 3 should print 6 5 4 instead of 4 5 6. The counter must still move on correctly to the next row. Use 4 rows.

Show the answer

Each row keeps its first number in first. A number at column col in a row of length row is first + (row - col), which gives the largest number at column 1. After the row, next_number moves to the first number of the next row, which is first + row.

The output is:

1
3 2
6 5 4
10 9 8 7

Summary

• Row number r has r numbers, so the inner loop runs over range(1, row + 1).
• One counter, set once before the outer loop, carries the numbers from row to row.
• Setting the counter inside the outer loop makes every row start at 1, and forgetting to change it makes every number 1.
• Walking the rows and adding each row's length finds the row and column of a number without printing the triangle.
• Python integers do not wrap around, so the counter can keep growing past any fixed limit.