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

[dimkadimon]

Один форумчанен Ktina придумал очень интересную задачку: составьте палиндром из чисел от 1 до 19. post1241958.html#p1241958

Решение этой задачи нашел gris:
$1.12.3.14.5.16.7.18.9.10.19.8.17.6.15.4.13.2.11 \to 11 2314 5167 1891 0 1981 7615 4132 11$

Теперь усложним задачу:
1. Для каких $N$ существуют такие палиндромы из чисел от 1 до $N$? Какое самое большое решение?
2. Можно ли составить такой палиндром из первых простых чисел?


Задачу можно решать тут или посылать ответ на сайт Carlos Rivera: http://www.primepuzzles.net/puzzles/puzz_891.htm

[dimkadimon]

Нашел решения для $N=1, 19, 20, 21, 22, 39, 40, 41, 59, 60, 61, 79, 80, 81, 98, 99$. Могу доказать что $N=101$ не существует.

[dimkadimon]

Нашел $N=220$, в середине "55":

102.94.16.9.148.109.65.66.188.83.124.126.10.22.14.133.25.176.87.134.172.86.186.71.202.193.140.108.195.49.106.8.51.32.163.101.204.63.206.103.35.116.80.20.118.127.131.212.74.113.122.145.100.26.45.
105.181.211.89.117.151.205.147.161.24.129.125.82.64.52.91.58.167.84.3.170.130.28.21.75.189.182.4.78.19.6.79.183.29.5.111.137.99.190.207.34.173.23.179.77.159.39.44.165.146.135.96.191.175.47.155.5
5.174.57.119.169.53.164.156.144.93.95.177.97.132.37.1.43.70.209.199.73.11.115.92.38.197.69.187.42.81.98.157.128.203.107.13.48.76.185.192.54.62.85.219.214.216.17.41.50.215.171.198.112.18.150.15.4
6.200.154.12.213.114.72.121.31.7.218.110.208.61.153.30.160.2.36.40.210.136.123.158.60.194.59.180.104.139.120.217.68.168.27.143.178.67.152.33.141.220.162.142.138.88.166.56.90.184.196.149.201

Кто может побить этот рекорд?

Палиндром из простых так и не могу найти. Доказано что $N=36$ и $N=247$ не существуют.

[kotenok gav]

В октябре будет свободное время, тогда побью!

[dimkadimon]

kotenok gav в сообщении #1244825 писал(а):

В октябре будет свободное время, тогда побью!

Буду с нетерпением ждать! Кстати, через несколько недель начнется новый Ал Зиммерманн. Ура!

[Dmitriy40]

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

Нашел решения для $N=1,$

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

Палиндром из простых так и не могу найти.

Легко: $2$. Очень даже палиндром.

А вот дальше всё очень интересно.
Чтобы последовательность цифр была палиндромом, надо чтобы все цифры встречались или чётное количество раз, или не более одной цифры встречалось нечётное количество раз. Этому условию отвечают лишь последовательности простых до: $2, 151, 1567, 1987, 2017, 2029, 4751, 5563, 5569, 6469, 6563, 6791, 9817$ (Ну и дальше ещё много конечно). Т.е. палиндромная последовательность из простыхчисел не может быть короче $36$ (для чисел до $151$) или $247$ (для чисел до 1567) или $300$ (для чисел до $1987$) членов.
Длиной 36 не подходит: она включает число 109, которое в записи наоборот ($901$) не является членом последовательности, при этом ни то ни другое разбить на два числа не получается (ноль оказывается или младшим или старшим, что недопустимо).
Длиной $247$ тоже не подходит по той же причине, $109$ не имеет допустимой пары.
Длиной $300$ уже имеет допустимую пару для $109$, это $1901$, которое тоже простое. Но появляется засада с числом $1009$ - оно обязано быть в центре палиндрома т.к. другого числа с двумя нулями в последовательности нет, но это невозможно - $1009$ палиндромом уже не является. Значит и длина $300$ не подходит.
Длиной $306$, числа до $2017$, обнаруживает новую засаду, число $2003$ не имеет пары и не влезает в центр палиндрома.
И эта засада весьма засадная, пара для числа $2003$ никак не меньше $30020$, а это уже $3248$ членов.
И среди этих членов будет число $4001$, пара для которого не меньше $100400$, т.е. уже минимум $9626$ членов.
А среди этих будет $100003$, пара для которого не меньше $3000010$, а это не меньше $216816$ членов.
А среди этих будет $1000003$, пара для которого не меньше $430000010$, уже $22848051$ членов.

Итого, такая последовательность из первых простых чисел не может быть короче $22848051$ членов. Искать её не переискать.
И очень сильно подозреваю что там дальше тоже будут ещё кучи ограничений, которые вероятно вообще аннулируют саму возможность существования палиндрома из первых простых чисел.

[Dmitriy40]

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

А среди этих будет $1000003$, пара для которого не меньше $430000010$, уже $22848051$ членов.

Ошибся, есть пара всего лишь $33000001$, $2031668$ членов.

Продожение.
До $33000001$ будет число $20000003$, пара к которому не меньше $5300000023$, это $248370961$ членов.
До $5300000023$ будет число $4000000007$, пара для которого не меньше $370000000043$, а это $14456422320$ членов (14 миллиардов).
До $370000000043$ будет $100000000003$, пара которому не меньше $3000000000013$, уже $108340298704$ членов (больше 100 миллиардов).
До $3000000000013$ будет $2000000000003$, пара к которому не меньше $330000000000023$, это уже почти 10 триллионов членов.
Сомневаюсь что кто-то сможет найти даже и столько, а ведь это далеко не конец.
Похоже всё же такого палиндрома не существует вовсе.

