О. ОРЕ - Приглашение в теорию чисел

Мы привели эту историю, которая никоим образом не является уникальной, чтобы подчеркнуть: запоминание таблицы умножения в те дни не было обычным этапом математического знания. Таким образом, мы видим, что использование в нашей арифметике чисел с небольшим основанием дает ряд преимуществ, как механических, так и интеллектуальных. Например, когда основанием является число b = 3, то в таблице умножения

| 0 1 2

|________

0 | 0 0 0

1 | 0 1 2

2 | 0 2 (1,1) 3

существует только единственное нетривиальное умножение, а именно: 2 • 2 = 4 = (1, 1) 3.

Для b = 2 мы имеем совершенно тривиальную таблицу

| 0 1

|____

0 | 0 0

1 | 0 1

Система задач 6.3.

1. Доказать, что количество нетривиальных умножений цифр (получающееся отбрасыванием умножений на 0 и 1) в системе с основанием b равно 1/2 ( b — 1) ( b — 2).

2. Чему равна сумма всех элементов в таблице умножения? Проверьте для b = 10.

Обсудим несколько задач, связанных с системами счисления, которые имеют отношение к выбору оснований систем счисления, удобных для машинного счета. Предположим, что мы имеем дело с обычным настольным арифмометром, который работает при помощи сцепленных числовых колес, каждое из которых имеет 10 цифр: 0, 1, … 9. Если имеется n колес, то мы можем представить все числа вплоть до

N = 99…9 ( n раз ), (6.4.1)

как и в (6.3.1).

Предположим теперь, что в качестве основания мы взяли число b , отличное от 10, но продолжаем рассматривать числа до N. Тогда мы должны иметь m колес, где m — целое число, удовлетворяющее условиям (6.3.2) и (6.3.3). Как и в (6.3.4). число m является целым числом, равным числу n /lg b или следующим за ним. Так как каждое колесо несет b цифр, то количество цифр, записанных на колесах, приближенно равно

D = n b /lg b .

Можно теперь спросить: какое нужно выбрать число b , чтобы получить наименьшее количество чисел, записанных на колесах? Чтобы найти наименьшее значение числа D , в формуле (6.4.2) необходимо лишь исследовать функцию

f ( b ) = b /lg b (6.4.3)

для различных оснований b = 2, 3, 4… С помощью таблицы логарифмов получаем значения

b 2 3 4 5 6

f ( b ) 6,64 6,29 6,64 7,15 7,71

Последующие значения для f ( b ) еще больше; например, f (10) = 10, как уже отмечалось. Мы заключаем, что для таких арифмометров имеет место следующее утверждение.

Наименьшее общее число цифр на арифмометре достигается при b = 3.

Видно, что для b = 2 и b = 4 общее число цифр не на много больше; в этом смысле маленькие основания имеют преимущество.

Рассмотрим небольшое изменение этой задачи. Обычные счеты того типа, который иногда используется для обучения детей счету, имеют несколько металлических спиц с девятью [9] На счетах, принятых в СССР, на каждой спице располагается 10 косточек. ( Прим. перев .) подвижными косточками на каждой из них, чтобы отмечать цифры чисел. С таким же успехом можно провести параллельные прямые на листе бумаги и отмечать цифры соответствующим количеством спичек, или же подобно древним начертить эти прямые на песке и отмечать цифры камешками.

Но вернемся к счетам. Если имеется n спиц и на каждой по 9 косточек, то можно представить вновь все целые числа с п знаками вплоть до числа N , записанного в (6.4.1). Теперь зададим следующий вопрос: можно ли, взяв другое основание b , сделать счеты более компактными, т. е. обойтись меньшим количеством косточек?

При основании b количество косточек на каждой спице будет b — 1. Как и прежде, для того чтобы счеты имели ту же вместимость N , количество знаков или спиц должно определяться соотношением (6.3.4). Это дает значение

E = n /lg b ( b — 1) (6.4.4)

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

g ( b ) = ( b — 1)/lg b (6.4.5)

для различных значений числа b = 2, 3… Значение функции g ( b ) для небольших значений числа b даны в таблице

b 2 3 4 5 6

g ( b ) 3,32 4,19 4,98 5,72 6,43

Для больших значений числа b функция продолжает возрастать, поэтому мы заключаем, что необходимое количество косточек на счетах будет минимально при b = 2.

Можно интерпретировать этот результат с другой точки зрения. Предположим, что мы отметили цифры нашего числа, используя спички или камешки, расположенные на прямых линиях. В десятичной системе будет от 0 до 9 отметок на каждой прямой. Это дает в среднем по 4,5 спички на каждой прямой для наугад взятых чисел; следовательно, числа с n знаками потребуют в среднем 4,5 n спичек, когда они укладываются произвольно.

Посмотрим, какое время потребуется, чтобы уложить эти спички на места. Имея в виду какое-нибудь расположение, предположим, что потребуется одна секунда, чтобы уложить одну спичку. Тогда общее время, требуемое для того, чтобы уложить все спички, будет в среднем составлять приблизительно 4,5 n секунд.

Предположим, что мы изменили наше основание на число 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. Если вы уже знакомы с дифференциальным исчислением, используйте его для определения формы кривых.

До появления электронных вычислительных машин всюду при вычислениях безраздельно господствовала десятичная система. Интерес к другим системам носил либо исторический, либо познавательный характер. Существовало лишь несколько отдельных задач, которые наиболее удачно формулировались с использованием двоичной или троичной систем счисления. Одним из излюбленных примеров в книгах по теории чисел является игра «Ним» [10] При игре в «Ним» раскладывается некоторое количество камешков в несколько кучек. Двое играющих по очереди берут камешки из кучек, при ходе можно брать произвольное количество камней, но только из одной кучки. Выигрывает игрок, взявший последний камень. ( Прим. перев .) . К тому времени, когда появилось много различных типов компьютеров, возникла задача сделать устройство ЭВМ как можно более компактным и эффективным. Это привело к тщательному изучению систем счисления с целью нахождения более подходящей системы. По ряду причин, некоторые из которых мы обсудили в предыдущем параграфе, двоичная система была признана предпочтительной. Единственным ее недостатком явилось то, что для большинства из нас требуются немалые усилия для того, чтобы чувствовать себя в ней «как дома», так как мы были воспитаны в других традициях. Следовательно, поскольку числа, которые должны вводиться в компьютеры, обычно записаны в десятичной системе, то требуется начальное устройство, переводящее их в двоичную систему, а ответы в конце концов должны быть выражены в десятичной системе, как уступка менее математически подготовленным членам общества.