A060839 -id:A060839 - cp's OEIS frontend

A357905 a(n) = log_3(A060839(n)).

0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 2, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1

Offset: 1

Jianing Song, Oct 19 2022

3-rank of the multiplicative group of integers modulo n.

			a(63) = 2 since (Z/63Z)* = C_6 X C_6 has 3-rank 2.

Jianing Song, Table of n, a(n) for n = 1..10000

Cf. A060839, A072273, A357906.

f[p_, e_] := If[Mod[p, 3] == 1, 1, 0]; f[3, e_] := 1; f[3, 1] = 0; a[1] = 0; a[n_] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Oct 05 2023 *)

a(n)=my(f=factor(n)); sum(i=1, #f~, if(f[i, 1]==3, min(f[i, 2]-1, 1), if(f[i, 1]%3==1, 1, 0)))

from sympy import factorint
def A357905(n): return sum(1 for p, e in factorint(n).items() if (p!=3 or e!=1) and p%3!=2) # Chai Wah Wu, Oct 19 2022

Additive with a(3) = 0, a(3^e) = 1, e >= 2; a(p^e) = 1 for p == 1 (mod 3), 0 for p == 2 (mod 3).

A160498 Number of cubic primitive Dirichlet characters modulo n.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 4, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 0

Offset: 1

Steven Finch, May 15 2009

Also called primitive Dirichlet characters of order 3.
Mobius transform of A060839.
C. David, J. Fearnley & H. Kisilevsky prove that Sum_{k=1..n} a(k) ~ C*n, with C = (11*sqrt(3)/(18*Pi)) * Product_{primes p == 1 (mod 3)} (1 - 2/(p*(p+1))) = 0.3170565167922841205670156...; they credit Cohen, F. Diaz y Diaz, & M. Olivier 2002 (see Proposition 5.2. and Corollary 5.3.). - Charles R Greathouse IV, Aug 26 2009 [corrected by Vaclav Kotesovec, Sep 16 2020]
a(n) is the number of primitive Dirichlet characters modulo n such that all entries are 0 or a cubic root of unity: 1, w = (-1 + sqrt(3)*i)/2 or w^2 = (-1 - sqrt(3)*i)/2. - Jianing Song, Feb 27 2019
Every term is 0 or a power of 2. - Jianing Song, Mar 02 2019
From Jianing Song, Apr 03 2021: (Start)
For n >= 2, a(n) is the number of cyclic cubic fields with discriminant n^2. See A343023 for detailed information.
The first occurrence of 2^t is 9*A121940(t-1) for t >= 2. (End)

			From _Jianing Song_, Mar 02 2019: (Start)
Let w = (-1 + sqrt(3)*i)/2 be one of the primitive 3rd root of unity.
For n = 7, the 2 cubic primitive Dirichlet characters modulo n are [0, 1, w, w^2, w^2, w, 1] and [0, 1, w^2, w, w, w^2, 1], so a(7) = 2.
For n = 9, the 2 cubic primitive Dirichlet characters modulo n are [0, 1, w, 0, w^2, w^2, 0, w, 1] and [0, 1, w^2, 0, w, w, 0, w^2, 1], so a(9) = 2. (End)

Jianing Song, Table of n, a(n) for n = 1..10000
C. David, J. Fearnley and H. Kisilevsky,On the vanishing of twisted L-functions of elliptic curves, Experim. Math. 13 (2004) 185-198.
Steven R. Finch, Cubic and quartic characters.
Steven R. Finch, Cubic and quartic characters.
Steven R. Finch, Quartic and Octic Characters Modulo n, arXiv:0907.4894 [math.NT], 2016.
Vaclav Kotesovec, Plot of Sum_{k=1..n} a(k) / n for n = 1..10000000

Cf. A114643 (number of quadratic primitive Dirichlet characters modulo n), A160499 (number of quartic primitive Dirichlet characters modulo n).
Cf. A060839 (number of solutions to x^3 == 1 (mod n)).
Cf. A121940, A343023.

A060839[n_] := Sum[If[Mod[k^3 - 1, n] == 0, 1, 0], {k, 1, n}]; a[n_] := Sum[ MoebiusMu[n/d]*A060839[d], {d, Divisors[n]}]; Table[a[n], {n, 2, 81}] (* Jean-François Alcover, Jun 19 2013 *)
f[3, 2] = 2; f[p_, e_] := If[Mod[p, 3] == 1 && e == 1, 2, 0]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 16 2020 *)