[Dmitriy40]

Хм, оказывается уже следующий шаг, число $40000000000001$ имеет пару $1000000000000403$ (это почти 29 триллионов членов) - и дальше роста нет, все простые числа вида $x000..00y$ до $6\cdot10^{15}$ имеют пары не выше этого предела. Значит где-то в интервале $(1\cdot10^{15}\ldots6\cdot10^{15})$ может существовать наименьший палиндром из первых простых чисел, длиной от 29 до 165 триллионов чисел.

[Dmitriy40]

В интервале $(6\cdot10^{15}\ldots17\cdot10^{15})$ решений снова нет.
Но вполне могут быть решения в интервале $(17\cdot10^{15}\ldots20\cdot10^{15})$ ($454\ldots532$ триллионов чисел).
Потом решений снова нет вплоть до $3\cdot10^{33}$.

-- 04.09.2017, 02:52 --

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

Значит где-то в интервале $(1\cdot10^{15}\ldots6\cdot10^{15})$ может существовать наименьший палиндром из первых простых чисел, длиной от 29 до 165 триллионов чисел.

Длина всего палиндрома при этом составит примерно от $415$ до $2450$ триллионов цифр.

[Dmitriy40]

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

Для каких $N$ существуют такие палиндромы из чисел от 1 до $N$? Какое самое большое решение?

Для очень и очень многих. Вряд ли множество решений вообще конечно.

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

Могу доказать что $N=101$ не существует.

Точно не существует гораздо больше вариантов (до $1000$): $N \ne 2\ldots18,$ $23\ldots38,$ $42\ldots58,$ $62\ldots78,$ $82\ldots97,$ $100\ldots121,$ $123\ldots200,$ $202\ldots218,$ $222\ldots238,$ $240,$ $242\ldots258,$ $260,$ $262\ldots278,$ $280,$ $282\ldots298,$ $300\ldots400,$ $402\ldots418,$ $420,$ $422\ldots438,$ $442\ldots458,$ $460,$ $462\ldots478,$ $480,$ $482\ldots498,$ $500\ldots600,$ $602\ldots618,$ $620,$ $622\ldots638,$ $640,$ $642\ldots658,$ $662\ldots678,$ $680,$ $682\ldots698,$ $700\ldots800,$ $802\ldots818,$ $820,$ $822\ldots838,$ $840,$ $842\ldots858,$ $860,$ $862\ldots878,$ $882\ldots898,$ $900\ldots999.$
Интересен вариант $N=122$, у него в центре палиндрома (обозначен чертой) будет число $\ldots,10|0,\ldots$, это единственное исключение из правила запрета нечётной цифры сотен (для чисел до $1000$).

[dimkadimon]

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

И среди этих членов будет число $4001$, пара для которого не меньше $100400$

А почему $11004$ не пара?

[Dmitriy40]

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

А почему $11004$ не пара?

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

[dimkadimon]

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

А среди этих будет $1000003$, пара для которого не меньше $430000010$, уже $22848051$ членов.

Тут можно использовать $33000001$ как пару, кстати простое. А вы это уже нашли...

-- 04.09.2017, 22:48 --

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

Интересен вариант $N=122$, у него в центре палиндрома (обозначен чертой) будет число

А вот и само решение $N=122$:

76.69.47.14.85.89.36.70.119.54.103.81.102.15.93.31.114.12.122.113.18.27.38.82.75.59.46.7.83.21.66.20.101.19.32.65.3.49.48.80.109.60.16.52.29.92.44.25.116.43.86.51.77.11.97.8.73.57.104.50.1|00 .105.40.17.53.78.79.117.71.5.68.34.6.115.24.42.99.22.56.106.90.108.84.94.35.62.39.110.10.26.61.23.87.64.9.55.72.88.37.28.13.112.2.121.4.111.33.95.120.118.30.1.45.91.107.63.98.58.41.74.96.67

Кстати огромное спасибо за столь замечательный анализ!

-- 04.09.2017, 22:49 --

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

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

Ну конечно, я что то ступил тут.

[Dmitriy40]

Да, там остались и ещё несколько ошибок, но принципиально на ситуацию они не влияют, лишь последовательность состояний чуть другая, но итоговой результат, с числом $1000000000000403$, тот же.
Вот правильная динамика увеличения предела:

Используется синтаксис Text

109->1901
307->4703
409->9041
503->23053
2003->30029
4001->100403
4007->170047
40009->1900043
100003->3000017
200003->3000029
200009->19000027
1000003->33000001
7000009->79000007
8000009->90000083
20000003->1300000021
300000007->6700000003
400000009->9000000043
500000003->23000000053
500000009->29000000059
4000000007->370000000043
40000000003->3000000000409
700000000009->3900000000007
2000000000003->300000000000241
40000000000001->1000000000000403

[dimkadimon]

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

Да, там остались и ещё несколько ошибок, но принципиально на ситуацию они не влияют, лишь последовательность состояний чуть другая, но итоговой результат, с числом $1000000000000403$, тот же.
Вот правильная динамика увеличения предела:

Еще раз спасибо. Значит все таки простое решение возможно в интервале $(1\cdot10^{15}\ldots6\cdot10^{15})$. Отличная новость, но как его найти?! Если это вообще возможно...

Получается все проблемы упираются в нули. А что если мы разрешим использовать добавочные нули? - тогда простое решение точно найдется.