Этюды для программистов

Рисунок 15.1. Числа расположены по спирали против часовой стрелки.

Закономерности проявляются, когда целые числа отображаются на плоскость (или в пространство). Одно из возможных отображений показано на рис. 15.1, где числа располагаются вокруг начальной точки по спирали против часовой стрелки. На рис. 15.2 целые числа заполняют треугольник положительного квадранта. Если достаточно далеко расширить рамки этих рисунков, то станет видно, что простые числа располагаются преимущественно вдоль отдельных прямых (в основном по диагоналям) и совершенно игнорируют другие прямые. Частично этот эффект легко объясним. В обоих расположениях целые числа, попадающие на любую диагональ, даются некоторым квадратичным многочленом. Если многочлен, соответствующий какой-либо прямой, разлагается на рациональные линейные множители, то эта прямая будет содержать одни составные числа. Таким образом, простым числам волей-неволей пришлось облюбовать неприводимые прямые. Однако некоторые неприводимые многочлены изобилуют простыми числами, и изобилие это не оскудевает, несмотря на то что плотность простых чисел среди всех целых медленно стремится к нулю. Иными словами, хотя разложение многочленов объясняет в некоторой степени скученность простых чисел, все же существуют многочлены, более богатые простыми числами, чем предсказывает обычный статистический анализ.

Рисунок 15.2. Числа в треугольнике.

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

Инструментовка. Для решения этой задачи больше всего подходит алгебраический язык. У вас должна быть возможность управлять эффективностью проверки на простоту.

Длительность исполнения. Одному исполнителю на 2 недели.

Литература

Гарднер (Gardner M). Mathematical Games. Scientific American, pp. 120-126, March 1964. [Имеется перевод: Гарднер М. Математические досуги. — М.: Мир, 1972, с. 410.]

Гаусс (Gauss С. F.). Disquisitiones Arithmeticae. Yale University Press, New Haven, CT, 1965.

По теории чисел написаны сотни книг. Но, как это ни странно, одна из первых книг по-прежнему остается одной из лучших. Помимо прочих достоинств она вышла в дешевом издании. Так почему бы не посоветоваться с классиком?

Штейн, Улам, Уэллс (Stein M. L, Ulam S. M., Wells M. В.). A Visual Display of Some Properties of the Distribution of Primes, American Mathematical Monthly, pp. 516–520, May 1964.

Гарднер излагает результаты Штейна, Улама и Уэллса более популярно, тем не менее обе работы легки для чтения. На эту тему почти ничего больше не написано, так что это, вероятно, увлечение Улама. Идея получать с помощью простых чисел красивые картинки позволяет убить лишнее машинное время, и, не исключено, что в этом все же что-то есть.

16. Горючие слезы, или Учет расхода бензина

Тридцать центов за галлон — дело прошлое. Сорок центов за галлон — дело прошлое. Пятьдесят центов за галлон — дело прошлое. Сейчас[22] галлон бензина стоит шестьдесят центов, и, возможно, вскоре мы останемся вообще без горючего. Так что на повестке дня — анализ индивидуального расходования бензина.

Многие ведут журнал покупок бензина. Обычно туда записывают дату, показания счетчика пройденного пути, марку бензина, цену одного галлона, сколько галлонов куплено и общую стоимость. Три последние величины зависят друг от друга; эта зависимость не совсем точная из-за ошибок округления, но ее все же можно использовать для проверки правильности исходных данных. С помощью ЭВМ вы можете получить разнообразную статистическую информацию. Интересно вычислить такие производные величины, как средняя стоимость одного галлона, средний пробег на галлон, средний пробег за день, средняя стоимость пробега в одну милю, среднее время расходования одного галлона. Кроме того, хорошо было бы получить такую же информацию по каждой марке бензина и посмотреть, есть ли разница между марками. Таблица 16.1 — фрагмент реального журнала покупок бензина[23].