К проблеме 196

[kazvadim]

Так как (по моему наблюдению) палиндром выстраивается по цифрам от краёв к центру, то крайние цифры чисел последовательности могут добавить информации.

[Dmitriy40]

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

Это наблюдение за числами последовательности 196?

А кажется без разницы, это "встроено" в метод построения последовательности, что "перевернуть и сложить". Я проверил 196 и 1997 по 10 тысяч итераций, остальные поленился.

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

Да, и ещё числа с нулём в последней цифре можно отнести как к последовательности N..N

Нельзя, старшая цифра должна быть ненулевой (до переворота). Во всяком случае в стандартном понимании последовательностей и палиндромов.

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

Вот просеять бы последовательность, оставив только те числа (и их номер итерации), где старшая цифра равна младшей

Это снова как раз легко, ведь ничего перебирать не нужно, строим последовательность и сразу же получаем обе цифры, можно даже ничего самому не строить а взять готовые числа из A006960, там более двух тысяч чисел.

[kazvadim]

Dmitriy40. Пока начинаю знакомиться с PARI/GP. Вот коряво и некрасиво дописал программу, чтобы выводила номера итераций и отдельно список палиндромов. Немного ускорил, останавливая шаг цикла после найденного варианта, чтобы не считала дальше другие варианты.

