Coding Stories: Exploring Factors
During my life, computing has served as a vehicle to express myself, think more deeply about the world and engage in the learning process. When I was ten years old I was given a Commodore 64 by my parents and I learned how to code in BASIC. I was not the most outgoing kid so I used the computer to make games that would entertain me. When I was in college I had a summer job in a Physics lab. My supervising professor told me to make a computational model of Tungsten. I learned to program in C and how to make a Monte Carlo simulation. When I became a science teacher I included programming in my classroom to get students excited about science and to explore the natural world through computing. In my current job I teach computing classes to students and try to help teachers find where computing fits into their teaching. This blog is a chance to share my stories about coding and learning.
I was sitting in my office when a mathematics problem came in from one of the advanced mathematics courses at my school. The teacher of the course, stated the problem in an email to me:
For the set of n natural numbers, {1, 2, …, n}, identify the element of the set that has the largest number of factors.
I thought this would be a good exercise for my Advanced Topics Computer Science students. When I got to class later that day I wrote the problem on the board as a warmup. My students worked in pairs to come up with a way to approach this problem. I often encourage them to sketch out their ideas before formally writing them in a computing language. This can be referred to as pseudocode but I like the term sketching. Here is an example.
Look at each number { 1,2,3,4,5.... n }
For each of the above #'s look at the the #'s {1 to that number
Check if the second number divides into the first number evenly
For each of the first numbers report the count of even divisions (factors)Developing a clear approach to a problem is always harder than a student thinks it is. However, once you figure this out, and assuming you know a computing language, it is pretty easy to write some code. Here is a Python version of the above pseudocode.
OUTPUT:
2 has 2 factors.
3 has 2 factors.
4 has 3 factors.One of the things I like about coding is that it makes you think about exactly what you are doing. In other words you think more about your thinking. It seems simple to find the factors of a number but we had to formalize all the steps involved in finding those factors in order to get the computer to do it for us. My class had experience with solving these kinds of problems so this code was not that hard for them to write.
As a class we talked about the different ways my students approached the problem in their code. During the discussion the students talked about improving the efficiency of the algorithm. They realized that you could reduce the time taken by only checking the divisors from 2 to half the number. We rewrote the 4th line from above.
for j in range(2,i//2+1)This approach misses two factors but since it always misses the same two (1 and the number itself) we can just add a value of 2 to count before printing it out. Finding ways to improve your algorithm in terms of efficiency and organization is a really important part of computing so I try to address it in many of my lessons.
So far this algorithm only tells you how many factors each number from 1 to n has and does not figure out which ones have the most. So we developed another algorithm to find the maximum number of factors and even append equivalently factor rich numbers to a list. Below is the sketch for an idea that a student shared to keep track of the number with the most factors.
Declare variables max_count=0 and max_factors=0.
In the loop check if count is greater than max_count
If it is greater then store max_count and the number in max_factors.My students were excited to have solved the problem. We set n = 10⁴ and got the answer: 7560 has 64 factors. A few of the groups figured out how to keep track of all the numbers with the most factors and also found that 9240 has 64 factors as well.
A few days later I visited the mathematics class to talk about the problem with them. The students in his class were not enrolled in computer science so I asked them to work in pairs to develop step by step instructions to tell a computer how to find which number has the most factors. After they developed an approach we wrote a program in Python together. With some help from me they created very similar code to what my computer science students created. The math students also realized another efficiency that you can see implemented below. All the highly factored numbers are even so you don’t have to check the odd ones. This reduces the time taken by a factor of 2. In CS we call the amount of time taken the time complexity of an algorithm. Below is a more final version of the code that finds all the numbers up to n that have the most factors.
OUTPUT:
The following numbers in the set { 1, . . . 100 } have the most factors
60 with 10 factors
72 with 10 factors
84 with 10 factors
90 with 10 factors
96 with 10 factorsThe students were excited that a computer could solve a math problem. One of them said, “now we don’t need math anymore. We can use computers.” I love the intersection of humor and problem solving so I laughed at his joke. However, I don’t think this student realized at the time that using computers means you in fact need math even more.
In fact, despite our ability to solve the stated problem there was an important limitation that we had not yet addressed. They had set out to find the answer for n = 10⁶. When we ran the code for this value it did not finish by the end of the class. In fact part of the motivation of having me come in was that they wanted to check if the solution listed in the textbook for one million was correct. We had a conversation about time complexity and Big O notation. I ran the above code in terminal for n=10,000 and it took 1.2 seconds. We estimated the number of calculations to be ≈ 1/8 n² . Based on the 𝑛² term in the time complexity we determined that 𝑛=10⁵ would take ≈ 125 seconds and 𝑛=10⁶ about 3 hours. Big O notation is a way of estimating how the time an algorithm takes depends on the parameters of the problem such as n. In this case the time complexity is proportional to n². We could wait the three hours to get the answer but what if we wanted to solve for even higher values of n.
The Sieve of Eratosthenes
I actually had been thinking about this issue after my CS students had tackled it and I was wondering if prime factors would help. As I was writing a program to find prime factors I came across a very cool Wikipedia entry with the following animation.
The Greek mathematician Eratosthenes came up with a procedure where he simply eliminated all the multiples of numbers and then used the non-eliminated numbers to generate a list of primes. If you watch the animation a few times the color coding helps make clear how it all works. It turns out that this approach to coming up with primes is much faster than checking each number one at a time. There is also a clever trick in the animation that surprisingly works. Each multiple is only added starting at its squared value.
Factors by Multiples Animation
As I was staring at the animation I realized I could use a similar approach to find the factors of numbers. For each number from 1 to n, I could step through the multiples up to n and then append them to a list indexed with the corresponding number. By checking how many multiples were assigned to each number I would know the factor count. I realized that I needed an animation to explain this idea and so I used p5 to create the Factors by Multiples sketch shown below. In the process I also learned how to use CCapture to turn my p5 sketch into an animated GIF.
I showed my animation to the the mathematics class and asked them what they noticed. They were able to explain the idea better than I could and seemed to appreciate that this was a useful approach to the problem. In the simple example above where n=64, you start by adding the factor 2 to all the multiples of 2 on the grid. Then you add 3 to all the multiples of 3 and so on up to 64. As you get to each factor you can then see based on what has been added how many factors it has. In the animation I control the shade of the box based on the number of factors to give a visual cue as to which numbers are factor rich. Maybe in another exploration I will do something more artistic with this idea. We talked in the class about the time complexity or in other words how long this process takes.
For the factor 2 you need to add it to 𝑛/2 cells on the grid. 𝑛/2 represents all of the multiples of 2 which appear on the grid. For the factor 3 you need to add it to 𝑛/3 cells. The pattern continues.
The students were pretty good at evaluating sums. We first agreed that this was a divergent sum. However, we could approximate its value based on n. We arrived at an answer of 𝑛⋅ln(𝑛) That expression diverges much slower than 𝑛² so as n gets larger it is much faster to use the second approach. I was excited about this because from an innocent mathematics problem we had arrived at a very important idea in computing. The time complexities that we had found expressed in big O can be written. 𝑂(𝑛²) and 𝑂(𝑛𝑙𝑜𝑔𝑛). It turns out that these are frequently encountered time complexities in search and sorting algorithms.
Factors by Multiples Python Code
I decided to write the code in python myself. Try it out below. It has no problem handling 𝑛=10⁶’
I could make it even faster with a compiled language such as Java or C++ but at some point I would hit a limit of time. One billion would still take more than a class period. This is when the problem got even more interesting.
Prime Factorization Approach
I asked the class how they were solving this problem before I showed up. They told me about prime factorization and some simple rules about how many factors a particular prime factorization has. Take the number 60 which happens to be factor rich.
60=2²⋅3¹⋅5¹
The number of factors of 60 can be calculated by multiplying each of the exponents plus 1. So for 60 we have (2+1)(1+1)(1+1)=12 At first I was not sure how this information would be helpful. To find the prime factorizations of all the numbers from 1 to n would take longer than the Eratosthenes inspired Python algorithm above. However, it turns out that I was missing the point. Unfortunately the class period was coming to an end. Luckily one of the students was excited about figuring out the answer to this problem. He set up a time to meet with me the next day. When we started talking I realized that we did not need to find all the prime factorizations. We just needed to find all the ones with the most factors. In computer science this is called a greedy approach. We would generate prime factorizations directly instead of computing them from all the natural numbers. To solve this problem we needed to be careful how we set it up.
First we needed a good way to represent prime factorizations. A list of exponents seemed like a reasonable way to do this. I shared this idea with the student who was somewhat new to coding. Below I show how a list of exponents can be used to show the number 60.
[2,1,1]=2²⋅3¹⋅5¹=60
The position of the exponent in the list corresponds to a specific prime. I also came up with some functions based on the prime factorizations shown below.
OUTPUT:
the prime factorization [2, 1, 1] has a value of 60
the prime factorization [2, 1, 1] has 12 factors
the prime factorization [2, 1, 1] should be written, 2^2*3^1*5^1Then we developed a few conjectures to help us find a greedy solution.
- The exponents should be non-ascending as any list that is not non-ascending could be swapped to a non-ascending list with the same number of factors but a lower value.
- There is no need for a 0 exponent in between non-zero exponents. This involves the same reasoning as the non-ascending rule.
- If you can increase any of the exponents and still not exceed n you should. Adding a prime to the list always increases the number of factors.
Keep in mind that these rules might not give you all the solutions but for the moment our goal it to find the lowest number with the most factors. Later perhaps you can come up with a way to generate the other solutions as they will be related to the ones generated by this algorithm.
Here is a system for generating all those prime factorizations that I am thinking about. Let’s say n=100. First lay out as many prime factors as you can. In this case you can lay out 3 primes. That gives you
[1,1,1]=2⋅3⋅5=30
You can’t include the 7 because 30⋅7=210 But you can still include another 2 giving you [2,1,1]=60. You can’t include another 3 at this point because that results in 180 which exceeds n. So in other words you keep adding the primes in order until you can’t any more. Here is what it might look like in code.
This is a confusing algorithm so I decided another animation in p5 would help clarify what I am doing. Eventually I would like to make this animation interactive where you can change the speed and the value of n.
So the first greedy prime factorization for n=100 is [2,1,1]. Now how can we find the next one. Well I could reduce the 5 exponent from 1 to 0. If I followed the above routine for two primes I would get. [3,2] = 72. Next I could reduce the exponent on the 3 from 2 to 1. That would give me [5,1] = 96. All three of these have 12 factors. The last step in my routine would be to eliminate the 3 which leaves us with [6] = 64. But that only has 7 factors. So for all the numbers from 1 to 100 I only need to check 4 prime factorizations. That is quite efficient. Unfortunately I missed two of the solutions that we found previously. [2,1,0,1] = 84 and [1,2,1] = 90. I would argue that we could come up with another algorithm to generate these solutions from the original base solutions. I will leave that as an exercise for the reader. Below is some python code to better define the algorithm for generating prime factorizations that I described above.
OUTPUT:
840 has 32 factors pf: [3, 1, 1, 1, 0, 0, 0, 0, 0]
900 has 27 factors pf: [2, 2, 2, 0, 0, 0, 0, 0, 0]
720 has 30 factors pf: [4, 2, 1, 0, 0, 0, 0, 0, 0]
960 has 28 factors pf: [6, 1, 1, 0, 0, 0, 0, 0, 0]
864 has 24 factors pf: [5, 3, 0, 0, 0, 0, 0, 0, 0]
576 has 21 factors pf: [6, 2, 0, 0, 0, 0, 0, 0, 0]
768 has 18 factors pf: [8, 1, 0, 0, 0, 0, 0, 0, 0]
512 has 10 factors pf: [9, 0, 0, 0, 0, 0, 0, 0, 0]Based on this algorithm we can see the numbers that have the most factors. The next step is to refactor the code to make it easier to read and also include a way to search for the highest factors. Note that I set 𝑛=10⁹ and it runs in a short time. Clearly it has a time complexity much smaller than 𝑛⋅𝑙𝑛(𝑛). I included a repl.it sketch of my code so that you can play around with it.
I shared this story because I love the progression of thinking that took place as I moved from one phase of the project to the next. I am hopeful that by telling these stories I can engage in more conversations about these ideas with a wider audience of people. Eventually I want to come back to this topic and think about interesting ways to visualize the mathematical properties of numbers. As an addendum to this story I will include another way to think about factors.
A highly composite number is a positive integer with more divisors than any smaller positive integer has. The term was coined by Ramanujan (1915). On Wikipedia I found a visualization of factor counts that seemed like a nice way to conclude this story.
