6
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Are you asking if it is evenly divisible? It would have to be a zero of the function to be evenly divisible. \$\endgroup\$ – dbasnett Apr 10 '11 at 13:24
  • \$\begingroup\$ Since this is a code review: f_n is a really bad name for a function, no matter what it does. In Lisp in particular, because, unlike in languages with infix operators, where it is easy to confuse the minus sign if used as a part of identifier with its usage as an operator, there isn't such problem in Lisp, thus, underscore isn't normally used in identifiers. \$\endgroup\$ – wvxvw Dec 27 '14 at 9:22
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ can you explain a bit more? I'm not sure I understand. \$\endgroup\$ – jaresty Apr 7 '11 at 13:22
  • 1
    \$\begingroup\$ Oh, wow. It took me a while to understand your explanation, but when you get it, it's very clear. Thanks! \$\endgroup\$ – jaresty Apr 8 '11 at 14:36
6
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.