2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Фибоначчи с заменой цифр
Сообщение11.08.2018, 17:00 
Аватара пользователя


01/12/11

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

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

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

 Профиль  
                  
 
 Re: Фибоначчи с заменой цифр
Сообщение11.08.2018, 19:46 


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

 Профиль  
                  
 
 Re: Фибоначчи с заменой цифр
Сообщение11.08.2018, 20:11 
Заслуженный участник


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

Кстати с нулём тут очевидная проблема. Его правильной позиционной записью должна бы быть пустая строка, так что 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), совпадая с обычной последовательностью Фибоначчи.

 Профиль  
                  
 
 Re: Фибоначчи с заменой цифр
Сообщение11.08.2018, 20:36 


05/09/16
11461
Функции.

Вспомогательная 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) возвращает "пусто", пришлось специально обходить.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модератор: Модераторы



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

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


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

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