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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A060839 Number of solutions to x^3 == 1 (mod n). 18
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,7
COMMENTS
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]
LINKS
Steven Finch, Greg Martin and Pascal Sebah, Roots of unity and nullity modulo n, Proc. Amer. Math. Soc., Vol. 138, No. 8 (2010), pp. 2729-2743.
Steven Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
FORMULA
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.
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]
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
EXAMPLE
a(7) = 3 because the three solutions to x^3 == 1 (mod 7) are x = 1,2,4.
MAPLE
A060839 := proc(n)
local a, pf, p, r;
a := 1 ;
for pf in ifactors(n)[2] do
p := op(1, pf);
r := op(2, pf);
if p = 2 then
;
elif p =3 then
if r >= 2 then
a := a*3 ;
end if;
else
if modp(p, 3) = 2 then
;
else
a := 3*a ;
end if;
end if;
end do:
a ;
end proc:
seq(A060839(n), n=1..40) ; # R. J. Mathar, Mar 02 2015
MATHEMATICA
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 *)
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 *)
PROG
(PARI) a(n)=sum(i=1, n, if((i^3-1)%n, 0, 1))
(Python)
from math import prod
from sympy import factorint
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
(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
CROSSREFS
Cf. A005088, A357905 (base-3 logarithm).
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).
Column 3 of A354057.
Sequence in context: A370414 A016472 A095346 * A088204 A100375 A353063
KEYWORD
nonn,nice,easy,mult
AUTHOR
Ahmed Fares (ahmedfares(AT)my-deja.com), May 02 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 02:16 EDT 2024. Contains 371264 sequences. (Running on oeis4.)