# (Common Lisp) Is f(n) = n^2 + 3n + 5 not ever divisible by 121?

Given the following problem:

``````;3.4 It is conjectured that for any n > 0, n^2 + 3n + 5
;is never divisible by 121. Test this conjecture for
; n = 1,2,...,9999,10000.[3]
``````

I wrote the following solution:

``````(defpackage :one-twenty-one-divisible (:use :cl))
(in-package :one-twenty-one-divisible)

(defun divisible (n) (= (mod n 121) 0))
(defun f_n (n) (+ (expt n 2) (* 3 n) 5))

(let ((divisible-result (loop for n from 1 to 10000 when (divisible (f_n n)) collect n)))
(format t "The conjecture that for 1 <= n <= 10,000 f(n) = n^2 + 3n + 5 is indivisible by 121 is ~:[false~;true~].~%" (null divisible-result))
(unless (null divisible-result) (format t "The following items were found to have f(n) that is divisible by 121: ~a ~%" divisible-result)))
``````

What do you think?

-
Are you asking if it is evenly divisible? It would have to be a zero of the function to be evenly divisible. –  dbasnett Apr 10 '11 at 13:24

I don't know Lisp, but you can speed up the calculation by observing that n² + 3n + 5 is never divisible by 11 (and hence never divisible by 121), except when n mod 11 == 4.

If you check the equation for the remaining candidates (11*k+4) in the "full" module 121 (e.g. using Lisp, but I did it in Excel), you get always an remainder of 33, so the conjecture is indeed true.

I would consider this exercise as "bad style", as it encourages the "brute force" instead of the "think" approach. There are enough not-so-easy to solve conjectures (e.g. Goldbach's conjecture) where falling back to brute force actually makes sense.

[More Explanation]

Modular arithmetic is described here, but I will try to give a short introduction: Let's say we want to know the remainder of the polynom by division by 11 when n is of the form 11*k + 3. We could write

``````(11*k+3)² + 3*(11*k+3) + 5
``````

But as we are only interested in remainders, not the numbers itself, we "forget" all multiples of 11 and write in modular arithmetics:

``````3² + 3*3 + 5 | mod 11
9 + 9 + 5 | mod 11
23 | mod 11
1 | mod 11
``````

This says that when we have a number 11*k + 3, our polynom will always have a remainder of 1 when divided by 11. n=3 gives a polynom value of 23, which is 1 mod 11. n=256 gives 66309, which is again 1 mod 11. As 121 = 11², if a number is not divisible by 11, it isn't divisible by 121 either. So no number n = 11*k + 3 is ever divisible by 121. Testing all the cases from n = 11*k + 0 to n = 11*k + 10 I found, that only for 11*k + 4 the polynom is divisible by 11. Checking all the values 11*k + 4 in module 121 (that are 121*u + v with v = 4, 15, 26, 37, 48, 59, 70, 81, 92, 103, 114) I found that all leave a remainder of 33, proving the conjecture (let's say we take n = 121 + 15 = 136, we get a polynom value of 18909, and as expected, a remainder of 33 when dividing by 121).

So there is nothing wrong with your code (and as I said I don't know Lisp), but in my opinion the "better" solution would be to say: It can be shown directly (even with paper and pencil) that the polynom is never divisible by 121, so no test is needed.

-
can you explain a bit more? I'm not sure I understand. –  jaresty Apr 7 '11 at 13:22
Oh, wow. It took me a while to understand your explanation, but when you get it, it's very clear. Thanks! –  jaresty Apr 8 '11 at 14:36
Landei's answer is great from a math standpoint, but I did have a tip from a Lisp standpoint. If you're just testing a conjecture, you might want to consider using the `THEREIS` clause in your `LOOP`. This will break out of the loop as soon as it finds the first example that returns something other `NIL`, and it will return that value as the overall return value of the `LOOP`. This has two advantages; one is that it's more efficient in the case that there are a lot of positive results, and (more importantly, in most instances) it communicates your intent more clearly.