A088232 -id:A088232 - cp's OEIS frontend

A329963 Numbers k such that sigma(k) is not divisible by 3.

1, 3, 4, 7, 9, 12, 13, 16, 19, 21, 25, 27, 28, 31, 36, 37, 39, 43, 48, 52, 57, 61, 63, 64, 67, 73, 75, 76, 79, 81, 84, 91, 93, 97, 100, 103, 108, 109, 111, 112, 117, 121, 124, 127, 129, 133, 139, 144, 148, 151, 156, 157, 163, 171, 172, 175, 181, 183, 189, 192, 193, 199, 201, 208, 211, 217, 219, 223, 225, 228, 229

Offset: 1

John L. Drost, Nov 25 2019

nonn

A number k is in the sequence iff in its prime factorization, all primes p == 1 (mod 3) occur to such a power p^e that e != 2 (mod 3), and all primes == 2 (mod 3) occur to even powers. (3 can occur to any power.) This sequence is similar but not identical to many others; in particular, 343 is in this sequence, but not in A034022. (And here we don't have 196, although it is in A034022). - First sentence corrected and additional notes added by Antti Karttunen, Jul 03 2024, see also Robert Israel's Nov 09 2016 comment in A087943.

The asymptotic density of this sequence is 0 (Dressler, 1975). - Amiram Eldar, Jul 23 2020

Robert Israel, Table of n, a(n) for n = 1..10000
Tewodros Amdeberhan, Victor H. Moll, Vaishavi Sharma, and Diego Villamizar, Arithmetic properties of the sum of divisors, arXiv:2007.03088 [math.NT], 2020. See p. 15 ff. [Note: the "if and only if" condition given in the beginning of Theorem 7.1 is for A003136, not for this sequence. - _Antti Karttunen_, Jul 04 2024]
Robert E. Dressler, A property of the phi and sigma_j functions, Compositio Mathematica, Vol. 31, No. 2 (1975), pp. 115-118.

Complement of A087943. Positions of zeros in A354100, nonzeros in A074941.
Cf. A000203, A353815 (characteristic function).
Setwise difference A003136 \ A088535.
Subsequences: A002476, A068228, A351537, A374135.
Cf. also A088232.
Not the same as A034022.

[k:k in [1..200]| DivisorSigma(1,k) mod 3 ne 0]; // Marius A. Burtea, Jan 02 2020

select(t -> numtheory:-sigma(t) mod 3 <> 0, [$1..200]); # Robert Israel, Jan 01 2020

Select[Range[200], !Divisible[DivisorSigma[1, #], 3] &] (* Amiram Eldar, Nov 25 2019 *)

isok(k) = (sigma(k) % 3) != 0; \\ Michel Marcus, Nov 26 2019

isA329963 = A353815; \\ Antti Karttunen, Jul 03 2024

More terms from Joshua Oliver, Nov 26 2019

Data section further extended up to a(71), to better differentiate from nearby sequences - Antti Karttunen, Jul 04 2024

A066498 Numbers k such that 3 divides phi(k).

Original entry on oeis.org

7, 9, 13, 14, 18, 19, 21, 26, 27, 28, 31, 35, 36, 37, 38, 39, 42, 43, 45, 49, 52, 54, 56, 57, 61, 62, 63, 65, 67, 70, 72, 73, 74, 76, 77, 78, 79, 81, 84, 86, 90, 91, 93, 95, 97, 98, 99, 103, 104, 105, 108, 109, 111, 112, 114, 117, 119, 122, 124, 126, 127, 129, 130, 133

Offset: 1

Benoit Cloitre, Jan 04 2002

nonn

Numbers k such that x^3 == 1 (mod k) has solutions 1 < x < k.
Terms are multiple of 9 or of a prime of the form 6k+1.
If k is a term of this sequence, then G =  is a non-abelian group of order 3k, where 1 < r < n and r^3 == 1 (mod k). For example, G can be the subgroup of GL(2, Z_k) generated by x = {{1, 1}, {0, 1}} and y = {{r, 0}, {0, 1}}. - Jianing Song, Sep 17 2019
The asymptotic density of this sequence is 1 (Dressler, 1975). - Amiram Eldar, Mar 21 2021

			If n < 7 then x^3 = 1 (mod n) has no solution 1 < x < n, but {2,4} are solutions to x^3 == 1 (mod 7), hence a(1) = 7.

Harry J. Smith, Table of n, a(n) for n=1..1000
Robert E. Dressler, A property of the phi and sigma_j functions, Compositio Mathematica, Vol. 31, No. 2 (1975), pp. 115-118.

Complement of A088232.
Cf. A000010, A066499, A066500, A066501, A066502.
A007645 gives the primes congruent to 1 mod 3.
Column k=2 of A277915.

Select[Range[150], Divisible[EulerPhi[#], 3]&] (* Harvey P. Dale, Jan 12 2011 *)

isok(k)={ eulerphi(k)%3 == 0 } \\ Harry J. Smith, Feb 18 2010

Simpler definition from Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 25 2003

Corrected and extended by Ray Chandler, Nov 05 2003

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

A354099 The 3-adic valuation of Euler totient function phi.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, May 17 2022

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A007949, A074942.
Cf. A088232 (positions of zeros), A066498 (of terms > 0).
Cf. also A354100.

a[n_] := IntegerExponent[EulerPhi[n], 3]; Array[a, 100] (* Amiram Eldar, May 17 2022 *)

PARI
```
A354099(n) = valuation(eulerphi(n),3);
```

A354099(n) = { my(f=factor(n)); sum(k=1,#f~,valuation((f[k,1]-1)*(f[k,1]^(f[k,2]-1)), 3)); }; \\ Demonstrates the additivity.

a(n) = A007949(A000010(n)).

Additive with a(p^e) = A007949((p-1)*p^(e-1)).

A254073 Number of solutions to x^3 + y^3 + z^3 == 1 (mod n) for 1 <= x, y, z <= n.

Original entry on oeis.org

1, 4, 9, 16, 25, 36, 90, 64, 162, 100, 121, 144, 252, 360, 225, 256, 289, 648, 468, 400, 810, 484, 529, 576, 625, 1008, 1458, 1440, 841, 900, 1143, 1024, 1089, 1156, 2250, 2592, 1602, 1872, 2268, 1600, 1681, 3240, 2115, 1936, 4050, 2116, 2209, 2304, 4410

Offset: 1

José María Grau Ribas, Jan 25 2015

It appears that a(n) = n^2 for n in A088232 (numbers n such that 3 does not divide phi(n)) and that a(n) != n^2 for n in A066498 (numbers n such that 3 divides phi(n)). - Michel Marcus, Mar 13 2015

It appears that a(p) != p^2 for primes in A002476 (primes of form 6m + 1). - Michel Marcus, Mar 13 2015

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Cf. A087412.

a[n_] := Sum[ If[ Mod[x^3 + y^3 + z^3, n] == 1, 1, 0], {x, n}, {y, n}, {z, n}]; a[1]=1; Table[a[n], {n, 2,22}]

a(n) = {nb = 0; for (x=1, n, for (y=1, n, for (z=1, n, if ((Mod(x^3,n) + Mod(y^3,n) + Mod(z^3,n)) % n == Mod(1, n), nb ++);););); nb;} \\ Michel Marcus, Mar 11 2015

a(n)={my(p=Mod(sum(i=0, n-1, x^(i^3%n)), 1-x^n)^3); polcoeff(lift(p), 1%n)} \\ Andrew Howroyd, Jul 18 2018

def A254073(n):
    ndict = {}
    for i in range(n):
        m = pow(i,3,n)
        if m in ndict:
            ndict[m] += 1
        else:
            ndict[m] = 1
    count = 0
    for i in ndict:
        ni = ndict[i]
        for j in ndict:
            k = (1-i-j) % n
            if k in ndict:
                count += ni*ndict[j]*ndict[k]
    return count # Chai Wah Wu, Jun 06 2017

A276919 Number of solutions to x^3 + y^3 + z^3 + t^3 == 1 (mod n) for 1 <= x, y, z, t <= n.

Original entry on oeis.org

1, 8, 27, 64, 125, 216, 336, 512, 1296, 1000, 1331, 1728, 1794, 2688, 3375, 4096, 4913, 10368, 7410, 8000, 9072, 10648, 12167, 13824, 15625, 14352, 34992, 21504, 24389, 27000, 30225, 32768, 35937, 39304, 42000, 82944, 48396, 59280, 48438, 64000, 68921, 72576, 77529, 85184, 162000, 97336

Offset: 1

José María Grau Ribas, Sep 22 2016

It appears that a(n) = n^3 for n in A088232. See also A066498. - Michel Marcus, Oct 11 2016

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Cf. A000189, A047726, A060839, A063454, A087412, A087786, A254073, A276920.

JJJ[4, n, lam] = Sum[If[Mod[a^3 + b^3 + c^3 + d^3, n] == Mod[lam, n], 1, 0], {d, 0, n - 1}, {a, 0, n - 1}, {b, 0, n - 1}, {c, 0 , n - 1}]; Table[JJJ[4, n, 1], {n, 1, 50}]

a(n) = sum(x=1, n, sum(y=1, n, sum(z=1, n, sum(t=1, n, Mod(x,n)^3 + Mod(y,n)^3 + Mod(z,n)^3 + Mod(t,n)^3 == 1)))); \\ Michel Marcus, Oct 11 2016

qperms(v) = {my(r=1,t); v = vecsort(v); for(i=1,#v-1, if(v[i]==v[i+1], t++, r*=binomial(i,t+1);t=0));r*=binomial(#v,t+1)}
a(n) = {my(t=0); forvec(v=vector(4,i,[1,n]), if(sum(i=1, 4, Mod(v[i], n)^3)==1, print1(v", "); t+=qperms(v)),1);t} \\ David A. Corneth, Oct 11 2016

def A276919(n):
    ndict = {}
    for i in range(n):
        i3 = pow(i,3,n)
        for j in range(i+1):
            j3 = pow(j,3,n)
            m = (i3+j3) % n
            if m in ndict:
                if i == j:
                    ndict[m] += 1
                else:
                    ndict[m] += 2
            else:
                if i == j:
                    ndict[m] = 1
                else:
                    ndict[m] = 2
    count = 0
    for i in ndict:
        j = (1-i) % n
        if j in ndict:
            count += ndict[i]*ndict[j]
    return count # Chai Wah Wu, Jun 06 2017

A132385 Number of distinct primes among the cubes mod n.

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 0, 3, 0, 4, 4, 4, 1, 2, 6, 5, 6, 1, 2, 7, 2, 8, 8, 8, 8, 2, 2, 2, 9, 10, 3, 10, 11, 11, 3, 2, 4, 5, 3, 11, 12, 4, 3, 13, 3, 14, 14, 14, 4, 14, 15, 4, 15, 4, 16, 5, 5, 16, 16, 16, 6, 6, 0, 17, 5, 18, 5, 18, 19, 5

Offset: 1

Jonathan Vos Post, Nov 07 2007

This is to cubes A000578 as A132213 is to squares A000290.
It seems that the size of a(n) as compared to its surrounding elements is dependent on whether or not n is in A088232. If n is in A088232 the sequence assumes "big" values, otherwise the values will be "small". - Stefan Steinerberger, Nov 24 2007
If n is in A088232, a(n) = A000720(n-1) - A056170(n). - Robert Israel, Jun 28 2018

			a(10) = 4 because the cubes mod 10 repeat 0, 1, 8, 7, 4, 5, 6, 3, 2, 9, 0, 1, 8, 7, 4, 5, ... of which the 4 distinct primes are {2, 3, 5, 7}.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000040, A000578, A000720, A056170, A132213.

f:= proc(n)
  if numtheory:-phi(n) mod 3 = 0 then nops(select(isprime, {seq(i^3 mod n, i=0..n-1)}))
  else numtheory:-pi(n-1) - nops(select(t -> t[2]>1, ifactors(n)[2]))
  fi
end proc:
map(f, [$1..100]); # Robert Israel, Jun 28 2018

Table[Length[Select[Union[Table[Mod[i^3, n], {i, 0, n}], Table[Mod[i^3, n], {i, 0, n}]], PrimeQ[ # ] &]], {n, 1, 70}] (* Stefan Steinerberger, Nov 12 2007 *)

a(n) = Card{p = k^3 mod n, for primes p and for all integers k}.

More terms from Stefan Steinerberger, Nov 12 2007

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010

A343783 a(n) is the largest primorial number (A002110) which divides phi(n).

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 6, 2, 6, 2, 2, 2, 6, 6, 2, 2, 2, 6, 6, 2, 6, 2, 2, 2, 2, 6, 6, 6, 2, 2, 30, 2, 2, 2, 6, 6, 6, 6, 6, 2, 2, 6, 6, 2, 6, 2, 2, 2, 6, 2, 2, 6, 2, 6, 2, 6, 6, 2, 2, 2, 30, 30, 6, 2, 6, 2, 6, 2, 2, 6, 2, 6, 6, 6, 2, 6, 30, 6, 6, 2, 6, 2, 2, 6, 2, 6

Offset: 1

Amiram Eldar, Apr 29 2021

nonn

			a(3) = 2 since phi(3) = 2 and 2 = A002110(1).
a(5) = 2 since phi(5) = 4 and 2 = A002110(1) is the largest primorial dividing 4.
a(7) = 6 since phi(7) = 6 and 6 = A002110(2).

Amiram Eldar, Table of n, a(n) for n = 1..10000
Paul Pollack and Carl Pomerance, Phi, primorials, and Poisson, Illinois J. Math., Vol. 64, No. 3 (2020), pp. 319-330; alternative link.

Cf. A000010, A002110, A034386, A053589.

prim[n_] := Times @@ Prime[Range[n]]; gp[n_] := Module[{k = 1}, While[Divisible[n, prim[k]], k++]; prim[k - 1]]; a[n_] := gp[EulerPhi[n]]; Array[a, 100]

f(n) = my(s=1); forprime(p=2, , if(n%p, return(s), s *= p)); \\ A053589
a(n) = f(eulerphi(n)); \\ Michel Marcus, May 01 2021

a(n) = A053589(A000010(n)).
Let pr(n) be the largest prime divisor of a(n) (i.e., a(n) = pr(n)# = A034386(pr(n))). Then pr(n) ~ log(log(n))/log(log(log(n))) on a set of integers of asymptotic density 1 (Pollack and Pomerance, 2020).
From Bernard Schott, May 05 2021: (Start)
a(2n) = a(n) for n>=1.
a(n) = 1 iff n = 1 or n = 2.
a(n) = 2 iff 3 does not divide phi(n) (A088232)
a(n) >= 6 iff 3 divides phi(n) (A066498). (End)

cp's OEIS Frontend

A329963 Numbers k such that sigma(k) is not divisible by 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Extensions

A066498 Numbers k such that 3 divides phi(k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A354099 The 3-adic valuation of Euler totient function phi.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A254073 Number of solutions to x^3 + y^3 + z^3 == 1 (mod n) for 1 <= x, y, z <= n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

A276919 Number of solutions to x^3 + y^3 + z^3 + t^3 == 1 (mod n) for 1 <= x, y, z, t <= n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

A132385 Number of distinct primes among the cubes mod n.

Views

Author

Keywords

Comments

Examples

Links