есть последовательность заданная формулой
x[n]=f(x[n-1],...,x[n-k]), где f - многочлен от k перемнных. Для простоты возьмем его первой степени. При каких условиях на f последовательность периодическая, независимо от первоначальных k элементов?
Примеры:
x[n]=x[n-1]+x[n-2] - Фибоначи, не периодическая
x[n]=x[n-1]-x[n-2] - периодическая
x[n]=x[n-2]-x[n-1] - не периодическая
x[n]=x[n-1] - периодическая
Как длина периода зависит от f?

чего?

А шо такое многочлен? А Фибоначи?

глюцерогены употреблять вредно!

ниасилил...

хотелось бы увидеть определение периодической последовательности.
Я думаю, последовательность А называется периодической, если существует число m такое, что для любого k>m А(k) = A(k-m).
НО последовательность 2 под это определение не подходит... не понимаю!

(0)Откуда на форуме 1с. Такие таланты неужели во всем инете нет форумов для типа математиков?

(6) Типа 1Снику математику знать не надо? Надо только уметь быстро колотить по клавишам?

Если линейная, то понятно, что все коэффициенты должны быть равны 0,1, либо -1. Это первое условие.

Далее - не может быть двух членов с коэффициентом 1, так же как и двух членов с коэффициентом -1.

(7) ну типа в размере средней школы надо. Тезиз матспособности 1С чуть выше мат способностей бухов.

Остаются варианты - все коэффициенты равны 0 - период 1.
Один коэффициент 1, остальные 0 - период к.
Один коэффициент -1, остальные 0 - период 2*к;
Один коэффициент 1, и один -1, остальные нули - надо думать.

Хотя... возможно лажаюсь...

Короче - сумма квадратов коэффициентов должна быть равна единице, либо все коэффициенты должны быть равны нулю. - вот такое первое условие...
Это еще одно просто предположение....

Что-то меня переклинило...

ИМХО, всё гораздо проще.
Нужно проверить сходимость в пределе.
Любая функция, не являющаяся ни сходящейся, ни расходящейся - является периодической.

(5) определение правильное
x[n]=x[n-1]-x[n-2] - периодическая, потому что:
a,b,b-a,-a,-b,a-b,a,b,....

А практическое применение у этой задачи есть?

не всегда коэф. единицы, например
x[n]=sqrt(2)*x[n-1]-x[n-2] - периодическая, период 8

(17) не знаю, мне просто нравится решать задачи

(18) какая же она периодическая...
Чушь сказал.

Прикольно, но периодическая.

(0) Уверен, что задача решается аналитически, без перебора?
Похожая задача была на сборах на союз. Но там выдавалась последовательность, и надо было найти её периодическую часть и длину периода.

(22) Не знаю, у меня есть только гепотеза

блин, вы такие все умные. вам бы ракеты строить, а не в 1се копатся. Оставили бы это уж лучше нам - экономистам

(23) Перебором решается достаточно легко - могу к вечеру набрасать модуль, но есно в случае иррациональностей (SQR(2)) - ничего не выйдет из-за ошибок округления.

(24) Не тронь математиков и физиков! Они нам, инженерам, жизнь облегчают.

Всё, решил математически - всё очень просто.

Короче - представим последовательность из N элементов в виде вектора.
Следующее значение вектора Xнов=А*Хпред, где а-матрица преобразования.
Матрица имеет вид -
01000...
00100...
00010...
........
abcde,
где a,b,c,d,e - коэффициенты. для х(N-k),x(n-k+1) и т.д.

Какой-то у меня монолог получаетася ;-)
Короче, если мы возведением матрицы в некоторую степень получим матрицу, у которой все элементы равны нулю, кроме нскольких (хоть всех) диагональных, которые, кроме нуля могут равнятся единице, либо единицы, значит цикл есть. причем, если возведением в эту степень (n) мы получаем единичную матрицу, значит цикл равен степени (n), если на диагонали единицы и нули, то через n итераций входим в цикл длиной n(при этом, после n операций обнулятся некоторые элементы, и дальше будет чистый цикл)
Если на диагонали есть элементы (-1), то понятно, что дальнейшим возведением матрицы в квадрат мы получим матрицу с единицами и нулями по диагонали, соответственно цикл равен n*2, и если на диагонали есть нули, то в цикл войдет только через n итераций.
Если получили матрицу нулевую, то цикл равен единицы (обнулятся все элементы)
Это решение.
...................................
теперь замечание:
понятно, что дискриминант исходной матрицы должен быть равен нулю, единице, либо минус единицы.
......
Сейчас будет программа.

Тьфу. Имелся в виду определитель.

(28)
Собственно, в общем случае, f() - непрерывный, ограниченый оператор вида: А(x):Rk -> Rk
В идеале, нужно найти все такие операторы, чтобы A(-m)=I имело решение.
Для линейного можно решить, если вспомнить функан.
 

Ничего не надо вспоминать. Нужно посчитать определитель, а затем возводить в степень.
Иначе не проверить является ли матрица корнем единичной (либо единичной с единицами замененными на нули)
Программа:

// считать определитель перед расчетом стало влом
// он должен быть равен 0,1, либо -1, иначе цикл невозможен.
Процедура ВывестиМатрицу(К,А[])
  перем стр,м,н;
  сообщить("");
  Для м=1 по к цикл
    стр="";
    Для н=1 по к цикл
      стр=стр+Формат(а[м*к+н],"ч12.4,");
    КонецЦикла;
    сообщить(стр);
  КонецЦикла;
  сообщить("");
КонецПроцедуры
Процедура НайтиЦикл(к,х[])
  перем а[1000],ан[1000],тмп[1000];
  макстранзакций=500;
  Округление=7;
  Погрешность=0.00000001;
  // соорудим матрицу
  Для м=1 по к цикл
    Для н=1 по к цикл
      а[м*к+н]=0;
    КонецЦикла;
  КонецЦикла;
  Для м=1 по к-1 цикл
    а[м*к+м+1]=1;
  КонецЦикла;
  Для м=1 по к цикл
    а[к*к+м]=х[м];
  КонецЦикла;
  ВывестиМатрицу(к,а);
  // соорудим единичную матрицу
  Для м=1 по к цикл
    Для н=1 по к цикл
      ан[м*к+н]=0;
    КонецЦикла;
  КонецЦикла;
  Для м=1 по к цикл
    ан[м*к+м]=1;
  конеццикла;
  
  Транзакция=0;
  Флаг=0;
  Пока (транзакция<макстранзакций) и (флаг=0) цикл
    Транзакция=Транзакция+1;
    сообщить(" ++++++ "+Транзакция+" ++++++++ ");
    сообщить("");
    // подготовим пустую матрицу
    Для м=1 по к цикл
      Для н=1 по к цикл
        тмп[м*к+н]=0;
      КонецЦикла;
    КонецЦикла;
    // перемножим матрицы
    Для м=1 по к цикл
      Для н=1 по к цикл
        Для о=1 по к цикл
          тмп[м*к+о]=тмп[м*к+о]+окр(а[м*к+н]*ан[н*к+о],округление);
        КонецЦикла;
      КонецЦикла;
    КонецЦикла;
    ВывестиМатрицу(к,тмп);
    // проверим результат
    Флаг=1;
    ЕстьНулиНаДиагонали=0;
    ЕстьОтрицательныеНаДиагонали=0;
    ЕстьПоложительныеНаДиагонали=0;
    Для м=1 по к цикл
      Для н=1 по к цикл
        рез=тмп[м*к+н];
        Если м=н тогда
          Если рез*рез<=погрешность Тогда
            ЕстьНулиНаДиагонали=1;
          ИначеЕсли Рез>0 тогда
            рез=рез-1;
            ЕстьПоложительныеНаДиагонали=1;
          Иначе
            рез=рез+1;
            ЕстьОтрицательныеНаДиагонали=1;
          КонецЕсли;
        КонецЕсли;
        Если рез*рез>Погрешность Тогда
          Флаг=0;
          прервать;
        КонецЕсли;
      КонецЦикла;
      Если Флаг=0 Тогда
        прервать;
      КонецЕсли;
    КонецЦикла;
    Если Флаг=0 Тогда
      // скопируем матрицу
      Для м=1 по к цикл
        Для н=1 по к цикл
          ан[м*к+н]=тмп[м*к+н];
        КонецЦикла;
      КонецЦикла;
    КонецЕсли;
  КонецЦикла;
  Если Флаг=0 Тогда
    сообщить("Цикл не найден");
  Иначе
    Если ЕстьНулиНаДиагонали=1 Тогда
      сообщить("цикл начнется через "+Транзакция+" Итераций");
    КонецЕсли;
    Если ЕстьОтрицательныеНаДиагонали=1 тогда
      Транзакция=Транзакция*2;
    ИначеЕсли ЕстьПоложительныеНаДиагонали=0 Тогда
      Транзакция=1;
    КонецЕсли;
    сообщить("цикл содержит в себе "+Транзакция+" Итераций");
  КонецЕсли;
КонецПроцедуры
Процедура Сформировать()
  перем х[100];
  к=2;
  х[1]=-1;
  х[2]=1.41421356;
  найтицикл(к,х);
  х[1]=-1;
  х[2]=1;
  найтицикл(к,х);
  х[1]=1;
  х[2]=0;
  найтицикл(к,х);
КонецПроцедуры
решение с парой изъянов.
1) влом стало считать определитель.
2) найдите сами неточность.

Короче - что за неточность - я знаю, и как исправлять то-же.
Остальным пища для размышлений...

никто не хочет состязаться ;-)
Ошибка была в ведущих нулях.
Вариант с заплаткой ниже.
Определитель не считается - так как это очень длительная операция на больших матрицах.
// вариант с заплаткой, очень влом писать нормально.
Процедура ВывестиМатрицу(К,А[])
  перем стр,м,н;
  сообщить("");
  Для м=1 по к цикл
    стр="";
    Для н=1 по к цикл
      стр=стр+Формат(а[м*к+н],"ч12.4,");
    КонецЦикла;
    сообщить(стр);
  КонецЦикла;
  сообщить("");
КонецПроцедуры
Процедура НайтиЦикл(знач к,х[])
  перем а[1000],ан[1000],тмп[1000];
  макстранзакций=100;
  Округление=7;
  Погрешность=0.00000001;
  // заплатка для начальных нулей
  пока 1<=к цикл
    Если х[1]=0 Тогда
      Для н=1 по к-1 цикл
        х[н]=х[н+1];
      конеццикла;
      к=к-1;
    иначе
      прервать;
    КонецЕсли;
  КонецЦикла;
  // соорудим матрицу
  Для м=1 по к цикл
    Для н=1 по к цикл
      а[м*к+н]=0;
    КонецЦикла;
  КонецЦикла;
  Для м=1 по к-1 цикл
    а[м*к+м+1]=1;
  КонецЦикла;
  Для м=1 по к цикл
    а[к*к+м]=х[м];
  КонецЦикла;
  ВывестиМатрицу(к,а);
  // соорудим единичную матрицу
  Для м=1 по к цикл
    Для н=1 по к цикл
      ан[м*к+н]=0;
    КонецЦикла;
  КонецЦикла;
  Для м=1 по к цикл
    ан[м*к+м]=1;
  конеццикла;
  
  Транзакция=0;
  Флаг=0;
  Пока (транзакция<макстранзакций) и (флаг=0) цикл
    Транзакция=Транзакция+1;
    сообщить(" ++++++ "+Транзакция+" ++++++++ ");
    сообщить("");
    // подготовим пустую матрицу
    Для м=1 по к цикл
      Для н=1 по к цикл
        тмп[м*к+н]=0;
      КонецЦикла;
    КонецЦикла;
    // перемножим матрицы
    Для м=1 по к цикл
      Для н=1 по к цикл
        Для о=1 по к цикл
          тмп[м*к+о]=тмп[м*к+о]+окр(а[м*к+н]*ан[н*к+о],округление);
        КонецЦикла;
      КонецЦикла;
    КонецЦикла;
    ВывестиМатрицу(к,тмп);
    // проверим результат
    Флаг=1;
    ЕстьНулиНаДиагонали=0;
    ЕстьОтрицательныеНаДиагонали=0;
    ЕстьПоложительныеНаДиагонали=0;
    Для м=1 по к цикл
      Для н=1 по к цикл
        рез=тмп[м*к+н];
        Если м=н тогда
          Если рез*рез<=погрешность Тогда
            ЕстьНулиНаДиагонали=1;
          ИначеЕсли Рез>0 тогда
            рез=рез-1;
            ЕстьПоложительныеНаДиагонали=1;
          Иначе
            рез=рез+1;
            ЕстьОтрицательныеНаДиагонали=1;
          КонецЕсли;
        КонецЕсли;
        Если рез*рез>Погрешность Тогда
          Флаг=0;
          прервать;
        КонецЕсли;
      КонецЦикла;
      Если Флаг=0 Тогда
        прервать;
      КонецЕсли;
    КонецЦикла;
    Если Флаг=0 Тогда
      // скопируем матрицу
      Для м=1 по к цикл
        Для н=1 по к цикл
          ан[м*к+н]=тмп[м*к+н];
        КонецЦикла;
      КонецЦикла;
    КонецЕсли;
  КонецЦикла;
  Если Флаг=0 Тогда
    сообщить("Цикл не найден");
  Иначе
    Если ЕстьНулиНаДиагонали=1 Тогда
      сообщить("цикл начнется через "+Транзакция+" Итераций");
    КонецЕсли;
    Если ЕстьОтрицательныеНаДиагонали=1 тогда
      Транзакция=Транзакция*2;
    ИначеЕсли ЕстьПоложительныеНаДиагонали=0 Тогда
      Транзакция=1;
    КонецЕсли;
    сообщить("цикл содержит в себе "+Транзакция+" Итераций");
  КонецЕсли;
