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

Question

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?

Answer 1

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.

Answer 2

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.