a(n)=sum(d=1, n, if(n%d==0, moebius(n/d)*sum(i=1, d, if((i^3-1)%d, 0, 1)), 0)) \\ Steven Finch, Jun 09 2009

A005088(n)=my(f=factor(n)[,1]); sum(i=1,#f,f[i]%3==1)
A060839(n)=3^((n%9==0)+A005088(n))
a(n)=sumdiv(n,d,moebius(n/d)*A060839(d)) \\ Charles R Greathouse IV, Aug 26 2009

a(n) = my(L=factor(n), w=omega(n)); for(i=1, w, if(!((L[i, 1]%3==1 && L[i, 2]==1) || L[i, 1]^L[i, 2] == 9), return(0))); 2^w \\ Jianing Song, Apr 03 2021

Multiplicative with a(p^e) = 2 if p^e = 9 or p == 1 (mod 3) and e = 1, otherwise 0. - Jianing Song, Mar 02 2019

a(n) = 2*A343023(n) for n >= 2. - Jianing Song, Apr 03 2021

a(1) = 1 prepended by Jianing Song, Feb 27 2019

A073103 Number of solutions to x^4 == 1 (mod n).

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 2, 4, 2, 4, 2, 4, 4, 2, 8, 8, 4, 2, 2, 8, 4, 2, 2, 8, 4, 4, 2, 4, 4, 8, 2, 8, 4, 4, 8, 4, 4, 2, 8, 16, 4, 4, 2, 4, 8, 2, 2, 16, 2, 4, 8, 8, 4, 2, 8, 8, 4, 4, 2, 16, 4, 2, 4, 8, 16, 4, 2, 8, 4, 8, 2, 8, 4, 4, 8, 4, 4, 8, 2, 32, 2, 4, 2, 8, 16, 2, 8, 8, 4, 8, 8, 4, 4, 2, 8, 16, 4, 2, 4, 8

Offset: 1

Benoit Cloitre, Aug 19 2002

a(n) = 2*A060594(n) for n = 5, 10, 13, 15, 16, 17, 20, 25, 26, 29, .... This subsequence, which contains all the primes of form 4k+1, seems to be asymptotic to 2n.

Shadow transform of A123865. - Michel Marcus, Jun 06 2013

T. D. Noe, Table of n, a(n) for n = 1..1000
Steven R. Finch, Quartic and Octic Characters Modulo n, arXiv:0907.4894 [math.NT], 2009.
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.
Lorenz Halbeisen and Norbert Hungerbühler, Number theoretic aspects of a combinatorial function, Notes on Number Theory and Discrete Mathematics 5(4) (1999), 138-150. (ps, pdf); see Definition 7 for the shadow transform.
Lorenz Halbeisen and Norbert Hungerbühler, Number theoretic aspects of a combinatorial function, Notes on Number Theory and Discrete Mathematics 5(4) (1999), 138-150; see Definition 7 for the shadow transform.
N. J. A. Sloane, Transforms.

Cf. A060594, A060839.

a:= n-> add(`if`(irem(j^4-1, n)=0, 1, 0), j=0..n-1):
seq(a(n), n=1..120);  # Alois P. Heinz, Jun 06 2013
# alternative
A073103 := 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
            a := a*p^min(r-1,3) ;
        else
            if modp(p,4) = 1 then
                a := 4*a ;
            else
                a := 2*a ;
            end if;
        end if;
    end do:
    a ;
end proc: # R. J. Mathar, Mar 02 2015

a[n_] := Sum[If[Mod[j^4-1, n] == 0, 1, 0], {j, 0, n-1}]; Table[a[n], {n, 1, 120}] (* Jean-François Alcover, Jun 12 2015, after Alois P. Heinz *)
f[2, e_] := 2^Min[e-1, 3]; f[p_, e_] := If[Mod[p, 4] == 1, 4, 2]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 17 2020 *)

PARI
```
a(n)=sum(i=1,n,if((i^4-1)%n,0,1))
```

