пречудово число

Пречудово число

Володимир Ільїн
"Квантіко" №1, 2014

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

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

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

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

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

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

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

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

– А от! Нещодавно читав в "Цікавої арифметиці". Шах однієї східної країни пообіцяв винахіднику шахів будь-яку нагороду. Той попросив … насипати зерен рису на кожну клітину дошки. На першу клітку одне зерно, на іншу – два, на третю – чотири … і так далі, кожен раз в 2 рази більше. Шах зрадів, що прохання, як йому здалося, так незначна, і негайно наказав все видати. Жадібність підвела шаха! У книжці доводиться, що за все виходить 264 – 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

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

– Слухай! На маткружке ми придумали пречудово число: 550 – це твір п'ятдесяти п'ятірок, а Мебіус – так називали вчителя інформатики – дав нам завдання:

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

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

>>> 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.

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


1 На сайті python.org в розділі Download (посилання зліва) скачайте інсталятор (для Windows – у верхній частині сторінки Python Windows x86 MSI Installer) і встановіть.
2 Пуск – Всі програми – Python 3.3 – Python (command line).


Like this post? Please share to your friends:
Залишити відповідь

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: