Фибоначчи с заменой цифр

[Ktina]

Первые два члена последовательности - 0 и 1, как и у Фибоначчи. Но в отличие от Фибоначчи, каждый следующий член равен сумме двух предыдущих, если в них заменить каждую цифру следующей за ней (а 9 заменяется на 0). Получается вот такая последовательность:

0 1 3 6 11 29 52 93 67 82 171 375 768 1365 ...

Как мы видим, она не всегда возрастает. Например, после 93 идёт 67. А может, она вообще когда-нибудь зациклится?

[wrest]

Вряд ли зациклится когда-нибудь. По коайней мере до 100000-го члена последовательность растет.

[arseniiv]

А возможны ли вообще нетривиальные циклы при таком правиле? В частности, какие циклы небольших длин возможны и что соответствующее зацикливание последовательности может требовать от её предыдущих членов? Может ли за разными парами следовать одно и то же значение?

Кстати с нулём тут очевидная проблема. Его правильной позиционной записью должна бы быть пустая строка, так что 0, 1 должно продолжаться 2. И вообще я подобные задачи предлагал бы формулировать для т. н. биективных (неудачное название, но лучшего не предложено) систем счисления, имеющих для основания $n$ цифры $1..n$ (против $0..n-1$ для обычных позиционных систем), так что натуральный ряд с нулём в такой троичной системе будет выглядеть

<пустая строка>, 1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33, 111, 112, …

Такие системы в данном случае лучше по той очевидной причине, что нельзя добавить к записи числа слева нулей и получить ещё одну запись того же числа, ведущую себя, однако, иначе в указанном правиле.

-- Сб авг 11, 2018 22:33:28 --

В частности, в десятичной′ системе (где десятая цифра — A) ваша последовательность будет определена и записана как

ε, 1, 2, 5, 9, 16, 37, 75, 134, 331, 687, 123A, 3139, 6591, 11952, 2A765, 54939, 97926, 174A87, …

а в десятичной будет записана как

0, 1, 2, 5, 9, 16, 37, 75, 134, 331, 687, 1240, 3139, 6591, 11952, 30765, 54939, 97926, 175087, …

-- Сб авг 11, 2018 22:36:02 --

Для-и-в унарной′ системе последовательность имеет самый приятный вид:

ε, 1, 1, 11, 111, 11111, 11111111, 1111111111111, 111111111111111111111, 1111111111111111111111111111111111, …

(среди цифр за 1 следует 1), совпадая с обычной последовательностью Фибоначчи.

[wrest]

Функции.

Вспомогательная dg_up(n,k) - "прокручивает" цифры числа n на k позиций. Для того, чтобы прибавить к каждой цифре 1 (как в этой загадке), ставим k=1

dg_up(n,k)=if(n==0,k%10,fromdigits(apply(x->(x+k)%10,digits(n))))

Основная: возвращает вектор (массив), являющийся последовательностью из n первых членов, n1 - первый член, n2-второй.

Ktina129007(n,n1,n2)=my(f1=n1,f2=n2,f=0,v=vector(n,i,0));v[1]=f1;v[2]=
f2;for(i=3,n,f=dg_up(f1,1)+dg_up(f2,1);f1=f2;f2=f;v[i]=f);return(v)

Запуск:

? Ktina129007(15,0,1)                                  
 %1 = [0, 1, 3, 6, 11, 29, 52, 93, 67, 82, 171, 375, 768, 1365, 3355]

-- 11.08.2018, 20:39 --

arseniiv в сообщении #1331818 писал(а):

Его правильной позиционной записью должна бы быть пустая строка, т

Кстати pari/gp ровно так и считает, функция digits(0) возвращает "пусто", пришлось специально обходить.