2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 Re: К проблеме 196
Сообщение20.11.2020, 13:48 


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

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


20/08/14
11721
Россия, Москва
kazvadim в сообщении #1493400 писал(а):
Это наблюдение за числами последовательности 196?
А кажется без разницы, это "встроено" в метод построения последовательности, что "перевернуть и сложить". Я проверил 196 и 1997 по 10 тысяч итераций, остальные поленился.
kazvadim в сообщении #1493400 писал(а):
Да, и ещё числа с нулём в последней цифре можно отнести как к последовательности N..N
Нельзя, старшая цифра должна быть ненулевой (до переворота). Во всяком случае в стандартном понимании последовательностей и палиндромов.
kazvadim в сообщении #1493400 писал(а):
Вот просеять бы последовательность, оставив только те числа (и их номер итерации), где старшая цифра равна младшей
Это снова как раз легко, ведь ничего перебирать не нужно, строим последовательность и сразу же получаем обе цифры, можно даже ничего самому не строить а взять готовые числа из A006960, там более двух тысяч чисел.

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение22.11.2020, 14:32 


15/11/20
179
Россия, Москва.
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);
чтобы перебирались не все двоичные числа, а только двоичные палиндромы длиной числа х. Подскажите, пожалуйста.

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


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

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение22.11.2020, 17:28 


15/11/20
179
Россия, Москва.
Dmitriy40 в сообщении #1493750 писал(а):
У Вас в программе ошибка с n, первый раз будет запись в p[0] и cp[0], а все вектора начинаются с 1. Надо или n++ (или n+=1) поставить в начало цикла, или инициализацию n сделать на 1.
Вроде бы всё нормально. Печатает: (1) 393 [101], (2) 787 [101], (3) 3663 [110], ...

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение22.11.2020, 18:06 
Заслуженный участник


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

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение23.11.2020, 23:19 


15/11/20
179
Россия, Москва.
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]));
}
Теперь интересно написать счётчик доли чисел, у которых первая цифра равна последней. Это просто, только не могу найти, как округлять числа, например, до второго знака после запятой

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение24.11.2020, 12:38 
Заслуженный участник


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

-- 24.11.2020, 12:49 --

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

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение24.11.2020, 14:15 


15/11/20
179
Россия, Москва.
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.

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение24.11.2020, 15:44 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение29.11.2020, 01:48 


15/11/20
179
Россия, Москва.
Интересно было посмотреть на распределение чисел из числовой последовательности 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.
Похоже, что график уже не нужен.
Пока нет идеи, что делать дальше с этими числами. Возвращаюсь к исследованию разложения на палиндромы.

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение01.12.2020, 10:03 


15/11/20
179
Россия, Москва.
Пока размышления, немного теории.

Простое утверждение (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$

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение12.12.2020, 15:35 


15/11/20
179
Россия, Москва.
К утверждению: из натурального числа в результате операции "перевернуть и сложить" получится число равное сумме палиндрома и натурального числа из цифр 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$ и т.п.

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение16.09.2021, 07:34 


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

 Профиль  
                  
 
 Re: К проблеме 196
Сообщение14.10.2021, 03:08 


15/11/20
179
Россия, Москва.
Рассмотрим самые большие найденные отложенные палиндромы. За период с 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

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

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



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

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


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

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