Description of the mathematics, and the Python solver, are at John Cook's blog post.

The main substantive difference from Cook's Python script is that factoring is built in to the main program. Also, I have removed the simplified formulas that apply when exponent is less than three. The code seems clearer using fewer formulas.

```NB. Calculates the number of distinct squares modulo n
NB. as defined by Stangl. Translated from Python written
NB. by John D. Cook implementing Stangl's solution. See
NB. http://www.johndcook.com/blog/2008/11/19/how-many-numbers-are-squares-mod-m/
NB. (Uses algebraic simplification suggested by Nemo J. Publius.)
NB. Cook cites W. D. Stangl,
NB. “Counting Squares in Z_n”, Mathematics Magazine,
NB. pp. 285-289, Vol. 69 No. 4 October 1996.

squares=: */ @: s @: factor

oPoX=: (1+ +: + ]^(exp+1:)) % 2+ +:
oPeX=: (2+  ] + ]^(exp+1:)) % 2+ +:
ePoX=:  3%~  5+ 2^(exp-1:)
ePeX=:  3%~  4+ 2^(exp-1:)

PXf=: 2 2 \$ ePeX`ePoX`oPeX`oPoX
NB. even(e) and odd(o) combinations of P and X

s=: verb define "1
'P X'=: y
exp=: X"_
<. (PXf {~ <  (2|P),(2|X))`:6 P
)

factor=: [: |: [:(~. ,: +/"1@:=) q:

testSquares=: verb define
assert   3 = squares    5   NB. ^/ 5 1
assert  11 = squares   25   NB. ^/ 5 2
assert  53 = squares  125   NB. ^/ 5 3
assert 261 = squares  625   NB. ^/ 5 4
assert   3 = squares    8   NB. ^/ 2 3
assert   4 = squares   16   NB. ^/ 2 4
assert 159 = squares 1000   NB. */ 2 5 ^3
)
NB. Test arguments broken out in notes for easier correlation with original.```

TracyHarms/SquaresModuloN (last edited 2010-04-21 17:21:27 by TracyHarms)