Відмінності між версіями «Проблема 196»

Перейти до навігації Перейти до пошуку
1520 байтів додано ,  6 років тому
нема опису редагування
{{Редагую|Dimma837}}
'''Проблема 196'''&nbsp;— умовна назва [[Відкриті математичні питання|невирішеної математичної задачі]]: чи призведе [[Ітерація|ітеративна]] операція ''«перевернути і скласти»'' ({{lang-en|Reverse-Then-Add}}), застосована до числа [[196 (число)|196]] певну кінцеву кількість разів, до [[паліндром]]у&nbsp;— числу, що однаково читається в обох напрямках (зліва направо та справа наліво)?<br/>
'''Числа Лішрел''' ({{lang-en| Lychrel number}})&nbsp;— це [[натуральні числа]], які не можуть стати паліндромами за допомогою ітеративного процесу «перевернути і скласти» в [[Десяткова система числення|десятковій системі числення]]. Цей процес називається ''196-алгоритмом''. Назва «Lychrel», придумана ''Wade VanLandingham'', являється приблизною [[Анаграма|анаграмою]] імені його подруги&nbsp;— ''Шеріл'' ({{lang-en|Cheryl}}). Не доведено існування жодного з чисел Лішрел, але деякі числа можуть ними бути і найменше з них&nbsp;— 196.
* 89 проходить незвично багато&nbsp;— 24 ітерації (найбільшу кількість для чисел менше 10000, які точно перетворюються у паліндром), перш ніж досягти паліндрома 8813200023188<ref>[http://www.jasondoucette.com/pal/89 REVERSAL-ADDITION PALINDROME TEST ON 89]</ref>.
* 10911 досягає паліндрома 4668731596684224866951378664 після 55 кроків<ref>[http://www.jasondoucette.com/pal/10911 REVERSAL-ADDITION PALINDROME TEST ON 10911]</ref>.
* 1.186.060.307.891.929.990 проходить 261 ітерацію<ref>[http://www.jasondoucette.com/pal/1186060307891929990 REVERSAL-ADDITION PALINDROME TEST ON 1186060307891929990]</ref> і стає 119-циферний паліндромом, який в даний час є світовим рекордом<ref>[http://www.jasondoucette.com/worldrecords.html#Most MOST DELAYED PALINDROMIC NUMBER {{ref-en}}]</ref> (найбільшим отриманим за допомогою алгоритма паліндромом). Воно було знайдено Джейсоном ДусеттеДусетом за допомогою комп'ютера 30 листопада 2005.
 
Припускають, що найменшим натуральним числом, що не перетворюється в паліндром, є тризначне число 196.
 
== Кандидати в числа Лішрел ==
В інших [[Система числення|системах числення]] існують числа, які ніколи не перетворяться в паліндром внаслідок даної операції<ref>[http://www.math.niu.edu/~rusin/known-math/96/palindrome Mathematical letters with proofs {{ref-en}}]</ref><ref>[http://www.mathpages.com/home/kmath004/kmath004.htm Digit Reversal Sums Leading to Palindromes {{ref-en}}]</ref>. Але в десятковій системі числення для жодного з кандидатів в числа Лішрел не існує строгого доведення, що воно є числом Лішрел. Таким чином, саме існування таких чисел не доведено. Подібні числа неофіційно називають «кандидати в числа Лішрел». {{OEIS|A023108}}:
Digit Reversal Sums Leading to Palindromes {{ref-en}}]</ref>. Але в десятковій системі числення для жодного з кандидатів в числа Лішрел не існує строгого доведення, що воно є числом Лішрел. Таким чином, саме існування таких чисел не доведено. Подібні числа неофіційно називають «кандидати в числа Лішрел». {{OEIS|A023108}}:
 
'''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 збільшилося до числа в один мільйон цифр після 2.415.836 ітерацій без досягнення паліндрома. Уокер опублікував свої дослідження в Інтернет разом з останньою контрольною точкою, запрошуючи інших відновити пошуки на основі останнього досягнутого числа.
 
У 1995 році Тім Ірвін використав [[суперкомп'ютер]] і досяг позначки в два мільйони цифр всього за три місяці, знову не знайшовши паліндрома. Джейсон Дусетте досяг 12,500,000 цифр в травні 2000 року. ''Wade VanLandingham'', використовуючи програму Джейсона ДусеттеДусетта, досяг 13 мільйонів цифр, що було опубліковано<ref>[http://www.jasondoucette.com/yesmagazine/yes-magazine-75-dpi.jpg Coming or Going? {{ref-en}}]</ref> в Yes Mag&nbsp;— канадському науковому журналі для дітей. З червня 2000 року VanLandingham продовжував лідирувати, використовуючи програми, написані різними ентузіастами. До 1 травня 2006 він досяг позначки 300 мільйонів цифр (зі швидкістю одного мільйона цифр кожні 5-7 днів). Використовуючи [[розподілені обчислення]], в 2011 році ''Romain Dolbeau'' за мільярд ітерацій отримав число, що складається з 413,930,770 цифр<ref>[http://www.isc-events.com/isc14_ap/presentationdetails.htm?t=presentation&o=264&a=select&ra=sessiondetails The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest]</ref>, а в липні 2012 року його обчислення досягли числа з 600&nbsp;млн цифр<ref>[http://www.dolbeau.name/dolbeau/p196/p196.html The p196_mpi page {{ref-en}}]</ref>. Паліндром все ще не виявлений.
 
Інші кандидати в числа Лішрел, які піддавалися такому ж перебору, як наприклад 879, 1997 і 7059, також були простежені протягом мільйонів ітерацій без виявлення паліндрома.
 
== Примітки ==
{{reflist}}
 
== Посилання ==
* [http://www.fourmilab.ch/documents/threeyears/threeyears.html Джон Уокер]{{ref-en}} — три роки обчислень.
* [http://www.fourmilab.ch/documents/threeyears/two_months_more.html Тім Ирвін]{{ref-en}} — близько двух місяців обчислень.
* [http://www.jasondoucette.com/worldrecords.html Джейсон Дусет — Світові рекорди]{{ref-en}} — Найбільші отримані паліндроми.
* [http://users.tmok.com/~pla/Lychrel/Lychrel.shtml Бенджамін Деспрес]{{ref-en}}.
* [http://www.p196.org/ 196 й інші числа Лішрел]{{ref-en}} — Сайт ''Wade VanLandingham''.
* {{MathWorld|urlname=196-Algorithm|title=196-Algorithm}}
* {{MathWorld|urlname=LychrelNumber|title=Lychrel Number}}
* {{MathWorld|urlname=PalindromicNumberConjecture|title=Palindromic Number Conjecture}}
* {{MathWorld|urlname=Reverse-Then-AddSequence|title=Reverse-Then-Add Sequence}}
 
[[Категорія:Математичні гіпотези]]
[[Категорія:Теорія чисел]]

Навігаційне меню