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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A046073 Number of squares in multiplicative group modulo n. 23
 1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 5, 1, 6, 3, 2, 2, 8, 3, 9, 2, 3, 5, 11, 1, 10, 6, 9, 3, 14, 2, 15, 4, 5, 8, 6, 3, 18, 9, 6, 2, 20, 3, 21, 5, 6, 11, 23, 2, 21, 10, 8, 6, 26, 9, 10, 3, 9, 14, 29, 2, 30, 15, 9, 8, 12, 5, 33, 8, 11, 6, 35, 3, 36, 18, 10, 9, 15, 6, 39, 4, 27, 20, 41, 3, 16, 21 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,5 COMMENTS a(n) is the number of different diagonal elements in Cayley table for multiplicative group modulo n. But the fact that the same number of different elements are on the diagonal of the Cayley table does not mean in every case that these groups are isomorphic. - Artur Jasinski, Jul 03 2010 The number of quadratic residues modulo n that are coprime to n. These residues are listed in A096103. - Peter Munn, Mar 10 2021 REFERENCES Daniel Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 95, 1993. LINKS Antti Karttunen, Table of n, a(n) for n = 1..16384 Steven R. Finch and Pascal Sebah, Square and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016. Eric Weisstein's World of Mathematics, Modulo Multiplication Group. Eric Weisstein's World of Mathematics, Quadratic Residue. FORMULA a(n) * A060594(n) = A000010(n) = phi(n) (This gives a formula for a(n) using the one in A060594(n) ). - Sharon Sela (sharonsela(AT)hotmail.com), Mar 09 2002 Multiplicative with a(2^e) = 2^max(e-3,0), a(p^e) = (p-1)*p^(e-1)/2 for p an odd prime. Sum_{k=1..n} a(k) ~ c * n^2/sqrt(log(n)), where c = (43/(80*sqrt(Pi))) * Product_{p prime} (1+1/(2*p))*sqrt(1-1/p) = 0.24627260085060864229... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022 MAPLE F:= n -> nops({seq}(`if`(igcd(t, n)=1, t^2 mod n, NULL), t=1..floor(n/2))): 1, seq(F(n), n=2..100); # Robert Israel, Jan 04 2015 # 2nd program A046073 := proc(n) local a, p, e, pf; a := 1; for pf in ifactors(n)[2] do p := op(1, pf) ; e := op(2, pf) ; if p = 2 then a := a*p^max(e-3, 0) ; else a := a*(p-1)/2*p^(e-1) ; end if; end do: a ; end proc: # R. J. Mathar, Oct 03 2016 MATHEMATICA Table[EulerPhi[n]/Sum[Boole[Mod[k^2, n] == 1] + Boole[n == 1], {k, n}], {n, 86}] (* or *) Table[Apply[Times, FactorInteger[n] /. {p_, e_} /; p > 0 :> Which[p == 1, 1, p == 2, 2^Max[e - 3, 0], True, (p - 1) p^(e - 1)/2]], {n, 86}] (* Michael De Vlieger, Jul 18 2017 *) PROG (PARI) A060594(n) = if(n<=2, 1, 2^#znstar(n)[3]); \\ This function from Joerg Arndt, Jan 06 2015 A046073(n) = eulerphi(n)/A060594(n); \\ Antti Karttunen, Jul 17 2017, after Sharon Sela's Mar 09 2002 formula. (PARI) A046073(n)=if(n>4, (n=znstar(n))[1]>>#n[3], 1) \\ Avoids duplicate computation of phi(n). - M. F. Hasler, Nov 27 2017, typo fixed Mar 11 2021 (Scheme) (define (A046073 n) (cond ((= 1 n) n) ((even? n) (* (A000079 (max (- (A007814 n) 3) 0)) (A046073 (A028234 n)))) (else (* (/ 1 2) (- (A020639 n) 1) (/ (A028233 n) (A020639 n)) (A046073 (A028234 n)))))) ;; Antti Karttunen, Jul 17 2017, after the given multiplicative formula. (Python) from sympy import factorint, prod def a(n): return 1 if n==1 else prod([2**max(e - 3, 0) if p==2 else (p - 1)*p**(e - 1)//2 for p, e in factorint(n).items()]) print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 17 2017 CROSSREFS Cf. A046072, A007735, A060594, A000010, A087692, A000224. Row lengths of A096103. Positions of ones: A018253. Sequence in context: A309155 A007735 A002616 * A309786 A162912 A230070 Adjacent sequences: A046070 A046071 A046072 * A046074 A046075 A046076 KEYWORD nonn,easy,mult AUTHOR Eric W. Weisstein EXTENSIONS Edited and verified by Franklin T. Adams-Watters, Nov 07 2006 STATUS approved

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 2 08:00 EST 2024. Contains 370461 sequences. (Running on oeis4.)