How to Solve it by Computer #4

Problem 2.4.3: Design an algorithm to determine whether or not a number n is a factorial number.

I thought a bit about the design choices. I think the simplest solution is just by dividing i starting with 2 until it reaches one. There are several tricks which can be used. And my first idea was to use dynamic programming and work backwards which could use pretty fast. On the other hand division is also pretty fast in this case.

Here’s the code. Pretty straight forward:

(defn isfactorial?
  [n]
  (loop [i 1
         n n]
    (cond (= n 1) true
          (< n 1) false
          :else (recur (inc i) (/ n i)))))

We continuously divide by 1, 2, 3, etc. If the result is 1 then it is a factorial. If the result is smaller than 1 then it isn’t.

user=> (isfactorial? 2)
true
user=> (isfactorial? 4)
false
user=> (isfactorial? 6)
true
user=> (isfactorial? 5040)
true
user=> (isfactorial? 15511210043330985984000000)
true
user=> (isfactorial? 15511210043330985984000002)
false

Problem 2.4.4: Design an algorithm which, given some integer n, finds the largest factorial number present as a factor in n.

The problem isn’t that interesting in itself but the solution is nice because we already got it for free. Why you ask? Look back at the function. This number is i – 1, in case the number is a factorial and otherwise i – 2. Why? Firstly, we increment i each time we call – basically beforehand. That’s why we need to decrement it by one in any case. In the case that it isn’t an factorial we also try to get smaller than one, i.e. we need one more division. Therefore, we decrement this i by 2.

(defn nearest-factorial
  [n]
  (loop [i 1
         n n]
    (cond (= n 1) (- i 1)
          (< n 1) (- i 2)
          :else (recur (inc i) (/ n i)))))