Пряме число

Навчання 26 серпня 2022 Перегляди: 74

— А ми на інформатиці перейшли на новий level! Почали вивчати Пітон! — важливо сказав восьмикласник Вовка, який тільки-но прийшов зі школи.

— Рептилій вивчають на зоології! — відповів Андрій, молодший брат Вовки, відірвавшись від комп’ютерної гри.

— Сам ти рептилія! — посміхнувся Вовка. — Пітон — це мова програмування, і названий він так не на честь змії, а на честь телевізійного шоу «Monty Python». Втім, пишеться так само, як змія.

— Ну і що ж такого особливого в твоєму Пітоні?

Та поки не знаю, — чесно зізнався Вовка. — Ми ж його тільки почали. Навчилися встановлювати і дізналися, що в ньому є довга арифметика і немає особливої різниці між рядками і числами!

— Як це? — запитав Андрій. Почуте його не дуже надихнуло. Сказати по правді, він не любив арифметику, всякий там усний рахунок. А тут ще «довга»…

— Ну дивись. На твоєму калькуляторі всього 10 розрядів. Це означає, що ти можеш працювати тільки з десятизначними числами. А Питон может вычислять хоть сто-, хоть миллион-, да хоть миллиард-секстиллионовзначные!

— Зараз покажу, давай його ^{встановим.1} А поки встановлюється, придумаємо, що б нам такого… довгого порахувати.

— А, ось! Нещодавно читав у «Цікавій арифметиці». Шах однієї східної країни пообіцяв винахіднику шахів будь-яку нагороду. Той попросив… насипати зірений рису на кожну клітку дошки. На першу клітку одне зерно, на іншу — два, на третю — чотири… і так далі, кожен раз в 2 рази більше. Шах зрадів, що прохання, як йому здалося, так нікчемне, і негайно наказав все видати. Жадібність підвела шаха! У книжці доводиться, що всього виходить 2⁶⁴ — 1 зірений, а це дуже багато. Давай порахуємо, скільки часу знадобилося б візирям, щоб відміряти рис точно, навіть якщо б у них було стільки зірок.

— ^{Запускаєм2}, — продовжив Вовка, у якого вже все встановилося, — можна вважати!

Андрія дещо здивувало те, що він побачив. Замість звичних значків і кнопок у чорному вікні було щось написано англійською і просто блимав курсор.

-ну ось. Сюди можемо вводити команди, — пояснив Вовка. — Скажімо,

>>> 2+2

натискаємо Enter і… вуаля:

4

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

— А як множення, ступінь писати? — запитав Андрій.

