Flow chart
The flow chart requires two numbers, M and N. Select several values
for M and try to establish what the flow chart does.
Age
11 to 14
Challenge level
Problem
Flow charts give very precise instructions, to perform a task or calculation.
The flow chart below uses three variables of which you can choose the starting value for M.
Select several values for M and try to establish what the flow chart does.
A printable version of the flow chart is available here
Image
If you start with certain numbers you reach the OUTPUT fairly quickly, but if you start with other numbers you don't.
e.g. if you start with 144 you reach the OUTPUT a lot sooner than if you start with 145.
What is special about the numbers that lead to an OUTPUT quickly?
What is special about the numbers that don't?
Certain values of D divide exactly into M during the procedure?
What is special about these values of D?
What is special about the value of N that you end up with?
How can the flow chart help you determine whether M is prime?
Getting Started
Use a table of values to keep track of M, D and N as they
change.
Student Solutions
Vivek from UWCSEA showed a very clear understanding of what the flow chart does:
The numbers that lead to an output quickly have very small
prime factors.
The numbers that don't, have very large prime factors.
The numbers that don't, have very large prime factors.
The values of D that divide exactly into M are all prime
numbers.
The value of N is the number of prime factors that the number
has (e.g. 12 can be expressed as the product of 3 prime factors - 2
x 2 x 3 and the output when M = 12 is 3).
The flow chart helps you determine whether M is prime because
if M is prime, the output is always 1: M can only be divided by D
when D is the prime number itself. This makes it go around in a
continuous loop without adding anything to N until M is divided by
D (which equals to M), so N is always 1 when M is prime.
Teachers' Resources
Why do this problem?
This problem is about flow charts, factors and prime factorisation.Possible approach
Teachers can present the flow chart to students and ask them to try to figure out what to do with it. A table of values can be drawn on the board to collect results.
There won't be an obvious algebraic relationship emerging but this might be a good opportunity to emphasise the need to look at the underlying mathematics rather than just the values. Discussion with the group can draw out comments and observations about what the flow chart is doing.
Students can then be directed to the questions in the problem.
If the group hasn't had much experience of using flow charts, some time could be set aside to discuss the merits of flow charts (efficient, clear, unambiguous) and some of their drawbacks (repetitive, tedious - try starting with a large prime number!).
Possible extension
Students can be asked to produce a flow chart that finds the
Highest Common Factor or Lowest Common Multiple of two inputs. Half
the class could work on the HCF while the other half works on the
LCM. They could then swap and test each other's flow charts.
Possible support
Suggest to students that they use a table of values to keep
track of M, D and N as they change.