Как стать автором
Обновить

Задача Александра Ивановича Корейко

Алгоритмы
Александр Иванович Корейко, один из ничтожнейших служащих ГЕРКУЛЕС’а, был человек в последнем приступе молодости, ему было 38 лет. На красном сургучном лице сидели желтые пшеничные брови и белые глаза. Английские усики цветом даже походили на созревший злак. Лицо его казалось бы совсем молодым, если бы не грубые ефрейторские складки, пересекавшие щеки и шею. На службе Александр Иванович вел себя как сверхсрочный солдат: не рассуждал, был исполнителен, трудолюбив, искателен и туповат.

— Робкий он какой-то, — говорил о нем начальник финсчета, — какой-то уж слишком приниженный, преданный какой-то чересчур. Только объявят подписку на заем, как он уже лезет со своим месячным окладом. Первым подписывается. А весь оклад-то 46 рублей. Хотел бы я знать, как он существует на эти деньги.

Была у Александра Ивановича удивительная особенность. Он мгновенно умножал и делил в уме большие трехзначные и четырехзначные числа. Но это не освободило Александра Ивановича от репутации туповатого парня.

— Слушай, Александр Иванович, — спрашивал сосед, — сколько будет 836 на 423?
(«Золотой теленок», Илья Ильф, Евгений Петров )

Перечитывая роман «Золотой теленок», я решил повторить расчеты подпольного миллионера. Я не обладаю способностью перемножать в уме большие числа и не ставлю перед собой задачу таковую способность развить. Моя цель скромнее — найти способ быстрого вычисления вышеприведенного примера. В качестве инструмента я решил использовать коллекцию красивых произведений, которую собрал по дороге на работу и храню в сотовом телефоне. Вот некоторые из них:

  • 13*23 =299
  • 17*47 =799
  • 7*11*13=1001

Первое, что я сделал — нашел разложение на множители:



По поводу разложения на множители. Как это сделать быстро. Берем первое число 423, сумма цифр делится на 9 значит число тоже делится на 9. Для деления используем быстрый алгоритм, который приводится ниже. 423/9= 46,(9)=47.
Второе число 836.Первый делитель почти очевиден — это 4. 836=4*209. 209 делится на 11, согласно соответствующему признаку делимости. Способ деления на 11 почти повторяет, метод который мы использовали для деления на 9 209/11= 2 (-2),11 (-11)= 18,9999..=19.

Теперь перепишем исходный пример в следующем виде:

423*836=4*99*47*(17+2)=4*99*799+4*99*94, здесь я использовал красивое произведение 17*47 =799.

4*99*799=4*(100-1)*(800-1)=4*(80000-900+1)=320 000-3 600+4

4*99*94=376*(100-1)=37 600-376

Осталось сложить полученные выражения:

320 000 + (37 600-3 600) + (4-376) = 320 000 + 34 000 — 372 = 354 000 — 372 = 353 628

— 353.628, — отвечал Корейко, помедлив самую малость. И сосед не проверял результата умножения, ибо знал, что туповатый Корейко никогда не ошибается.

Наш результат совпадает с ответом Корейко. Разумеется, в уме приведенные расчеты выполнить, скорее, всего, невозможно. Мне помогали карандаш и бумага. Вопрос о том, как вычислить пример устно, остается открытым.

Жду советов.

Прочитав полученные комментарии, я должен признать, что не нашел того, что искал. По-видимому, неверно изложил свою мысль. В прекрасной книге «Вы, конечно, шутите, мистер Фейнман!» есть глава, которая называется «Счастливые числа». В ней Ричард Фейнман рассказывает о своей коллекции методов и чисел для быстрых вычислений.
Я запомнил значения нескольких логарифмов и начал замечать, что происходит. Например, если кто-то спрашивает: «Чему равно 28 в квадрате?», замечаешь, что квадратный корень из двух равен 1, 4, а 28 — это 20, умноженное на 1, 4, поэтому 28 в квадрате должно примерно равняться 400, умноженному на 2, или 800.
Если кто-нибудь спрашивает, сколько получится, если разделить 1 на 1, 73, то можно сразу ответить, что 0, 577, потому что знаешь, что 1, 73 — это почти квадратный корень из 3, поэтому 1/1, 73 равно одной трети квадратного корня из 3. А если нужно определить отношение 1/1, 75, оно равно величине обратной дроби 7/4, а вы помните, что если в знаменателе стоит 7, то десятичные цифры повторяются: 0, 571428…

