К проблеме 196

[kazvadim]

Проблема $196$ - это открытая математическая задача (см. энциклопедии).
Числа последовательности $196$ можно разложить на суммы трёх палиндромов, два из которых равны, а третий состоит из нулей и единиц:

$2\cdot393+101=887$

$2\cdot787+101=1675$

$2\cdot3663+0110=7436$

$2\cdot6336+1111=13783$

$2\cdot25752+01010=52514$

$2\cdot41514+11011=94039$

$2\cdot93039+01010=187088$

$2\cdot483384+101101=1067869$

$2\cdot5372735+000010000=10755470$

$2\cdot08555580+1100011=18211171$
и т.д.
Так как в результате умножения палиндрома, содержащего цифры не больше $4$, на $2$ получится палиндром. И в результате сложения такого палиндрома с палиндромом, состоящим из нулей и единиц, получится палиндром. То возникает вопрос: можно ли найти закономерность в последовательности:
$ 393,787,3663,6336,25752,41514,93039,483384,5372735,08555580,... $ (1)
Если такую закономерность можно найти, то следующим шагом будет вычисление палиндрома (количества итераций, когда палиндром появится в последовательности (1)), который содержит цифры не больше $4$. Или доказательство того, что такого палиндрома нет в последовательности.

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствует внятная формулировка вопроса (в частности, пояснение, из каких соображений выбиралось именно такое представление чисел);
- когда она появится, по-видимому, понадобятся и собственные содержательные попытки решения задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Математика (общие вопросы)»

[Dmitriy40]

По моему эта задача эквивалентна исходной: что искать формулу для двух палиндромов, что формулу для исходного числа, не вижу кардинальной большой разницы. Тем более что к виду $2a+b$, где $a$ число из цифр 0,1,2,3,4 и $b$ число из цифр 0,1 можно тривиально привести вообще любое число. Т.е. задачи не просто похожи, а в точности эквивалентны.
В общем не думаю что оно разрешимо. Но Вы пытайтесь конечно ...

Ну и просто для информации. Когда-то занимался этой задачей, не математикой, а лишь программированием её, добрые люди за несколько лет насчитали почти полтора миллиарда итераций и 600млн цифр и выложили всё это длинное число в общий доступ (277мег zip архив). Потом насчитали даже миллиард чисел и соответственно почти $2.416$млрд итераций (количество цифр растёт практически линейно с коэффициентом $0.4139$ от количества итераций), но их уже не выкладывали (в то время, 7 лет назад, сейчас не знаю). У меня тогда терпения хватило на 300млн итераций (124млн цифр), а учитывая квадратичную зависимость ... дальше понадобились бы годы и годы счёта. В любом случае 600млн цифр наверняка хватит проверять свои гипотезы, а то на первых сотнях-тысячах-миллионах результаты часто бывают неадекватны.

[kazvadim]

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

По моему эта задача эквивалентна исходной: что искать формулу для двух палиндромов, что формулу для исходного числа, не вижу кардинальной большой разницы. Тем более что к виду $2a+b$, где $a$ число из цифр 0,1,2,3,4 и $b$ число из цифр 0,1 можно тривиально привести вообще любое число. Т.е. задачи не просто похожи, а в точности эквивалентны.
В общем не думаю что оно разрешимо. Но Вы пытайтесь конечно ...

Тоже так сначала подумал. Смущает то, что в представленной последовательности (1) палиндромов до бесконечности не встретится палиндром, у которого все цифры были бы не больше 4.
Если "$a$ число из цифр 0,1,2,3,4 и $b$ число из цифр 0,1", то да, но не для всех. Где $a$ палиндром.
Мне не удаётся привести к такому же виду (разложения на сумму трёх таких палиндромов) перевёрнутые числа последовательности 196.
Например, число $887=393+393+101$, а перевёрнутое число 788 никак не раскладывается, если $a$ палиндром, а $b$ число из цифр 0,1.

[Dmitriy40]

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

Смущает то, что в представленной последовательности (1) палиндромов до бесконечности не встретится палиндром, у которого все цифры были бы не больше 4.