КонецПроцедуры
Процедура Сформировать()
  перем х[100];
  к=2;
  х[1]=-1;
  х[2]=1.41421356;
  найтицикл(к,х);
  х[1]=-1;
  х[2]=1;
  найтицикл(к,х);
  к=10;
  х[1]=-1;
  х[2]=1;
  х[3]=-1;
  х[4]=1;
  х[5]=-1;
  х[6]=1;
  х[7]=-1;
  х[8]=1;
  х[9]=-1;
  х[10]=1;
  найтицикл(к,х);
  к=3;
  х[1]=0;
  х[2]=-1;
  х[3]=0;
  найтицикл(к,х);
  к=4;
  х[1]=0;
  х[2]=0;
  х[3]=0;
  х[4]=0;
  найтицикл(к,х);
КонецПроцедуры

Много букаффф.
Ни асилил...
 
Господи, какой же я старый и ленивый...
В 1993-м году окончил с красным дипломом Университет по специальности "Автоматизация управления в технических системах".
Спутники орбитальные рассчитывали...
Системы диф. уравнений...
Сейчас смотрю на эти матрицы, определители, рисуемые NS-ом... - тошнит...
 
Примерно то же самое, что в бассейне проводил с 3-го класса по 2 часа в день... Был чемпионом республики по современному пятиборью...
Сейчас посмотрю на воду - тошнит... Не то что спортивно плавать - просто купаться - не хочется...

(36) Тебя тошнит, а меня клинит ;-) в матрице одни нули, и определитель равен первому коэффициенту.
При отбрасывании начальных нулевых коэффициентов. Первый, не нулевой должен быть равен единице, либо минус единице. Вот и всех делов (ежели первый не единица - ес-но ряд никогда не зациклится.)
Чичас склею еще одну заплатку.

реально тошнит....

Процедура ВывестиМатрицу(К,А[])
  перем стр,м,н;
  сообщить("");
  Для м=1 по к цикл
    стр="";
    Для н=1 по к цикл
      стр=стр+Формат(а[м*к+н],"ч12.4,");
    КонецЦикла;
    сообщить(стр);
  КонецЦикла;
  сообщить("");
КонецПроцедуры
Процедура НайтиЦикл(знач к,х[])
  перем а[1000],ан[1000],тмп[1000];
  макстранзакций=100;
  Округление=7;
  Погрешность=0.00000001;
  сообщить("");
  Для м=1 по к цикл
    сообщить(х[м]);
  КонецЦикла;
  Сообщить("посчитаем...");
  // заплатка для начальных нулей
  пока 1<=к цикл
    Если х[1]=0 Тогда
      Для н=1 по к-1 цикл
        х[н]=х[н+1];
      конеццикла;
      к=к-1;
    иначе
      прервать;
    КонецЕсли;
  КонецЦикла;
  // Заплатка по определителю
  Если к=0 Тогда
    сообщить("ряд сразу занулится, период равен единице");
    возврат;
  Иначеесли (х[1]<>1)и(х[1]<>-1) Тогда
    сообщить("Определитель матрицы по модулю не равен единице, ряд не может зациклиться");
    возврат;
  КонецЕсли;
  // соорудим матрицу
  Для м=1 по к цикл
    Для н=1 по к цикл
      а[м*к+н]=0;
    КонецЦикла;
  КонецЦикла;
  Для м=1 по к-1 цикл
    а[м*к+м+1]=1;
  КонецЦикла;
  Для м=1 по к цикл
    а[к*к+м]=х[м];
  КонецЦикла;
  ВывестиМатрицу(к,а);
  // соорудим единичную матрицу
  Для м=1 по к цикл
    Для н=1 по к цикл
      ан[м*к+н]=0;
    КонецЦикла;
  КонецЦикла;
  Для м=1 по к цикл
    ан[м*к+м]=1;
  конеццикла;
  
  Транзакция=0;
  Флаг=0;
  Пока (транзакция<макстранзакций) и (флаг=0) цикл
    Транзакция=Транзакция+1;
    сообщить(" ++++++ "+Транзакция+" ++++++++ ");
    сообщить("");
    // подготовим пустую матрицу
    Для м=1 по к цикл
      Для н=1 по к цикл
        тмп[м*к+н]=0;
      КонецЦикла;
    КонецЦикла;
    // перемножим матрицы
    Для м=1 по к цикл
      Для н=1 по к цикл
        Для о=1 по к цикл
          тмп[м*к+о]=тмп[м*к+о]+окр(а[м*к+н]*ан[н*к+о],округление);
        КонецЦикла;
      КонецЦикла;
    КонецЦикла;
    ВывестиМатрицу(к,тмп);
    // проверим результат
    Флаг=1;
    ЕстьНулиНаДиагонали=0;
    ЕстьОтрицательныеНаДиагонали=0;
    ЕстьПоложительныеНаДиагонали=0;
    Для м=1 по к цикл
      Для н=1 по к цикл
        рез=тмп[м*к+н];
        Если м=н тогда
          Если рез*рез<=погрешность Тогда
            ЕстьНулиНаДиагонали=1;
          ИначеЕсли Рез>0 тогда
            рез=рез-1;
            ЕстьПоложительныеНаДиагонали=1;
          Иначе
            рез=рез+1;
            ЕстьОтрицательныеНаДиагонали=1;
          КонецЕсли;
        КонецЕсли;
        Если рез*рез>Погрешность Тогда
          Флаг=0;
          прервать;
        КонецЕсли;
      КонецЦикла;
      Если Флаг=0 Тогда
        прервать;
      КонецЕсли;
    КонецЦикла;
    Если Флаг=0 Тогда
      // скопируем матрицу
      Для м=1 по к цикл
        Для н=1 по к цикл
          ан[м*к+н]=тмп[м*к+н];
        КонецЦикла;
      КонецЦикла;
    КонецЕсли;
  КонецЦикла;
  Если Флаг=0 Тогда
    сообщить("Цикл не найден");
  Иначе
    Если ЕстьНулиНаДиагонали=1 Тогда
      сообщить("цикл начнется через "+Транзакция+" Итераций");
    КонецЕсли;
    Если ЕстьОтрицательныеНаДиагонали=1 тогда
      Транзакция=Транзакция*2;
    ИначеЕсли ЕстьПоложительныеНаДиагонали=0 Тогда
      Транзакция=1;
    КонецЕсли;
    сообщить("цикл содержит в себе "+Транзакция+" Итераций");
  КонецЕсли;
