cp's OEIS Frontend

A046073 Number of squares in multiplicative group modulo n.

%I A046073 #71 Feb 16 2025 08:32:38
%S A046073 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,
%T A046073 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,
%U A046073 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
%N A046073 Number of squares in multiplicative group modulo n.
%C A046073 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
%C A046073 The number of quadratic residues modulo n that are coprime to n. These residues are listed in A096103. - _Peter Munn_, Mar 10 2021
%D A046073 Daniel Shanks, Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 95, 1993.
%H A046073 Antti Karttunen, <a href="/A046073/b046073.txt">Table of n, a(n) for n = 1..16384</a>
%H A046073 Steven R. Finch and Pascal Sebah, <a href="https://arxiv.org/abs/math/0604465">Square and Cubes Modulo n</a>, arXiv:math/0604465 [math.NT], 2006-2016.
%H A046073 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ModuloMultiplicationGroup.html">Modulo Multiplication Group</a>.
%H A046073 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/QuadraticResidue.html">Quadratic Residue</a>.
%F A046073 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
%F A046073 Multiplicative with a(2^e) = 2^max(e-3,0), a(p^e) = (p-1)*p^(e-1)/2 for p an odd prime.
%F A046073 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
%p A046073 F:= n -> nops({seq}(`if`(igcd(t,n)=1,t^2 mod n,NULL), t=1..floor(n/2))):
%p A046073 1, seq(F(n), n=2..100); # _Robert Israel_, Jan 04 2015
%p A046073 # 2nd program
%p A046073 A046073 := proc(n)
%p A046073     local a,p,e,pf;
%p A046073     a := 1;
%p A046073     for pf in ifactors(n)[2] do
%p A046073         p := op(1,pf) ;
%p A046073         e := op(2,pf) ;
%p A046073         if p = 2 then
%p A046073             a := a*p^max(e-3,0) ;
%p A046073         else
%p A046073             a := a*(p-1)/2*p^(e-1) ;
%p A046073         end if;
%p A046073     end do:
%p A046073     a ;
%p A046073 end proc: # _R. J. Mathar_, Oct 03 2016
%t A046073 Table[EulerPhi[n]/Sum[Boole[Mod[k^2, n] == 1] + Boole[n == 1], {k, n}], {n, 86}] (* or *)
%t A046073 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 *)
%o A046073 (PARI)
%o A046073 A060594(n) = if(n<=2, 1, 2^#znstar(n)[3]); \\ This function from _Joerg Arndt_, Jan 06 2015
%o A046073 A046073(n) = eulerphi(n)/A060594(n); \\ _Antti Karttunen_, Jul 17 2017, after Sharon Sela's Mar 09 2002 formula.
%o A046073 (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
%o A046073 (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.
%o A046073 (Python)
%o A046073 from sympy import factorint, prod
%o A046073 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()])
%o A046073 print([a(n) for n in range(1, 51)]) # _Indranil Ghosh_, Jul 17 2017
%Y A046073 Cf. A046072, A007735, A060594, A000010, A087692, A000224.
%Y A046073 Row lengths of A096103.
%Y A046073 Positions of ones: A018253.
%K A046073 nonn,easy,mult
%O A046073 1,5
%A A046073 _Eric W. Weisstein_
%E A046073 Edited and verified by _Franklin T. Adams-Watters_, Nov 07 2006