?

Log in

No account? Create an account
Factors and Factorials - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Factors and Factorials [Jan. 7th, 2009|01:49 pm]
Lindsey Kuper
[Tags|]

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.

LinkReply

Comments:
[User Picture]From: pixelherder
2009-01-07 09:06 pm (UTC)
What's interesting is that for finding the prime factors of each number up to n, if you save them, then you only have to find a single divisor and then you could just sum the factors of those to. It seems like this problem lends itself to some really neat memoization.
(Reply) (Thread)
[User Picture]From: lindseykuper
2009-01-14 09:52 am (UTC)
Well, according to the problem statement, the program shouldn't expect the input in any particular order. I just happened to do 2...100 because I wanted to test all the inputs and that was the easiest and prettiest way. So in the general case, you wouldn't be likely to have the prime factors of n! already stored, at the point when you had to calculate them for (n + 1)! Or are you talking about some other memoization idea that I'm missing entirely?
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2009-01-07 09:50 pm (UTC)

Your nerdsniping was successful

Python in 37 lines at http://pastie.org/355066
(Reply) (Thread)
[User Picture]From: conform
2009-01-08 12:18 am (UTC)

Re: Your nerdsniping was successful

my output was a little longer, with a slightly different approach: http://pastie.org/355170
(Reply) (Parent) (Thread)
[User Picture]From: pixelherder
2009-01-08 06:08 am (UTC)

Re: Your nerdsniping was successful

Since I'm giving Haskell another try: 15 lines of code at http://pastie.org/355372 (4 to compute the multiplicities, 11 for the REPL).
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2009-01-08 03:15 pm (UTC)

Re: Your nerdsniping was successful

Nice! I do like mine (and conform's (and pixelherder's, I think)) for being able to handle arbitrarily large inputs, though.
(Reply) (Parent) (Thread)
[User Picture]From: billings
2009-01-08 03:42 pm (UTC)

Re: Your nerdsniping was successful

44 lines python, different approach (can't read conform's approach to tell), arbitrarily large inputs, and a real sieve of eratosthenes

http://pastie.org/355725
(Reply) (Parent) (Thread)
[User Picture]From: jes5199
2009-01-08 11:16 pm (UTC)

Re: Your nerdsniping was successful

first non-trivial program I've ever written in Scala.
http://pastie.org/356165

i got tired and cheated on the primes, but it reuses the values of the line above, so I only have to factor n instead of n!
(Reply) (Parent) (Thread)
[User Picture]From: jes5199
2009-01-08 11:19 pm (UTC)

Re: Your nerdsniping was successful

scala is weird. It's like writing strictified haskell in ruby syntax with unsafePerformIO always on, plus the Java API
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2009-01-08 11:36 pm (UTC)

Re: Your nerdsniping was successful

class Lindsey {

I'm grinning so big. Thank you.

(see also)
(Reply) (Parent) (Thread)