А почему это смущает? Если предположить что цифры встречаются примерно равновероятно (это не совсем так, см. ниже, но приблизительно верно), то с ростом длины числа вероятность что все его цифры будут меньше пяти уменьшается как $1/2^N$ где $N$ количество цифр. Т.е. чем дальше, тем менее вероятно, а количество цифр быстро растёт ... Так что не вижу в этом ничего удивительного. Удивительно скорее наоборот, что такие маленькие вероятности всё же реализуются (для других начальных чисел).
Впрочем это верно лишь для случайных цифр, а они вряд ли совсем уж случайны.

Как строить палиндромы я не знаю, а вот про сами числа кое-что скажу. Например в том самом 600млн цифирном числе цифры 0-9 встретились соответственно следующее количество раз (в миллионах): $62.216, 58.208, 61.720, 57.736, 60.101, 60.132, 57.745, 61.720, 58.205, 62.217$. Видно что распределение симметрично, а в остальном близко к равномерному, хотя и явно отличается от него, но значительного перекоса в частотах цифр нет.
Дополнительно, когда писал программу, проверял насколько часто возникают переносы между цифрами (а значит ваши палиндромы имеют цифры больше 4) и насколько далеко они могут распространяться (т.е. сколько девяток подряд бывает в числе), оказалось вероятность переносов практически $0.5$ (тут могу чуть наврать, теоретически она должна быть $0.4139$), а длины распространения падают как раз как $1/2^k$, но при этом иногда попадаются и 16 девяток подряд, и больше (вот 32 не попалось ни разу или в них не попал перенос). Что в общем совпадает с оценкой вероятности.

[kazvadim]

Dmitriy40.
Насколько Вас понял, то вероятность позволяет проникнуть палиндрому в последовательность 196.
Но, чем больше число, тем вероятность меньше.
Поэтому закономерность чисел последовательности (1) смогла бы помочь... Но как вывести эту закономерность - это мне не поддаётся.
Закономерность чисел последовательности 196 ничего не даёт по цифрам числа...

[Dmitriy40]

Да. Только под числом понимается не $196$, а каждое число в его последовательности. Ну так, на всякий случай поясню.
И учтите что это не более чем догадка/предположение, в числах может быть внутренняя структура, которая где-то очень далеко, но ближе бесконечности, вдруг раз и реализуется в палиндром. Ведь с другими числами такое происходит, и достаточно быстро. Так что вероятность вовсе не доказательство. Просто надежды всё меньше и меньше, ведь ещё 5 лет назад было насчитано уже миллиард цифр ...

-- 15.11.2020, 21:29 --

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

[kazvadim]

Поэтому интерес не в расчётах очередного 100 млрд. числа, а в доказательстве до бесконечности.
Для этого хотелось бы вывести некоторую закономерность, связанную с числами из последовательности 196.

-- 15.11.2020, 22:10 --

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

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

Действительно. Из 10 первых чисел последовательности (1):
5-ка встречается в 3-х числах,
6-ка встречается в 2-х числах,
7-ка встречается в 3-х числах,
8-ка встречается в 3-х числах,
9-ка встречается в 2-х числах.
Вычислю ещё несколько чисел последовательности (1). Если результат будет уплотняться, то есть над чем призадуматься.

[Dmitriy40]

kazvadim
10 это простите ни о чём (разброс может быть $\pm 3$). Насчитайте хотя бы сотню, для разброса порядка $\pm 10$.
И сравните с встречаемостью цифр 0-4.

Если есть внятный алгоритм получения этих палиндромов из последовательности чисел 196 (начало которой насчитать легко), могу помочь с прогой. Пока без перебора не вижу как их получать.

[kazvadim]

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

kazvadim
10 это простите ни о чём (разброс может быть $\pm 3$). Насчитайте хотя бы сотню, для разброса порядка $\pm 10$.
И сравните с встречаемостью цифр 0-4.

Если есть внятный алгоритм получения этих палиндромов из последовательности чисел 196 (начало которой насчитать легко), могу помочь с прогой. Пока без перебора не вижу как их получать.

С сотней чисел просижу месяц (вручную). Алгоритм (вроде бы внятный) есть. Помогите, пожалуйста, если есть время.
Думаю поймёте на примерах.
1. 887 - 3 знака, вычитаем 101, 111; 010 вычитать не имеет смысла, так как 887 нечётно и тогда не разделится нацело на 2. Затем делим на 2. Подходит 101, чтобы в результате получился палиндром. $(887-101)/2=393$
2. 18211171 - 8 знаков, но первый знак 1. И последняя цифра выражена нечётным числом 1. Значит рассматриваем комбинации из 7 знаков палиндрома из 0,1, где первый и последний знак 1. 1000001, 1001001, 1010101, 1011101, 1100011,110101, 1110111, 1111111. Остановились на 1100011, так как $(18211171-1100011)/2=8555580$.

[Dmitriy40]

Это я и назвал перебором. Перебирать все варианты второго палиндрома. Для числа в полсотни цифр это кажется миллионы вариантов ... Да ещё плюс не помню навскидку формулу получения палиндромов, где-то помню видел, но надо искать. Подумаю ... Без простого генератора палиндромов не хочется заниматься перебором.
Впрочем, это ж двоичный палиндром, а его генерить несложно. Хотя ... Для числа в 100 цифр палиндром из 50 битов, а это квадриллион комбинаций ... Многовато. Реально лишь знаков до 40, миллион комбинаций уже не страшно, а это как раз около сотни итераций.

[Dmitriy40]

Вопрос, почему не подходят такие варианты?
$13783=11+2\cdot6886$
$94039=111+2\cdot46964$
$187088=10+2\cdot93539$
$10755470=0+2\cdot5377735$ - особенно этот красив :)
Т.е. я понимаю что тут двоичный палиндром слишком короткий, но у вас ведь тоже есть не менее странная комбинация $2\cdot5372735+000010000=10755470$. Как бы это дело формализовать? Ограничить минимальную длину двоичного полинома длиной исходного числа что ли? Но и в нём могут быт младшие нули ...

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

(Оффтоп)

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

196:
[0,0,0,2,0,0,0,0,0,1]:887=101+393*2
[0,0,0,0,0,0,0,2,1,0]:1675=101+787*2
[0,0,0,2,0,0,2,0,0,0]:7436=110+3663*2
[0,0,0,0,0,0,2,0,2,0]:13783=11+6886*2
[0,0,2,0,0,2,0,1,0,0]:52514=1010+25752*2
[0,0,0,0,2,0,2,0,0,1]:94039=111+46964*2
[0,0,0,2,0,1,0,0,0,2]:187088=10+93539*2
[0,0,0,2,2,0,0,0,2,0]:1067869=101101+483384*2
[0,0,0,2,0,2,0,3,0,0]:10755470=0+5377735*2
[1,0,0,0,0,4,0,0,2,0]:18211171=1100011+8555580*2
[0,2,0,0,0,2,2,2,0,0]:35322452=11110+17655671*2
[0,0,4,2,0,2,0,0,0,0]:60744805=10100101+25322352*2
[0,0,0,0,2,4,0,2,0,0]:111589511=100001+55744755*2
[0,4,0,2,0,0,0,2,1,0]:227574622=0+113787311*2
[0,0,4,0,0,0,3,0,0,2]:454050344=111100+226969622*2
[0,0,0,0,6,0,0,0,2,1]:897100798=111110+448494844*2
[2,0,0,0,0,1,0,2,2,2]:1794102596=1000+897050798*2
[2,0,0,4,0,0,0,2,2,0]:8746117567=1000110001+3873003783*2
[0,2,0,0,2,0,4,2,0,0]:16403234045=1111001111+7646116467*2
[0,0,5,4,0,2,0,0,0,0]:70446464506=0+35223232253*2
[0,0,0,0,5,2,4,0,0,0]:130992928913=100000001+65446464456*2
[0,0,4,0,2,4,0,0,2,0]:450822227944=1111111100+224855558422*2
[0,0,4,0,4,0,0,2,0,2]:900544455998=1100000110+449722227944*2
[0,0,0,0,2,0,0,0,4,6]:1800098901007=1101111011+899498894998*2
[6,0,0,0,4,0,0,0,1,2]:8801197801088=1000001000+4400098900044*2
[4,2,0,0,0,0,0,1,6,0]:17602285712176=110110000+8801087801088*2
[0,4,0,4,2,0,2,2,0,0]:84724043932847=10101111110101+37311466411373*2
[0,0,0,2,0,0,0,6,2,4]:159547977975595=100001+79773988937797*2
[0,0,0,2,0,4,0,5,4,0]:755127757721546=10000010000+377558878855773*2
[0,2,2,0,2,3,2,4,0,0]:1400255515443103=110000000000011+645127757721546*2
[2,2,4,4,2,2,0,0,0,0]:4413700670963144=11010000101100+2201345335431022*2
[2,2,0,2,6,0,4,0,0,0]:8827391431036288=110110110000+4413640660463144*2
[0,0,2,2,2,0,4,0,6,0]:17653692772973576=100001000+8826846336486288*2
[0,0,0,2,4,6,0,5,0,0]:85191620502609247=10100111011100101+37545754745754573*2
[4,2,2,0,2,1,2,2,0,2]:159482241005228405=11101000000010111+74190620502609147*2
[2,0,6,4,0,2,4,0,0,0]:664304741147513356=11000101101000110+326652320023256623*2
[0,2,0,0,4,4,2,4,2,0]:1317620482294916822=111000000001110+658754741147457856*2
[0,2,5,2,2,4,4,0,0,0]:3603815405135183953=1111110100010111111+1246352652562536421*2
[2,2,0,6,2,5,0,0,2,0]:7197630720180367016=110000110110000110+3543815305035183453*2
[2,0,0,2,3,0,8,4,0,0]:13305261530450734933=10000001110000001+6647630764670367466*2
[0,2,4,6,6,0,2,0,0,0]:47248966933966985264=100111100100000+23624433411433442632*2
[0,0,0,2,4,0,6,2,2,4]:93507933867933969538=10000000000000010+46748966933966984764*2
[29,30,48,62,72,57,59,55,45,29] - digit counts

