Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Проблема 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.
- 10911 досягає паліндрома 4668731596684224866951378664 після 55 кроків.
- 1.186.060.307.891.929.990 проходить 261 ітерацію і стає 119-циферним паліндромом, який в даний час є світовим рекордом (найбільшим отриманим за допомогою алгоритму паліндромом). Воно було знайдено Джейсоном Дусетом за допомогою комп'ютера 30 листопада 2005.
Припускають, що найменшим натуральним числом, що не перетворюється в паліндром, є тризначне число 196.
Кандидати в числа Лішрел
В інших системах числення існують числа, які ніколи не перетворяться в паліндром внаслідок даної операції. Але в десятковій системі числення для жодного з кандидатів в числа Лішрел не існує строгого доведення, що воно є числом Лішрел. Таким чином, саме існування таких чисел не доведено. Подібні числа неофіційно називають «кандидати в числа Лішрел». послідовність 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 є найменшим кандидатом в числа Лішрел, воно отримало найбільшу увагу.
Джон Вокер почав вивчати потік числа 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 мільйонів цифр, що було опубліковано в Yes Mag — канадському науковому журналі для дітей. З червня 2000 року VanLandingham продовжував лідирувати, використовуючи програми, написані різними ентузіастами. До 1 травня 2006 він досяг позначки 300 мільйонів цифр (зі швидкістю одного мільйона цифр кожні 5-7 днів). Використовуючи розподілені обчислення, в 2011 році Romain Dolbeau за мільярд ітерацій отримав число, що складається з 413,930,770 цифр, а в липні 2012 року його обчислення досягли числа з 600 млн цифр. Паліндром все ще не виявлений.
Інші кандидати в числа Лішрел, які піддавалися такому ж перебору, як, наприклад, 879, 1997 і 7059, також були простежені протягом мільйонів ітерацій без виявлення паліндрома.
Примітки
- REVERSAL-ADDITION PALINDROME TEST ON 89
- REVERSAL-ADDITION PALINDROME TEST ON 10911
- REVERSAL-ADDITION PALINDROME TEST ON 1186060307891929990
- MOST DELAYED PALINDROMIC NUMBER(англ.)
- Mathematical letters with proofs (англ.). Архів оригіналу за 16 травня 2006. Процитовано 31 січня 2015.
- Digit Reversal Sums Leading to Palindromes(англ.)
- Coming or Going?(англ.)
- The p196_mpi Implementation of the Reverse-And-Add Algorithm for the Palindrome Quest. Архів оригіналу за 19 квітня 2015. Процитовано 31 січня 2015.
- The p196_mpi page [Архівовано 2015-02-11 у Wayback Machine.](англ.)
Посилання
- Джон Вокер (англ.) — три роки обчислень.
- Тім Ирвін (англ.) — близько двох місяців обчислень.
- Джейсон Дусет — Світові рекорди (англ.) — Найбільші отримані паліндроми.
- Бенджамін Деспрес (англ.).
- 196 й інші числа Лішрел(англ.) — Сайт Wade VanLandingham.
- Weisstein, Eric W. 196-Algorithm(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Lychrel Number(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Palindromic Number Conjecture(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Reverse-Then-Add Sequence(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Problema 196 umovna nazva nevirishenoyi matematichnoyi zadachi chi prizvede iterativna operaciya perevernuti i sklasti angl Reverse Then Add zastosovana do chisla 196 pevnu kincevu kilkist raziv do palindromu chisla sho odnakovo chitayetsya v oboh napryamkah zliva napravo ta sprava nalivo Chisla Lishrel angl Lychrel number ce naturalni chisla yaki ne mozhut stati palindromami za dopomogoyu iterativnogo procesu perevernuti i sklasti v desyatkovij sistemi chislennya Cej proces nazivayetsya 196 algoritmom Nazva Lychrel pridumana Wade VanLandingham ye pribliznoyu anagramoyu imeni jogo podrugi Sheril angl Cheryl Ne dovedeno isnuvannya zhodnogo z chisel Lishrel ale deyaki chisla mozhut nimi buti i najmenshe z nih 196 Zmist 1 Algoritm 2 Kandidati v chisla Lishrel 3 Pov yazani termini 4 Doslidzhennya chisla 196 5 Primitki 6 PosilannyaAlgoritmred Sut operaciyi perevernuti i sklasti polyagaye v dodavanni do chisla jogo perevernutoyi kopiyi palindromu Napriklad 56 65 121 521 125 646 Deyaki chisla zokrema vsi odnoznachni i dvoznachni chisla stayut palindromami dosit shvidko pislya dekilkoh zastosuvan operaciyi i tomu ne ye chislami Lishrel Blizko 80 vsih chisel menshih 10000 peretvoryuyutsya v palindrom za 4 abo menshe krokiv Blizko 90 za 7 i menshe krokiv Os kilka prikladiv chisel sho ne ye chislami Lishrel 56 staye palindromom pislya odniyeyi iteraciyi 56 65 121 57 staye palindromom pislya dvoh iteracij 57 75 132 132 231 363 59 takozh ne ye chislom Lishrel oskilki vono staye palindromom pislya 3 iteracij 59 95 154 154 451 605 605 506 1111 89 prohodit nezvichno bagato 24 iteraciyi najbilshu kilkist dlya chisel menshe 10000 yaki tochno peretvoryuyutsya u palindrom persh nizh dosyagti palindroma 8813200023188 1 10911 dosyagaye palindroma 4668731596684224866951378664 pislya 55 krokiv 2 1 186 060 307 891 929 990 prohodit 261 iteraciyu 3 i staye 119 cifernim palindromom yakij v danij chas ye svitovim rekordom 4 najbilshim otrimanim za dopomogoyu algoritmu palindromom Vono bulo znajdeno Dzhejsonom Dusetom za dopomogoyu komp yutera 30 listopada 2005 Pripuskayut sho najmenshim naturalnim chislom sho ne peretvoryuyetsya v palindrom ye triznachne chislo 196 Kandidati v chisla Lishrelred V inshih sistemah chislennya isnuyut chisla yaki nikoli ne peretvoryatsya v palindrom vnaslidok danoyi operaciyi 5 6 Ale v desyatkovij sistemi chislennya dlya zhodnogo z kandidativ v chisla Lishrel ne isnuye strogogo dovedennya sho vono ye chislom Lishrel Takim chinom same isnuvannya takih chisel ne dovedeno Podibni chisla neoficijno nazivayut kandidati v chisla Lishrel poslidovnist A023108 z Onlajn enciklopediyi poslidovnostej cilih chisel 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 Vidileni zhirnim shriftom chisla vvazhayutsya odnimi z bazovih chisel Lishrel Komp yuterni programi Dzhejsona Duseta Yana Petersa i Bendzhamina Despresa znajshli j inshih kandidativ v chisla Lishrel Bilsh togo Bendzhamin Despres viyaviv vsi bazovi chisla Lishrel sho skladayutsya z mensh nizh 17 cifr Sajt Wade VanLandingham mistit spiski bazovih chisel Lishrel dlya kozhnoyi dovzhini chisla Metod gruboyi sili yakij spochatku rozrobiv Dzhon Voker buv vdoskonalenij Napriklad Vaughn Suite rozrobiv programu yaka zberigaye tilki pershi i ostanni kilka cifr kozhnoyi iteraciyi dozvolyayuchi testuvati cifrovi zakonomirnosti protyagom miljoniv iteracij bez neobhidnosti zberezhennya kozhnoyi iteraciyi povnistyu Ale poki sho ne bulo pridumano algoritmu yakij bi obminav iterativnij proces otrimuyuchi palindromi inshim sposobom Pov yazani terminired nbsp Potik chisla 196 i sporidnenih z nim chisel Termin potik angl Thread vviv Dzhejson Dusette poznachayuchi tak poslidovnist chisel oderzhuvanih u rezultati iteracij vihidnogo chisla Bazove chislo angl Seed i pov yazani z nim sporidneni chisla angl Kin shodyatsya v odnomu potoci Potik ne vklyuchaye vihidne bazove chislo abo jogo rodicha a tilki chisla yaki ye zagalnimi dlya oboh pislya togo yak voni zijdutsya Bazovi chisla ye pidposlidovnistyu chisel Lishrel ce najmenshi chisla z kozhnogo potoku sho ne utvoryuyut palindrom Bazove chislo mozhe buti same po sobi palindromom Sporidneni chisla takozh ye pidmnozhinoyu chisel Lishrel ce vsi chisla potoku za vinyatkom bazovogo abo bud yake chislo yake uvillyayetsya v cej potik z bud yakogo miscya pislya odniyeyi iteraciyi Cej termin buv vvedenij Kodzi Yamasitoyu v 1997 roci Doslidzhennya chisla 196red Oskilki 196 ye najmenshim kandidatom v chisla Lishrel vono otrimalo najbilshu uvagu Dzhon Voker pochav vivchati potik chisla 196 12 serpnya 1987 na robochoyi stanciyi Sun 3 260 Vin napisav programu na C yaka vikonuye operaciyu perevernuti i sklasti i pereviryaye na palindrom pislya kozhnogo kroku Programa bula zapushena u fonovomu rezhimi z nizkim prioritetom Vona zberigala kontrolni tochki v fajl kozhni dvi godini i v moment zakrittya sistemi zapisuyuchi dosyagnuti do togo chasu chislo i nomer iteraciyi Programa zapuskalasya avtomatichno z ostannoyi kontrolnoyi tochki pislya kozhnogo vklyuchennya komp yutera Vona pracyuvala protyagom majzhe troh rokiv a potim zupinilasya yak i bulo zaprogramovano 24 travnya 1990 z povidomlennyam nbsp Dosyagnuta tochka zupinki na 2 415 836 iteraciyi Chislo mistit 1 000 000 cifr Originalnij tekst angl Stop point reached on pass 2 415 836 Number contains 1 000 000 digits nbsp Chislo 196 zbilshilosya do chisla v odin miljon cifr pislya 2 415 836 iteracij bez dosyagnennya palindroma Voker opublikuvav svoyi doslidzhennya v Internet razom z ostannoyu kontrolnoyu tochkoyu zaproshuyuchi inshih vidnoviti poshuki na osnovi ostannogo dosyagnutogo chisla U 1995 roci Tim Irvin vikoristav superkomp yuter i dosyag poznachki v dva miljoni cifr vsogo za tri misyaci znovu ne znajshovshi palindroma Dzhejson Dusette dosyag 12 500 000 cifr v travni 2000 roku Wade VanLandingham vikoristovuyuchi programu Dzhejsona Dusetta dosyag 13 miljoniv cifr sho bulo opublikovano 7 v Yes Mag kanadskomu naukovomu zhurnali dlya ditej Z chervnya 2000 roku VanLandingham prodovzhuvav lidiruvati vikoristovuyuchi programi napisani riznimi entuziastami Do 1 travnya 2006 vin dosyag poznachki 300 miljoniv cifr zi shvidkistyu odnogo miljona cifr kozhni 5 7 dniv Vikoristovuyuchi rozpodileni obchislennya v 2011 roci Romain Dolbeau za milyard iteracij otrimav chislo sho skladayetsya z 413 930 770 cifr 8 a v lipni 2012 roku jogo obchislennya dosyagli chisla z 600 mln cifr 9 Palindrom vse she ne viyavlenij Inshi kandidati v chisla Lishrel yaki piddavalisya takomu zh pereboru yak napriklad 879 1997 i 7059 takozh buli prostezheni protyagom miljoniv iteracij bez viyavlennya palindroma Primitkired REVERSAL ADDITION PALINDROME TEST ON 89 REVERSAL ADDITION PALINDROME TEST ON 10911 REVERSAL ADDITION PALINDROME TEST ON 1186060307891929990 MOST DELAYED PALINDROMIC NUMBER angl Mathematical letters with proofs angl Arhiv originalu za 16 travnya 2006 Procitovano 31 sichnya 2015 Digit Reversal Sums Leading to Palindromes angl Coming or Going angl The p196 mpi Implementation of the Reverse And Add Algorithm for the Palindrome Quest Arhiv originalu za 19 kvitnya 2015 Procitovano 31 sichnya 2015 The p196 mpi page Arhivovano 2015 02 11 u Wayback Machine angl Posilannyared Dzhon Voker angl tri roki obchislen Tim Irvin angl blizko dvoh misyaciv obchislen Dzhejson Duset Svitovi rekordi angl Najbilshi otrimani palindromi Bendzhamin Despres angl 196 j inshi chisla Lishrel angl Sajt Wade VanLandingham Weisstein Eric W 196 Algorithm angl na sajti Wolfram MathWorld Weisstein Eric W Lychrel Number angl na sajti Wolfram MathWorld Weisstein Eric W Palindromic Number Conjecture angl na sajti Wolfram MathWorld Weisstein Eric W Reverse Then Add Sequence angl na sajti Wolfram MathWorld Otrimano z https uk wikipedia org w index php title Problema 196 amp oldid 43366882