Я надеялся, что кто-то располагает своей коллекцией счастливых чисел, из которой получается число Корейко.
Кстати, счастливые числа встречаются в самых неожиданных местах. В той же главе у Фейнмана есть такой эпизод.
Это весьма обеспокоило японца, потому что он явно прекрасно умел выполнять арифметические операции с помощью счёт, а тут его почти победил какой-то посетитель ресторана.
«Raios cubicos!» — мстительно говорит он. Кубические корни! Он хочет брать кубические корни с помощью арифметики! Трудно найти более сложную фундаментальную задачу в арифметике. Должно быть, это был его конёк в упражнениях со счетами.
Он пишет на бумаге число — любое большое число — я до сих пор его помню: 1729, 03. Он начинает работать с этим числом и при этом что-то бормочет и ворчит: «Бу-бу-бу-хм-гм-бу-бу», — он трудится как демон! Он просто погружается в этот кубический корень!
Я же тем временем просто сижу на своём месте.
Один из официантов говорит: «Что Вы делаете?»
Я указываю на голову. «Думаю!» — говорю я. Затем пишу на бумаге 12. Ещё через какое-то время — 12, 002.
Человек со счетами вытирает со лба пот и говорит: «Двенадцать!»
«О, нет! — возражаю я. — Больше цифр! Больше цифр!» Я знаю, что, когда с помощью арифметики берёшь кубический корень, то каждая последующая цифра требует большего труда, чем предыдущая. Это работа не из лёгких.
Он опять уходит в работу и при этом бормочет: «Уф-фыр-хм-уф-хм-гм…». Я же добавляю ещё две цифры. Наконец, он поднимает голову и говорит: «12, 0!»
Официанты просто светятся от счастья. Они говорят японцу: «Смотрите! Он делает это в уме, а Вам нужны счёты! И цифр у него больше!»
Он был абсолютно измотан и ушёл, побеждённый и униженный. Официанты поздравили друг друга.
Каким же образом посетитель выиграл у счётов? Число было 1729, 03. Я случайно знал, что в кубическом футе 1728 кубических дюймов, так что было ясно, что ответ немногим больше 12. Излишек же, равный 1, 03, — это всего лишь одна часть из почти 2000, а во время курса исчисления я запомнил, что для маленьких дробей излишек кубического корня равен одной трети излишка числа. Так что мне пришлось лишь найти дробь 1/1728, затем умножить полученный результат на 4 (разделить на 3 и умножить на 12). Вот так мне удалось получить целую кучу цифр.


А ведь число 1729 обладает интересным свойством. Однажды Годфри Харди приехал навестить в больнице Сриниваса Рамануджана. Харди приехал на такси с номером 1729 и по ходу беседы с Рамануджаном заметил, что, мол, удивительно скучное число ему попалось в качестве номера. На это индиец ответил, что это не правда — 1729 является минимальным натуральным числом, представимым в виде суммы кубов двух натуральных чисел двумя разными способами. Действительно,

1729 = 1^3 + 12^3 = 9^3 + 10^3.

Не правда ли, удивительное совпадение?

Тем не менее, я не оставлял попыток найти быстрое решение для примера Корейко. Этот метод мне понравился, хотя и он несовершенен.

836*423=(840-4)*(420+2)+836

Произведение (840-4)*(420+2) является аналогом известной формулы (a-b)*(a+b). В нашем случае перекрестные произведения 840*2 и 420*4 равны и имеют противоположные знаки, поэтому они сокращаются. На выходе получаем следующее:

840*420-8+836=2*42*42*100+828=8*21*21*100+828

Возвести 21 в квадрат можно разными способами. Наверное самый простой, через выражение 21^2-20^2=41. Отсюда 21^2=400+41=441;
441*8=3200+320+8=3528.

И окончательно, 352800+828=353 628.

Посмотрев на решение, увидел еще одно упрощение.

8*21*21*100+828=800*21*21+800+28=800*(21*21+1)+28

А последнее выражение уже действительно считается в уме.

800*442+28=353600+28=353 628.

Вернувшись спустя какое-то время к данному примеру, я попытался еще раз быстро вычислить 840*420. Предыдущий вариант с умножением 8*21*21 меня не совсем устраивал. Попытаемся вычислить 2*42*42. Квадрат чисел в интервале 41...49 можно получить следующим образом.

