A300268 Number of solutions to 1 +- 4 +- 9 +- ... +- n^2 == 0 (mod n).

1, 0, 2, 4, 6, 0, 10, 48, 32, 0, 94, 344, 370, 0, 1268, 4608, 3856, 0, 13798, 55960, 50090, 0, 182362, 721952, 690496, 0, 2485592, 9586984, 9256746, 0, 34636834, 135335936, 130150588, 0, 493452348, 1908875264, 1857293524, 0, 7049188508, 27603824928

Offset: 1

Author

Seiichi Manyama, Mar 01 2018

Keywords

• nonn

Examples

			Solutions for n = 7:
-------------------------------
1 +4 +9 +16 +25 +36 +49 =  140.
1 +4 +9 +16 +25 +36 -49 =   42.
1 +4 +9 -16 -25 -36 +49 =  -14.
1 +4 [phone] = -112.
1 +4 -9 +16 -25 -36 +49 =    0.
1 +4 -9 [phone] =  -98.
1 -4 +9 -16 +25 -36 +49 =   28.
1 -4 +9 -16 +25 -36 -49 =  -70.
1 -4 -9 +16 +25 -36 +49 =   42.
1 -4 -9 +16 +25 -36 -49 =  -56.
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..3334 (terms 1..1000 from Alois P. Heinz)

Crossrefs

Number of solutions to 1 +- 2^k +- 3^k +- ... +- n^k == 0 (mod n): A300190 (k=1), this sequence (k=2), A300269 (k=3).

Cf. A083527, A215573.

Programs

Maple

b:= proc(n, i, m) option remember; `if`(i=0, `if`(n=0, 1, 0),
      add(b(irem(n+j, m), i-1, m), j=[i^2, m-i^2]))
    end:
a:= n-> b(0, n-1, n):
seq(a(n), n=1..60);  # Alois P. Heinz, Mar 01 2018

Mathematica

b[n_, i_, m_] := b[n, i, m] = If[i == 0, If[n == 0, 1, 0],
     Sum[b[Mod[n + j, m], i - 1, m], {j, {i^2, m - i^2}}]];
a[n_] := b[0, n - 1, n];
Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Mar 19 2022, after Alois P. Heinz *)

PARI

a(n) = my (v=vector(n,k,k==1)); for (i=2, n, v = vector(n, k, v[1 + (k-i^2)%n] + v[1 + (k+i^2)%n])); v[1] \\ Rémy Sigrist, Mar 01 2018

Ruby

def A(n)
  ary = [1] + Array.new(n - 1, 0)
  (1..n).each{|i|
    i2 = 2 * i * i
    a = ary.clone
    (0..n - 1).each{|j| a[(j + i2) % n] += ary[j]}
    ary = a
  }
  ary[(n * (n + 1) * (2 * n + 1) / 6) % n] / 2
end
def A300268(n)
  (1..n).map{|i| A(i)}
end
p A300268(100)