Coding Stories: Exploring Factors

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)
OUTPUT:
2 has 2 factors.
3 has 2 factors.
4 has 3 factors.
for j in range(2,i//2+1)
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.
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 factors
Sieve of of Eratosthenes

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.

[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^1
  • 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.
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]
Highly Composite Numbers on Wikipedia

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Greg Benedis-Grab

Greg Benedis-Grab

79 Followers

exploring the intersection of coding, education and disciplinary knowledge