(40+i)^2=(15+i)*100+(10-i)^2. В нашем случае 42^2=(15+2)*100+64=1764. А искомое значение равно 2*1764=3528

Окончательный результат, естественно, не изменился и равен 352800+828=353 628.

Ну и последнее замечание о примере Александра Ивановича. Вернемся к представлению искомого числа через множители 4*9*11*19*47. Сгруппировав коэффициенты разложения, получим (400-4)*(900-7). В таком виде задача решается совсем быстро и на этом я решил для себя, что вопрос закрыт.

Надо заметить, что кроме Корейко неплохо считали в уме и другие литературные персонажи. Например, Воланд.
− Девять месяцев, − задумчиво считал Воланд, − двести сорок девять тысяч… Это выходит круглым счетом двадцать семь тысяч в месяц? Маловато, но при скромной жизни хватит. Да еще десятки.

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

Размышления над способами быстрого деления на 9 привели меня к следующим наблюдениям. Поскольку мы можем заменить деление умножением на 0,111..., то в некоторых случаях выручает следующий алгоритм. Сначала ищется период итоговой дроби — это остаток от деления суммы цифр исходного числа на 9, в нашем случае это (2+4+9)%9=6. Затем начинаем двигаться слева направо и записывать сумму цифр делимого.

(2) (2+4=6) (2+4+9=15) (15) (15)…

Десятки по правилам сложения в столбик переносим в левый разряд. Ответ — 27,66666…

Еще один пример 734/9.

Период — (7+3+4)%9=5

(7) (7+3=10) (7+3+4=14) (14)…

Ответ — 81,5

А вот еще один литературный герой, который отличался быстротой устного счета
— Ну, видите ли, я вдруг постигнул ваш характер. Итак, почему ж не дать бы мне по пятисот рублей за душу, но… состоянья нет; по пяти копеек, извольте, готов прибавить, чтобы каждая душа обошлась, таким образом, в тридцать копеек.

— Ну, батюшка, воля ваша, хоть по две копейки пристегните:

— По две копеечки пристегну, извольте. Сколько их у вас? Вы, кажется, говорили семьдесят?

— Нет. Всего наберется семьдесят восемь.

— Семьдесят восемь, семьдесят восемь, по тридцати копеек за душу, это будет… — здесь герой наш одну секунду, не более, подумал и сказал вдруг: — это будет двадцать четыре рубля девяносто шесть копеек! — он был в арифметике силен.


Пример Чичикова, разумеется, проще задачи Корейко, но и здесь есть различные подходы. Предлагаю решение от программиста, то есть человека который помнит степени двойки.

78*32=39*64=(40-1)*64=2560-64=2496

Но Чичиков не был программистом, Павел Иванович добывал себе на жизнь иным трудом. А посему, считать предложенным способом не мог. У него был другой подход, возможно, такой.

78=80-2
32=30+2

(80-2)*(30+2)= 2 400+2*(80-30)-4=2 500-4=2 496

А может и такой. Вспомним следующий прием. Если надо умножить что-то на 33, то мы можем разделить это что-то на 3, умножить результат на 100 и вычесть первое частное. Таким образом,
78*33= 26*100-26, а 78*32=26*100-26-78=25*100-4=2 496

Я имею обыкновение возвращаться к старым задачам, хотя бы для того чтобы вспомнить условие. В этот раз я обнаружил, что пример Чичикова можно решить с помощью алгоритма перемножения чисел, последние цифры которых дают в сумме 10. Это метод открыл один из учеников Рачинского С.А. Вот как это делается:

32*78=3*(7+1)*100+2*(78-30)=2496

Недавно обнаружил еще один литературный пример на умножение.

Но один из членов попросил разрешения задать еще один вопрос:
— Сколько будет, если умножить двенадцать тысяч восемьсот девяносто семь на тринадцать тысяч восемьсот шестьдесят три?
— Семьсот двадцать девять,-- не моргнув глазом, ответил Швейк.

Заметим, что Швейк считает быстро, но неверно. Впрочем, допускаю, что ответ был им дан в системе исчисления, которая отличается от десятичной.
Теги:Устный счетлитературные задачи
Хабы: Алгоритмы
Всего голосов 23: ↑9 и ↓14-5
Просмотры11K

Похожие публикации

Лучшие публикации за сутки