# 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 numberCheck if the second number divides into the first number evenlyFor 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_countIf 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 factors60 with 10 factors72 with 10 factors84 with 10 factors90 with 10 factors96 with 10 factors`

# 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 60the prime factorization [2, 1, 1] has 12 factorsthe 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]`

--

--

## More from Greg Benedis-Grab

exploring the intersection of coding, education and disciplinary knowledge

Love podcasts or audiobooks? Learn on the go with our new app.

## Greg Benedis-Grab

79 Followers

exploring the intersection of coding, education and disciplinary knowledge