The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A060594 Number of solutions to x^2 == 1 (mod n), that is, square roots of unity modulo n. 53
 1, 1, 2, 2, 2, 2, 2, 4, 2, 2, 2, 4, 2, 2, 4, 4, 2, 2, 2, 4, 4, 2, 2, 8, 2, 2, 2, 4, 2, 4, 2, 4, 4, 2, 4, 4, 2, 2, 4, 8, 2, 4, 2, 4, 4, 2, 2, 8, 2, 2, 4, 4, 2, 2, 4, 8, 4, 2, 2, 8, 2, 2, 4, 4, 4, 4, 2, 4, 4, 4, 2, 8, 2, 2, 4, 4, 4, 4, 2, 8, 2, 2, 2, 8, 4, 2, 4, 8, 2, 4, 4, 4, 4, 2, 4, 8, 2, 2, 4, 4, 2, 4, 2 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS Sum_{k=1..n} a(k) appears to be asymptotic to C*n*log(n) with C = 0.6... - Benoit Cloitre, Aug 19 2002 a(q) is the number of real characters modulo q. - Benoit Cloitre, Feb 02 2003 Also number of real Dirichlet characters modulo n and Sum_{k=1..n}a(k) is asymptotic to (6/Pi^2)*n*log(n). - Steven Finch, Feb 16 2006 Let P(n) be the product of the numbers less than and coprime to n. By theorem 59 in Nagell (which is Gauss's generalization of Wilson's theorem): for n > 2, P == (-1)^(a(n)/2) (mod n). - T. D. Noe, May 22 2009 Shadow transform of A005563. - Michel Marcus, Jun 06 2013 For n > 2, a(n) = 2 iff n is in A033948. - Max Alekseyev, Jan 07 2015 For n > 1, number of square numbers on the main diagonal of an (n-1) X (n-1) square array whose elements are the numbers from 1..n^2, listed in increasing order by rows. - Wesley Ivan Hurt, May 19 2021 REFERENCES Trygve Nagell, Introduction to Number Theory, AMS Chelsea, 1981, p. 100. [From T. D. Noe, May 22 2009] Gérald Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, Cours spécialisé, 1995, Collection SMF, p. 260. J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, pp. 196-197. LINKS T. D. Noe, Table of n, a(n) for n = 1..1000 Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016. Keith Matthews, Solving the congruence x^2=a(mod m). Emilia Mezzetti and Rosa Maria Miró-Roig, Togliatti systems and Galois coverings, arXiv preprint arXiv:1611.05620 [math.AG], 2016-2018. See Lemma 6.1. John S. Rutherford, Sublattice enumeration. IV. Equivalence classes of plane sublattices by parent Patterson symmetry and colour lattice group type, Acta Cryst. (2009). A65, 156-163. [See Table 4]. N. J. A. Sloane, Transforms. László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6. FORMULA If n == 0 (mod 8), a(n) = 2^(A005087(n) + 2); if n == 4 (mod 8), a(n) = 2^(A005087(n) + 1); otherwise a(n) = 2^(A005087(n)). - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 29 2001 a(n) = 2^omega(n)/2 if n == +/-2 (mod 8), a(n) = 2^omega(n) if n== +/-1, +/-3, 4 (mod 8), a(n) = 2*2^omega(n) if n == 0 (mod 8), where omega(n) = A001221(n). - Benoit Cloitre, Feb 02 2003 For n >= 2 A046073(n) * a(n) = A000010(n) = phi(n). This gives a formula for A046073(n) using the one in A060594(n). - Sharon Sela (sharonsela(AT)hotmail.com), Mar 09 2002 Multiplicative with a(2) = 1; a(2^2) = 2; a(2^e) = 4 for e > 2; a(q^e) = 2 for q an odd prime. - Eric M. Schmidt, Jul 09 2013 a(n) = 2^A046072(n) for n>2, in accordance with the above formulas by Ahmed Fares. - Geoffrey Critzer, Jan 05 2015 a(n) = Sum_{k=1..n} floor(sqrt(1+n*(k-1)))-floor(sqrt(n*(k-1))). - Wesley Ivan Hurt, May 19 2021 From Amiram Eldar, Dec 30 2022: (Start) Dirichlet g.f.: (1-1/2^s+2/4^s)*zeta(s)^2/zeta(2*s). Sum_{k=1..n} a(k) ~ (6/Pi^2)*n*(log(n) + 2*gamma - 1 - log(2)/2 - 2*zeta'(2)/zeta(2)), where gamma is Euler's constant (A001620). (End) EXAMPLE The four numbers 1^2, 3^2, 5^2 and 7^2 are congruent to 1 modulo 8, so a(8) = 4. MAPLE A060594 := proc(n) option remember; local a, b, c; if type(n, even) then a:= padic:-ordp(n, 2); b:= 2^a; c:= n/b; min(b/2, 4) * procname(c) else 2^nops(numtheory:-factorset(n)) fi end proc: map(A060594, [\$1 .. 100]); # Robert Israel, Jan 05 2015 MATHEMATICA a[n_] := Sum[ Boole[ Mod[k^2 , n] == 1], {k, 1, n}]; a[1] = 1; Table[a[n], {n, 1, 103}] (* Jean-François Alcover, Oct 21 2011 *) a[n_] := Switch[Mod[n, 8], 2|6, 2^(PrimeNu[n]-1), 1|3|4|5|7, 2^PrimeNu[n], 0, 2^(PrimeNu[n]+1)]; Array[a, 103] (* Jean-François Alcover, Apr 09 2016 *) PROG (PARI) a(n)=sum(i=1, n, if((i^2-1)%n, 0, 1)) (PARI) a(n)=my(o=valuation(n, 2)); 2^(omega(n>>o)+max(min(o-1, 2), 0)) \\ Charles R Greathouse IV, Jun 06 2013 (PARI) a(n)=if(n<=2, 1, 2^#znstar(n)[3] ); \\ Joerg Arndt, Jan 06 2015 (Sage) print([len(Integers(n).square_roots_of_one()) for n in range(1, 100)]) # Ralf Stephan, Mar 30 2014 (Python) from sympy import primefactors def a007814(n): return 1 + bin(n - 1).count('1') - bin(n).count('1') def a(n): if n%2==0: A=a007814(n) b=2**A c=n//b return min(b//2, 4)*a(c) else: return 2**len(primefactors(n)) print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jul 18 2017, after the Maple program (Python) from sympy import primefactors def A060594(n): return (1<>(s:=(~n & n-1).bit_length()))))*(1 if n&1 else 1<

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified March 28 03:48 EDT 2023. Contains 361577 sequences. (Running on oeis4.)