Проблема 196

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Проблема 196 — умовна назва невирішеної математичної задачі: чи призведе ітеративна операція «перевернути і скласти» (англ. Reverse-Then-Add), застосована до числа 196 певну кінцеву кількість разів, до паліндрому — числу, що однаково читається в обох напрямках (зліва направо та справа наліво)?

Числа Лішрел (англ. Lychrel number) — це натуральні числа, які не можуть стати паліндромами за допомогою ітеративного процесу «перевернути і скласти» в десятковій системі числення. Цей процес називається 196-алгоритмом. Назва «Lychrel», придумана Wade VanLandingham, є приблизною анаграмою імені його подруги — Шеріл (англ. Cheryl). Не доведено існування жодного з чисел Лішрел, але деякі числа можуть ними бути і найменше з них — 196.

Алгоритм[ред. | ред. код]

Суть операції «перевернути і скласти» полягає в додаванні до числа його перевернутої копії — паліндрому. Наприклад, 56 + 65 = 121, 521 + 125 = 646.

Деякі числа (зокрема, всі однозначні і двозначні числа) стають паліндромами досить швидко — після декількох застосувань операції, і тому не є числами Лішрел. Близько 80 % всіх чисел, менших 10000, перетворюються в паліндром за 4 або менше кроків. Близько 90 % — за 7 і менше кроків.

Ось кілька прикладів чисел, що не є числами Лішрел:

  • 56 стає паліндромом після однієї ітерації: 56 + 65 = 121.
  • 57 стає паліндромом після двох ітерацій: 57 + 75 = 132, 132 + 231 = 363.
  • 59 також не є числом Лішрел, оскільки воно стає паліндромом після 3 ітерацій: 59 + 95 = 154, 154 + 451 = 605, 605 + 506 = 1111.
  • 89 проходить незвично багато — 24 ітерації (найбільшу кількість для чисел менше 10000, які точно перетворюються у паліндром), перш ніж досягти паліндрома 8813200023188[1].
  • 10911 досягає паліндрома 4668731596684224866951378664 після 55 кроків[2].
  • 1.186.060.307.891.929.990 проходить 261 ітерацію[3] і стає 119-циферним паліндромом, який в даний час є світовим рекордом[4] (найбільшим отриманим за допомогою алгоритму паліндромом). Воно було знайдено Джейсоном Дусетом за допомогою комп'ютера 30 листопада 2005.

Припускають, що найменшим натуральним числом, що не перетворюється в паліндром, є тризначне число 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 розробив програму, яка зберігає тільки перші і останні кілька цифр кожної ітерації, дозволяючи тестувати цифрові закономірності протягом мільйонів ітерацій без необхідності збереження кожної ітерації повністю. Але поки що не було придумано алгоритму, який би обминав ітеративний процес, отримуючи паліндроми іншим способом.

Пов'язані терміни[ред. | ред. код]

Потік числа 196 і споріднених з ним чисел

Термін потік (англ. Thread) ввів Джейсон Дусетте, позначаючи так послідовність чисел, одержуваних у результаті ітерацій вихідного числа. Базове число (англ. Seed) і пов'язані з ним споріднені числа (англ. Kin) сходяться в одному потоці. Потік не включає вихідне базове число або його родича, а тільки числа, які є загальними для обох, після того, як вони зійдуться.

Базові числа є підпослідовністю чисел Лішрел; це найменші числа з кожного потоку, що не утворюють паліндром. Базове число може бути саме по собі паліндромом.

Споріднені числа також є підмножиною чисел Лішрел; це всі числа потоку, за винятком базового, або будь-яке число, яке увілляється в цей потік з будь-якого місця після однієї ітерації. Цей термін був введений Кодзі Ямасітою в 1997 році.

Дослідження числа 196[ред. | ред. код]

Оскільки 196 є найменшим кандидатом в числа Лішрел, воно отримало найбільшу увагу.

Джон Вокер почав вивчати потік числа 196 12 серпня 1987 на робочої станції Sun 3/260. Він написав програму на C, яка виконує операцію «перевернути і скласти» і перевіряє на паліндром після кожного кроку. Програма була запущена у фоновому режимі з низьким пріоритетом. Вона зберігала контрольні точки в файл кожні дві години і в момент закриття системи, записуючи досягнуті до того часу число і номер ітерації. Програма запускалася автоматично з останньої контрольної точки після кожного включення комп'ютера. Вона працювала протягом майже трьох років, а потім зупинилася (як і було запрограмовано) 24 травня 1990 з повідомленням:

Досягнута точка зупинки на 2.415.836 ітерації.
Число містить 1.000.000 цифр.
Оригінальний текст (англ.)
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, також були простежені протягом мільйонів ітерацій без виявлення паліндрома.

Примітки[ред. | ред. код]

  1. ↑ REVERSAL-ADDITION PALINDROME TEST ON 89
  2. ↑ REVERSAL-ADDITION PALINDROME TEST ON 10911
  3. ↑ REVERSAL-ADDITION PALINDROME TEST ON 1186060307891929990
  4. ↑ MOST DELAYED PALINDROMIC NUMBER(англ.)
  5. ↑ Mathematical letters with proofs (англ.). Архів оригіналу за 16 травня 2006. Процитовано 31 січня 2015.
  6. ↑ Digit Reversal Sums Leading to Palindromes(англ.)
  7. ↑ Coming or Going?(англ.)
  8. ↑ The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest. Архів оригіналу за 19 квітня 2015. Процитовано 31 січня 2015.
  9. ↑ The p196_mpi page [Архівовано 2015-02-11 у Wayback Machine.](англ.)

Посилання[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=Проблема_196&oldid=39839758