К проблеме 196

[Dmitriy40]

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

Смутная мысль. А не могли ли среди миллионов чисел из последовательности 196 пропустить палиндром с нулём или нулями в конце числа. Просто не введя процедуру распознавания таких палиндромов.

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

Впрочем, можете сами убедиться, вот программа для поиска младших 4-х нулей и её чуть облагороженный вывод для первых 100 тысяч итераций (слева номер итерации, потом первые и последние 9 цифр числа):

x=196; i=0; while(i<=10^5, d=digits(x); if(x%10000==0, printf("%d:%d...%d\n", i,d[1..9],d[#d-8..#d])); x+=fromdigits(Vecrev(d)); i++); quit

675:109997222...422170000
18042:109993891...408840000
25052:109997195...260170000
45303:109996535...664460000
62055:109990268...886210000
66182:109990957...974810000
74126:109999102...220090000
89760:109996323...632260000

А вот сюда выложил список (5634 вхождений) с одним нулём справа, те же первые сто тысяч итераций.

-- 16.11.2020, 12:06 --

Кстати это же говорит что младший ноль встречается вдвое реже равновероятного (5634 вместо 10000 раз).

[Dmitriy40]

Ради Вашего спокойствия взял свою старую программу расчёта последовательности и модифицировал в ней проверку на палиндром с пропуском младших нулей. Запустил, 40 минут счёта и среди первых 10млн итераций такого урезанного палиндрома не обнаружено.

[kazvadim]

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

Ради Вашего спокойствия взял свою старую программу расчёта последовательности и модифицировал в ней проверку на палиндром с пропуском младших нулей. Запустил, 40 минут счёта и среди первых 10млн итераций такого урезанного палиндрома не обнаружено.

И это правильно. Не должно было быть так просто

[Dmitriy40]

Была мысль что при младших нулях старшие цифры всегда 10999 (и много девяток), но вдруг нашлось два контрпримера: 495301:110000781476431...822466419800000 и 863390:110005521728266...866391721560000.

[kazvadim]

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

Ну и потом в проблеме 196 палиндромы понимаются более узко чем Вы, они имеют точное количество цифр, без всяких дописываний нулей слева.

Вот это и насторожило. А если у числа последняя цифра 0, а первая разумеется не 0, то сразу не палиндром.
Тут надо сбрасывать последние нулевые цифры, а потом смотреть, палиндром или не палиндром.

[Dmitriy40]

kazvadim
Надо или не надо — вопрос определений, что считать палиндромом. Ваше понимание отличается, тоже имеет право на жизнь. Но в известной проблеме 196 используется другое.

[kazvadim]

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

kazvadim
Надо или не надо — вопрос определений, что считать палиндромом. Ваше понимание отличается, тоже имеет право на жизнь. Но в известной проблеме 196 используется другое.

Это осознаю. Это другое определение почему-то уничижает цифру 0, которая ничем не провинилась перед другими цифрами. Что мешает применить другое (расширенное) понимание определения палиндрома? Начальное определение: палиндром - это число, которое читается с конца так же, как с начала.
Чем, например, провинилось число 12345543210, которое не признают палиндромом. Наверное тем, что перевернув, получим 1234554321... Но тогда, если исчез 0 после переворота, то где исчезнувший 0 до переворота. На мой взгляд правильней всё же так.
012345543210 переворачиваем, получим 012345543210. Количество знаков числа сохраняем (0 - тоже знак для палиндромов). Иначе при перевороте числа теряем знаки. И получается, что перевёрнутое число насчитывает меньше знаков, чем исходное число. Какой-то странный переворот.

[Dmitriy40]

kazvadim
Повторю, это вопрос определений.
Обычно для палиндромов операция переворота определяется как сохраняющая длину в цифрах. И тогда переворот числа $1000$ даёт число $0001$ и никаких знаков не теряется и ничего не уничижает и соответственно они оба не палиндромы (оба читаются по разному слева и справа), а не $1$, как Вы желаете. То что математически $0001=1$ — дело немного другое и не обязательно верное для палиндромов.
Лично мне больше нравится обычное определение, сохраняющее длину числа (хотя бы потому что мне меньше мороки с написанием программ ) и не нравятся "палиндромы по вашему" $7000000$ и аналогичные.

-- 16.11.2020, 19:05 --

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

[kazvadim]

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

kazvadim
Лично мне больше нравится обычное определение, сохраняющее длину числа (хотя бы потому что мне меньше мороки с написанием программ ) и не нравятся "палиндромы по вашему" $7000000$ и аналогичные.

Не хотелось бы, чтобы беседа о "палиндромах по моему" повлияла на нашу работу. Не против обычного определения. Отвлёкся, извините.

[Dmitriy40]

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

(Программа и её результат)

x=196; zz=vector(10);
{while(x<1e20,
   d=digits(x); b=vector(#d); b[1]=x%2; b[#b]=b[1]; if(b[1]==0, b[2]=1; b[#b-1]=1);
   printf("%d:", x);
   while(1,
      y=fromdigits(b); if(y>x, break);
      w=digits((x-y)/2);
      if(Vecrev(w)==w,
         z=vector(10);
         for(i=1,#w, z[w[i]+1]++); zz+=z;
         printf("%c%d:%d=%d+%d*2", 13,z,x,b,(x-y)/2);
         break;
      );
      i=2; j=#b-1;
      while(i<=j, b[i]=1-b[i]; b[j]=b[i]; if(b[i]==1, break; , i++; j--; if(i>j, break(2)) ) );
   );
   print;
   x+=fromdigits(Vecrev(d));
)}
printf("%d - digit counts\n", zz);

196:
[0,0,0,2,0,0,0,0,0,1]:887=[1,0,1]+393*2
[0,0,2,0,0,0,0,0,1,0]:1675=[1,1,1,1]+282*2
[0,0,0,2,0,0,2,0,0,0]:7436=[0,1,1,0]+3663*2
13783:
[0,0,2,0,0,2,0,1,0,0]:52514=[0,1,0,1,0]+25752*2
[0,2,0,0,2,1,0,0,0,0]:94039=[1,1,0,1,1]+41514*2
187088:
1067869:
10755470:
18211171:
[0,6,0,0,0,0,0,2,0,0]:35322452=[0,1,1,0,0,1,1,0][phone]*2
[0,0,4,2,0,2,0,0,0,0]:60744805=[1,0,1,0,0,1,0,1][phone]*2
111589511:
227574622:
[0,0,4,0,2,0,2,1,0,0]:454050344=[0,0,1,1,0,1,1,0,0][phone]*2
[2,0,0,2,4,1,0,0,0,0]:897100798=[0,1,1,0,0,0,1,1,0][phone]*2
1794102596:
[2,0,0,4,0,0,0,2,2,0]:8746117567=[1,0,0,0,1,1,0,0,0,1][phone]*2
16403234045:
70446464506:
130992928913:
[0,0,4,0,2,4,0,0,2,0]:450822227944=[0,0,1,1,1,1,1,1,1,1,0,0][phone]*2
[0,0,4,0,6,0,0,2,0,0]:900544455998=[0,1,1,1,0,0,0,0,1,1,1,0][phone]*2
1800098901007:
[6,0,0,0,4,0,0,0,1,2]:8801197801088=[0,0,0,1,0,0,0,0,0,1,0,0,0][phone]*2
17602285712176:
[0,4,0,4,2,0,2,2,0,0]:84724043932847=[1,0,1,0,1,1,1,1,1,1,0,1,0,1][phone]*2
159547977975595:
[0,0,0,2,0,4,0,5,4,0]:755127757721546=[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0][phone]*2
1400255515443103:
[2,2,4,4,2,2,0,0,0,0]:4413700670963144=[0,0,1,1,0,1,0,0,0,0,1,0,1,1,0,0]+2201345335431022*2
[2,2,0,2,6,0,4,0,0,0]:8827391431036288=[0,0,0,0,1,1,0,1,1,0,1,1,0,0,0,0]+4413640660463144*2
17653692772973576:
[0,0,0,2,4,6,0,5,0,0]:85191620502609247=[1,0,1,0,0,1,1,1,0,1,1,1,0,0,1,0,1]+37545754745754573*2
159482241005228405:
[2,0,6,4,0,2,4,0,0,0]:664304741147513356=[0,1,1,0,0,0,1,0,1,1,0,1,0,0,0,1,1,0]+326652320023256623*2
1317620482294916822:
[0,2,5,2,2,4,4,0,0,0]:3603815405135183953=[1,1,1,1,1,1,0,1,0,0,0,1,0,1,1,1,1,1,1]+1246352652562536421*2
[2,2,0,6,2,5,0,0,2,0]:7197630720180367016=[0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0]+3543815305035183453*2
13305261530450734933:
[0,2,4,6,6,0,2,0,0,0]:47248966933966985264=[0,0,0,0,0,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0]+23624433411433442632*2
[0,0,2,2,4,0,6,0,2,4]:93507933867933969538=[0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0]+46248966933966984264*2
[18,22,41,46,48,33,26,20,14,7] - digit counts

[kazvadim]

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

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

И в формулировке можно изменить слова. Вместо "палиндром, состоявший из 0 и 1" написать "двоичное число". На суть решения это не влияет.

[kazvadim]

Вернусь к вопросу, на который ответил ошибочно.

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

Вопрос, почему не подходят такие варианты?
$13783=11+2\cdot6886$
$94039=111+2\cdot46964$
$187088=10+2\cdot93539$
$10755470=0+2\cdot5377735$ - особенно этот красив :)

Например. Рассмотрим представление $187088=10+2\cdot93539$.
Если бы палиндром содержал цифры меньше 5, например, 43434, то
$10+2\cdot43434=86878$ не палиндром.
Было представление $187088=1010+2\cdot93039$, напишем вместо 93039 палиндром 43034, тогда $1010+2\cdot43034=87078$ палиндром.
Запутался в словах, как называть такие двоичные числа.
Разрешите числа вида 01010 пока назову «условный палиндром», то есть число, при дописывании нулей в начале которого, будет читаться с конца так же, как с начала.

[Dmitriy40]

Тогда надо уточнять сколько именно нулей дописывать слева (вероятно чтобы длина всех палиндромов сравнялась), иначе не вижу разницы между 10 и 110 и и 1000 и 1100 и 1010 — они все палиндромы, однако подходит только последний.

-- 17.11.2020, 20:07 --

Заметьте, конец второй страницы темы, а задача так нормально и не поставлена ...

[kazvadim]

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

Тогда надо уточнять сколько именно нулей дописывать слева (вероятно чтобы длина всех палиндромов сравнялась), иначе не вижу разницы между 10 и 110 и и 1000 и 1100 и 1010 — они все палиндромы, однако подходит только последний.

-- 17.11.2020, 20:07 --

Заметьте, конец второй страницы темы, а задача так нормально и не поставлена ...

10=010; 110=0110; 1000=0001000; 1100=001100; 1010=01010
Дописывать столько нулей слева, сколько нулей в конце справа. Длина условного палиндрома должна быть равна длине первого палиндрома.
Ох, если бы умел писать правильные математические формулировки. И в постановке задачи цель изменилась. Доказывать отсутствие палиндрома из цифр меньше 5 до бесконечности лучше с помощью расчета вероятности цифр, как Вы подсказали.

[Dmitriy40]

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

Длина условного палиндрома должна быть равна длине первого палиндрома.

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

Плюс, для первых итераций вывод такой программы отличается от предыдущей лишь в двух случаях: 1675: (решение не найдено) и [2,0,0,2,0,4,0,0,0,0]:18211171=[11100111]+[03555530]*2 (наоборот найдено). В остальных случаях длина второго палиндрома совпадает с длиной остальных и он не заканчивается на 0 и решения обеих программ идентичны. И тоже много пропусков с отсутствующими решениями.

(Программа и её вывод)

x=196; zz=vector(10);
{while(x<1e20,
   d=digits(x); b=vector(#d); b[1]=x%2; b[#b]=b[1]; if(b[1]==0, b[2]=1; b[#b-1]=1);
   printf("%d:", x);
   while(1,
      y=fromdigits(b); if(y>x, break);
      w=digits((x-y)/2); if(#w<#d, w=concat(vector(#d-#w), w));
      if(Vecrev(w)==w,
         z=vector(10);
         for(i=1,#w, z[w[i]+1]++); zz+=z;
         printf("%c%d:%d=%d+%d*2", 13,z,x,b,w);
         break;
      );
      i=2; j=#b-1;
      while(i<=j, b[i]=1-b[i]; b[j]=b[i]; if(b[i]==1, break; , i++; j--; if(i>j, break(2)) ) );
   );
   print;
   x+=fromdigits(Vecrev(d));
)}
printf("%d - digit counts\n", zz);

196:
[0,0,0,2,0,0,0,0,0,1]:887=[1,0,1]+[3,9,3]*2
1675:
[0,0,0,2,0,0,2,0,0,0]:7436=[0,1,1,0]+[3,6,6,3]*2
13783:
[0,0,2,0,0,2,0,1,0,0]:52514=[0,1,0,1,0]+[2,5,7,5,2]*2
[0,2,0,0,2,1,0,0,0,0]:94039=[1,1,0,1,1]+[4,1,5,1,4]*2
187088:
1067869:
10755470:
[2,0,0,2,0,4,0,0,0,0]:18211171=[1,1,1,0,0,1,1,1]+[0,3,5,5,5,5,3,0]*2
[0,6,0,0,0,0,0,2,0,0]:35322452=[0,1,1,0,0,1,1,0]+[1,7,1,1,1,1,7,1]*2
[0,0,4,2,0,2,0,0,0,0]:60744805=[1,0,1,0,0,1,0,1]+[2,5,3,2,2,3,5,2]*2
111589511:
227574622:
[0,0,4,0,2,0,2,1,0,0]:454050344=[0,0,1,1,0,1,1,0,0]+[2,2,6,4,7,4,6,2,2]*2
[2,0,0,2,4,1,0,0,0,0]:897100798=[0,1,1,0,0,0,1,1,0]+[4,4,3,0,5,0,3,4,4]*2
1794102596:
[2,0,0,4,0,0,0,2,2,0]:8746117567=[1,0,0,0,1,1,0,0,0,1]+[3,8,7,3,0,0,3,7,8,3]*2
16403234045:
70446464506:
130992928913:
[0,0,4,0,2,4,0,0,2,0]:450822227944=[0,0,1,1,1,1,1,1,1,1,0,0]+[2,2,4,8,5,5,5,5,8,4,2,2]*2
[0,0,4,0,6,0,0,2,0,0]:900544455998=[0,1,1,1,0,0,0,0,1,1,1,0]+[4,4,4,7,2,2,2,2,7,4,4,4]*2
1800098901007:
[6,0,0,0,4,0,0,0,1,2]:8801197801088=[0,0,0,1,0,0,0,0,0,1,0,0,0]+[4,4,0,0,0,9,8,9,0,0,0,4,4]*2
17602285712176:
[0,4,0,4,2,0,2,2,0,0]:84724043932847=[1,0,1,0,1,1,1,1,1,1,0,1,0,1]+[3,7,3,1,1,4,6,6,4,1,1,3,7,3]*2
159547977975595:
[0,0,0,2,0,4,0,5,4,0]:755127757721546=[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0]+[3,7,7,5,5,8,8,7,8,8,5,5,7,7,3]*2
1400255515443103:
[2,2,4,4,2,2,0,0,0,0]:4413700670963144=[0,0,1,1,0,1,0,0,0,0,1,0,1,1,0,0]+[2,2,0,1,3,4,5,3,3,5,4,3,1,0,2,2]*2
[2,2,0,2,6,0,4,0,0,0]:8827391431036288=[0,0,0,0,1,1,0,1,1,0,1,1,0,0,0,0]+[4,4,1,3,6,4,0,6,6,0,4,6,3,1,4,4]*2
17653692772973576:
[0,0,0,2,4,6,0,5,0,0]:85191620502609247=[1,0,1,0,0,1,1,1,0,1,1,1,0,0,1,0,1]+[3,7,5,4,5,7,5,4,7,4,5,7,5,4,5,7,3]*2
159482241005228405:
[2,0,6,4,0,2,4,0,0,0]:664304741147513356=[0,1,1,0,0,0,1,0,1,1,0,1,0,0,0,1,1,0]+[3,2,6,6,5,2,3,2,0,0,2,3,2,5,6,6,2,3]*2
1317620482294916822:
[0,2,5,2,2,4,4,0,0,0]:3603815405135183953=[1,1,1,1,1,1,0,1,0,0,0,1,0,1,1,1,1,1,1]+[1,2,4,6,3,5,2,6,5,2,5,6,2,5,3,6,4,2,1]*2
[2,2,0,6,2,5,0,0,2,0]:7197630720180367016=[0,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0]+[3,5,4,3,8,1,5,3,0,5,0,3,5,1,8,3,4,5,3]*2
13305261530450734933:
[0,2,4,6,6,0,2,0,0,0]:47248966933966985264=[0,0,0,0,0,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0]+[2,3,6,2,4,4,3,3,4,1,1,4,3,3,4,4,2,6,3,2]*2
[0,0,2,2,4,0,6,0,2,4]:93507933867933969538=[0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0]+[4,6,2,4,8,9,6,6,9,3,3,9,6,6,9,8,4,2,6,4]*2
[20,22,39,48,48,37,26,20,13,7] - digit counts

А раз для некоторых чисел решение в виде желаемых Вами палиндромов отсутствует, то непонятно закономерность в какой последовательности чисел Вы собрались искать, ведь последовательность получается с пропусками. К тому же из 43 проверенных чисел решение отсутствует для 20, это почти половина! И встречаются непрерывные куски без решений, только среди этих 43 их два по 3 числа.
Проверил ещё 43 итерации дальше, решение отсутствует почти в половине случаев (почти строго через раз), большая часть которых числа вида $1\ldots7$ (собственно решений с такими числами вообще ни одного нет), но есть и с разной чётностью первой и последней цифры. После числа $70446464506$ все отсутствующие решения начинаются со старшей $1$.

Всё это плавно подводит к вопросу который я хотел задать позже, когда Вы наконец определитесь какие же числа/палиндромы ищете: с чего Вы вообще постулировали существование представления чисел последовательности 196 в виде суммы двух палиндромов (с коэффициентом $2$ и палиндромов весьма специального вида)? Мне это как-то совсем не очевидно. Этот вопрос кем-то исследовался? Может исходный постулат о существовании таких палиндромов неверен и задача поиска их закономерности становится бессмысленной?