КонецПроцедуры
Процедура Сформировать()
  перем х[100];
  к=2;
  х[1]=-1;
  х[2]=1.41421356;
  найтицикл(к,х);
  х[1]=-1;
  х[2]=1;
  найтицикл(к,х);
  к=10;
  х[1]=-1;
  х[2]=1;
  х[3]=-1;
  х[4]=1;
  х[5]=-1;
  х[6]=1;
  х[7]=-1;
  х[8]=1;
  х[9]=-1;
  х[10]=1;
  найтицикл(к,х);
  к=3;
  х[1]=0;
  х[2]=-1;
  х[3]=0;
  найтицикл(к,х);
  к=4;
  х[1]=2;
  х[2]=0;
  х[3]=1;
  х[4]=0;
  найтицикл(к,х);
  к=1;
  х[1]=0;
  найтицикл(к,х);
КонецПроцедуры

//*******************************************
Функция ПроверитьМассив(к,х[])
  Статус="Начало";
  Для Инд=1 По к Цикл
    Если Статус="Начало" Тогда
      Если х[Инд]=1 Тогда
        Статус="Единица";
      ИначеЕсли х[Инд]=0 Тогда
        Статус="Ноль";
      Иначе
        Возврат 0;
      КонецЕсли;
    ИначеЕсли Статус="Единица" Тогда
      Если х[Инд]<>0 Тогда
        Возврат 0;
      КонецЕсли;
    ИначеЕсли Статус="Ноль" Тогда
      Если х[Инд]=0 Тогда
      ИначеЕсли х[Инд]=1 Тогда
        Статус="Единица";
      Иначе
        Возврат 0;
      КонецЕсли;
    КонецЕсли;
  КонецЦикла;
  Возврат 1;
КонецФункции
//*******************************************
Процедура ПребразоватьМассив(к,х[],y[])
  База=y[1];
  Для Инд=1 По к-1 Цикл
    y[Инд]=y[Инд+1]+База*х[Инд];
  КонецЦикла;
  y[к]=х[к]*База;
КонецПроцедуры
//*******************************************
Процедура НайтиЦикл(к,х[])
  перем y[100];
  Для Инд=1 По к Цикл
    y[Инд]=х[Инд];
  КонецЦикла;
  Для Инд=1 По 1000 Цикл
    Если ПроверитьМассив(к,y)=1 Тогда
      Сообщить("Есть "+Инд);
      Возврат;
    КонецЕсли;
    ПребразоватьМассив(к,х,y);
  КонецЦикла;
  Сообщить("Нет ");