a(n)=my(f=factor(n)); prod(i=1,#f~, if(f[i,1]==2, 2^min(f[i,2]-1,3), if(f[i,1]%4==1, 4, 2))) \\ Charles R Greathouse IV, Mar 02 2015

from math import prod
from sympy import primefactors
def A073103(n): return (1<>1) for p in primefactors(n>>s)) # Chai Wah Wu, Oct 26 2022

Sum_{k=1..n} a(k) seems to be asymptotic to C*n*Log(n) with C>1.4...(when Sum_{k=1..n} A060594(k) is asymptotic to C/2*n*Log(n)).
Multiplicative with a(p^e) = p^min(e-1, 3) if p = 2, 4 if p == 1 (mod 4), 2 if p == 3 (mod 4). - David W. Wilson, Jun 09 2005
In fact, Sum_{k=1..n} a(k) is asymptotic to c*n*log(n)^2 where 2*c=0.190876.... - Steven Finch, Aug 12 2009 [c = 7/(2*Pi^3) * Product_{p prime == 1 (mod 4)} (1 - 4/(p+1)^2) = 0.0954383605... (Finch et al., 2010). - Amiram Eldar, Mar 26 2021]

A319100 Number of solutions to x^6 == 1 (mod n).

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 6, 4, 6, 2, 2, 4, 6, 6, 4, 4, 2, 6, 6, 4, 12, 2, 2, 8, 2, 6, 6, 12, 2, 4, 6, 4, 4, 2, 12, 12, 6, 6, 12, 8, 2, 12, 6, 4, 12, 2, 2, 8, 6, 2, 4, 12, 2, 6, 4, 24, 12, 2, 2, 8, 6, 6, 36, 4, 12, 4, 6, 4, 4, 12, 2, 24, 6, 6, 4, 12, 12, 12, 6, 8, 6, 2

Offset: 1

Jianing Song, Sep 10 2018

All terms are 3-smooth. a(n) is even for n > 2. Those n such that a(n) = 2 are in A066501.

			Solutions to x^6 == 1 (mod 13): x == 1, 3, 4, 9, 10, 12 (mod 13).
Solutions to x^6 == 1 (mod 27): x == 1, 8, 10, 17, 19, 26 (mod 27) (x == 1, 8 (mod 9)).
Solutions to x^6 == 1 (mod 37): x == 1, 10, 11, 26, 27, 36 (mod 37).

Jianing Song, Table of n, a(n) for n = 1..10000
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.

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), this sequence (k=6), A319101 (k=7), A247257 (k=8).
Cf. A046072, A066501, A088232, A293483, A000010.
Mobius transform gives A307381.

a(n)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(6, Z[i]))

Multiplicative with a(2) = 1, a(4) = 2, a(2^e) = 4 for e >= 3; a(3) = 2, a(3^e) = 6 if e >= 2; for other primes p, a(p^e) = 6 if p == 1 (mod 6), a(p^e) = 2 if p == 5 (mod 6).
If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(6, k_i).
a(n) = A060594(n)*A060839(n).
For n > 2, a(n) = A060839(n)*2^A046072(n).
a(n) = A060594(n) iff n is not divisible by 9 and no prime factor of n is congruent to 1 mod 6, that is, n in A088232.
a(n) = A000010(n)/A293483(n). - Jianing Song, Nov 10 2019
Sum_{k=1..n} a(k) ~ c * n * log(n)^3, where c = (1/Pi^4) * Product_{p prime == 1 (mod 6)} (1 - (12*p-4)/(p+1)^3) = 0.0075925601... (Finch et al., 2010). - Amiram Eldar, Mar 26 2021

A319099 Number of solutions to x^5 == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 5, 1, 1, 1, 1, 1, 5, 1, 5, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 5, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 5, 5, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 5, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1

Offset: 1

Jianing Song, Sep 10 2018

All terms are powers of 5. Those n such that a(n) > 1 are in A066500.

			Solutions to x^5 == 1 (mod 11): x == 1, 3, 4, 5, 9 (mod 11).
Solutions to x^5 == 1 (mod 25): x == 1, 6, 11, 16, 21 (mod 25) (x == 1 (mod 5)).
Solutions to x^5 == 1 (mod 31): x == 1, 2, 4, 8, 16 (mod 31).

