Loading AI tools
число З Вікіпедії, вільної енциклопедії
Проблема 196 — умовна назва невирішеної математичної задачі: чи призведе ітеративна операція «перевернути і скласти» (англ. Reverse-Then-Add), застосована до числа 196 певну кінцеву кількість разів, до паліндрому — числа, що однаково читається в обох напрямках (зліва направо та справа наліво)?
Числа Лішрел (англ. Lychrel number) — це натуральні числа, які не можуть стати паліндромами за допомогою ітеративного процесу «перевернути і скласти» в десятковій системі числення. Цей процес називається 196-алгоритмом. Назва «Lychrel», придумана Wade VanLandingham, є приблизною анаграмою імені його подруги — Шеріл (англ. Cheryl). Не доведено існування жодного з чисел Лішрел, але деякі числа можуть ними бути і найменше з них — 196.
Суть операції «перевернути і скласти» полягає в додаванні до числа його перевернутої копії — паліндрому. Наприклад, 56 + 65 = 121, 521 + 125 = 646.
Деякі числа (зокрема, всі однозначні і двозначні числа) стають паліндромами досить швидко — після декількох застосувань операції, і тому не є числами Лішрел. Близько 80 % всіх чисел, менших 10000, перетворюються в паліндром за 4 або менше кроків. Близько 90 % — за 7 і менше кроків.
Ось кілька прикладів чисел, що не є числами Лішрел:
Припускають, що найменшим натуральним числом, що не перетворюється в паліндром, є тризначне число 196.
В інших системах числення існують числа, які ніколи не перетворяться в паліндром внаслідок даної операції[5][6]. Але в десятковій системі числення для жодного з кандидатів в числа Лішрел не існує строгого доведення, що воно є числом Лішрел. Таким чином, саме існування таких чисел не доведено. Подібні числа неофіційно називають «кандидати в числа Лішрел». послідовність A023108 з Онлайн енциклопедії послідовностей цілих чисел, OEIS:
196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1495, 1497, 1585, 1587, 1675, 1677, 1765, 1767, 1855, 1857, 1945, 1947, 1997.
Виділені жирним шрифтом числа вважаються одними з базових чисел Лішрел. Комп'ютерні програми Джейсона Дусета, Яна Петерса і Бенджаміна Деспреса знайшли й інших кандидатів в числа Лішрел. Більш того, Бенджамін Деспрес виявив всі базові числа Лішрел, що складаються з менш, ніж 17 цифр. Сайт Wade VanLandingham містить списки базових чисел Лішрел для кожної довжини числа.
Метод грубої сили, який спочатку розробив Джон Вокер, був вдосконалений. Наприклад, Vaughn Suite розробив програму, яка зберігає тільки перші і останні кілька цифр кожної ітерації, дозволяючи тестувати цифрові закономірності протягом мільйонів ітерацій без необхідності збереження кожної ітерації повністю. Але поки що не було придумано алгоритму, який би обминав ітеративний процес, отримуючи паліндроми іншим способом.
Термін потік (англ. Thread) ввів Джейсон Дусетте, позначаючи так послідовність чисел, одержуваних у результаті ітерацій вихідного числа. Базове число (англ. Seed) і пов'язані з ним споріднені числа (англ. Kin) сходяться в одному потоці. Потік не включає вихідне базове число або його родича, а тільки числа, які є загальними для обох, після того, як вони зійдуться.
Базові числа є підпослідовністю чисел Лішрел; це найменші числа з кожного потоку, що не утворюють паліндром. Базове число може бути саме по собі паліндромом.
Споріднені числа також є підмножиною чисел Лішрел; це всі числа потоку, за винятком базового, або будь-яке число, яке увілляється в цей потік з будь-якого місця після однієї ітерації. Цей термін був введений Кодзі Ямасітою в 1997 році.
Оскільки 196 є найменшим кандидатом в числа Лішрел, воно отримало найбільшу увагу.
Джон Вокер почав вивчати потік числа 196 12 серпня 1987 на робочої станції Sun 3/260. Він написав програму на C, яка виконує операцію «перевернути і скласти» і перевіряє на паліндром після кожного кроку. Програма була запущена у фоновому режимі з низьким пріоритетом. Вона зберігала контрольні точки в файл кожні дві години і в момент закриття системи, записуючи досягнуті до того часу число і номер ітерації. Програма запускалася автоматично з останньої контрольної точки після кожного включення комп'ютера. Вона працювала протягом майже трьох років, а потім зупинилася (як і було запрограмовано) 24 травня 1990 з повідомленням:
![]() |
Оригінальний текст (англ.) Stop point reached on pass 2,415,836. Number contains 1,000,000 digits. |
![]() |
Число 196 збільшилося до числа в один мільйон цифр після 2.415.836 ітерацій без досягнення паліндрома. Вокер опублікував свої дослідження в Інтернет разом з останньою контрольною точкою, запрошуючи інших відновити пошуки на основі останнього досягнутого числа.
У 1995 році Тім Ірвін використав суперкомп'ютер і досяг позначки в два мільйони цифр всього за три місяці, знову не знайшовши паліндрома. Джейсон Дусетте досяг 12,500,000 цифр в травні 2000 року. Wade VanLandingham, використовуючи програму Джейсона Дусетта, досяг 13 мільйонів цифр, що було опубліковано[7] в Yes Mag — канадському науковому журналі для дітей. З червня 2000 року VanLandingham продовжував лідирувати, використовуючи програми, написані різними ентузіастами. До 1 травня 2006 він досяг позначки 300 мільйонів цифр (зі швидкістю одного мільйона цифр кожні 5-7 днів). Використовуючи розподілені обчислення, в 2011 році Romain Dolbeau за мільярд ітерацій отримав число, що складається з 413,930,770 цифр[8], а в липні 2012 року його обчислення досягли числа з 600 млн цифр[9]. Паліндром все ще не виявлений.
Інші кандидати в числа Лішрел, які піддавалися такому ж перебору, як, наприклад, 879, 1997 і 7059, також були простежені протягом мільйонів ітерацій без виявлення паліндрома.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.