[seqfan] Re: x(i-1) = ( x(i+1) - x(i)) mod M, period-N solutions?

[Ron Hardin]

----- Original Message ----
> From: N. J. A. Sloane <njas at research.att.com>
> To: seqfan at list.seqfan.eu
> Cc: njas at research.att.com
> Sent: Sat, September 4, 2010 12:24:23 PM
> Subject: [seqfan] Re: x(i-1) = ( x(i+1) - x(i)) mod M, period-N solutions?
> 
> Ron, can you submit it in the format
> where you read it by  antidiagonals:
> 0  0 0  0 0 0  0 0 3 0  0 0 0 0 0  0  0 3 ... (I picked one
> of the two directions arbitrarily) please?
> 
> Also  the third column of the table of
> high water marks should be another new  entry.
> 
> If you submit those two, I will format the array  itself,
> 0   0   0   0   0   0   0    0   0   0   0   0   0   0   0   0    0   0   0
> 0   0   0   0   0   0    0   0   0   0   0   0   0   0   0    0   0   0   0
> 0   3   0   3   0    3   0   3   0   3   0   3   0   3    0   3   0   3   0
> 0   0   0   0    4   0   0   0   0   4   0   0   0    0   4   0   0   0   0
> 0   0   0    0   0   0   0   0   0   0  10   0    0   0   0   0   0   0   0
> 0   3    0  15   0   3   0  15   0   3   0   15   0   3   0  15   0   3    0
> ...
> nicely and put it the example lines.
> 
> Thanks!

The program itself is the easiest, goes from 1 to 64261 (N=358,M=1)
that being the first antidiagonal that has a six figure count
(N=36,M=323, count=104328), which would shift the 5-place table.
It runs only a few minutes.

#include <stdio.h>
int x[100000];
unsigned long long count;
go(N,M,INDEX) {
    int i;
    count=0;
    if(N<2||M<2) { count=1; goto xx; }
    for(x[0]=0; x[0]<M; x[0]++) {
        for(x[1]=0; x[1]<M; x[1]++) {
            for(i=2; i<N+2; i++)x[i]=(x[i-1]+x[i-2])%M;
            if(x[N]==x[0]&&x[N+1]==x[1])count++;
        }
    }
    xx:;
    printf("%d %llu\n",INDEX,count-1); fflush(stdout);
}

main()
{
    int index,n,m;
    n=1; m=1;
    for(index=1;index<=64261;index++) {
        go(n,m,index);
        n=n+1;
        m=m-1;
        if(m==0) { m=n; n=1; }
        if(n+2>=sizeof x/sizeof*x)exit(0);
    }
}