Jianing Song, Table of n, a(n) for n = 1..10000

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), this sequence (k=5), A319100 (k=6), A319101 (k=7), A247257 (k=8).
Cf. A030430, A066500, A293482, A000010.
Mobius transform gives A307380.

f[p_, e_] := If[Mod[p, 5] == 1, 5, 1]; f[5, 1] = 1; f[5, e_] := 5; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

a(n)=my(Z=znstar(n)[2]); prod(i=1,#Z,gcd(5,Z[i]));

Multiplicative with a(5) = 1, a(5^e) = 5 if e >= 2; for other primes p, a(p^e) = 5 if p == 1 (mod 5), a(p^e) = 1 otherwise.
If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(5, k_i).
a(n) = A000010(n)/A293482(n). - Jianing Song, Nov 10 2019

A319101 Number of solutions to x^7 == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 7

Offset: 1

Jianing Song, Sep 10 2018

All terms are powers of 7. Those n such that a(n) > 1 are in A066502.

			Solutions to x^7 == 1 (mod 29): x == 1, 7, 16, 20, 23, 24, 25 (mod 29).
Solutions to x^7 == 1 (mod 43): x == 1, 4, 11, 16, 21, 35, 41 (mod 43).
Solutions to x^7 == 1 (mod 49): x == 1, 8, 15, 22, 29, 36, 43 (mod 49) (x == 1 (mod 7)).

Jianing Song, Table of n, a(n) for n = 1..10000

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), this sequence (k=7), A247257 (k=8).
Cf. A066502, A140444, A293484, A000010.
Mobius transform gives A307382.

f[p_, e_] := If[Mod[p, 7] == 1, 7, 1]; f[7, 1] = 1; f[7, e_] := 7; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

a(n)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(7, Z[i]))

Multiplicative with a(7) = 1, a(7^e) = 7 if e >= 2; for other primes p, a(p^e) = 7 if p == 1 (mod 7), a(p^e) = 1 otherwise.
If the multiplicative group of integers modulo n is isomorphic to C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j; then a(n) = Product_{i=1..m} gcd(7, k_i).
a(n) = A000010(n)/A293484(n). - Jianing Song, Nov 10 2019

A088232 Numbers k such that 3 does not divide phi(k).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 15, 16, 17, 20, 22, 23, 24, 25, 29, 30, 32, 33, 34, 40, 41, 44, 46, 47, 48, 50, 51, 53, 55, 58, 59, 60, 64, 66, 68, 69, 71, 75, 80, 82, 83, 85, 87, 88, 89, 92, 94, 96, 100, 101, 102, 106, 107, 110, 113, 115, 116, 118, 120, 121, 123, 125, 128

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 03 2003

nonn

n such that the congruence x^3 == 1 mod(n) has only the trivial solution x=1 i.e. A060839(n) = 1 . Complement of sequence A066498.
Let U(n) be the group of positive integers coprime to n under mod n multiplication.  Let U(n)^3 = {x^3: x is an element of U(n)}.  These are the n such that U(n) = U(n)^3. - Geoffrey Critzer, Jun 07 2015
In other words, numbers divisible neither by 9 nor by any primes of the form 6k+1. - Ivan Neretin, Sep 03 2015
The asymptotic density of this sequence is 0 (Dressler, 1975). - Amiram Eldar, Jul 23 2020

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Robert E. Dressler, A property of the phi and sigma_j functions, Compositio Mathematica, Vol. 31, No. 2 (1975), pp. 115-118.
Kevin Ford, Florian Luca, and Pieter Moree, Values of the Euler phi-function not divisible by a given odd prime, and the distribution of Euler-Kronecker constants for cyclotomic fields, arXiv:1108.3805 [math.NT], 2011-2012.

Cf. A000010, A066498 (complement).
Positions of 1's in A060839, of 0's in A354099, of nonzeros in A074942.
Cf. also A329963.

select(t -> numtheory:-phi(t) mod 3 <> 0, [$1..1000]); # Robert Israel, Sep 04 2015

