Войти
Существуют ли какие-либо числа Лайкрела с основанием 10?
(больше нерешенных задач по математике)Номер Lychrel является натуральным числом, которое не может образовывать палиндром через итеративный процесс многократно реверсирования его цифры и добавление полученного числа. Этот процесс иногда называют алгоритмом 196 по имени самого известного числа, связанного с процессом. В базовой десяти, нет числа Lychrel пока не доказано существование, но многое, в том числе 196, подозревается в эвристических и статистических основаниях. Имя «Личрел» было придумано Уэйдом Ван Лендингемом как грубая анаграмма имени его подруги «Шерил».
Процесс обратного сложения производит сумму числа и числа, образованного путем изменения порядка его цифр на обратный. Например, 56 + 65 = 121. Другой пример: 125 + 521 = 646.
Некоторые числа быстро становятся палиндромами после многократного переворота и сложения и, следовательно, не являются числами Лихрела. Все однозначные и двузначные числа в конечном итоге становятся палиндромами после многократного переворачивания и сложения.
Около 80% всех чисел меньше 10 000 превращаются в палиндром за четыре или меньше шагов; около 90% из них разрешаются за семь или меньше шагов. Вот несколько примеров чисел, отличных от Лихрела:
Наименьшее число, которое, как известно, не образует палиндром, - 196. Это наименьший кандидат на число Лихрела.
Число, полученное в результате перестановки цифр числа Лихрела, не оканчивающегося нулем, также является числом Лихрела.
Позвольте быть натуральным числом. Мы определяем функцию Лихреля для системы счисления следующим образом:
где - количество цифр в числе в базе, а
- значение каждой цифры числа. Ряд является число Lychrel, если не существует натуральное число такое, что, где это -й итерации из
В других основаниях (эти основания представляют собой степень двойки, например, двоичные и шестнадцатеричные ), можно доказать, что некоторые числа никогда не образуют палиндром после многократного переворота и сложения, но такого доказательства не было найдено для 196 и других чисел с основанием 10.
Он высказал предположение, что 196 и другие номера, которые еще не дали палиндром это номер Lychrel, но ни один номер в базе десять до сих пор не доказан, что Lychrel. Числа, которые не были продемонстрированы как отличные от Lychrel, неофициально называются числами «кандидатов Lychrel». Первые несколько кандидатов числа Лихрела (последовательность A023108 в OEIS ):
Цифры, выделенные жирным шрифтом, представляют собой номера семян подозреваемого Лихрела (см. Ниже). Компьютерные программы Джейсона Дусетта, Яна Петерса и Бенджамина Депре нашли других кандидатов Lychrel. Действительно, программа Бенджамина Депре определила все предполагаемые номера семян Lychrel менее 17 цифр. На сайте Уэйда Ван Лендингема указано общее количество найденных подозрительных семенных чисел Личрела для каждой длины цифры.
Метод грубой силы, первоначально примененный Джоном Уокером, был усовершенствован, чтобы использовать преимущества итерационного поведения. Например, Vaughn Suite разработала программу, которая сохраняет только первые и последние несколько цифр каждой итерации, позволяя выполнять тестирование шаблонов цифр в миллионах итераций без необходимости сохранять каждую итерацию целиком в файл. Однако до сих пор не разработан алгоритм, позволяющий обойти итерационный процесс обращения и добавления.
Термин поток, введенный Джейсоном Дусеттом, относится к последовательности чисел, которая может или не может привести к палиндрому через процесс обратного и сложения. Любое заданное семя и связанные с ним номера родственников сходятся в одном потоке. Цепочка не включает исходное начальное число или родственный номер, а только числа, общие для обоих, после того, как они сойдутся.
Начальные числа - это подмножество чисел Лихрела, то есть наименьшее число каждой нити, не производящей палиндром. Начальное число может быть само по себе палиндромом. Первые три примера выделены жирным шрифтом в списке выше.
Родственные числа - это подмножество чисел Лихрела, которые включают все номера потока, кроме начального, или любое число, которое сходится в данном потоке после одной итерации. Этот термин был введен Кодзи Ямаситой в 1997 году.
Поскольку 196 ( основание-10 ) является наименьшим кандидатским числом Лихрела, ему было уделено наибольшее внимание.
В 1980-х годах проблема палиндрома 196 привлекла внимание любителей микрокомпьютеров, и поисковые программы Джима Баттерфилда и других появились в нескольких журналах по массовым вычислениям. В 1985 году программа Джеймса Киллмана безуспешно работала более 28 дней, пройдя 12 954 прохода и достигнув числа из 5366 цифр.
Джон Уокер начал свой 196 Palindrome Quest 12 августа 1987 года на рабочей станции Sun 3/260. Он написал программу на языке C для выполнения итераций разворота и сложения, а также для проверки наличия палиндрома после каждого шага. Программа работала в фоновом режиме с низким приоритетом и создавала контрольную точку для файла каждые два часа, а когда система была выключена, записывала достигнутое количество и количество итераций. Он автоматически перезапускался с последней контрольной точки после каждого выключения. Он длился почти три года, а затем был прекращен (в соответствии с инструкциями) 24 мая 1990 года с сообщением:
196 выросло до миллиона цифр после 2 415 836 итераций, не достигнув палиндрома. Уокер опубликовал свои выводы в Интернете вместе с последней контрольной точкой, приглашая других возобновить квест, используя набранный на данный момент номер.
В 1995 году Тим Ирвин и Ларри Симкинс использовали многопроцессорный компьютер и всего за три месяца достигли отметки в два миллиона цифр, не обнаружив палиндрома. Затем Джейсон Дусетт последовал его примеру и в мае 2000 года достиг 12,5 миллионов цифр. Уэйд ВанЛандингем использовал программу Джейсона Дусетта, чтобы набрать 13 миллионов цифр - рекорд, опубликованный в Yes Mag : Canada's Science Magazine for Kids. С июня 2000 года Уэйд ВанЛандингем несет флаг, используя программы, написанные разными энтузиастами. К 1 мая 2006 года VanLandingham достигла отметки в 300 миллионов цифр (со скоростью один миллион цифр каждые 5-7 дней). Используя распределенную обработку, в 2011 году Ромен Долбо выполнил миллиард итераций, чтобы получить число из 413 930 770 цифр, а в феврале 2015 года его вычисления достигли числа в миллиард цифр. Палиндром пока не найден.
Другие потенциальные числа Лихрела, которые также были подвергнуты тому же методу грубой силы повторного обратного сложения, включают 879, 1997 и 7059: они были взяты на несколько миллионов итераций, при этом палиндром не был обнаружен.
В основании 2, 10110 (22 в десятичной системе) было доказано, чтобы быть числом Lychrel, так как после 4 этапа она достигает 10110100, после 8 шагов она достигает 1011101000, после 12 шагов она достигает 101111010000, и вообще после 4 п шагов она достигает число, состоящее из 10, за которым следуют n +1 единиц, за которым следует 01, за которым следуют n +1 нулей. Это число, очевидно, не может быть палиндромом, и ни одно из других чисел в последовательности не является палиндромом.
Доказано, что числа Лихрела существуют в следующих основаниях: 11, 17, 20, 26 и все степени двойки.
Никакая база не содержит чисел Лихрела, меньших, чем основание. Фактически, в любой данной базе b ни одно однозначное число не требует более двух итераций, чтобы сформировать палиндром. Для b gt; 4, если k lt; b / 2, то k становится палиндромным после одной итерации: k + k = 2k, что является однозначным по основанию b (и, следовательно, палиндромом). Если k gt; b / 2, k становится палиндромным после двух итераций.
Наименьшее число в каждой базе, которое могло бы быть числом Лихреля (последовательность A060382 в OEIS ):
| б | Наименьшее возможное число Лихрела в базе b, записанное в базе b (основание 10) |
|---|---|
| 2 | 10110 (22) |
| 3 | 10211 (103) |
| 4 | 10202 (290) |
| 5 | 10313 (708) |
| 6 | 4555 (1079) |
| 7 | 10513 (2656) |
| 8 | 1775 (1021) |
| 9 | 728 (593) |
| 10 | 196 (196) |
| 11 | 83А (1011) |
| 12 | 179 (237) |
| 13 | 12СА (2701) |
| 14 | 1BB (361) |
| 15 | 1EC (447) |
| 16 | 19D (413) |
| 17 | B6G (3297) |
| 18 | 1AF (519) |
| 19 | Привет (341) |
| 20 | Эй Джей (379) |
| 21 год | 1CI (711) |
| 22 | KL (461) |
| 23 | LM (505) |
| 24 | MN (551) |
| 25 | 1FM (1022) |
| 26 год | OP (649) |
| 27 | PQ (701) |
| 28 год | QR (755) |
| 29 | РС (811) |
| 30 | СТ (869) |
| 31 год | ТУ (929) |
| 32 | УФ (991) |
| 33 | VW (1055) |
| 34 | 1IV (1799) |
| 35 год | 1JW (1922) |
| 36 | YZ (1259) |
Числа Лихрела могут быть расширены до отрицательных целых чисел путем использования представления цифр со знаком для представления каждого целого числа.