— Дуже просто — дивись! Плюс як +, мінус як -, множення — зірочкою * (Shift 8), ступінь двома зірочками (* *), ділення — прямим слішем (/). Можна ділити націло (//). Наприклад, 29/10 — це дві цілих дев’ять десятих, а 29//10 — рівно 2. І ще брати залишок від поділу (%). У нас виходить…

>>> 2**64 — 1

ввів Вовка і натиснув Enter, — 18446744073709551615 зірений!

— Припустимо, що вони вважали вдесятьох і кожен відраховував 100 зірок на секунду… У хвилині 60 секунд, в годині 60 хвилин… у тисячолітті 1000 років… Готово. Давай не будемо рахувати частки тисячоліть, розділимо націло. І Андрій набрав:

>>> 2**64-1//100*60*60*24*365*1000

18446744073709551616

— Дурниця якась!

— Звичайно, — сказав Вовка, — як і в математиці, в Пітоні можна і потрібно ставити дужки.

>>> (2**64-1)//(100*60*60*24*365*1000)

Комп’ютер відповів:

5849424

— П’ять мільйонів вісімсот сорок дев’ять тисяч чотириста двадцять чотири тисячоліття і ще небагато. Винахідник шахів, напевно, винайшов ще й еліксир безсмертя, якщо збирався стільки чекати!

— Слухай! На маткружці ми придумали нагальне число: 5⁵⁰ — це твір п’ятдесяти п’ятьох, а Мебіус — так називали вчителя інформатики — дав нам завдання:

Довести, що існує число без нулів, яке ділиться на нагальне.

Найпростіший спосіб довести, що щось існує, — це просто знайти його! Вперед, Пітоне!

>>> 5**50

88817841970012523233890533447265625

Спочатку Андрій дуже зрадів, тому що йому першому з усього класу вдалося «наживо» побачити нагальне число. Але радість була недовгою. У найпоширенішому виявилося цілих три нулі…

— Нічого, продовжимо! — сказав Андрій і почав множити на два, сім… Нічого не допомогло, навіть зведення в квадрат. Скрізь опинялися нулі…

— Ми можемо спробувати «вигнати» нулі з преотличного, — запропонував Вовка. Візьмемо, припустимо, 1023. Помножимо на 101 — нуль зникне або хоча б переїде лівіше: 1023•101 = 102300 + 1023 = 103323.

Тепер його можна помножити на 10001 (або 1023 відразу на 10101, це одне і те ж).

А, зрозумів! — сказав Андрій і швидко помножив 550 на 1000000000001:

88817841970101341075860545970499515533447265625

Останній нуль «перемістився» на 19-те місце справа.

— Спробуємо помножити на 1000001000000000001…

Число стало значно довшим, але нуль переїхав лівіше — на 26-ту позицію. Потім на 32-ту, 49-ту. Множення на 10000000000000000100000100 00001000001000000000001 «зрушило» останній нуль на 63-тє місце справа. Але лівіше нього все одно залишалося кілька нулів! Андрій втомився.

— А що, якщо нулі ніколи не «виженуться»? — запитав він.

Питання Вовку поставив у глухий кут. Дійсно, навіть на прикладі 1023 при таких множеннях нуль залишиться завжди! Хлопці приунили. Але тут втрутився тато.

— Які ознаки ділення ви знаєте? — запитав тато.

— На 2, 3, 4, 5, 9, 10… При чому тут це?

— На 4 — це добре! А на 8?

— Ну, останні три цифри повинні ділитися на 8. Це елементарно, тому що якщо їх «відкинути», буде число, що закінчується трьома нулями, а тисяча ділиться на 8.

— Чудово, а на власне?

— Такого ми не проходили, — ображено відповів Андрій, підозрюючи, що тато просто знущається.

-… Може, якщо останні 50 цифр числа діляться на пряме, то і саме число ділиться! Ну і що?.. — задумався Вовка.

— Радісно продовжив він. — Нуль у нас зараз на 63-й позиції. Візьмемо останні 50 цифр числа — це і буде відповідь!

— Сам відраховуй, — огризнувся все ще засмучений Андрій.

— А ось і не буду! Пітон — сила! Просто знайдемо залишок від поділу нашого монстра на один з п’ятдесятьма нулями. Рядки в Пітоні записуються в лапках. Їх теж можна складати і навіть множити, при цьому вони «склеюються». Дивись, — Вовка набрав:

> > > «Вовка-молодець!» * 100

На екрані висвітилося ще сто написів «Вовка-молодець!».

— «Зберемо» наше число:

>>> int(«»1″»+»»0″»*50)

Тут int для того, щоб з рядком як з числом робити арифметичні дії. Можна, звичайно, і просто 10 * * 50 написати, але з рядками цікавіше! Назад — функція str. Вона перекладає число на рядок. Це можна було діяти з числом як з рядком. Наприклад:

>>> len(str(5**50))

35

— Функція len шукає довжину рядка. Значить, у твоєму преотличному — 35 знаків! Порахуй!

Таким чином…

>>> 5**50*1000000000000000010000010000001000001000000000001 % int(«»1″»+ «»0″»*50)

Ну ось і відповідь:

75394925527871325954265557811595499515533447265625

— Перевіримо, — сказав Андрій, який до цього часу трохи заспокоївся.

>>> 75394925527871325954265557811595499515533447265625 % (5**50)

0

— Точно! Залишок дорівнює нулю, значить ділиться! І нулів немає!

— А ось тут, до речі, дужки необов’язкові, — зауважив Вовка. — Тому що в Пітоні, як у математиці, — якщо без дужок, то спочатку ступінь (* *), потім множення і ділення (* ,/,//), а потім додавання і віднімання.

Андрій вивів число на принтер — то Мебіус здивується!

«Довгі» завдання

1. Професор Бурік не вірить, що число можливих різних станів кубика Рубіка дорівнює 43 252 003 274 489 856 000. 1 січня 2014 року опівночі він запустив для перевірки свій комп’ютер, який перевіряє мільярд статків на секунду. У скільки Бурику треба бути вдома, щоб побачити результат?

2. Доведіть ознаку ділимості на нагальну.

3. Скільки серед першого тисячі ступенів двійки, рахуючи з першого, починаються з одиниці?

Підказка: допоможе визначити довжину рядка, функції len і str.

Художник Артем Костюкевич

¹ На сайті python.org в розділі Download (посилання ліворуч) завантажте інсталятор (для Windows — вгорі сторінки Python Windows x86 MSI Installer) і ^{встановіть .2}

Пуск — Всі програми — Python 3.3 — Python (command line).