* Warren Smith <warren.wds@gmail.com> [Sep 01. 2012 11:55]:
N=40 det=6.439842994660582748450 e31 circ=-+++---+-++---++-+-+---------++-++--+-++
think I'll quit finding them now.
----
In summary, all 2^N different NxN circulant sign matrices can have their determinants computed in O(N) arithmetic operations per matrix using the fourier trick combined with the gray code trick.
If however we were to generate "binary necklaces" via a "3-gray code" for them, Mark Weston & Vincent Vajnovszki: Gray codes for necklaces and Lyndon words of arbitrary base, Pure Mathematics and Applications 17, 1-2 (2006) 175-182. http://homelinux.capitano.unisi.it/~puma/17_1_2/weston.pdf
T.Ueda: Gray codes for necklaces, Discrete Maths. 219,1-3 (2000) 235-248.
IIRC these are only conjectured to have <=3 changes per update. There are no Gray codes for even n >= 8 (fxtbook p.408). For all (feasible, n<=35) odd n I could find Gray codes (for the necklaces, not bracelets). n==37 would have taken 13 days (and 64GB + eps of RAM), the computation was stopped as the machine died at t_0 + 12.5 days (and I have not had access to a machine with enough RAM since). Given A215723(n) is divisible by 2^(n-1), I created A215897 = A215723(n) / 2^(n-1). Now a power of 2 is neatly handled by the floating point exponent, but with printing I suggest to divide by 2^(n-1). Could you indicate how fast your search is?
T.M.Y. Wang and C.D. Savage: A Gray code for necklaces of fixed density, SIAM J. Discrete Maths 9,4 (1996) 654-673.
then we could effectively compute the determinants of all NxN circulant sign matrices in O(1) arithmetic operations per matrix, which would have enabled me to reach, not N=40, but in fact about N=44, with the same amount of computing. Perhaps somebody will program that refinement.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun