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

[Чтобы вычислить дату пасхи для годов, номера которых < 1582, обратитесь к САСМ 5 (1962), 209-210. Первым систематическим алгоритмом для вычисления даты пасхи были канонические пасхалии Викториуса Аквитанского (Victorius of Aqmtania) (457 г н. э.). Существует много подтверждений тому, что единственным нетривиальным применением арифметики в Европе на протяжении средних веков было вычисление даты пасхи, поэтому подобные алгоритмы имеют историческое значение. Более подробно об этом говорится в книге Т. Н. OBeirne, Puzzles and Paradoxes (London: Oxford University Press, 1965), Chapter 10; в книге N. Dershowitz, E. M. Reingold, Calendrical Calculations (Cambridge Univ. Press, 1997), описываются всевозможные алгоритмы, имеющие отношение к датам.]

15. Первым таким годом является 10 317 г. н. э., хотя описанная ошибка почти приводит к проблемам для годов н. э. 10108 + 19к, где О < fc < 10.

Между прочим, Т. X. ОБерн (Т. Н OBeirne) указал, что даты пасхи повторяются с периодом 5 700 ООО лет. Расчеты, проведенные Робертом Хиллом (Robert Hill), показали, что самой частой датой пасхи является 19 апреля (220 400 раз в течение указанного периода), самой ранней и наименее частой - 22 марта (27 550 раз), а самой поздней и предпоследней по частоте-25 апреля (42 ООО раз). Хилл нашел изящное объяснение того интересного факта, что частота каждой конкретной даты пасхи в указанном периоде времени всегда кратна 25.

16. Будем работать с масштабированными числами, Rn = 10"Гп. В этом случае Rn(l/m) = R тогда и татько тогда, когда 10"/(Л+ ) < пг < W/lR- ); отсюда на.ходи,м

= [2- 107(2Л- 1)].

* СУММА ГАРМОНИЧЕСКОГО РЯДА BUF

Выходные данные

0006.16

0008.449

0010.7509

0013.05363

получены за 65595u плюс время вывода. (Было бы быстрее вычислить Rn(l/m) непосредственно при т < 10"\/2, а затем применить предлагаемую процедуру.)

17. Положим 7V= [2-10"/(2m.-t-l)J. Тогда 5n = Hn+ OiN/10) + Y:T=iii2 10"/(2fc-l)J-[2 • 10"/(2fc-bl)J)fc/10" = Я;у-0(771-)-Ь O(m/10") - 1-Ь 2Я2т - Я„ = nln 10-Ь 27 - 1+ 21п2 + 0(10""), если просуммировать по частям и положить т к 10".

Между прочим, следующие несколько значений - это 5б = 15.356262, Sr = 17.6588276, 58 = 19.96140690, 59 - 22.263991779 и 5io = 24.5665766353; приближенным значением для Sio будет й; 24.566576621, которое точнее расчетного.

FAREY STJ STZ

9F X 1 Y

X+l Y+1

Предполагаем, что в rll содержится n, где n > 1.

ENTX STX STX STl ENT2 LDX INCX 0,1 ENTA 0 DIV STA MUL SLAX SUB STA LDA MUL SLAX SUB STA

xo yo •

yi -к +

- 0.

- 1.

- 1.

- n. 0.

Y+1.2 TEMP Y+1,2 5

y,2 Y+2.2 TEMP X+l, 2 5

X,2 X+2.2

[{Ук+п)1ук+\\.

Ук+2-

Xk+2-

CMPA Y+2.2 Проверить условие Xk+2 < Ук+2-INC2 1 fc •(- fc -Ь 1.

JL IB Если да, продолжить. 9Н JMP * Выйти из подпрограммы.

19. (а) По индукции. (Ь) Пусть fc > О и = ахк+\ - Хк, Y = аук+\ - Ук, где о = {{ук + п)/ук+\\- Из (а) й того, что О < У < п, получаем X ± У и X/Y > Хк+\1ук+\-Поэтому, если X/Y ф Хк+21Ук+2, то по определению X/Y > Хк+2/Ук+2- Отсюда следует, что

1 Хук+1 - Yxk+i Х Хк+1 Yyk+i Уук+1 У Ук+1

Уук+,

Хк+2 Ук+2)

(*=+2

\Ук+2 Ук + 1

Ук+1+Y

Хк+Л

Ук+i )

>

УУк+2 Ук+\Ук+2 Yyk + iyk+2 Yyk+iyk+2 Yyk + l

Исторические замечания. К Гарос (С Haros) предложил более сложное правило построения таких последовательностей в работе J. de IEcole Polytechnique 4,11 (1802), 364-368; его метод правилен, но доказательство несовершенно. Несколькими годами позже геолог Джон Фарей (John Farey) независимо предположил, что Хк/Ук всегда равно {xk-i + Xk+i)/iyk-i+yk+i) [Philos. Magazine and Journal 47 (1816), 385-386], доказательство вскоре