Жак Арсак - Программирование игр и головоломок

Теорема. Любая такая последовательность становится (начиная с некоторого места) постоянной, равной 153.

Пример.Начнем с 33:

33

3³ + 3³ = 54

5³ + 4³ = 189

1³ + 8³ + 9³ = 1242

1³ + 2³ + 4³ + 2³ = 81

8³ + 1³ = 153

1³ + 5³ + З³ = 153

1³ + 5³ + З³ = 153

и теперь последовательность стала постоянной.

Используйте ваш компьютер для доказательства этой теоремы.

? Головоломка 13.Варианты.

Нелегко сказать, какую роль в предыдущей теореме играет то, что исходное число кратно трем. Но от вас не потребует чрезмерных усилий в общем случае, что два последовательных числа последовательности имеют равные остатки при делении их на 3. В последовательностях, которые мы стали изучать, все члены последовательности делятся на 3. Можно доказать также, что все члены последовательности, кроме, быть может, первого, делятся на 9.

Если взять натуральное число, не кратное трем, то все члены соответствующей последовательности будут иметь один и тот же остаток при делении на 3. Что, кроме этого, вы можете узнать о поведении этих последовательностей?

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

? Головоломка 14.Теорема 6174. Построим последовательность натуральных чисел следующим образом. Начальный элемент — натуральное число с четырьмя цифрами, которые не все равны между собой. Мы переходим от данного члена последовательности к следующему но такому правилу.

Пусть a , b , c, d — четыре цифры, представляющие десятичную запись данного числа. Расположим их в порядке убывания слева направо и получим первое число. Расположим их в обратном порядке и вычтем это второе числа из первого. Это и есть искомый следующий член последовательности.

Теорема.Эта последовательность для любого начального элемента становится (начиная с некоторого места) постоянной, равной 6174.

Пример.Начнем с 7815:

8751 − 1578 = 7173

7731 − 1377 = 6354

6543 − 3456 = 3087

8730 − 0378 = 8352

8532 − 2385 = 6174

6174 − 1467 = 6174

Используйте ваш компьютер для доказательства этой теоремы. Это окажется намного проще, чем в предыдущей головоломке, поскольку имеется всего лишь 9000 чисел с четырьмя цифрами, и нужно исследовать 9000 последовательностей. Но вы можете сделать число испытаний намного меньше этого…

?? Головоломка 15.Господин S и господин P [7] S — первая буква слова «somme» (фр. сумма), P — слова «produit» (фр. произведение). — Примеч. ред. .

Вот одна из наиболее классических арифметических головоломок. Выберем два натуральных числа, больших единицы, но меньших ста. Значение их суммы сообщено господину S , значение их произведения — господину P . Ни один из них не знает, какое число сообщено другому. Господин P звонит господину S по телефону.

P . Я не могу найти эти два числа.

S . Я знаю, что вам это и не удалось бы.

P . Ах, так… Но тогда я их знаю!

S . Ну, тогда и я тоже их знаю!

Рассуждение позволяет существенно видоизменить задачу, и даже более того — предъявить решение. Много ли их? Используйте ваш компьютер, чтобы их найти.

??** Головоломка 16.Чемпион головоломок.

На мой взгляд, наиболее замечательная арифметическая головоломка, над которой мне пришлось особенно долго работать и которая дала мне возможность получить некоторые удовлетворительные результаты, — это, конечно, проблема простых чисел. Пусть дано число n (конечно, нечетное) и достаточно большое; сказать, является ли оно простым и, если можно, дать его разложение на простые множители.

Если не предполагать, что n велико, то есть простой способ действовать: делить n на простые числа и смотреть, удается ли деление без остатка. Если да, то число составное и допускает разложение в произведение. Впрочем, при таком методе многие делители можно вообще не рассматривать. Если n есть произведение двух сомножителей p и q :

n = p * q ,

то либо p = q , либо один из сомножителей больше другого, так что можно считать, что p — делитель, q — частное и p ≤ q . Поэтому будем делить n на последовательно возрастающие простые числа, для которых частное больше или равно делителю. Так как мы не располагаем таблицей простых чисел, то используем последовательность Делителей, которая заведомо содержит все простые числа, например, последовательность нечетных чисел или лучше целых чисел вида 6 k ± 1.

Число операций растет как квадратный корень из n . Если вы добавите к n одну цифру, то вы увеличите время вычисления примерно раза в три. Но более важно другое. Если вы увеличиваете n , вы можете превысить «арифметические способности» своего компьютера. Как вы узнаете, правильно ли выполнено деление? Предел, которого вы можете достичь таким образом, существенно зависит от марки вашего микрокомпьютера [8] Да и от языка, который вы используете. — Примеч. ред. .

Таким образом, вы должны бороться со следующими трудностями:

— точность вашего компьютера. Вам нужно иметь возможность делать вычисления с повышенной точностью, а это очень дорогостояще по времени;

— число требуемых операций;

— доверие к вашей программе. Если ваша машина сообщает вам, что

9873564383 = 631181 * 15643,

то вы, вероятно, сможете проверить этот результат на вашем микрокалькуляторе, А если компьютер сообщит вам, что 9873564401 — простое число, то как вы это проверите? Проделав вычисления на руках?

Вот основы метода Ж.-М. Полларда [POL].

По данному числу n (нечетному натуральному) строится последовательность по описанному ниже правилу:

— первый член последовательности равен 2;

— следующий за x элемент равен x ² − 1 по модулю n (остатку от деления x ² − 1 на n ).

Оказывается, что эта последовательность периодична. Это легко видеть. Остаток от деления на n есть неотрицательное целое, меньшее n , поэтому не может быть более n различных остатков. Поэтому неизбежно, что как только число членов превысит n , среди членов последовательности мы получим два одинаковых, что и означает периодичность последовательности. Но она может оказаться периодической с намного более коротким периодом, чем n . Вот, например, последовательность для n = 137:

a 1= 2

a 2= 3

a 3= 8

a 4= 63

a 5= 132

a 6= 24

a 7= 27