# Factors and Factorials

At Streamtech, where I'm thinking about applying for an internship, they say, "When applying for a programming job, feel free to solve one of these problems in your language of choice and send along the code." You know I had to pick the one that was about factorials.

Here's what the output looks like for 2 through 100. Kind of pretty, don't you think?

```\$ petite --script factors.scm
2! =  1
3! =  1  1
4! =  3  1
5! =  3  1  1
6! =  4  2  1
7! =  4  2  1  1
8! =  7  2  1  1
9! =  7  4  1  1
10! =  8  4  2  1
11! =  8  4  2  1  1
12! = 10  5  2  1  1
13! = 10  5  2  1  1  1
14! = 11  5  2  2  1  1
15! = 11  6  3  2  1  1
16! = 15  6  3  2  1  1
17! = 15  6  3  2  1  1  1
18! = 16  8  3  2  1  1  1
19! = 16  8  3  2  1  1  1  1
20! = 18  8  4  2  1  1  1  1
21! = 18  9  4  3  1  1  1  1
22! = 19  9  4  3  2  1  1  1
23! = 19  9  4  3  2  1  1  1  1
24! = 22 10  4  3  2  1  1  1  1
25! = 22 10  6  3  2  1  1  1  1
26! = 23 10  6  3  2  2  1  1  1
27! = 23 13  6  3  2  2  1  1  1
28! = 25 13  6  4  2  2  1  1  1
29! = 25 13  6  4  2  2  1  1  1  1
30! = 26 14  7  4  2  2  1  1  1  1
31! = 26 14  7  4  2  2  1  1  1  1  1
32! = 31 14  7  4  2  2  1  1  1  1  1
33! = 31 15  7  4  3  2  1  1  1  1  1
34! = 32 15  7  4  3  2  2  1  1  1  1
35! = 32 15  8  5  3  2  2  1  1  1  1
36! = 34 17  8  5  3  2  2  1  1  1  1
37! = 34 17  8  5  3  2  2  1  1  1  1  1
38! = 35 17  8  5  3  2  2  2  1  1  1  1
39! = 35 18  8  5  3  3  2  2  1  1  1  1
40! = 38 18  9  5  3  3  2  2  1  1  1  1
41! = 38 18  9  5  3  3  2  2  1  1  1  1  1
42! = 39 19  9  6  3  3  2  2  1  1  1  1  1
43! = 39 19  9  6  3  3  2  2  1  1  1  1  1  1
44! = 41 19  9  6  4  3  2  2  1  1  1  1  1  1
45! = 41 21 10  6  4  3  2  2  1  1  1  1  1  1
46! = 42 21 10  6  4  3  2  2  2  1  1  1  1  1
47! = 42 21 10  6  4  3  2  2  2  1  1  1  1  1  1
48! = 46 22 10  6  4  3  2  2  2  1  1  1  1  1  1
49! = 46 22 10  8  4  3  2  2  2  1  1  1  1  1  1
50! = 47 22 12  8  4  3  2  2  2  1  1  1  1  1  1
51! = 47 23 12  8  4  3  3  2  2  1  1  1  1  1  1
52! = 49 23 12  8  4  4  3  2  2  1  1  1  1  1  1
53! = 49 23 12  8  4  4  3  2  2  1  1  1  1  1  1
1
54! = 50 26 12  8  4  4  3  2  2  1  1  1  1  1  1
1
55! = 50 26 13  8  5  4  3  2  2  1  1  1  1  1  1
1
56! = 53 26 13  9  5  4  3  2  2  1  1  1  1  1  1
1
57! = 53 27 13  9  5  4  3  3  2  1  1  1  1  1  1
1
58! = 54 27 13  9  5  4  3  3  2  2  1  1  1  1  1
1
59! = 54 27 13  9  5  4  3  3  2  2  1  1  1  1  1
1  1
60! = 56 28 14  9  5  4  3  3  2  2  1  1  1  1  1
1  1
61! = 56 28 14  9  5  4  3  3  2  2  1  1  1  1  1
1  1  1
62! = 57 28 14  9  5  4  3  3  2  2  2  1  1  1  1
1  1  1
63! = 57 30 14 10  5  4  3  3  2  2  2  1  1  1  1
1  1  1
64! = 63 30 14 10  5  4  3  3  2  2  2  1  1  1  1
1  1  1
65! = 63 30 15 10  5  5  3  3  2  2  2  1  1  1  1
1  1  1
66! = 64 31 15 10  6  5  3  3  2  2  2  1  1  1  1
1  1  1
67! = 64 31 15 10  6  5  3  3  2  2  2  1  1  1  1
1  1  1  1
68! = 66 31 15 10  6  5  4  3  2  2  2  1  1  1  1
1  1  1  1
69! = 66 32 15 10  6  5  4  3  3  2  2  1  1  1  1
1  1  1  1
70! = 67 32 16 11  6  5  4  3  3  2  2  1  1  1  1
1  1  1  1
71! = 67 32 16 11  6  5  4  3  3  2  2  1  1  1  1
1  1  1  1  1
72! = 70 34 16 11  6  5  4  3  3  2  2  1  1  1  1
1  1  1  1  1
73! = 70 34 16 11  6  5  4  3  3  2  2  1  1  1  1
1  1  1  1  1  1
74! = 71 34 16 11  6  5  4  3  3  2  2  2  1  1  1
1  1  1  1  1  1
75! = 71 35 18 11  6  5  4  3  3  2  2  2  1  1  1
1  1  1  1  1  1
76! = 73 35 18 11  6  5  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1
77! = 73 35 18 12  7  5  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1
78! = 74 36 18 12  7  6  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1
79! = 74 36 18 12  7  6  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1  1
80! = 78 36 19 12  7  6  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1  1
81! = 78 40 19 12  7  6  4  4  3  2  2  2  1  1  1
1  1  1  1  1  1  1
82! = 79 40 19 12  7  6  4  4  3  2  2  2  2  1  1
1  1  1  1  1  1  1
83! = 79 40 19 12  7  6  4  4  3  2  2  2  2  1  1
1  1  1  1  1  1  1  1
84! = 81 41 19 13  7  6  4  4  3  2  2  2  2  1  1
1  1  1  1  1  1  1  1
85! = 81 41 20 13  7  6  5  4  3  2  2  2  2  1  1
1  1  1  1  1  1  1  1
86! = 82 41 20 13  7  6  5  4  3  2  2  2  2  2  1
1  1  1  1  1  1  1  1
87! = 82 42 20 13  7  6  5  4  3  3  2  2  2  2  1
1  1  1  1  1  1  1  1
88! = 85 42 20 13  8  6  5  4  3  3  2  2  2  2  1
1  1  1  1  1  1  1  1
89! = 85 42 20 13  8  6  5  4  3  3  2  2  2  2  1
1  1  1  1  1  1  1  1  1
90! = 86 44 21 13  8  6  5  4  3  3  2  2  2  2  1
1  1  1  1  1  1  1  1  1
91! = 86 44 21 14  8  7  5  4  3  3  2  2  2  2  1
1  1  1  1  1  1  1  1  1
92! = 88 44 21 14  8  7  5  4  4  3  2  2  2  2  1
1  1  1  1  1  1  1  1  1
93! = 88 45 21 14  8  7  5  4  4  3  3  2  2  2  1
1  1  1  1  1  1  1  1  1
94! = 89 45 21 14  8  7  5  4  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1
95! = 89 45 22 14  8  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1
96! = 94 46 22 14  8  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1
97! = 94 46 22 14  8  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1  1
98! = 95 46 22 16  8  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1  1
99! = 95 48 22 16  9  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1  1
100! = 97 48 24 16  9  7  5  5  4  3  3  2  2  2  2
1  1  1  1  1  1  1  1  1  1```

The code that does it is about 100 lines of Scheme, not including the comments. The most difficult part was figuring out how to do the formatting stuff.

Now, I really want to put this away and do some Python or something, but now that it's done, I realize that my algorithm isn't very smart: it calculates n! and then goes about finding the prime factors of that big number. But we could actually find the prime factors of n! just by finding the prime factors of each of the numbers up to n and then adding up their multiplicities. (For example, 5! is 5 x 4 x 3 x 2 = 5 x 22 x 3 x 2 = 5 x 3 x 23.) I'm not sure how big n has to get before that starts to be cheaper, but I imagine the answer is "not very big". Maybe I'll play with it more later.

Tags:
• #### Marathon (Part the First)

On race day, I got up at 3:30 a.m. I was in Evanston and needed to be at the starting line at McCormick Place before six, and I didn't have a car. I…

• #### Marathon logistics

On a brighter note, the marathon is tomorrow morning, and I went down to McCormick Place to get my Marathon Packet, which consists of a bib number…

• #### I feel like all my journal entries lately have been of epic length

...and yet there's all this stuff that I haven't been covering. I barely wrote about graduation, and I didn't say much about iD training or the…

• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic