|
|
A000224
|
|
Number of squares mod n.
|
|
53
|
|
|
1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, 4, 9, 8, 10, 6, 8, 12, 12, 6, 11, 14, 11, 8, 15, 12, 16, 7, 12, 18, 12, 8, 19, 20, 14, 9, 21, 16, 22, 12, 12, 24, 24, 8, 22, 22, 18, 14, 27, 22, 18, 12, 20, 30, 30, 12, 31, 32, 16, 12, 21, 24, 34, 18, 24, 24, 36, 12
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
Multiplicative with a(p^e) = floor(p^e/6) + 2 if p = 2; floor(p^(e+1)/(2p + 2)) + 1 if p > 2. - David W. Wilson, Aug 01 2001
Sum_{k=1..n} a(k) ~ c * n^2/sqrt(log(n)), where c = (17/(32*sqrt(Pi))) * Product_{p prime} (1 - (p^2+2)/(2*(p^2+1)*(p+1))) * (1-1/p)^(-1/2) = 0.37672933209687137604... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022
|
|
EXAMPLE
|
The sequence of squares (A000290) modulo 10 reads 0, 1, 4, 9, 6, 5, 6, 9, 4, 1, 0, 1, 4, 9, 6, 5, 6, 9, 4, 1,... and this reduced sequence contains a(10) = 6 different values, {0,1,4,5,6,9}. - R. J. Mathar, Oct 10 2014
|
|
MAPLE
|
{seq( modp(b^2, m), b=0..m-1) };
nops(%) ;
# 2nd implementation
local a, ifs, f, p, e, c ;
a := 1 ;
ifs := ifactors(n)[2] ;
for f in ifs do
p := op(1, f) ;
e := op(2, f) ;
if p = 2 then
if type(e, 'odd') then
a := a*(2^(e-1)+5)/3 ;
else
a := a*(2^(e-1)+4)/3 ;
end if;
else
if type(e, 'odd') then
c := 2*p+1 ;
else
c := p+2 ;
end if;
a := a*(p^(e+1)+c)/2/(p+1) ;
end if;
end do:
a ;
|
|
MATHEMATICA
|
a[2] = 2; a[n_] := a[n] = Switch[fi = FactorInteger[n], {{_, 1}}, (fi[[1, 1]] + 1)/2, {{2, _}}, 3/2 + 2^fi[[1, 2]]/6 + (-1)^(fi[[1, 2]]+1)/6, {{_, _}}, {p, k} = fi[[1]]; 3/4 + (p-1)*(-1)^(k+1)/(4*(p+1)) + p^(k+1)/(2*(p+1)), _, Times @@ Table[ a[Power @@ f], {f, fi}]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Mar 09 2015 *)
|
|
PROG
|
(PARI) a(n) = local(v, i); v = vector(n, i, 0); for(i=0, floor(n/2), v[i^2%n+1] = 1); sum(i=1, n, v[i]) \\ Franklin T. Adams-Watters, Nov 05 2006
(PARI) a(n)=my(f=factor(n)); prod(i=1, #f[, 1], if(f[i, 1]==2, 2^f[1, 2]\6+2, f[i, 1]^(f[i, 2]+1)\(2*f[i, 1]+2)+1)) \\ Charles R Greathouse IV, Jul 15 2011
(Haskell)
a000224 n = product $ zipWith f (a027748_row n) (a124010_row n) where
f 2 e = 2 ^ e `div` 6 + 2
f p e = p ^ (e + 1) `div` (2 * p + 2) + 1
|
|
CROSSREFS
|
Cf. A095972, A046530 (cubic residues), A052273 (4th powers), A052274 (5th powers), A052275 (6th powers), A085310 (7th powers), A085311 (8th powers), A085312 (9th powers), A085313 (10th powers), A085314 (11th powers), A228849 (12th powers).
|
|
KEYWORD
|
nonn,easy,nice,mult
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|