2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Палиндром из натуральных чисел
Сообщение26.08.2017, 04:18 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Один форумчанен 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

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение31.08.2017, 16:38 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение03.09.2017, 15:30 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Нашел $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$ не существуют.

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение03.09.2017, 15:37 


21/05/16
4292
Аделаида
В октябре будет свободное время, тогда побью!

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение03.09.2017, 16:51 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
kotenok gav в сообщении #1244825 писал(а):
В октябре будет свободное время, тогда побью!

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

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение03.09.2017, 19:59 
Заслуженный участник


20/08/14
11058
Россия, Москва
dimkadimon в сообщении #1244108 писал(а):
Нашел решения для $N=1,$
dimkadimon в сообщении #1244823 писал(а):
Палиндром из простых так и не могу найти.
Легко: $2$. Очень даже палиндром. :mrgreen:

А вот дальше всё очень интересно.
Чтобы последовательность цифр была палиндромом, надо чтобы все цифры встречались или чётное количество раз, или не более одной цифры встречалось нечётное количество раз. Этому условию отвечают лишь последовательности простых до: $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$ членов. Искать её не переискать.
И очень сильно подозреваю что там дальше тоже будут ещё кучи ограничений, которые вероятно вообще аннулируют саму возможность существования палиндрома из первых простых чисел.

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение03.09.2017, 22:00 
Заслуженный участник


20/08/14
11058
Россия, Москва
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 триллионов членов.
Сомневаюсь что кто-то сможет найти даже и столько, а ведь это далеко не конец.
Похоже всё же такого палиндрома не существует вовсе.

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение04.09.2017, 01:21 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение04.09.2017, 02:32 
Заслуженный участник


20/08/14
11058
Россия, Москва
В интервале $(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$ триллионов цифр.

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение04.09.2017, 05:10 
Заслуженный участник


20/08/14
11058
Россия, Москва
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$).

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение04.09.2017, 16:50 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Dmitriy40 в сообщении #1244879 писал(а):
И среди этих членов будет число $4001$, пара для которого не меньше $100400$

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

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение04.09.2017, 16:52 
Заслуженный участник


20/08/14
11058
Россия, Москва
dimkadimon в сообщении #1245119 писал(а):
А почему $11004$ не пара?
Потому что оно не простое. А здесь речь лишь о простых числах.

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение04.09.2017, 16:55 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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 писал(а):
Потому что оно не простое. А здесь речь лишь о простых числах.

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

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение04.09.2017, 17:04 
Заслуженный участник


20/08/14
11058
Россия, Москва
Да, там остались и ещё несколько ошибок, но принципиально на ситуацию они не влияют, лишь последовательность состояний чуть другая, но итоговой результат, с числом $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

 Профиль  
                  
 
 Re: Палиндром из натуральных чисел
Сообщение04.09.2017, 17:08 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Dmitriy40 в сообщении #1245127 писал(а):
Да, там остались и ещё несколько ошибок, но принципиально на ситуацию они не влияют, лишь последовательность состояний чуть другая, но итоговой результат, с числом $1000000000000403$, тот же.
Вот правильная динамика увеличения предела:

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 31 ]  На страницу 1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group