cp's OEIS Frontend

A060839 Number of solutions to x^3 == 1 (mod n).

%I A060839 #47 Aug 10 2023 02:22:29
%S A060839 1,1,1,1,1,1,3,1,3,1,1,1,3,3,1,1,1,3,3,1,3,1,1,1,1,3,3,3,1,1,3,1,1,1,
%T A060839 3,3,3,3,3,1,1,3,3,1,3,1,1,1,3,1,1,3,1,3,1,3,3,1,1,1,3,3,9,1,3,1,3,1,
%U A060839 1,3,1,3,3,3,1,3,3,3,3,1,3,1,1,3,1,3,1,1,1,3,9,1,3,1,3,1,3,3,3,1,1,1,3,3,3
%N A060839 Number of solutions to x^3 == 1 (mod n).
%C A060839 Sum_{k=1..n} a(k) appears to be asymptotic to C*n*log(n) with C = 0.4... - _Benoit Cloitre_, Aug 19 2002 [C = (11/(6*Pi*sqrt(3))) * Product_{p prime == 1 (mod 3)} (1 - 2/(p*(p+1))) = 0.3170565167... (Finch and Sebah, 2006). - _Amiram Eldar_, Mar 26 2021]
%H A060839 T. D. Noe, <a href="/A060839/b060839.txt">Table of n, a(n) for n = 1..1000</a>
%H A060839 Steven Finch, Greg Martin and Pascal Sebah, <a href="https://doi.org/10.1090/S0002-9939-10-10341-4">Roots of unity and nullity modulo n</a>, Proc. Amer. Math. Soc., Vol. 138, No. 8 (2010), pp. 2729-2743.
%H A060839 Steven Finch and Pascal Sebah, <a href="https://arxiv.org/abs/math/0604465">Squares and Cubes Modulo n</a>, arXiv:math/0604465 [math.NT], 2006-2016.
%F A060839 Let b(n) be the number of primes dividing n which are congruent to 1 (mod 3) (sequence A005088); then a(n) is 3^b(n) if n is not divisible by 9 and 3^(b(n) + 1) if n is divisible by 9.
%F A060839 Multiplicative with a(3) = 1, a(3^e) = 3, e >= 2, a(p^e) = 3 for primes p of the form 3k+1, a(p^e) = 1 for primes p of the form 3k+2. - _David W. Wilson_, May 22 2005 [Corrected by _Jianing Song_, Oct 21 2022]
%F A060839 If the multiplicative group of integers modulo n has (Z/nZ)* = C_{k_1} X C_{k_2} X ... X C_{k_r}, then a(n) = Product_{i=1..r} gcd(3,k_r). - _Jianing Song_, Oct 21 2022
%e A060839 a(7) = 3 because the three solutions to x^3 == 1 (mod 7) are x = 1,2,4.
%p A060839 A060839 := proc(n)
%p A060839     local a,pf,p,r;
%p A060839     a := 1 ;
%p A060839     for pf in ifactors(n)[2] do
%p A060839         p := op(1,pf);
%p A060839         r := op(2,pf);
%p A060839         if p = 2 then
%p A060839             ;
%p A060839         elif p =3 then
%p A060839             if r >= 2 then
%p A060839                 a := a*3 ;
%p A060839             end if;
%p A060839         else
%p A060839             if modp(p,3) = 2 then
%p A060839                 ;
%p A060839             else
%p A060839                 a := 3*a ;
%p A060839             end if;
%p A060839         end if;
%p A060839     end do:
%p A060839     a ;
%p A060839 end proc:
%p A060839 seq(A060839(n),n=1..40) ; # _R. J. Mathar_, Mar 02 2015
%t A060839 a[n_] := Sum[ If[ Mod[k^3-1, n] == 0, 1, 0], {k, 1, n}]; Table[ a[n], {n, 1, 105}](* _Jean-François Alcover_, Nov 14 2011, after PARI *)
%t A060839 f[p_, e_] := If[Mod[p, 3] == 1, 3, 1]; f[3, 1] = 1; f[3, e_] := 3; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Aug 10 2023 *)
%o A060839 (PARI) a(n)=sum(i=1,n,if((i^3-1)%n,0,1))
%o A060839 (Python)
%o A060839 from math import prod
%o A060839 from sympy import factorint
%o A060839 def A060839(n): return prod(3 for p, e in factorint(n).items() if (p!=3 or e!=1) and p%3!=2) # _Chai Wah Wu_, Oct 19 2022
%o A060839 (PARI) a(n)=my(f=factor(n)); prod(i=1, #f~, if(f[i, 1]==3, 3^min(f[i, 2]-1, 1), if(f[i, 1]%3==1, 3, 1))) \\ _Jianing Song_, Oct 21 2022
%Y A060839 Cf. A005088, A357905 (base-3 logarithm).
%Y A060839 Number of solutions to x^k == 1 (mod n): A060594 (k=2), this sequence (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), A319101 (k=7), A247257 (k=8).
%Y A060839 Column 3 of A354057.
%K A060839 nonn,nice,easy,mult
%O A060839 1,7
%A A060839 Ahmed Fares (ahmedfares(AT)my-deja.com), May 02 2001