Палиндром из натуральных чисел

[Dmitriy40]

Кстати некий аналог этого анализа вполне применим и к просто натуральному ряду. Например из интервала $1000\ldots1999$ допустимы лишь те варианты, где единственной нечётное количество раз встречающейся цифрой будет обязательно $0$. Если все цифры встречаются чётное количество раз или нечётное количество раз встретился не $0$ - некуда ставить число $1000$, оно может быть лишь ровно в центре палиндрома. Плюс требование на чётность количества встреч комбинации $00$ во всех числах. Потому к примеру после $N=899$ следующим вероятно допустимым будет лишь $N=1019$. И это же применимо для всего диапазона $1000\ldots9999$, т.е. для нечётной цифры тысяч вариантов будет намного меньше, чем для чётной. Аналогично и для ещё больших чисел, количество условий лишь возрастает. Правда и количество допустимых вариантов тоже быстро растёт.

-- 04.09.2017, 17:21 --

dimkadimon в сообщении #1245129 писал(а):

Отличная новость, но как его найти?! Если это вообще возможно...

Я не знаю. 30 триллионов простых чисел ... Ну пусть найти их все несложно, несколько недель и всё, но вот как их хранить? Это ведь от 120 до 750 терабайт! Чтобы вести учёт какие использованы, какие нет. Без понятия. Возможно их можно разбить на сотни миллиардов групп, переводящих состояние палиндрома с выраниванием на границу чисел со всех 4-х сторон в новое состояние с теми же свойствами, но это всё равно слишком много информации. И не уверен что будет гарантия непропуска решений.

-- 04.09.2017, 17:33 --

dimkadimon в сообщении #1245129 писал(а):

Получается все проблемы упираются в нули.

Не только, возможно там внутри есть и ещё другие условия, когда для каких-то простых тоже не будет пары (не подобрать допустимую комбинацию даже из нескольких чисел). Но это уже так просто не проверить, тут то условие простое, две цифры и лишь нули в середине. Это у меня получилось необходимое условие, но совершенно не достаточное. Ну так я и пытался лишь оценить снизу.
Правда в таком огромном диапазоне думаю пары найдутся для всех, а вот с чётностью количества пар могут быть проблемы (и будут! на примере $N=151$ это уже проверил руками). А чётность количества никак не отследить без получения всего полного списка простых. И даже с ним, кроме явных запретов будут и многовариантные комбинации. Т.е. оценку снизу можно будет немного улучшить, но кардинально это уже не спасёт, только полное решение. В общем мрак.

[dimkadimon]

опубликовали последовательность: https://oeis.org/A289469

[dimkadimon]

Можно составить палиндром из 36 простых если добавить 4 нуля:

73.13.59.3.151.127.61.0.17.0.109.113.103.29.41.7.43.89.71.37. 9 7.31.79.83.47.149.23.0.131.19.0.107.101.67.2.11.5.139.53.137

73.79.137.2.139.0.101.5.13.29.11.67.17.149.53.47.0.113.103.8 9 .83.0.131.107.43.59.41.71.7.61.19.23.151.0.109.3.127.31.97.37

[Dmitriy40]

Не, считаю просто добавление нулей не комильфо. Вот разрешить делить поток цифр на числа с допустимыми левыми нулями другое дело. Нули нужны лишь для переворота чисел $101,103,107,109$, значит достаточно допустить иметь ведущий ноль для чисел $011,013,017,019$ - и этого должно быть достаточно для построения палиндрома. Ну или для любых ровно 4-х чисел из множества $011,013,017,019,0113,0127,0131,0137,0139,0149,0151$.

[Dmitriy40]

Один из вариантов такого палиндрома: 71,73,79,23,59,83,47,61,103,109,107,2,113,101,5,139,41,137,|9|7,31,149,3,151,0131,127,019,013,011,67,43,89,53,29,7,37,17.

[Dmitriy40]

Мда, моё предложение ничем не лучше Вашего и фактически к нему же и сводится.

[Dmitriy40]

Можно поставить задачу не все первые простые числа, а просто последовательные простые числа. Тогда будут вот такие решения:
7,19,23,1|1|,13,29,17;
7,19,23,11,|3|1,13,29,17;
7,31,13,29,1|7|,19,23,11,37;
31,13,29,17,|5|,7,19,23,11,3 (это самое длинное решение, во всяком случае для чисел до 1000).

[dimkadimon]

Dmitriy40 в сообщении #1245594 писал(а):

значит достаточно допустить иметь ведущий ноль для чисел $011,013,017,019$

Вот такое решение:

73.127.31.101.67.149.017.019.71.5.131.139.23.89.53.103.47.|9|7.43.013.59.83.29.3.113.151.79.107.109.41.7.61.011.37.2.137

