Determining if f(n) = n^2 + 3n + 5 is ever divisible by 121

Given the following problem:


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\$.

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?

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 11k + 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 = 11k + 3 is ever divisible by 121. Testing all the cases from n = 11k + 0 to n = 11k + 10 I found, that only for 11k + 4 the polynom is divisible by 11. Checking all the values 11k + 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.

StackExchange Code Review Q#1375, answer score: 11