A048153 - OEIS

%I #58 Jun 29 2026 18:20:36

%S 0,1,2,2,10,13,14,12,24,45,44,38,78,77,70,56,136,129,152,130,182,209,

%T 184,148,250,325,288,294,406,365,372,304,484,561,490,402,666,665,572,

%U 540,820,805,860,726,840,897,846,680,980,1125,1156,1170,1378,1305,1210

%N a(n) = Sum_{k=1..n} (k^2 mod n).

%C See A048152 for the array T[n,k] = k^2 mod n.

%C Starting with a(2)=1 each 4th term is odd: a(n=2+4*k) = 1, 13, 45, 77, 129, 209, 325, 365, ... - _Zak Seidov_, Apr 22 2009

%C Positions of squares in A048153: 1, 2, 33, 51, 69, 105, 195, 250, 294, 1250, 4913, 9583, 13778, 48778, 65603, 83521.

%C Corresponding values of squares are: {0, 1, 22, 34, 46, 70, 130, 175, 203, 875, 3468, 6734, 9711, 34481, 46308, 58956}^2 = {0, 1, 484, 1156, 2116, 4900, 16900, 30625, 41209, 765625, 12027024, 45346756, 94303521, 1188939361, 2144430864, 3475809936}. - _Zak Seidov_, Nov 02 2011

%C For n > 1 also row sums of A060036. - _Reinhard Zumkeller_, Apr 29 2013

%C Conjecture: a(n) <= (n^2-1)/2. - _Aspen A.M. Meissner_, Mar 06 2025

%C The above conjecture is true; see the closed form in the Formula section, which gives the stronger bound a(n) <= n*(n-1)/2. - _Ondrej Kutal_, Jun 23 2026

%H Zak Seidov, <a href="/A048153/b048153.txt">Table of n, a(n) for n = 1..10000</a>

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/4654032">Conjecture: Sum_{i=1..n-1} floor(i^2/n) >= (n-1)*(n-2)/3</a>.

%F a(n) == n*(n+1)*(2n+1)/6 (mod n). - _Charles R Greathouse IV_, Dec 28 2011

%F a(n) == n*(n-1)*(2n-1)/6 (mod n). - _Chai Wah Wu_, Jun 02 2024

%F a(n) mod n = A215573(n). - _Alois P. Heinz_, Jun 03 2024

%F a(n) = n*(n-m)/2 - 2*n*Sum_{D<0, D==0 or 1 (mod 4), -D|n} h(D)/w(D), where m = A000188(n) is the largest integer with m^2|n, h(D) is the class number of the quadratic order of discriminant D (the form class number; cf. A000003), and w(D) is its number of units (w(-3)=6, w(-4)=4, otherwise w(D)=2). - _Ondrej Kutal_, Jun 23 2026

%e a(5) = 1^2 + 2^2 + (3^2 mod 5) + (4^2 mod 5) + (5^2 mod 5) = 1 + 4 + 4 + 1 + 0 = 10. (It is easily seen that the last term, n^2 mod n, is always zero and would not need to be included.) - _M. F. Hasler_, Oct 21 2013

%t Table[Sum[PowerMod[k,2,n], {k,n-1}], {n,1,10000}] (* _Zak Seidov_, Nov 02 2011 *)

%o (Haskell)

%o a048153 = sum . a048152_row  -- _Reinhard Zumkeller_, Apr 29 2013

%o (PARI) a(n)=sum(k=1,n,k^2%n) \\ _Charles R Greathouse IV_, Oct 21 2013

%o (Python)

%o def A048153(n): return sum(k**2%n for k in range(1,n)) # _Chai Wah Wu_, Jun 02 2024

%o (PARI) a(n) = my(m=sqrtint(n\core(n))); n*(n-m)/2 - 2*n*sumdiv(n, d, my(D=-d, w=if(d==3,6,if(d==4,4,2))); if(D%4==0||D%4==1, qfbclassno(D)/w, 0)); \\ _Ondrej Kutal_, Jun 23 2026

%Y Cf. A000330, A048152, A215573, A000003, A000188.

%K nonn

%O 1,3

%A _Clark Kimberling_

%E Definition made more explicit by _M. F. Hasler_, Oct 21 2013