Определение: если F(н) = н^2 + 3н + 5 не делится на 121


Учитывая следующие проблемы:

Предполагается, что для любого \$н > 0\$, \$н^2 + 3н + 5\$ никогда не делится на 121. Проверить эту догадку для \$Н = 1,2,...,9999,10000\$.

Я написал следующее решение:

(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)))

Что вы думаете?



722
6
задан 22 марта 2011 в 06:03 Источник Поделиться
Комментарии
2 ответа

Я не знаю Lisp, но вы можете ускорить вычисления, наблюдая, что N2 + 3н + 5 не делится на 11 (и, следовательно, не делится на 121), кроме случаев, когда п Mod 11 == 4.

Если вы посмотрите на уравнение для оставшихся кандидатов (11*к+4) в "полном" модуль 121 (например, с помощью Lisp, но я делал это в Excel), вы получаете всегда остаток 33, так что предположение действительно верно.

Я хотел бы рассмотреть такое упражнение как "плохой стиль", как он призывает "грубой силы" вместо "думаю" подход. Есть достаточно не так легко решить гипотезы (например, гипотеза Гольдбаха), где падал на грубую силу, на самом деле имеет смысл.

[Более Подробное Объяснение]

Модульная арифметика описано здесь, но я постараюсь дать краткое введение: допустим, мы хотим узнать остаток полинома от деления на 11, когда n имеет вид 11*к + 3. Мы могли бы написать

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

Но так как нас интересуют только остатки, а не цифры, мы "забываем" все кратные 11 и пишите в модульной арифметики:

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

Это говорит, что когда у нас есть номер 11*к + 3, Наш полином всегда будет иметь остаток 1 при делении на 11. н=3 дает полином значение 23, то есть 1 мод 11. Н=256 дает 66309, что опять-таки 1 мод 11. Как 121 = 112, если число не делится на 11, то оно не делится на 121 либо. Поэтому нет число N = 11*к + 3 не делится на 121. Тестирование всех дел от N = 11*к + 0 до N = 11*к + 10 я нашел, что только для 11*к + 4 в полином делится на 11. Просмотрев все характеристики 11*к + 4 в модуль 121 (то есть 121*у + V с V с = 4, 15, 26, 37, 48, 59, 70, 81, 92, 103, 114) я обнаружил, что все оставить остаток 33, подтверждающих догадки (допустим, мы принимаем Н = 121 + 15 = 136, то получим полином стоимость 18909, как и ожидалось, остаток от деления на 33 121).

Так что нет ничего плохого с вашим кодом (и как я уже сказал, Я не знаю, Лисп), но на мой взгляд "лучшее" решение, можно было бы сказать: это может быть показано прямо (даже с бумаги и карандаша), что полином не делится на 121, так что тест не нужен.

11
ответ дан 7 апреля 2011 в 09:04 Источник Поделиться

Landei ответ Отлично подходит с математической точки зрения, но у меня была подсказка от шепелявить точки зрения. Если ты просто проверял гипотезу, вы, возможно, захотите рассмотреть возможность использования существует пункт в вашем цикле. Это будет вырваться из петли, как только он находит первый пример, который возвращает что-то другое, Нил, и он будет возвращать это значение в качестве общего возвращаемое значение из цикла. Это имеет два преимущества: одно заключается в том, что он более эффективен, в случае, если есть много положительных результатов, и (что еще более важно, в большинстве случаев) он общается более четко намерениях.

6
ответ дан 1 июля 2011 в 09:07 Источник Поделиться