КонецПроцедуры
//*******************************************
Процедура Сформировать()
  перем х[100];
  х[1]=-1;
  х[2]=1.41421356;
  найтицикл(2,х);
  х[1]=-1;
  х[2]=1;
  найтицикл(2,х);
  х[1]=1;
  х[2]=-1;
  найтицикл(2,х);
  х[1]=1;
  найтицикл(1,х);
КонецПроцедуры

Что-то я начинаю вспоминать....
Возведением какой-то матрицы в степень мы по диагонали получаем гл. собственный вектор....
и соответственно он где-то должен быть единичным....
если я не ошибаюсь...

(41) Тебе зачем? Ты откуда?

Что зачем? В смысле откуда?

Зачем - в смысле зачем эта задачка, для чего,так сказать, решить ее пытаешься.
Откуда - в смысле если учишься, то где.

(0) Задал - мне стало интересно.
Я давно уже вышел из того возраста, когда учатся...
Во всяком случае, когда спрашивают, где учишься.

(40) Есно у тебя неверно.

Неужели больше никому неинтересно?
Может проще можно решить?

Придумал!
для формулы x[n]=f(x[n-1],...,x[n-k])=C[1]*x[n-1]+...+C[k]*x[n-k] (рассматривал только однородный случай) построим характеристическое уравнение t^k=C[1]*t^(k-1)+...+C[k-1]*t+C[k]. Последовательность удовлетворяющее условию формулы будет периодической независимо от первых k членов, тогда и только тогда, когда корнями характеристического уравнения являются попарно различные корни из 1 (в т.ч. комплексные). Длина периода равна НОК наименьших степеней в которых эти корни уравнения дают 1.

(48) Не факт, что это так...
как ты будешь находить все корни уравнения охрененной степени?
или будешь подставлять все корни из единицы?
Где доказательство, что это правильно?

x^2=-х+sqrt(2) - уже не подходит.

(49) корни искать действительно не просто. надо подумать, возможно для определения периодичности достаточно проверять необходимые но не достаточные условия (например |С[k]|=1).
(50) конечно не катит, надо для x[n]=sqrt(2)*x[n-1]-x[n-2] рассматривать x^2=sqrt(2)*х-1.
Сейчас попробую выложить доказательство.

мда... народ вам че, занятся нечем?
хотя завидую. белой завистью. когда-то и вот так мог. а сейчас: Дебет Кредет плюс минус умножить разделить. ээх

А не проще ли (39) В нормальный вид привести? Работает очень быстро.

не вдавался в (39), опиши словами как работает алгоритм

ПРОСНИТЕСЬ
МАТРИЦА ВАС ИМЕЕТ!!!

мля, ребяты, а с кем это вы сейчас разговаривали ... :)

Доказательство для (48)
Рассмотрим отображение сдвига A:(x[n-1],...,x[n-k])->(x[n],...,x[n-k+1]). Его матрица (тоже A) выглядит так:
C[1] . . . . C[k]
   1 0 0 . . 0
   0 1 0 . . 0
   . . . . . .
   0 . . 0 1 0
характеристическое уравнение для нее t^k=C[1]*t^(k-1)+..+C[k-1]*t+C[k]. Понятно, что если последовательность периодическая с периодом P, то A^P=E - единичная матрица. Перейдем к жордановому базису (матрица в нем A*: (A*)^P=E). Если t[1],...,t[n] - корни характеристического многочлена, то t[1]^P=...=t[n]^P=1.

(54) Удаляются в коэффициентах начальные нули, первый проверяется на равенство 1/-1, если равен - строится матрица (28), затем она последовательно возводится в степень, с ограничением на количество умножений.
Как только матрица становится пустой, кроме диагональных элементов.
И на диагонали только 1 и -1 - значит цикл есть.
если на диагонали только единицы - значит цикл равен степени, если есть минус единицы - значит цикл равен степени умноженной на 2 (при возведении в квадрат получаем единичную матрицу). В алгоритме делается поправка на погрешность результата (например для случая коэффициента равного корню из двух)
начальная матрица А строится таким образом
что если Х=
x1
x2
x3
.
.
то Ах=
х2
х3
х4
.
.
В алгоритме остались ошметки на проверку на нули на диагонали - но эта проверка не нужна, так как определитель матрицы всегда равен единице, либо -1 (и не может быть равен нулю)

(57) возведение матрицы в степень и проверка на единичную проще, чем решение уравнения N-ой степени. Тем более, что нормальных методов для определения всех корней не существует.
Хотя метод подстановки всех корней из единицы - имеет право на существование.

Не взлетит!
Нельзя разогнать воздух относительно крылев!

А как быть с неоднородным случаем, то есть когда f(0,...,0)<>0

