# [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
thought
of as the number of bits that can be set independently.  Not arbitrarily chosen
bits,
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)
1,1,1,2,3,2,1,1,1,1,1,1,3,1,1,1,3,1,1,3,1,2,1,2,5,2,1,2,1,1,1,1,1,1,1,1,
1,3,4,1,5,1,4,3,1,1,1,1,1,1,1,1,1,1,1,2,1,2,1,2,7,2,1,2,1,2,1,3,1,5,3,1,
1,3,5,1,3,1,1,1,3,1,1,1,7,1,1,1,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,2...

with larger antidiagonal table
http://rhhardin.home.mindspring.com/temp.txt

(The series is labelled A500074 in my work-in-progress accumulation
http://rhhardin.home.mindspring.com/working.txt
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)

```