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

a 8= 43

a 9= 67

a 10= 104

a 11= 129

a 12= 63 = a 4

Последовательность периодична с периодом 8.

Пусть дана последовательность, вычисленная для некоторого n . Предположим, что n делится на s , и что соответствующая числу s последовательность периодична с периодом p .

Для достаточно большого i имеем a i + p = a i по модулю p , следовательно, a i + p − a i делится на p . Так как, кроме того, и n делится на p , то наибольший общий делитель (НОД) чисел a i + p − a i и n отличен от 1 [9] Повторим эти рассуждения чуть более подробно. Пусть a 1 = 2, a i +1 = a i ² − 1 mod n , b 1 = 2, b i +1 = b i ² mod s — последовательности, соответствующие числам n и s соответственно. Тогда легко доказать по индукции, что b i = a i mod s . Одним из периодов последовательности { а i } является n . Значит, n является периодом и для последовательности { b i }. Известно, что любой период последовательности кратен ее минимальному периоду, Так как p , по определению, является минимальным периодом последовательности b i , то n делится на p . — Примеч. ред. .

Построим последовательность Полларда для n = 22879:

a 1= 2

a 2= 3

a 3= 8

a 4= 63

a 5= 3968

a 6= 4271

a 7= 6877

a 8= 2235

a 9= 7602

a 10= 20928

a 11= 8486

a 12= 11982

НОД чисел a 12− a 4и n = 22879 есть 137, делитель числа n .

Если мы способны сказать, становится ли данная последовательность периодической (головоломка 1), то мы располагаем быстрым методом определения, имеет ли данное число делитель. Можете играть. Это не такая уж простая программа…

Есть тест на простоту числа, основанный на так называемой малой теореме Ферма: если n — простое, причем число n не является делителем a , то

a n −1= 1 по модулю n .

Представим n в виде n = 2 sm + 1. Назовем число n сильно псевдопростым по основанию a , если выполнено одно из следующих двух условий:

либо a m = 1 по модулю n ,

либо a m 2 r = n − 1 по модулю n = 2 sm + 1 для некоторого r , 0 ≤ r < s .

Очень мало сильно псевдопростых чисел, не являющихся простыми; так

2047 = 23 * 89 — сильно псевдопросто по основанию 2,

1373653 = 829 * 1657 — по основанию 2 и 3,

25326001 = 2251 * 11251 — по основанию 2, 3 и 5,

3215031751 = 151 * 751 * 28351 — по основанию 2, 3, 5 и 7.

Метод интересен, потому что a n вычисляется за время, растущее не быстрее, чем ln n . Это утверждение вытекает из соотношений:

а 0= 1, а 1= а ,

a 2 n = ( а * а ) n , a 2 n +1= ( a * a ) n * а .

Все, что нужно для работы, у вас есть. Больше делать нечего, кроме собственно составления программы.

Кстати: знаете ли вы две универсальные конструкции в информатике? Первая — «известно, что…». Вторая — «это и нужно сделать…».

Я надеялся не приводить в этой книге никаких готовых программ. Программирую не я, а вы. И я не очень люблю смотреть, как подростки копируют программу, набирая ее на клавиатуре и при этом не отдавая себе отчета в том, что она делает и как устроена. Но сказать, что делает та или иная программа, может оказаться настоящей головоломкой, Программы, которые мы будем обсуждать, написаны на некотором воображаемом языке [10] Этот язык описан на стр.7–8 выше. Здесь лишь кратко напоминаются формы записи условных операторов и операторов цикла. — Примеч. ред. . Вам придется по крайней мере сделать усилие, чтобы перевести их на ваш обычный язык: Бейсик, LSE или Паскаль. Условная команда записывается в виде

ЕСЛИ условие ТО последовательность команд

КОНЕЦ_ЕСЛИ

(последовательность команд выполняется тогда и только тогда, когда условие истинно)

или

ЕСЛИ условие ТО последовательность команд

ИНАЧЕ последовательность команд

КОНЕЦ_ЕСЛИ

(если условие истинно, то выполняется последовательность команд, заключенная между ТО и ИНАЧЕ, в противном случае выполняется та последовательность команд, которая расположена между ИНАЧЕ и КОНЕЦ_ЕСЛИ).

В обоих случаях КОНЕЦ_ЕСЛИ играет роль закрывающей скобки, связанной с открывающей скобкой ЕСЛИ. Мы будем использовать цикл

ПОКА условие ВЫПОЛНЯТЬ

последовательность команд

ВЕРНУТЬСЯ

Последовательность команд, содержащаяся между ВЫПОЛНЯТЬ и ВЕРНУТЬСЯ, повторяется, ПОКА условие истинно.

* Головоломка 17.Для забавы. Вот легко понимаемая программа. Здесь n и b — два натуральных числа и b нечетно (это существенно)

ПРОЧЕСТЬ n , b

ПОКА n > b ВЫПОЛНЯТЬ

ЕСЛИ n четно ТО n := n /2

ИНАЧЕ n := n − b

КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

СООБЩИТЬ ЕСЛИ n = 0 ТО 'ДА'

ИНАЧЕ 'НЕТ' КОНЕЦ_ЕСЛИ

Вы можете попробовать выполнить ее вручную для

n = 2 77− 3, b = 7.

Забавно, не правда ли? Несмотря на свою исключительную» простоту, эта программа, кажется, новая…

*** Головоломка 18.Посерьезнее. Эта — несомненно более трудная. И тоже неопубликованная. Боюсь, что вы можете избаловаться… На вход программы подается n — нечетное натуральное число.

ПРОЧЕСТЬ n

q := ( n − 1)/4; p := целая_часть ( q )

ЕСЛИ q ≠ p ТО СООБЩИТЬ 'НЕТ';

КОНЕЦ_РАБОТЫ КОНЕЦ ЕСЛИ

ЕСЛИ нечетное p ТО СООБЩИТЬ 'НЕТ';

КОНЕЦ_РАБОТЫ КОНЕЦ_ЕСЛИ

a := 4; b := 1

ПОКА p ≥ a ВЫПОЛНЯТЬ

p := p /2

ЕСЛИ нечетное p ТО p := p − a /2 − b ;

b := a − b КОНЕЦ ЕСЛИ a := a + a ВЕРНУТЬСЯ

ЕСЛИ p = 0 ТО СООБЩИТЬ b ;

КОНЕЦ РАБОТЫ КОНЕЦ_ЕСЛИ

ЕСЛИ p + 2* b = a ТО СООБЩИТЬ a − b ;

КОНЕЦ РАБОТЫ КОНЕЦ_ЕСЛИ

ЕСЛИ p = 4 * ( a − b ) ТО СООБЩИТЬ 2 * a − b ;

КОНЕЦ РАБОТЫ КОНЕЦ_ЕСЛИ

СООБЩИТЬ 'НЕТ'; КОНЕЦ_РАБОТЫ

Я не запрещаю вам перевести эту программу на ваш любимый язык, а затем испытать ее для различных значений n . Есть маленький шанс, что вы угадаете, на что она способна. Это не очевидно!

** Головоломка 19.Вклад Жака Гебенстрейта. Я обязан Жаку Гебенстрейту следующей программой. Она была предложена в том виде, в каком я ее привожу, без какого-либо комментария (это было сделано без злого умысла с его стороны: сам он получил не больше от того, кто дал ему эту программу).

ПРОЧЕСТЬ a , b ; p : = max ( a , b ); q := min ( a , b )

ПОКА q > eps ВЫПОЛНЯТЬ