(61) Сейчас подумаю.

В случае начального нулевого вектора -
хнов=Ах+в;
в=(0,0,0,0,...,1) после нескольких итераций
хнов=А*А*А*А*А....*А*в
хнов должен быть нулевым.
соответственно определитель А должен быть равен нулю ли бо нулевым должен быть вектор в.
Исходя из структуры матрицы А - либо все её коэффициенты должны быть равны нулю, соответственно вектор в тоже должен быть нулевым, либо изначально вектор в должен быть нулевым.

(63) а вот такая последовательность:
x[n]=C-x[n-1]

опять похоже лажу сказал...

(63,64) Еще не проснулся. Надо думать.

Единственное что пришло в голову:
1. однородная часть f должна удовлетворять условию (48) также
2. матрица A^(n-1)+A^(n-2)+...+A+E должна обнулять вектор (1,0,...,0), то есть ее первый столбец должен быть нулевым.
Однако, может оказаться так, что для 1 и 2 условия значения n могут оказаться разными :-(

(67) Как следствие: если последовательность циклична при некотором ненулевом свободном члене, то она циклична при любом свободном члене.

Вот это точно не так.
последовательность
х(N+1)=х(N)+1 разве циклична?

(69) естественно нет, 2-е условие не выполняется: матрица A+E=(1)+(1)=(2) не обнуляет вектор (1). Для одной переменной справа это очевидно только последовательности вида (64)

Интересует также и обратная задача:
верно ли что ля любой периодической последовательности найдется (возможно даже однородный) многочлен первой степени f для которого верно x[n]=f(x[n-1],...,x[n-k]).

(46) Почему?

(72) потому, что даже длину цикла неправильную выдает.
-1,1,-1,1 должно быть 10. на тестовых примерах - тоже неправильная длина.

//*******************************************
Функция ПроверитьМассив(к,х[])
  Статус="Начало";
  Един=0;
  Для Инд=1 По к Цикл
    Если Статус="Начало" Тогда
      Если х[Инд]=1 Тогда
        Статус="Единица";
        Един=Инд;
      ИначеЕсли х[Инд]=0 Тогда
        Статус="Ноль";
      Иначе
        Возврат 0;
      КонецЕсли;
    ИначеЕсли Статус="Единица" Тогда
      Если х[Инд]<>0 Тогда
        Возврат 0;
      КонецЕсли;
    ИначеЕсли Статус="Ноль" Тогда
      Если х[Инд]=0 Тогда
      ИначеЕсли х[Инд]=1 Тогда
        Статус="Единица";
        Един=Инд;
      Иначе
        Возврат 0;
      КонецЕсли;
    КонецЕсли;
  КонецЦикла;
  Возврат Един;
КонецФункции
//*******************************************
Процедура ПребразоватьМассив(к,х[],y[])
  Округление=7;
  База=y[1];
  Для Инд=1 По к-1 Цикл
    y[Инд]=y[Инд+1]+Окр(База*х[Инд],Округление);
  КонецЦикла;
  y[к]=Окр(х[к]*База,Округление);
КонецПроцедуры
//*******************************************
Процедура НайтиЦикл(к,х[])
  перем y[100];
  Для Инд=1 По к Цикл
    y[Инд]=х[Инд];
  КонецЦикла;
  Для Инд=1 По 1000 Цикл
    Рез=ПроверитьМассив(к,y);
    Если Рез<>0 Тогда
      Сообщить("Есть "+(Инд+Рез-1));
      Возврат;
    КонецЕсли;
    ПребразоватьМассив(к,х,y);
  КонецЦикла;
  Сообщить("Нет ");
КонецПроцедуры
//*******************************************
Процедура Сформировать()
  перем х[100];
  к=2;
  х[2]=-1;
  х[1]=1.41421356;
  найтицикл(к,х);
 х[2]=-1;
  х[1]=1;
  найтицикл(к,х);
  к=10;
  х[10]=-1;
  х[9]=1;
  х[8]=-1;
  х[7]=1;
  х[6]=-1;
  х[5]=1;
  х[4]=-1;
  х[3]=1;
  х[2]=-1;
  х[1]=1;
  найтицикл(к,х);
  к=3;
  х[3]=0;
  х[2]=-1;
  х[1]=0;
  найтицикл(к,х);
  к=4;
  х[4]=2;
  х[3]=0;
  х[2]=1;
  х[1]=0;
  найтицикл(к,х);
  к=1;
  х[1]=1;
  найтицикл(к,х);
  к=4;
  х[4]=-1;
  х[3]=1;
  х[2]=-1;
  х[1]=1;
  найтицикл(к,х);
КонецПроцедуры

Алгоритм (74) работает верно, если верно утверждение:
равенство K1*X1+K2*X2+…+Kn*Xn=0 выполняется для любых чисел X1,X2,…,Xn тогда и только тогда когда K1=K2=…=Kn=0.

а что такое К и что такое Х ?
работает вроде верно. И быстро.

Обоснование алгоритма.
x[n]=f(x[n-1],...,x[n-k]) подставим значение x[n-1]. Получим x[n]=f1(x[n-2],...,x[n-k-1]). Повторим эту процедуру. x[n]=fi(x[n-1-i],...,x[n-k-i]).
Свойства полученных многочленов:
1. по-прежнему многочлен от k перемнных
2. для набора x[n-1-i],...,x[n-k-i] fi единственный многочлен. Других нет! Это следует из (75). А (75) верно.
Если на какой то итерации мы получим fi с нулевыми коэффициентами, кроме одного, который равен единице. То x[n]= x[n-i-ПозЕдиницы], для любых начальных значений последовательности. Соответственно последовательность периодическая.

К (71) все просто слишком, для цикла длины T формула x[n]=x[n-T]

(78) Все очень даже не просто.
Обратная задача. Пусть k[1],…k[k], коэффициенты в f(x[n-1],...,x[n-k]). Необходимо найти такие k[1],…k[k], что бы после I итераций fi(x[n-1-i],...,x[n-k-i])= x[n-k-i].
Примеры:
1. Пусть k=2 i=1. Получаем систему уравнений: k[1]^2+ k[2]=0 и k[1]* k[2]=1. Решение: k[1]=-1, k[2]=-1.
2. Пусть k=2 i=2. Получаем систему уравнений: k[1]^3+ 2*k[1]*k[2]=0 и k[1]^2* k[2]+ k[2]^2=1. Решение: нет.
3. Пусть k=2 i=3. Получаем систему уравнений: k[1]^4+ 3*k[1]^2*k[2]+ k[2]^2=0 и k[1]^3* k[2]+ 2*k[1]*k[2]^2=1. Решение: не знаю.
В общем случае надо решать систему уравнений:
h1(k[1],…, k[k])=0
………………..
hk(k[1],…, k[k])=1
Причем h1,hk это многочлены далеко не первой степени.
PS интересно как был найден пример (sqrt(2),-1)

(79) пример найден благодаря теореме из (48) достаточно взять корень 8 степени из 1 и его сопряженный и построить многочлен

(79) ты хочешь сказать что пример в (78) не удовлетворяет произвольной периодической последовательности?

Это не единственное решение. ИМХО самое не интересное. (79) это соображения как найти все решения. Т.е. построить таблицу "Брадиса". МножествоРешений(k,t), где k количество переменных в искомом многочлене f(x[n-1],...,x[n-k]), t период периодической последовательности порожденной f(x[n-1],...,x[n-k].
Очевидно, что МножествоРешений(k,t) для каждого k,t конечно.

(82) получилось заумно.
МножествоРешений(k,t) это множество f(x[n-1],...,x[n-k]) от k переменных пораждающих последовательность с периодом t.

МножествоРешений(t) = МножествоРешений(1,t) + МножествоРешений(2,t) + ...
Очевидно из (48) k<=t, поэтому
МножествоРешений(t) = МножествоРешений(1,t) + ... + МножествоРешений(k,t)
МножествоРешений(i,t) получается полным перебором попарно различных корней из 1, таких что НОК их степеней равна t.
 

Таблица всевозможных последовательностей (в поле действительных чисел)данного периода:
период 1:
x[n]=x[n-1]
период 2:
x[n]=x[n-2]
x[n]=-x[n-1]+С
период 3:
x[n]=x[n-3]
x[n]=-x[n-1]-x[n-2]+С

период 4:
x[n]=x[n-4]
x[n]=-x[n-2]+C
x[n]=x[n-1]-x[n-2]+x[n-3]
x[n]=-x[n-1]-x[n-2]-x[n-3]+C

разумеется x[n]=C тоже периода 1

:))
увлеченные люди...
который день обсуждают тему...
начитаются Мартина Гарднера и Дьюдени и ....

периода 5:
вломы высчитывать коэффициенты, скажу только что получается 6 многочленов

Жаль нет Maple. периода 6 - 10 многочленов.

период 7 - 14 многочленов

монолог...
период 8 - 24 многочлена

думаю тема свернута, придумаю новую задачку о последовательностях

Спасибо автору за бесцельно потраченное время!

(93) да нет, что ты... Не вздумай закрывать эту тему. Весьма интерессно... Ща тока мозги соберу с пола.... )))