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

Для 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 секунд.