Prepend[Position[Table[Union[Select[Range[n], CoprimeQ[#, n] &]] ==
     Union[Mod[Select[Range[n], CoprimeQ[#, n] &]^3, n]], {n, 1,155}], True], 1] // Flatten (* Geoffrey Critzer, Jun 07 2015 *)
Select[Range[140],!Divisible[EulerPhi[#],3]&] (* Harvey P. Dale, Sep 23 2017 *)

is(n)=eulerphi(n)%3 \\ Charles R Greathouse IV, Feb 04 2013

a(n) ~ k n sqrt(log(n)) for some constant k. k appears to be around 1.08. [Charles R Greathouse IV, Feb 14 2012]

More terms from Ray Chandler, Nov 05 2003

A247257 The number of octic characters modulo n.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 2, 4, 2, 4, 2, 4, 4, 2, 8, 8, 8, 2, 2, 8, 4, 2, 2, 8, 4, 4, 2, 4, 4, 8, 2, 16, 4, 8, 8, 4, 4, 2, 8, 16, 8, 4, 2, 4, 8, 2, 2, 16, 2, 4, 16, 8, 4, 2, 8, 8, 4, 4, 2, 16, 4, 2, 4, 16, 16, 4, 2, 16, 4, 8, 2, 8, 8, 4, 8, 4, 4, 8, 2, 32

Offset: 1

R. J. Mathar, Mar 02 2015

Number of solutions to x^8 == 1 (mod n). - Jianing Song, Nov 10 2019

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Steven Finch, Quartic and octic characters modulo n, arXiv:0907.4894 [math.NT], 2009.

Number of solutions to x^k == 1 (mod n): A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), A319101 (k=7), this sequence (k=8).

A247257 := 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
            if r >= 5 then
                a := a*16 ;
            else
                a := a*op(r,[1,2,4,8]) ;
            end if;
        elif modp(p,4) = 3 then
            a := a*2;
        elif modp(p,8) = 5 then
            a := a*4;
        elif modp(p,8) = 1 then
            a := a*8;
        else
            error
        end if;
    end do:
    a ;
end proc:

g[p_, e_] := Which[p==2, 2^Min[e-1, 4], Mod[p, 4]==3, 2, Mod[p, 8]==5, 4, True, 8];
a[1] = 1; a[n_] := Times @@ g @@@ FactorInteger[n];
Array[a, 80] (* Jean-François Alcover, Nov 26 2017, after Charles R Greathouse IV *)

g(p,e)=if(p==2, 2^min(e-1,4), if(p%4==3, 2, if(p%8==5, 4, 8)))
a(n)=my(f=factor(n)); prod(i=1,#f~, g(f[i,1],f[i,2])) \\ Charles R Greathouse IV, Mar 02 2015

Multiplicative with a(p^e) = p^min(e-1, 4) if p = 2, gcd(8, p-1) if p > 2. - Jianing Song, Nov 10 2019

A087692 Number of cubes in multiplicative group modulo n.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 2, 4, 2, 4, 10, 4, 4, 2, 8, 8, 16, 2, 6, 8, 4, 10, 22, 8, 20, 4, 6, 4, 28, 8, 10, 16, 20, 16, 8, 4, 12, 6, 8, 16, 40, 4, 14, 20, 8, 22, 46, 16, 14, 20, 32, 8, 52, 6, 40, 8, 12, 28, 58, 16, 20, 10, 4, 32, 16, 20, 22, 32, 44, 8, 70, 8, 24, 12, 40, 12, 20, 8, 26, 32, 18, 40

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 27 2003

Cubic analog of A046073. - Steven Finch, Mar 01 2006

Robert Israel, Table of n, a(n) for n = 1..10000
Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.

Cf. A000010, A060839, A046073 (squares), A250207 (4th powers).

b:= proc(p,i)
  if p = 3 then if i=1 then 2 else 2*3^(i-2) fi
  elif p mod 6 = 1 then (p-1)*p^(i-1)/3
  else (p-1)*p^(i-1)
  fi
end proc:
seq(mul(b(f[1],f[2]), f = ifactors(n)[2]), n = 1 .. 1000); # Robert Israel, Jan 04 2015

Map[Length,Table[Select[Range[n],CoprimeQ[#, n] && IntegerQ[PowerMod[#, 1/3, n]] &], {n, 1, 82}]] (* Geoffrey Critzer, Jan 07 2015 *)
f[p_, e_] := (p - 1)*p^(e - 1)/If[Mod[p, 6] == 1, 3, 1]; f[3, e_] := 2*3^(e-2); f[3, 1] = 2; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 10 2023 *)

a(n) = my(f = factor(n)); prod(j=1, #f~, p=f[j,1]; k=f[j,2]; if (p == 3, if (k==1, 2, 2*3^(k-2)), if ((p % 6) == 1, ((p-1)*p^(k-1))/3, (p-1)*p^(k-1)))); \\ Michel Marcus, Jan 05 2015

a(n) = phi(n) / A060839(n).
Multiplicative with a(3) = 2, a(3^k) = 2*3^(k-2) otherwise;
a(p^k) = (p-1)*p^(k-1)/3 if prime p == 1 mod 6; a(p^k) = (p-1)*p^(k-1) for all other primes p. - Robert Israel, Jan 04 2015
Sum_{k=1..n} a(k) ~ c * n^2/log(n)^(1/3), where c = (17/(36*Gamma(2/3))) * Product_{p = 3 or p prime == 2 (mod 3)} (1+1/*p)*(1-1/p)^(2/3) * Product_{p prime == 1 (mod 3)} (1+1/(3*p))*(1-1/p)^(2/3) = 0.33051128776333262024... (Finch and Sebah, 2006). - Amiram Eldar, Oct 18 2022

More terms from Steven Finch, Mar 01 2006

A354057 Square array read by ascending antidiagonals: T(n,k) is the number of solutions to x^k == 1 (mod n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 4, 1, 2, 1, 1, 1, 4, 3, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 3, 4, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 6, 1, 4, 1, 2, 1, 1, 1, 4, 1, 4, 1, 4, 1, 2, 1, 2, 1, 1, 1

Offset: 1

Jianing Song, May 16 2022

Row n and Row n' are the same if and only if (Z/nZ)* = (Z/n'Z)*, where (Z/nZ)* is the multiplicative group of integers modulo n.
Given n, T(n,k) only depends on gcd(k,psi(n)). For the truncated version see A354060.
Each column is multiplicative.

			  n/k  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
   1   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   2   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
   3   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   4   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   5   1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4
   6   1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2  1  2
   7   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
   8   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
   9   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  10   1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4  1  2  1  4
  11   1  2  1  2  5  2  1  2  1 10  1  2  1  2  5  2  1  2  1 10
  12   1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4  1  4
  13   1  2  3  4  1  6  1  4  3  2  1 12  1  2  3  4  1  6  1  4
  14   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  15   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8
  16   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8
  17   1  2  1  4  1  2  1  8  1  2  1  4  1  2  1 16  1  2  1  4
  18   1  2  3  2  1  6  1  2  3  2  1  6  1  2  3  2  1  6  1  2
  19   1  2  3  2  1  6  1  2  9  2  1  6  1  2  3  2  1 18  1  2
  20   1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8  1  4  1  8

Jianing Song, Table of n, a(n) for n = 1..5050 (the first 100 ascending diagonals)

k-th column: A060594 (k=2), A060839 (k=3), A073103 (k=4), A319099 (k=5), A319100 (k=6), A319101 (k=7), A247257 (k=8).
Applying Moebius transform to the rows gives A354059.
Applying Moebius transform to the columns gives A354058.
Cf. A327924.

T(n,k)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(k, Z[i]))

If (Z/nZ)* = C_{k_1} X C_{k_2} X ... X C_{k_r}, then T(n,k) = Product_{i=1..r} gcd(k,k_r).
T(p^e,k) = gcd((p-1)*p^(e-1),k) for odd primes p. T(2,k) = 1, T(2^e,k) = 2*gcd(2^(e-2),k) if k is even and 1 if k is odd.
A327924(n,k) = Sum_{q|n} T(n,k) * (Sum_{s|n/q} mu(s)/phi(s*q)).

cp's OEIS Frontend

A357905 a(n) = log_3(A060839(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A160498 Number of cubic primitive Dirichlet characters modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions

A073103 Number of solutions to x^4 == 1 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A319100 Number of solutions to x^6 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A319099 Number of solutions to x^5 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A319101 Number of solutions to x^7 == 1 (mod n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A088232 Numbers k such that 3 does not divide phi(k).

Views