[Лукомор]

Любопытное наблюдение:

если к числу $196$ дописать впереди не значащий ноль,
то за три шага получим число-палиндром -

$0196 + 6910 = 7106$;
$7106 + 6017 = 13123$;
$13123 + 32131 = 45254$;

[kazvadim]

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

Вопрос, почему не подходят такие варианты?
$13783=11+2\cdot6886$
$94039=111+2\cdot46964$
$187088=10+2\cdot93539$
$10755470=0+2\cdot5377735$ - особенно этот красив :)
Т.е. я понимаю что тут двоичный палиндром слишком короткий, но у вас ведь тоже есть не менее странная комбинация $2\cdot5372735+000010000=10755470$. Как бы это дело формализовать? Ограничить минимальную длину двоичного полинома длиной исходного числа что ли? Но и в нём могут быт младшие нули ...

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

(Оффтоп)

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

196:
[0,0,0,2,0,0,0,0,0,1]:887=101+393*2
[0,0,0,0,0,0,0,2,1,0]:1675=101+787*2
[0,0,0,2,0,0,2,0,0,0]:7436=110+3663*2
[0,0,0,0,0,0,2,0,2,0]:13783=11+6886*2
[0,0,2,0,0,2,0,1,0,0]:52514=1010+25752*2
[0,0,0,0,2,0,2,0,0,1]:94039=111+46964*2
[0,0,0,2,0,1,0,0,0,2]:187088=10+93539*2
[0,0,0,2,2,0,0,0,2,0]:1067869=101101+483384*2
[0,0,0,2,0,2,0,3,0,0]:10755470=0+5377735*2
[1,0,0,0,0,4,0,0,2,0]:18211171=1100011+8555580*2
[0,2,0,0,0,2,2,2,0,0]:35322452=11110+17655671*2
[0,0,4,2,0,2,0,0,0,0]:60744805=10100101+25322352*2
[0,0,0,0,2,4,0,2,0,0]:111589511=100001+55744755*2
[0,4,0,2,0,0,0,2,1,0]:227574622=0+113787311*2
[0,0,4,0,0,0,3,0,0,2]:454050344=111100+226969622*2
[0,0,0,0,6,0,0,0,2,1]:897100798=111110+448494844*2
[2,0,0,0,0,1,0,2,2,2]:1794102596=1000+897050798*2
[2,0,0,4,0,0,0,2,2,0]:8746117567=1000110001+3873003783*2
[0,2,0,0,2,0,4,2,0,0]:16403234045=1111001111+7646116467*2
[0,0,5,4,0,2,0,0,0,0]:70446464506=0+35223232253*2
[0,0,0,0,5,2,4,0,0,0]:130992928913=100000001+65446464456*2
[0,0,4,0,2,4,0,0,2,0]:450822227944=1111111100+224855558422*2
[0,0,4,0,4,0,0,2,0,2]:900544455998=1100000110+449722227944*2
[0,0,0,0,2,0,0,0,4,6]:1800098901007=1101111011+899498894998*2
[6,0,0,0,4,0,0,0,1,2]:8801197801088=1000001000+4400098900044*2
[4,2,0,0,0,0,0,1,6,0]:17602285712176=110110000+8801087801088*2
[0,4,0,4,2,0,2,2,0,0]:84724043932847=10101111110101+37311466411373*2
[0,0,0,2,0,0,0,6,2,4]:159547977975595=100001+79773988937797*2
[0,0,0,2,0,4,0,5,4,0]:755127757721546=10000010000+377558878855773*2
[0,2,2,0,2,3,2,4,0,0]:1400255515443103=110000000000011+645127757721546*2
[2,2,4,4,2,2,0,0,0,0]:4413700670963144=11010000101100+2201345335431022*2
[2,2,0,2,6,0,4,0,0,0]:8827391431036288=110110110000+4413640660463144*2
[0,0,2,2,2,0,4,0,6,0]:17653692772973576=100001000+8826846336486288*2
[0,0,0,2,4,6,0,5,0,0]:85191620502609247=10100111011100101+37545754745754573*2
[4,2,2,0,2,1,2,2,0,2]:159482241005228405=11101000000010111+74190620502609147*2
[2,0,6,4,0,2,4,0,0,0]:664304741147513356=11000101101000110+326652320023256623*2
[0,2,0,0,4,4,2,4,2,0]:1317620482294916822=111000000001110+658754741147457856*2
[0,2,5,2,2,4,4,0,0,0]:3603815405135183953=1111110100010111111+1246352652562536421*2
[2,2,0,6,2,5,0,0,2,0]:7197630720180367016=110000110110000110+3543815305035183453*2
[2,0,0,2,3,0,8,4,0,0]:13305261530450734933=10000001110000001+6647630764670367466*2
[0,2,4,6,6,0,2,0,0,0]:47248966933966985264=100111100100000+23624433411433442632*2
[0,0,0,2,4,0,6,2,2,4]:93507933867933969538=10000000000000010+46748966933966984764*2
[29,30,48,62,72,57,59,55,45,29] - digit counts

Очень даже подходят. Просто начинал перебор двоичных палиндромов длиной исходного числа. А посмотреть более короткие комбинации не догадался. Спасибо. Значит, несколько вариантов разложения, это может пригодиться.
Да, теперь можно начинать перебор от одного знака до длины исследуемого числа. Вроде бы это может ускорить работу программы и помочь находить самый оптимальный двоичный палиндром.
Спасибо за программу. Теперь есть инструмент и можно поработать.
Смутная мысль. А не могли ли среди миллионов чисел из последовательности 196 пропустить палиндром с нулём или нулями в конце числа. Просто не введя процедуру распознавания таких палиндромов.

-- 16.11.2020, 09:58 --

Лукомор в сообщении #1492573 писал(а):

Любопытное наблюдение:

если к числу $196$ дописать впереди не значащий ноль,
то за три шага получим число-палиндром -

$0196 + 6910 = 7106$;
$7106 + 6017 = 13123$;
$13123 + 32131 = 45254$;

Действительно любопытно. Опять возникает смутное подозрение, что в математике палиндромов с цифрой 0 не всё доработано.