数学奥林匹克升级题

kenmark

1. //1.c
   
2. #include <stdio.h>
   
3. 
   
4. char a[2000];
   
5. 
   
6. int main()
   
7. {
   
8.         long i;
   
9.         a[1] = 1;
   
10.         a[2] = 9;
    
11.         a[3] = 8;
    
12.         a[4] = 2;
    
13.         for (i = 5; i < 1999; ++i)
    
14.                 putchar('0' + (a[i] = (a[i-1]+a[i-2]+a[i-3]+a[i-4])%10));
    
15. 
    
16.         return 0;
    
17. }

复制代码

gxqcn

原帖由 无心人 于 2009-1-21 09:30 发表
TO 80#
GxQ是如何画的图？

在 Execl 中画好，然后截屏，再打上水印。

kenmark

1982099086374045324433444570681504093686330283360219246134423320833488332645728291022598467520417244772065348057024398445144435682178847764415444794441320619628516029786015286172661580479006512429720877240396869926637280772627728415882314083562693080198861388095262558081762615466170423982213846190661366619280996487544031824590829988499020136009548631880738865764291684978825388433882190223746077048912025962299222510843502079848990649980637628392269960499244996825164673066574281560231622116085924051062974225322295846314421182235222172223960837864538067148035648316883540217008536267160411620978487768891640116861164235446932049586879040374483944075686554043186835288310269746639428370883988837640778241522093462570467744277060398007524893440194485182673842714465944299446370669128011024736065786677666530429506017424770827740891864976687780277622778465382819088512643580693866338045762053086712665966675428932263346695666316669780491482594081324095824938449520631004598681380233860714241184473820338483382695228796027548417020912249722015848552029348495644930687128897264910449744491820114623566079286510281122611080974001562479220372245346819426132285722677228910887364033062198085148811888590267508031262110461120473482718841140611866114285946437044536829540879488994025186059048136885788815264796689928875888938887140273246572043962075462794227560893002574843940699480132623342219460994249946875664178061524231060736627166035424556067924275822790841364471682730227122273460332869588017648530643366833040712003586217660916625928437268396645166811664730441982099086374045324433444570681504093686330283360219246134423320833488332645728291022598467520417244772065348057024398445144435682178847764415444794441320619628516029786015286172661580479006512429720877240396869926637280772627728415882314083562693080198861388095262558081762615466170423982213846190661366619280996487544031824590829988499020136009548631880738865764291684978825388433882190223746077048912025962299222510843502079848990649980637628392269960499244996825164673066574281560231622116085924051062974225322295846314421182235222172223960837864538067148035648316883540217008536267160411620978487768891640116861164235446932049586879040374483944075686554043186835288310269746639428370883988837640778241522093462570467744277060398007524893440194485182673842714465944299446370669128011024736065786677666530429506017424770827740891864976687780277622778465382819088512643580693866338045762053086712665966675428932263346695666316669780491482594081324095824938449520631004598681380233860714241184473820338483382695228796027548417020912249722015848552029348495644930687128897264910449744491820114623566079286510281122611080974001562479220372245346819426132285722677228910887364033062198085148811888590267508031262110461120473482718841140611866114285946437044536829540879488994025186059048136885788815264796689928875888938887140273246572043962075462794227560893002574843940699480132623342219460994249946875664178061524231060736627166035424556067924275822790841364471682730227122273460332869588017648530643366833040712003586217660916625928437268396645166811664730441982

无心人

我想到了反推
可是我去反3044去了
哎

mathe

有点奇怪，怎么会这么大的周期。
其实就是模10的递归数列$a(n+4)=a(n+3)+a(n+2)+a(n+1)+a(n)$
我们只要分别讨论这个数列模2和模5的两种情况就可以了
模2的情况很简单，就是1 1 0 0 0 1 1 0 0 0 1 1...所以周期为5.
而模5的情况要复杂一些，我们需要看5阶域$F_5$上的方程$x^4-x^3-x^2-x-1=0$的所有根。
这里主要需要先判断方程在$F_5$上否可以因子分解。
可以因子分解和不可以因子分解两种情况不同

kenmark

可是决定下一个需要四个前项，所以想到将四个合成一个四位数，根据四位数有穷个和正反变换的唯一性证明循环

无心人

因为本质上这个序列是个四维的
理论最大周期是10000

目前无法推测具体的序列循环中数据的共性

无心人

汗， 1111的周期也是1560

mathe

判断了一下，好像是不可约多项式。也就是说这个方程的四个根生成一个$5^4$阶域$F_{5^4}$
所以对于4个根$x_1,x_2,x_3,x_4$它们的幂都是$5^4-1=624$.
于是递归序列模5的通项公式可以写成$a_1x_1^n+a_2x_2^n+a_3x_3^n+a_4x_4^n$
显然624是递推序列模5的周期，而由于5是模2的周期，我们得到624*5=3120是序列的一个周期。而最小周期必然是3120的一个因子

kenmark

1111不属于1982序列，是另一个里的，难道每个循环序列周期都是1560？题目又升级了