Простые числа и палиндромы

[kazvadim]

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

[Dmitriy40]

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 писал(а):

При дальнейшем увеличении длины их конечно становится найти все труднее, но вовсе не из-за того, что их становится меньше

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

[kazvadim]

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

[Dmitriy40]

kazvadim в сообщении #1499521 писал(а):

Насколько пока удалось увидеть, то срабатывают не больше 4-х вставок (с чем это связано постараюсь понять).

Скорее не меньше, это явное условие q>=5. Просто более коротких слишком много и не интересны. Хотите выводите все, но готовьтесь к мегабайтам текста.
Ну и если запустите, то за пару минут будут выведены много 5, две 6 и даже та самая 7.
Разумеется как и всегда выводится лишь самая длинная из возможных последовательностей (за это отвечает сброс флага f=0 и проверка его при выводе).

[kazvadim]

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

Скорее не меньше, это явное условие q>=5. Просто более коротких слишком много и не интересны.

А-а, вот на чём я прокололся...

[Dmitriy40]

Ура, буквально только что нашлась вторая семёрка!
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

[kazvadim]

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 не известно. Смысл в том, что не надо перебирать простые палиндромы, а только исходить из начального числа и добавлять к нему комбинации вставок. Уверен, потомство есть.

[Dmitriy40]

Ну, например некоторые простые числа:
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

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

[kazvadim]

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

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

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

[Dmitriy40]

Нашлись ещё 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

[Dmitriy40]

Добавлю программу для проверки чисел в моём формате записи с примером вызова для последней из семёрок (она начинается со второй строки, в первой не палиндром):

? {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

[kazvadim]

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

[kazvadim]

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

[kazvadim]

Вот что ещё бы понять - почему в 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);
}

Это всё понадобилось потому, что нужно ускорение работы программы, так как есть ещё продолжение работы...

[kazvadim]

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