login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

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. 31
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) = 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

REFERENCES

Trygve Nagell, Introduction to Number Theory, AMS Chelsea, 1981, p. 100. [From T. D. Noe, May 22 2009]

G. Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, Cours spécialisé, 1995, Collection SMF, p. 260.

LINKS

T. D. Noe, Table of n, a(n) for n = 1..1000

S. R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

K. Matthews, Solving the congruence x^2=a(mod m)

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

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

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 map(a, xrange(1, 101)) # Indranil Ghosh, Jul 18 2017, after the Maple program

CROSSREFS

Cf. A000010, A005087, A046073, A073103 (x^4==1 (mod n)).

Sequence in context: A239202 A083533 A076500 * A104361 A211449 A086876

Adjacent sequences:  A060591 A060592 A060593 * A060595 A060596 A060597

KEYWORD

nonn,mult

AUTHOR

Jud McCranie, Apr 11 2001

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified August 18 18:04 EDT 2017. Contains 290732 sequences.