x=196;
it=50;
n=0; p=vector(it); cp=vector(it);
{while(x<1e24,
   d=digits(x); b=-2+x%2;
   print1("(", n, ") ", x, "=");
   while(1,
      b+=2; v=digits(b,2); y=fromdigits(v); if(y>x, break);
      i=#v; while(i>1 && v[i]==0, i--); if(i<#v, v=concat(vector(#v-i),v));\\Расширим двоичный палиндром
      if(Vecrev(v)!=v, next);
      w=digits((x-y)/2);
      i=#w; while(i>1 && w[i]==0, i--); if(i<#w, w=concat(vector(#w-i),w));\\Расширим второй палиндром
      if(Vecrev(w)!=w, next);
      if(y==0 || #v==#w, cp[n]=y; p[n]=(x-y)/2; printf("%d+%d*2",y,(x-y)/2));
        if(y==0 || #v==#w, break);     
   );
    print;
    n+=1; x+=fromdigits(Vecrev(d));
  );
  print; 
  for(j=1,it, print("(", j, ") ", p[j], " [", cp[j], "]"));
}

Теперь не могу сообразить, как изменить строку

b+=2; v=digits(b,2); y=fromdigits(v); if(y>x, break);

чтобы перебирались не все двоичные числа, а только двоичные палиндромы длиной числа х. Подскажите, пожалуйста.

[Dmitriy40]

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

Теперь не могу сообразить, как изменить строку

b+=2; v=digits(b,2); y=fromdigits(v); if(y>x, break);

чтобы перебирались не все двоичные числа, а только двоичные палиндромы длиной числа х. Подскажите, пожалуйста.

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

b+=2; v=binary(b); if(#v<ceil(#d/2), v=concat(vector(#d-#v),v));\\Дополнение слева нулями до половины (с округлением вверх) длины x (тут вопрос какой именно длины должен быть двоичный палиндром)
v=concat(Vecrev(v),v[(#d%2)+1..#v]);\\Получение палиндрома (и чётной и нечётной общей длины)
y=fromdigits(v); if(y>x, break);

Ну и тут уже не надо расширять его, он уже нужной длины.

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

-- 22.11.2020, 17:13 --

У Вас в программе ошибка с n, первый раз будет запись в p[0] и cp[0], а все вектора начинаются с 1. Надо или n++ (или n+=1) поставить в начало цикла, или инициализацию n сделать на 1.

[kazvadim]

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

У Вас в программе ошибка с n, первый раз будет запись в p[0] и cp[0], а все вектора начинаются с 1. Надо или n++ (или n+=1) поставить в начало цикла, или инициализацию n сделать на 1.

Вроде бы всё нормально. Печатает: (1) 393 [101], (2) 787 [101], (3) 3663 [110], ...

[Dmitriy40]

Значит я чего-то не понимаю, ведь для нулевой итерации n=0, а нулевых элементов векторов не бывает.
А, разобрался, первый раз туда просто не попадает, 196 не раскладывается на нужные палиндромы. Запустите с x=887 и получите ошибку ...

[kazvadim]

Dmitriy40. Написал программу разбиения числовой последовательности на три части, основываясь на Вашем наблюдении.

x=196;
it=50;
n=0; m1=0; m2=0; m3=0;
i1=vector(it); i2=vector(it); i3=vector(it); v1=vector(it); v2=vector(it); v3=vector(it);
{while(x<1e20,
   d=digits(x); i=#d;
    a=d[1]; b=d[i];
    if(a==b, m1+=1; i1[m1]=n; v1[m1]=x; print("(", n, ") ", v1[m1], " [1]"));
    if(a==(b+1), m2+=1; i2[m2]=n; v2[m2]=x; print("(", n, ") ", v2[m2], " [2]"));
    if((b-a)>1, m3+=1; i3[m3]=n; v3[m3]=x; print("(", n, ") ", v3[m3], " [3]"));
    n+=1; x+=fromdigits(Vecrev(d));
   );
 print; print("N...N");
 for(j=1,m1, print("(", i1[j], ") ", v1[j]));
 print; print("N...N-1");
 for(j=1,m2, print("(", i2[j], ") ", v2[j]));
 print; print("1...1+n, n=1,2,3,4,5,6,7,8");
 for(j=1,m3, print("(", i3[j], ") ", v3[j]));
}

Теперь интересно написать счётчик доли чисел, у которых первая цифра равна последней. Это просто, только не могу найти, как округлять числа, например, до второго знака после запятой

[Dmitriy40]

Зачем что-то округлять если все такие числа уже попали в v1[]? А их количество просто m1? Ну а доля соответственно просто отношение m1 к общему количеству n?
Встроенной функции округления до произвольной цифры нет, можно делать так: x=round(x*10^N)/10^N.

-- 24.11.2020, 12:49 --

Интересно, а вы заметили что 37-я итерация с числом 1317620482294916822 не попала ни в один из массивов?

[kazvadim]

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

Зачем что-то округлять если все такие числа уже попали в v1[]? А их количество просто m1? Ну а доля соответственно просто отношение m1 к общему количеству n?
Встроенной функции округления до произвольной цифры нет, можно делать так: x=round(x*10^N)/10^N.

Неудобно смотреть на числа с большим количеством знаков после запятой. Попробую написать программу доли чисел [1] в зависимости от количества знаков. Затем расширить эту программу на числа (последовательности) из 2,3,4,... крайних знаков и построить график если в этом пакете есть такая возможность.

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

Интересно, а вы заметили что 37-я итерация с числом 1317620482294916822 не попала ни в один из массивов?

Это у меня ошибка. В третьем условии надо было написать или (b-a)>0, или b>>a.

[Dmitriy40]

kazvadim
Если просто неудобно смотреть, то есть встроенные средства выводить на печать число с заданным количеством знаков после запятой: printf("%0.9f", x) — вывести число с плавающей точкой в поле шириной не менее чем 0 символов, причём ровно 9 знаков после запятой (остальные округлятся до этих вот девяти). Если надо сделать перевод строки, то в строку формата добавляете "\n". Подробнее сами смотрите в любом справочнике про printf.
Т.е. надо чётко разделять вычисление значения и печать результата вычислений, первое лучше вести как можно точнее, второе же форматировать по вкусу.

Построить график можно, даже два вида (грубый прямо в тексте plot и красивый в графическом файле ploth), но из функции, как по массиву я не разобрался, предпочитаю вывести массив в текстовый файл и загнать в Excel и уже там строить графики, это быстрее и удобнее.

PS. И наверное вопросы по языку PARI/GP лучше задавать не в общей теме раздела математики, этим Вы только отпугиваете математиков отсюда, а в профильном разделе/теме, я же давал на неё ссылку (там возможно даже уже и есть ответы на эти вопросы).

[kazvadim]

Интересно было посмотреть на распределение чисел из числовой последовательности 196, которые начинают читаться от начала и от конца одинаково до заданного количества цифр. Примерно так:

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

x=196; \\ первое число последовательности
li=10; \\ количество крайних цифр числа (от начала и от конца) 
sgn=1; \\ переменная количества знаков числа
n=0; \\ переменная количества итераций
m=0; \\ переменная количества выпадений
it=500; \\ интервал итераций
{while(sgn<10000, \\ предельное количество знаков числа
   sgn+=1; E=10^sgn;
      while(x<E,
        n+=1; e=0; k=0;
        d=digits(x); x+=fromdigits(Vecrev(d));
        d1=digits(x); i=#d1; if(li>i, break);
           while(e<li,
             e+=1; ei=i-e+1; a=d1[e]; b=d1[ei];
             if(a==b, k+=1); if(k==li, m+=1);
           );
        if(n==it, sh=m/n; print; 
           print1 ("extreme=", e, ", iterations=", n, ", signs=", sgn, ", score=", m, ", share=");
           printf("%0.5f", sh); it+=500);
      );
  );
}

extreme=10, iterations=500, signs=216, score=1, share=0.00200
extreme=10, iterations=1000, signs=411, score=4, share=0.00400
extreme=10, iterations=1500, signs=621, score=7, share=0.00467
extreme=10, iterations=2000, signs=834, score=7, share=0.00350
extreme=10, iterations=2500, signs=1049, score=11, share=0.00440
extreme=10, iterations=3000, signs=1268, score=11, share=0.00367
extreme=10, iterations=3500, signs=1469, score=13, share=0.00371
extreme=10, iterations=4000, signs=1671, score=15, share=0.00375
extreme=10, iterations=4500, signs=1884, score=16, share=0.00356
extreme=10, iterations=5000, signs=2088, score=18, share=0.00360
extreme=10, iterations=5500, signs=2298, score=18, share=0.00327
extreme=10, iterations=6000, signs=2501, score=20, share=0.00333
extreme=10, iterations=6500, signs=2703, score=22, share=0.00338
extreme=10, iterations=7000, signs=2917, score=23, share=0.00329
extreme=10, iterations=7500, signs=3133, score=23, share=0.00307
extreme=10, iterations=8000, signs=3340, score=25, share=0.00313
extreme=10, iterations=8500, signs=3536, score=27, share=0.00318
extreme=10, iterations=9000, signs=3733, score=30, share=0.00333
extreme=10, iterations=9500, signs=3942, score=31, share=0.00326
extreme=10, iterations=10000, signs=4158, score=34, share=0.00340
extreme=10, iterations=10500, signs=4349, score=36, share=0.00343
extreme=10, iterations=11000, signs=4552, score=40, share=0.00364
extreme=10, iterations=11500, signs=4764, score=43, share=0.00374
extreme=10, iterations=12000, signs=4971, score=44, share=0.00367
extreme=10, iterations=12500, signs=5179, score=48, share=0.00384
extreme=10, iterations=13000, signs=5386, score=49, share=0.00377
extreme=10, iterations=13500, signs=5596, score=50, share=0.00370
extreme=10, iterations=14000, signs=5800, score=53, share=0.00379
extreme=10, iterations=14500, signs=6008, score=55, share=0.00379
extreme=10, iterations=15000, signs=6212, score=57, share=0.00380
extreme=10, iterations=15500, signs=6426, score=59, share=0.00381
extreme=10, iterations=16000, signs=6631, score=60, share=0.00375
extreme=10, iterations=16500, signs=6841, score=61, share=0.00370
extreme=10, iterations=17000, signs=7044, score=63, share=0.00371
extreme=10, iterations=17500, signs=7243, score=64, share=0.00366
extreme=10, iterations=18000, signs=7455, score=65, share=0.00361
extreme=10, iterations=18500, signs=7660, score=66, share=0.00357
extreme=10, iterations=19000, signs=7872, score=68, share=0.00358
extreme=10, iterations=19500, signs=8081, score=69, share=0.00354
extreme=10, iterations=20000, signs=8295, score=70, share=0.00350
extreme=10, iterations=20500, signs=8496, score=72, share=0.00351
extreme=10, iterations=21000, signs=8707, score=74, share=0.00352
extreme=10, iterations=21500, signs=8926, score=74, share=0.00344
extreme=10, iterations=22000, signs=9135, score=75, share=0.00341
extreme=10, iterations=22500, signs=9345, score=79, share=0.00351
extreme=10, iterations=23000, signs=9552, score=81, share=0.00352
extreme=10, iterations=23500, signs=9754, score=83, share=0.00353
extreme=10, iterations=24000, signs=9958, score=86, share=0.00358

Этот пример показывает, что при разбиении всего числа итераций 24000 на равные интервалы по 500 итераций получаем для количества крайних цифр 10:
- количество знаков чисел с каждым шагом увеличивается примерно на 210;
- количество выпадений при этом прибавляет примерно 2;
- доля выпадений стремиться к среднему примерно 0,0035.
Похоже, что график уже не нужен.
Пока нет идеи, что делать дальше с этими числами. Возвращаюсь к исследованию разложения на палиндромы.

[kazvadim]

Пока размышления, немного теории.

Простое утверждение (1).
Из натурального числа в результате операции "перевернуть и сложить" получится число равное сумме палиндрома и числа с разрядами 0 и 1.

Представим числа в позиционной системе счисления. Исходное натуральное число
$x=a_{n-1}a_{n-2}...a_1a_0, 0\leq a_i\leq9$, где $i$ - номер разряда, цифры.
В результате операции "перевернуть и сложить" получим число
$y=b_nb_{n-1}...b_1b_0$, где:
если $a_i+a_{n-i-1}\leqslant 9$, то к разряду $b_{i+1}$ числа $y$ прибавлено 0;
если $a_i+a_{n-i-1}>9$, то к разряду $b_{i+1}$ числа $y$ прибавлено 1.
При этом разряд $b_n$ равен 0 или 1.
Найдём число $v=d_nd_{n-1}...d_1d_0$, где $d_0=0$ и:
$d_i=0$, если к разряду $b_i$ числа $y$ не прибавлялось 1;
$d_i=1$, если к разряду $b_i$ числа $y$ прибавлялось 1.
Число $v$ - это число из цифр 0 и 1.
Число $z=c_{n-1}c_{n-2}...c_1c_0$ получим, вычитая из числа $y$ число $d$. Число $z$ - это палиндром, так как $a_i+a_{n-i-1}=a_{n-i-1}+a_i$ и $c_i=b_i-d_i$.
Тогда $y=z+d$, где $z$ - палиндром, $d$ - число из цифр 0,1.

Например: $x=1675, y=1675+5761=7436, z=6336, d=1100$

[kazvadim]

К утверждению: из натурального числа в результате операции "перевернуть и сложить" получится число равное сумме палиндрома и натурального числа из цифр 0, 1. Как правило, такое разложение имеет несколько вариантов. Посмотрим на примере чисел последовательности 196

x=196; 
n=0;
{while(x<1e7,
    print("(", n, ") ", "x=", x, "=");
    d=digits(x); b=-1;
        while(1,
       b+=1; v=digits(b,2); y=fromdigits(v); 
            if(y>x, break); 
       z=x-y; w=digits(z); u=fromdigits(Vecrev(w));
            if(z==u, printf("      %d+%d; ", z, y); print);
        );
   n+=1; x+=fromdigits(Vecrev(d));
  );
}

(0) x=196=
(1) x=887=
      787+100; 
      777+110; 
(2) x=1675=
      575+1100; 
      565+1110; 
(3) x=7436=
      6336+1100; 
(4) x=13783=
      3773+10010; 
      2772+11011; 
(5) x=52514=
      41514+11000; 
      41414+11100; 
(6) x=94039=
      93939+100; 
      93039+1000; 
      92929+1110; 
      83938+10101; 
      83038+11001; 
      82928+11111; 
(7) x=187088=
      87078+100010; 
      77077+110011; 
(8) x=1067869=
      967769+100100; 
      957759+110110; 

Разложение, рассмотренное при доказательстве утверждения (1), верно для всех натуральных чисел. Числа, которые в результате операции "перевернуть и сложить" дают палиндром приводят к разложению, когда натуральное число из цифр 0,1 равно 0. Например, $12368+86321=98689$,. Но есть ещё разложения: $98689=87678+11011, 98689=97579+1110$ и т.п.

[kazvadim]

Посмотрел на задачу от обратного. Получилось, что если обозначить цепочки палиндромов по принципу: «от палиндрома до палиндрома до старшего по количеству знаков», то удвоенный старший палиндром относится к подклассу чисел Лишрел. Посмотрел $100 000$ итераций, контр примера не нашёл. Вернулся к началу темы. Существуют двоичные палиндромы не равные нулю, которые при прибавлении к удвоенному палиндрому составляют бесконечную последовательность чисел Лишрел.

[kazvadim]

Рассмотрим самые большие найденные отложенные палиндромы. За период с 30 ноября 2005 по 5 января 2021 найдено и подтверждено только $2$ больших палиндрома. И, соответственно, $4$ больших кандидата в числа Лишрел (это когда большой палиндром умножим на $2$ и, разделив на $11$, тоже умножив на $2$ (почему с третьей итерации числа последовательностей «перевернуть и сложить» делятся на $11$, а палиндромы из таких последовательностей, делённые на $11$ дают палиндром, не раскладываемый на предыдущую итерацию «перевернуть и сложить», и тоже приводящий к кандидату в число Лишрел – это доказательство может пролить свет на решение проблемы)). К сожалению я не математик, просто хороший экспериментатор. Если есть возможность, помогите с доказательством и пойдём дальше.
В круглых скобках количество итераций, в фигурных скобках длина числа, в квадратных скобках разложение на простые.

start x=1186060307891929990 Джейсон Дусетт, 30 ноября 2005
(261) {l=119}; [2,4;11,2;19,1;83,1;193,1;1549272270043,1;48814524233722672915113188924424363867011100343337392696161477453949437593269316660542324149259573,1]
x=44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 x/11=4051151443543312511130713543332170035353162151145311441451221541441135411512613535300712333453170311152133453441511504 ***palindrom***
(29017) end

start x=1999291987030606810 Андрей Щебетов, май 2017
(261) {l=119}; [2,4;11,2;19,1;83,1;193,1;1549272270043,1;48814524233722672915113188924424363867011100343337392696161477453949437593269316660542324149259573,1]
x=44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 x/11=4051151443543312511130713543332170035353162151145311441451221541441135411512613535300712333453170311152133453441511504 ***palindrom***
(29017) end
start x=12000700000025339936491 Rob van Nobelen, 26 апреля 2019
(288) {l=142}
[2, 1; 7, 1; 11, 1; 29, 1; 1279, 1; 90823, 1; 165712919739319, 1; 77171416979016555719654812731854573535912566742275150799021248004386657809196143280046554640435176180592799623340937, 1]; x=6634343445544188178365154497662249922269477578658488045222897505659677887769565057982225408848568757749622299422667944515638718814455443434366 x/11=603122131413108016215014045242022720206316143514408004111172500514516171615415005271111400804415341613602027220242540410512610801314131221306 ***palindrom***
(28915) end

start x=12000700000025339936491 Rob van Nobelen, 26 апреля 2019
(288) {l=142}
[2, 1; 7, 1; 11, 1; 29, 1; 1279, 1; 90823, 1; 165712919739319, 1; 77171416979016555719654812731854573535912566742275150799021248004386657809196143280046554640435176180592799623340937, 1]; x=6634343445544188178365154497662249922269477578658488045222897505659677887769565057982225408848568757749622299422667944515638718814455443434366 x/11=603122131413108016215014045242022720206316143514408004111172500514516171615415005271111400804415341613602027220242540410512610801314131221306 ***palindrom***
(28915) end

start x=13568441660506503386420 Антон Стефанов, 5 января 2021
(289) {l=142}
[2, 1; 7, 1; 11, 1; 29, 1; 1279, 1; 90823, 1; 165712919739319, 1; 77171416979016555719654812731854573535912566742275150799021248004386657809196143280046554640435176180592799623340937, 1];
x=6634343445544188178365154497662249922269477578658488045222897505659677887769565057982225408848568757749622299422667944515638718814455443434366 x/11=603122131413108016215014045242022720206316143514408004111172500514516171615415005271111400804415341613602027220242540410512610801314131221306 ***palindrom***
(28916) end