[seqfan] Formula cleanup? Solutions of a modulo difference equation

Ron Hardin rhhardin at att.net
Mon Nov 15 20:48:40 CET 2010

Take a nXk binary array, and let s(i,j) be the sum modulo 2 of the neighbors of 
element i,j.

How many solutions are there with s(i,j) never equal to any neighbor's s()?

The number of solutions always comes out a power of two.  Perhaps it can be 
of as the number of bits that can be set independently.  Not arbitrarily chosen 
however, but bits somewhere.

So let T(n,k) be the log base 2 of the number of solutions, ie the number of 
independent bits.

It comes out (tabl by antidiagonal)

with larger antidiagonal table

(The series is labelled A500074 in my work-in-progress accumulation
awaiting the b-file feature of wiki)

After a day of numerology, the following formula matches all the values
(5580 of them accumulated)

Empirical: Let x=gcd(k+1,2^k).
T(n,k)=gcd(n+1,k+1) for k or n even;
T(n,k)=gcd(n+1,k+1)-1 for k and n odd with (n+1-x) modulo (2x) = 0;
T(n,k)=gcd(n+1,k+1) otherwise.

Is there a cleanup of the formula, or an explanation that occurs to anyone?

(the x=gcd(k+1,2^k) is to pick out all the powers of two in k+1)

 rhhardin at mindspring.com
rhhardin at att.net (either)

More information about the SeqFan mailing list