-- 07.09.2017, 21:11 --

Dmitriy40 в сообщении #1245745 писал(а):

31,13,29,17,|5|,7,19,23,11,3 (это самое длинное решение, во всяком случае для чисел до 1000)

Здорово. А вы можете это доказать?

[Dmitriy40]

dimkadimon в сообщении #1245884 писал(а):

Здорово. А вы можете это доказать?

Да. В несколько шагов.
Если ограничиться лишь числами от 11 до 97, то палиндрома быть не может т.к. не для всех чисел есть пара. А количество цифр всегда чётное, значит не может быть ни цифры в центре палиндрома, ни обмена цифрами между числами. Значит необходимо или хотя бы одно число до 10, или добавлять число 101 с расположением точно в центре палиндрома.
С числом 101 вновь встаёт проблема отсутствия пар.
С числами до 10 все возможные варианты проверил на допустимость (по количеству нечётных встреч цифр), указанный вариант самый длинный.
Т.е. до 102 других более длинных вариантов нет.
В интервале от 102 до 306 все числа трёхзначные, поэтому в случае нечётной длины палиндрома в центре будет цифра (например 131, 151, 181, 191), остальные же числа будут всегда выровнены на границы чисел и соответственно должны иметь пары - а это совершенно не так, пары например к 197 нет, пар к числам 2xx тем более нет, и т.д. Если же брать симметричные палиндромы, то тем более они всегда будут выровнены на границу чисел - та же проблема отсутствия пар.
Аналогичное рассуждение и для любого интервала внутри одной сотни.
Более того, среди простых чисел до 999 нет ни одной достаточно длинной непрерывной последовательности чисел с одинаковой младшей цифрой, да ещё и равной старшей цифре. Т.е. палиндром ну никак не укладывается в одну сотню.
Если брать палиндромы пересекающие сотни, то плюсом добавляется засада отсутствия пар для чисел с нулём в записи. Это не считая других проблем отсутствия пар.
Остался вопрос с палиндромом, начинающимся до 100 и продолжающимся в первую-вторую сотню. Но 101 может быть лишь в центре палиндрома (иначе ноль вылезет), а пары уже для 103 до 1000 нету.
Всё, все варианты исключены. Если не ошибаюсь.

PS. Кстати, вероятно это вообще самое длинное решение для чисел до $10^{15}$ - того самого вероятного палиндрома, который фиг найдёшь. Потому что для чисел более 1000 (собственно уже более 102) в полный рост встанет проблема отсутствия пар в пределах одной и той же старшей цифры (ведь младшая то меняется, а количество цифр во всех числах одинаково и значит обмена цифрами между числами не будет), а при попытке пересечь границу старшей цифры натыкаемся на уже исследованную проблему отсутствия пар. Конечно это надо проверить более подробно.

-- 07.09.2017, 16:49 --

Можно даже проще.
Рассмотрим палиндромы из чисел одинаковой длины (только двухзначных, только трёхзначных, только четырёхзначных, ...). Для чисел чётной длины центр палиндрома обязан быть между числами (иначе или слева или справа будет на цифру больше), для чисел нечётной длины в центре палиндрома должна быть центральная цифра числа (иначе баланс снова не сойдётся). В обоих случаях уже соседние числа будут выровнены на границу чисел и никакого обмена цифрами между числами не будет. Значит каждое число обязано иметь для себя пару. Но пар для чисел с чётной старшей цифрой нет и быть не может среди чисел той же длины в цифрах.
Т.е. палиндромов из последовательных простых чисел одинаковой длины быть не может. (Т.к. между числом и парным к нему всегда встретится число с чётной старшей цифрой.)

Смена длины чисел происходит при $10^n, n \in \mathbb{N}$, случай с 10 уже рассмотрен отдельно, остальные же натыкаются на ту самую исследованную проблему отсутствия пар для чисел с нулями в середине. Можно ли найти такой диапазон вокруг $10^n, n>2$ чтобы все числа имели пары внутри этого же диапазона - не думаю, но надо проверять.

-- 07.09.2017, 16:56 --

dimkadimon в сообщении #1245884 писал(а):

Вот такое решение:
73.127.31.101.67.149.017.019.71.5.131.139.23.89.53.103.47.|9|7.43.013.59.83.29.3.113.151.79.107.109.41.7.61.011.37.2.137

Красиво, спасибо, у меня оно так и не нашлось, надоело ждать перебор.

[Dmitriy40]

Рассмотрим варианты палиндрома вокруг $10^n$. Центр палиндрома выделен символами || (одним или двумя).
1. Вокруг 1000. Проверим все варианты расположения первого простого числа после 1000 (равного 1009):

