2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Простые числа и палиндромы
Сообщение07.01.2021, 18:33 


15/11/20
74
Россия, Москва.
mathpath
На мой взгляд. Использовать железо, напролом вырубая лес, в поиске цветов –это грубо. Аккуратно найти лесную тропинку, ведущую к цветам, – интересней. Реализация простых палиндромов на бесконечности для меня очевидна. Но предстоит доказать хотя бы один конкретный вид таких чисел. Пока информации не хватает для построения логической цепочки доказательства.

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение07.01.2021, 20:41 
Заслуженный участник


20/08/14
7429
Россия, Москва
kazvadim
Не могу утверждать что программа прям шедевр, но она работает и простые возможные оптимизации эффекта не дают (это проверял отдельно):
Код:
p=vector(100);
{MyF(x,q)=my(i,k,y,d,xx,f=1);
   k=logint(x,10)+1; d=(x%3)*2; xx=x*10^k*10+x;
   for(i=1,9, if((i+d)%3==0, next); y=xx+i*10^k; if(ispseudoprime(y), p[q+1]=i; MyF(y, q+1); f=0));
   if(f==1 && q>=5, print(q,":",p[1..q],", digits=",k));
}
forprime(x=1,9, p[1]=x; MyF(x, 1));
{for(x=1,10^6-1,
   v=digits(x); k=#v;
   if(v[1]==5 || v[1]%2==0, for(j=2,#v, v[j]=9); x=fromdigits(v); next);
   q=fromdigits(Vecrev(v))+x*10^k*10;
   forstep(i=q,q+9*10^k,10^k, if(ispseudoprime(i), p[1]=i; MyF(i, 1)));
)}
Можно было бы ещё сильнее проредить 9 перебираемых цифр, но простые условия кончились (на признаке делимости на 3), а делимость на малые числа ispseudoprime проверит и сама достаточно быстро (и даже быстрее ручной проверки), так что эффекта вероятно вообще не будет или будет обратный, как его не было с признаком делимости на 3 и полуторакратным прореживанием.

mathpath в сообщении #1499496 писал(а):
После того, как несколько лет назад доказали, что всегда существуют 2 простых числа, лежащие не далее как на расстоянии не более чем в 256,
246.

mathpath в сообщении #1499496 писал(а):
При дальнейшем увеличении длины их конечно становится найти все труднее, но вовсе не из-за того, что их становится меньше
Их разумеется становится меньше (точнее падает их плотность, т.е. количество на фиксированном интервале), как собственно и просто самих простых чисел, но, возможно, они тоже не кончаются никогда.

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение07.01.2021, 20:58 


15/11/20
74
Россия, Москва.
Dmitriy40
Спасибо! Буду изучать (о использованных в Вашей программе функциях пока не имел представления).
Насколько пока удалось увидеть, то срабатывают не больше 4-х вставок (с чем это связано постараюсь понять).

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


20/08/14
7429
Россия, Москва
kazvadim в сообщении #1499521 писал(а):
Насколько пока удалось увидеть, то срабатывают не больше 4-х вставок (с чем это связано постараюсь понять).
Скорее не меньше, это явное условие q>=5. Просто более коротких слишком много и не интересны. Хотите выводите все, но готовьтесь к мегабайтам текста.
Ну и если запустите, то за пару минут будут выведены много 5, две 6 и даже та самая 7.
Разумеется как и всегда выводится лишь самая длинная из возможных последовательностей (за это отвечает сброс флага f=0 и проверка его при выводе).

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение07.01.2021, 21:27 


15/11/20
74
Россия, Москва.
Dmitriy40 в сообщении #1499525 писал(а):
Скорее не меньше, это явное условие q>=5. Просто более коротких слишком много и не интересны.
А-а, вот на чём я прокололся...

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


20/08/14
7429
Россия, Москва
Ура, буквально только что нашлась вторая семёрка!
7:[7406070506050706047, 6, 6, 8, 9, 1, 3], digits=1279

Утром нашлись и ещё две:
7:[9594424197914244959, 4, 6, 8, 9, 7, 3], digits=1279
7:[9673048502058403769, 3, 8, 2, 6, 4, 9], digits=1279

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение08.01.2021, 06:24 


15/11/20
74
Россия, Москва.
Dmitriy40 в сообщении #1499542 писал(а):
Ура, буквально только что нашлась вторая семёрка!
7:[7406070506050706047, 6, 6, 8, 9, 1, 3], digits=1279
Красиво! Аккуратно (по тропинке) 1279 знаков.
Если этот палиндром имеет такую производительность, то стало интересно заглянуть в его родословную, когда его главная ветвь остановилась на 7-ми. Скорее всего помогут цифры-вставки, например: [7406070506050706047, 6, 6, 8, 9, 1, 6, 6, 8, 9, 1, 3] (не проверено) или другие комбинации из цифр-вставок 6, 6, 8, 9, 1 с продолжением в дочерней цепочке. Сколько времени у меня уйдёт на написание такой программы – даже PARI не известно. Смысл в том, что не надо перебирать простые палиндромы, а только исходить из начального числа и добавлять к нему комбинации вставок. Уверен, потомство есть.

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


20/08/14
7429
Россия, Москва
Ну, например некоторые простые числа:
8:[7047894987407, 1, 3, 8, 2, 1, 5, 1], digits=1791
8:[7047894987407, 1, 3, 8, 2, 8, 7, 2], digits=1791
8:[7047894987407, 1, 5, 3, 8, 4, 6, 5], digits=1791
8:[7047894987407, 1, 6, 2, 2, 4, 0, 8], digits=1791
9:[7047894987407, 0, 6, 1, 0, 3, 7, 6, 9], digits=3583
9:[7047894987407, 1, 6, 9, 3, 3, 4, 6, 6], digits=3583
10:[7047894987407, 0, 6, 1, 0, 3, 7, 0, 2, 8], digits=7167
10:[7047894987407, 0, 6, 1, 5, 5, 7, 0, 8, 3], digits=7167

8:[7406070506050706047, 6, 0, 6, 4, 3, 4, 1], digits=2559
8:[7406070506050706047, 6, 5, 4, 2, 7, 8, 9], digits=2559
10:[7406070506050706047, 5, 0, 6, 0, 1, 9, 5, 8, 3], digits=10239
10:[7406070506050706047, 5, 0, 6, 8, 0, 6, 3, 0, 6], digits=10239
10:[7406070506050706047, 5, 0, 6, 8, 0, 6, 9, 7, 9], digits=10239
10:[7406070506050706047, 9, 8, 2, 0, 7, 7, 5, 9, 6], digits=10239

8:[9594424197914244959, 1, 9, 9, 6, 5, 0, 1], digits=2559
8:[9594424197914244959, 4, 1, 7, 9, 6, 7, 7], digits=2559
8:[9594424197914244959, 4, 2, 3, 4, 9, 5, 8], digits=2559
8:[9594424197914244959, 4, 6, 8, 9, 0, 8, 9], digits=2559
8:[9594424197914244959, 4, 6, 8, 9, 3, 3, 7], digits=2559
9:[9594424197914244959, 4, 6, 1, 3, 1, 2, 6, 9], digits=5119
9:[9594424197914244959, 4, 6, 5, 2, 5, 2, 3, 3], digits=5119
9:[9594424197914244959, 4, 6, 8, 8, 9, 0, 0, 3], digits=5119
10:[9594424197914244959, 4, 6, 8, 9, 3, 3, 7, 4, 7], digits=10239

8:[9673048502058403769, 3, 2, 3, 4, 5, 3, 8], digits=2559
8:[9673048502058403769, 3, 4, 4, 5, 2, 6, 9], digits=2559
8:[9673048502058403769, 3, 8, 2, 6, 8, 1, 9], digits=2559
8:[9673048502058403769, 3, 8, 7, 7, 3, 9, 2], digits=2559
8:[9673048502058403769, 3, 8, 7, 7, 5, 5, 2], digits=2559
9:[9673048502058403769, 1, 2, 7, 5, 6, 4, 2, 1], digits=5119
9:[9673048502058403769, 3, 8, 1, 4, 5, 6, 3, 3], digits=5119
9:[9673048502058403769, 3, 8, 1, 4, 5, 7, 1, 9], digits=5119
9:[9673048502058403769, 3, 8, 9, 0, 3, 9, 6, 9], digits=5119
10:[9673048502058403769, 9, 7, 2, 6, 9, 7, 0, 6, 1], digits=10239

Но в каждой из этих цепочек много чисел были составными.

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение08.01.2021, 17:55 


15/11/20
74
Россия, Москва.
Dmitriy40 в сообщении #1499638 писал(а):
Но в каждой из этих цепочек много чисел были составными.
Затея с цепочками предполагает более короткий путь к выводу свойства простого палиндрома внутри заданного алгоритма. Но это ещё предстоит исследовать, а пока собираем информацию.
Нахождение простого палиндрома с большим количеством знаков с помощью этого алгоритма – тоже хорошая задача. И ещё не известно, что даст больше информации.

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение13.01.2021, 03:08 
Заслуженный участник


20/08/14
7429
Россия, Москва
Нашлись ещё 4 семёрки:
7:[322594652535256495223, 9, 6, 1, 3, 8, 5], digits=1407
7:[372310072171270013273, 6, 6, 6, 2, 9, 9], digits=1407
7:[393341495595594143393, 9, 3, 9, 5, 3, 3], digits=1407
7:[393955415636514559393, 6, 7, 1, 9, 5, 9], digits=1407

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


20/08/14
7429
Россия, Москва
Добавлю программу для проверки чисел в моём формате записи с примером вызова для последней из семёрок (она начинается со второй строки, в первой не палиндром):
Код:
? {MyList(s)=my(x,k,d,i);
   if(#s>0, x=s[1]; k=logint(x,10)+1; printf("1:%d, digits=%d",s[1..1],k); if(ispseudoprime(x), print(", prime"), print));
   if(#s>1, x=x*10^k*10+s[2]*10^k+fromdigits(Vecrev(digits(x))); d=x%3; k=k*2+1; printf("2:%d, digits=%d",s[1..2],k); if(s[2]>0 && d>0 && ispseudoprime(x), print(", prime"), print));
   for(i=3,#s, x=x*10^k*10+s[i]*10^k+x; d=(d*2+s[i])%3; k=k*2+1; printf("%d:%d, digits=%d",i,s[1..i],k); if(s[i]>0 && d>0 && ispseudoprime(x), print(", prime"), print));
}
? MyList([3939554156,3,6,7,1,9,5,9,1])
1:[3939554156], digits=10
2:[3939554156,3], digits=21, prime
3:[3939554156,3,6], digits=43, prime
4:[3939554156,3,6,7], digits=87, prime
5:[3939554156,3,6,7,1], digits=175, prime
6:[3939554156,3,6,7,1,9], digits=351, prime
7:[3939554156,3,6,7,1,9,5], digits=703, prime
8:[3939554156,3,6,7,1,9,5,9], digits=1407, prime
9:[3939554156,3,6,7,1,9,5,9,1], digits=2815

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение14.01.2021, 04:22 


15/11/20
74
Россия, Москва.
Посмотрев (и убедившись) на работу двух алгоритмов: с приставкой и вставкой, - пойдём дальше. Сдвоенный алгоритм: приставка И/ИЛИ вставка. Этот алгоритм (на мой взгляд) вычисляет ВСЕ простые палиндромы по непрерывным цепочкам до бесконечности. Посмотрим (для упрощения наблюдения) на цифро-нечётные простые палиндромы, состоящие из 1,3. Другие комбинации цифр 1,3,7,9 показывают тоже самое.
Видно, что алгоритма: приставка ИЛИ вставка – достаточно.

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение16.01.2021, 18:05 


15/11/20
74
Россия, Москва.
Подытожим. Извините, немного лирики. Мы с Dmitriy40 открыли многовековой ларец простых чисел с помощью отмычки - простой палиндром. Но достали пока из ларца один сокровенный алмаз, а там целая россыпь... продолжим работать...

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение20.01.2021, 03:45 


15/11/20
74
Россия, Москва.
Вот что ещё бы понять - почему в A002385 простые палиндромы подаются просто кучей (без правильной сортировки). Посмотрим на программу (PARI) по ссылке A002385:
Код:
forprime(p=2, 10^5, my(d=digits(p, 10)); if(d==Vecrev(d), print1(p, ", ")));
Сравним скорости программ на примере 9 знаков:
Код:
a=1; \\ 2a+1 - начальное количество знаков простых палиндромов
b=4; \\ b>=a, 2b+1 - расчётное количество знаков простых палиндромов
v=[1,3,7,9]; al=0;
{for(i=a,b, e=10^(2*i); s=2*i+1; yes=0;
      for(j=1,4, e1=v[j]*e; e2=(v[j]+1)*e;
          forprime(pr = e1, e2,
          d=digits(pr); if(d==Vecrev(d), yes+=1; print1(pr, ", "));               
              );
           );
          print; print("sign=", s, "  yes=", yes); al+=yes;
      );
    print("all yes=", al);
}
Это всё понадобилось потому, что нужно ускорение работы программы, так как есть ещё продолжение работы...

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение21.01.2021, 06:16 


15/11/20
74
Россия, Москва.
Математики! Сидит же теорема, что если половина числа из натурального ряда в простых числах, то палиндром тоже - простое число с вероятностью вставки 1,3,7,9. Мне, физику-экспериментатору на это уйдёт много времени (не вхож в математику, работаю интуицией).
Помощь?

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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