b и допустим ту же самую вместимость для представления чисел. В таком случае на каждой прямой будет от 0 до b — 1 спичек, следовательно, в среднем 1/2 (b — 1) из всего количества спичек. Как мы упоминали несколько раз, мы будем иметь приблизительно n/lg b прямых. Отсюда делаем вывод, что среднее время, требуемое для представления числа с n знаками, составляет примерно
n/lg n 1/2 • (b — 1) = 1/2 E
секунд, здесь Е есть выражение из (6.4.4). Так как это время было минимальным для b = 2, мы также можем сделать вывод:
среднее время, необходимое для установления числа с помощью спичек на прямых, минимально для b = 2.
Система задач 6.4.
1. Постройте графики функций y = f(b) из (6.4.3) и у = g(b) из (6.4.5) для b> 1. Если вы уже знакомы с дифференциальным исчислением, используйте его для определения формы кривых.
§ 5. Компьютеры и их системы счисления
До появления электронных вычислительных машин всюду при вычислениях безраздельно господствовала десятичная система. Интерес к другим системам носил либо исторический, либо познавательный характер. Существовало лишь несколько отдельных задач, которые наиболее удачно формулировались с использованием двоичной или троичной систем счисления. Одним из излюбленных примеров в книгах по теории чисел является игра «Ним»[10]. К тому времени, когда появилось много различных типов компьютеров, возникла задача сделать устройство ЭВМ как можно более компактным и эффективным. Это привело к тщательному изучению систем счисления с целью нахождения более подходящей системы. По ряду причин, некоторые из которых мы обсудили в предыдущем параграфе, двоичная система была признана предпочтительной. Единственным ее недостатком явилось то, что для большинства из нас требуются немалые усилия для того, чтобы чувствовать себя в ней «как дома», так как мы были воспитаны в других традициях. Следовательно, поскольку числа, которые должны вводиться в компьютеры, обычно записаны в десятичной системе, то требуется начальное устройство, переводящее их в двоичную систему, а ответы в конце концов должны быть выражены в десятичной системе, как уступка менее математически подготовленным членам общества.
Разумеется, двоичная система, используемая в ЭВМ, является той же самой системой, которую мы обсуждали в предыдущем параграфе, однако используемая терминология носит более технический оттенок. Двоичные цифры 0, 1 называются битами, что является сокращением английского выражения Binary digiTs (двоичные цифры). Так как существуют лишь две возможности: 0 и 1 в каждой позиции, то часто говорят об элементе с двумя состояниями.
Если следовать общему правилу, изложенному в § 2 этой главы, то представление данного числа в двоичной системе довольно просто. Например, возьмем N = 1971. Повторное деление на b = 2 дает
1971 = 985 • 2 + 1,
985 = 492 • 2 + 1,
492 = 246 • 2 + 0,
246 = 123 • 2 + 0,
123 = 61 • 2 + 1,
61 = 30 • 2 + 1,
30 = 15 • 2 + 0,
15 = 7 • 2 + 1,
7 = 3 • 2 + 1,
3 = 1 • 2 + 1,
1 = 0 • 2 + 1,
Следовательно,
197110 = (1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1)2.
Ранее мы отмечали, что в двоичной системе числа имеют более длинные выражения, следовательно, становится труднее с первого взгляда оценить величину числа. По этой причине в языке ЭВМ часто используется восьмеричная система счисления (с основанием 8). Это является лишь незначительным изменением двоичной системы, которое получается разбиением бит в числе на группы по три. Это можно представить себе как систему с основанием
b = 8 = 23.
Коэффициентами при этом являются восемь чисел
0 = 000, 4 = 100, 1 = 001, 5 = 101, 2 = 010, 6 = 110, 3 = 011, 7 = 111.
В качестве иллюстрации возьмем число 1971 из рассмотренного выше примера; в восьмеричной системе оно представляется как
1971 = 011, 110, 110, 011 = (3, 6, 6, 3)8.
Таким образом, этот способ записи незначительно отличается от предыдущего. В действительности, такое деление на группы нам хорошо знакомо по обычным десятичным числам: при записи и произнесении большого числа мы обычно делим его цифры на группы по три, например,
N = 89 747 321 924.
Таким образом, можно сказать, что это является представлением нашего числа при основании b = 1000= 103.
В компьютерах иногда используются и другие представления чисел. Предположим, что мы хотим записать десятичное число, скажем, N = 2947, в ЭВМ, работающей в двоичной системе. Тогда, вместо того чтобы полностью менять N на двоичное число, можно было бы изменить лишь цифры этого числа
2 = 0010,
9 = 1001,
4 = 0100,
7 = 0111
и, таким образом,
N = 0010, 1001, 0100, 0111.
Такие числа известны как кодированные десятичные числа. Этот метод иногда называется «системой 8421», так как эти десятичные цифры представляются в виде сумм двоичных единиц
0 = 0000, 1 = 0001, 2 = 0010,
22 = 4 = 0100, 23 = 8 = 1000.
Такие кодированные десятичные числа неудобны для всех видов вычислений, но не всегда целью ЭВМ являются вычисления. Тем же образом, любая буква алфавита или любой другой символ могут быть приписаны какому-нибудь двоичному числу. Это означает, что любое слово или предложение можно запоминать как двоичное число. Таким образом, если бы мы были соответствующим образом натренированы и имели бы дело со столь же подготовленной аудиторией, то могли бы общаться лишь с помощью бит.
Система задач 6.5.
1. Найдите двоичное представление чисел Ферма (§ 3, гл. 2)
2. Найдите двоичные представления четных совершенных чисел (§ 4, гл. 3)
§ 6. Игры с числами
Существует множество видов игр с числами, некоторые из которых были известны еще в средние века. Большинство из них не представляет интереса для теории чисел, скорее всего, они подобно магическим квадратам принадлежат к классу кроссвордов с числами. Некоторые из них проиллюстрируем примерами.
Перед вами телеграмма, посланная школьником домой, с настоятельной просьбой:
S E N D
M O R E
_________
M O N E Y[11]
Будем рассматривать эту схему, как сложение двух четырехзначных чисел SEND и MORE, в сумме дающих число MONEY. Каждая буква означает определенную цифру. Задача состоит в том, чтобы определить, какие это цифры. Так как всего 10 цифр, то в каждой такой задаче может фигурировать не более 10 букв, в этом примере 8. В идеальном случае задача должна иметь единственное решение.
В нашем примере очевидно, что M = 1, так как М — первая цифра либо суммы S + М, либо S + M+1, где S и М — числа, не превосходящие числа 9. Тогда для числа S имеются две возможности:
S = 9 или S = 8,
так как либо S + 1, либо S + 1 + 1 есть двузначное число. Установим сначала, что S не может быть цифрой 8, ибо, если бы S было 8, то должен был бы быть перенос из колонки сотен, что дает
S + M + 1 = 8 + 1 + 1 = 10
при сложении в колонке сотен. Следовательно, О должно было бы быть нулем и наше послание читалось бы так:
8 Е N D
1 0 R Е
_________
1 0 N Е Y
Но, исследуя колонку сотен, находим, что обязательно должен быть перенос из колонки десятков (иначе Е + 0 = Е, а не N), и так как Е≤ 9, то
E + 0 + 1 = 10.
Это вынудило бы нас положить N = 0, но мы уже знаем, что О = 0, поэтому такой случай невозможен, и мы заключаем, что S = 9, и послание теперь читается так:
9 Е N D
1 0 R E
_________
1 0 N Е Y
Так как Е≠N, то сложение в колонке сотен приводит к условию E + 1 = N,
и
9 Е E+1 D
1 0 R Е
____________
1 0 E+1 Е Y
Сложение в колонке десятков дает либо
E + 1 + R = 10 + E, либо E + 1 + R + 1 = 10 + E.
Первый случай невозможен, так как он дает R = 9, что противоречит тому, что S = 9. Во втором случае R = 8, и послание читается так:
9 Е Е+1 D
1 0 8 E
____________
1 0 E+1 Е Y
И наконец, сумма в колонке единиц такова:
D + E = 10 + Y.
Для трех буквD, E, Y остаются только значения 2, 3, 4, 5, 6, 7. Наибольшая сумма двух различных чисел из них равна 13. Отсюда существует всего две возможности для Y: либо Y = 2, либо Y = 3. Последний случай невозможен, так как при этом D + E = 13, но мы не можем иметь E = 7, так как тогда N = E + 1 = 8 = R; также не может быть D = 7, так как тогда E = 6 и N = E + 1 = 7 = D.