(Список вариантов)

9001,|,1009, - но в интервале 1009-9001 будет число 4007, пара к которому весьма и весьма далеко
,1|009, недопустимо
,10|09, недопустимо
,100|9, недопустимо
x900,|1|,009, недопустимо
,1|0|09, недопустимо
,10|0|9, недопустимо
,100|9|,001x недопустимо

Допустимых вариантов не видно.

2. Вокруг 10000. Варианты расположения числа 10007:

(Список вариантов)

,70001,|,10007, - для числа 40009 пара слишком далеко
,1|0007,
,10|007,
,100|07,
,1000|7,
,|1|0007,
,1|0|007,
,10|0|07,
,100|0|7,
,10000|7|,

Допустимых вариантов не видно.

3. Вокруг $10^5$. Варианты расположения числа 100003:

(Список вариантов)

,|,100003, пара слишком далеко
,1|00003,
,10|0003,
,100|003,
,1000|03,
,10000|3,
,|1|00003,
,1|0|0003,
,10|0|003,
,100|0|03,
,1000|0|3,
,10000|3|,

Допустимых вариантов не видно.

4. Вокруг $10^6$. Варианты расположения числа 1000003:

(Список вариантов)

,|,1000003, пара слишком далеко
,1|000003,
,10|00003,
,100|0003,
,1000|003,
,10000|03,
,100000|3,
,|1|000003,
,1|0|00003,
,10|0|0003,
,100|0|003,
,1000|0|03,
,10000|0|3,
,100000|3|,

Допустимых вариантов не видно.

5. Вокруг $10^7$. Варианты расположения числа 10000019:

(Список вариантов)

,|,10000019, пара слишком далеко
,1|0000019,
,10|000019,
,100|00019,
,1000|0019,
,10000|019,
,100000|19,
,1000001|9,
,|1|0000019,
,1|0|000019,
,10|0|00019,
x9,100|0|0019, - вот вероятно подходящий вариант
,1000|0|019,
,10000|0|19,
,100000|1|9,
,1000001|9|,100000123 слишком далеко
,1000001|9|,100000127 слишком далеко
,1000001|9|,100000193 слишком далеко

Возможно подходит вариант ,x9,100|0|0019, надо проверять дальше.

[dimkadimon]

Dmitriy40 в сообщении #1245896 писал(а):

Да. В несколько шагов.

Большое спасибо

-- 08.09.2017, 19:55 --

Кстати есть еще один вариант - использовать числа в двоичной системе. Например вот решение для натуральных чисел от 1 до 22:

1000.1100.110.10100.10011.11.1010.1101.1011.1110.100|00.10.1111.10110.1.10101.111.100.10010.101.1001.10001


А вот решение для первых 7 простых:

11.101.1011.10|0|01.1101.10.111

[Dmitriy40]

dimkadimon в сообщении #1246136 писал(а):

Кстати есть еще один вариант - использовать числа в двоичной системе.

Да, интересный вариант. Но слишком лёгкий, решение для первых простых есть почти для любой длины. Несколько первых исключений (наибольшее простое число): $N_p \ne 2,3,11,19,29,73,97,$ $127,137,139,149,$ $157,163,173,181,193,197,$ $211,227,233,241,271,281,$ $311,337,349,359,383,$ $409,421,433,443,463,479,491,$ $1051,1117,1129,1187,1201$.
Интересно что от числа $31$ до $71$ исключений нет, сплошной диапазон допустимости, аж более чем в два раза по числам. Как и для $491 \ldots 1051$. Потом $131059 \ldots 262151$, потом $524261 \ldots 1048609$, потом $2097047 \ldots 4194301$, потом $8388581 \ldots 16777289$, потом $33554393 \ldots 67108859$, потом $134217689 \ldots 268435399$. Подозрительна близость границ диапазонов к степеням $2$.
Не менее удивительно и отсутствие длинных непрерывных недопустимых диапазонов, до $10^8$ самый длинный $38119 \ldots 38219$ (длиной всего $10$), до $10^9$ самый длинный $585035497 \ldots 585035963$ (длиной $27$).

[dimkadimon]

Dmitriy40 в сообщении #1246158 писал(а):

Но слишком лёгкий, решение для первых простых есть почти для любой длины

Секундочку! Потенциальные решения есть, а вот настоящих решений мало. Я больше 7 простых пока не нашел...

[Dmitriy40]

dimkadimon
Вы правы, я тоже не нашёл (до $N_p < 43$). Т.е. мои данные выше - снова лишь необходимое условие, не где решения точно есть, а лишь где их точно нет.
Приношу извинения за ввод в заблуждение.

[dimkadimon]

Сделал новую последовательность для бинарных чисел: https://oeis.org/A291633