A354058 -id:A354058 - cp's OEIS frontend

A007431 a(n) = Sum_{d|n} phi(d)*mu(n/d).

0, 1, 0, 1, 1, 3, 0, 5, 2, 4, 0, 9, 1, 11, 0, 3, 4, 15, 0, 17, 3, 5, 0, 21, 2, 16, 0, 12, 5, 27, 0, 29, 8, 9, 0, 15, 4, 35, 0, 11, 6, 39, 0, 41, 9, 12, 0, 45, 4, 36, 0, 15, 11, 51, 0, 27, 10, 17, 0, 57, 3, 59, 0, 20, 16, 33, 0, 65, 15, 21, 0, 69, 8, 71, 0, 16, 17, 45, 0, 77, 12, 36, 0, 81, 5, 45, 0

Offset: 0

N. J. A. Sloane

Also Moebius transform applied twice to natural numbers.
Also number of complex primitive Dirichlet characters modulo n and Sum_{k=1..n} a(k) is asymptotic to (18/Pi^4)*n^2. - Steven Finch, Feb 16 2006
Dirichlet convolution of phi(n) and mu(n). - Richard L. Ollerton, May 07 2021
From Jianing Song, May 21 2022: (Start)
a(n) is the number of degree-psi(n) primitive Dirichlet characters mod n, where psi = A002322. Also, a(n) is the number of degree-(k*psi(n)) primitive Dirichlet characters mod n for all k >= 1.
a(n) is the maximum element in the n-th row of A354058 (or A354061). (End)

			From _Jianing Song_, May 21 2022: (Start)
a(45) = 12: psi(45) = 12, there are 3 degree-12 primitive characters modulo 5 and 4 degree-12 primitive characters modulo 9, so a(45) = 3 * 4 = 12.
a(63) = 20: psi(63) = 6, there are 5 sextic primitive characters modulo 7 and 4 sextic primitive characters modulo 9, so a(63) = 5 * 4 = 20. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Antti Karttunen, Table of n, a(n) for n = 0..20000 (terms 0..1000 from T. D. Noe)
H. Jager, On the number of Dirichlet characters with modulus not exceeding x, Nederl. Akad. Wetensch. Proc. Ser. A 76=Indag. Math. 35 (1973) 452-455.
Wolfgang Schramm, The Fourier transform of functions of the greatest common divisor, Electronic Journal of Combinatorial Number Theory A50 (8(1)), 2008.
N. J. A. Sloane, Transforms

Cf. A007432.

Cf. A000010, A008683, A130054 (Dirichlet inverse), A354058, A354061.

a007431 0 = 0
a007431 n = sum $ map (a008683 . gcd n) [1..n]
-- Reinhard Zumkeller, Jan 06 2014

[0] cat [&+[EulerPhi(d)*MoebiusMu(Floor(n/d)):d in Divisors(n)]:n in [1..90]]; // Marius A. Burtea, Aug 10 2019

with(numtheory); f:=n->add( phi(d)*mobius(n/d), d in divisors(n)); [seq(f(n),n=0..120)];

Table[Sum[EulerPhi[d] MoebiusMu[n/d], {d, Divisors[n]}], {n, 0, 86}] (* Jean-François Alcover, Apr 04 2011 *)
Table[DirichletConvolve[MoebiusMu[n], EulerPhi[n], n, m], {m, 86}] (* Jan Mangaldan, Mar 15 2013 *)
f[p_, e_] := If[e == 1, p-2, p^e - 2*p^(e-1) + p^(e-2)]; a[1] = 1; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Jun 23 2020 *)

a(n)=if(n<1,0,direuler(p=2,n,(1-X)^2/(1-p*X))[n]) \\ Ralf Stephan

a(n) = sumdiv(n,d, moebius(d) * eulerphi(n/d) ); \\ Joerg Arndt, Apr 14 2013

A007431(n) = if(!n,n,my(f=factor(n)); prod(i=1, #f~, if(1==f[i, 2], f[i, 1]-2, ((f[i,1]-1)^2)*(f[i, 1]^(f[i, 2]-2))))); \\ Antti Karttunen, Dec 15 2024, after Vladeta Jovovic's multiplicative formula

Multiplicative with a(p) = p-2 and a(p^e) = (p-1)^2*p^(e-2) for e > 1. - Vladeta Jovovic, Jan 25 2002
Dirichlet g.f.: zeta(s-1)/zeta^2(s).
a(n) = Sum_{k=1..n} mu(gcd(n,k)) for n > 0. - Benoit Cloitre, Jun 14 2007
a(n) = Sum_{k=1..n} (phi(gcd(k,n)) * cos(2*Pi*k/n)). - Enrique Pérez Herrero, Jan 18 2013
a(n) = Sum_{d|n} tau_{-2}(d)*n/d = Sum_{d|n} tau_{-3}(d)*sigma_1(n/d), where tau_{-3} is A007428, tau_{-2} A007427 and sigma_1 A000203. - Enrique Pérez Herrero, Jan 19 2013
G.f.: Sum_{n>=1} a(n)*x^n/(1 - x^n) = Sum_{n>=1} mu(n)*x^n/(1 - x^n)^2. - Ilya Gutkovskiy, Apr 25 2017
Sum_{k=1..n} a(k) ~ 18 * n^2 / Pi^4. - Vaclav Kotesovec, Nov 04 2018
Sum_{n>=1} a(n)*x^n/(1 - x^n) = Sum_{n>=1} phi(n)*x^n. - Mamuka Jibladze, Aug 09 2019
Sum_{d|n} a(d) = phi(n) (A000010). - Amiram Eldar, Jun 23 2020
a(n) = Sum_{k=1..n} mu(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021
a(n) = A354058(n,psi(n)) = A354061(n,psi(n)) with psi = A002322. - Jianing Song, May 21 2022

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)).

A354061 Irregular table read by rows: T(n,k) is the number of degree-k primitive Dirichlet characters modulo n, 1 <= k <= psi(n), psi = A002322.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 1, 0, 3, 0, 0, 0, 1, 2, 1, 0, 5, 0, 2, 0, 0, 2, 0, 0, 4, 0, 0, 0, 0, 0, 1, 0, 1, 4, 1, 0, 1, 0, 9, 0, 1, 0, 1, 2, 3, 0, 5, 0, 3, 2, 1, 0, 11, 0, 0, 0, 0, 0, 0, 0, 1, 0, 3, 0, 0, 0, 4, 0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 3, 0, 1, 0, 15

Offset: 1

Jianing Song, May 16 2022

Given n, T(n,k) only depends on gcd(k,psi(n)).
The n-th row contains entirely 0's if and only if n == 2 (mod 4).
If n !== 2 (mod 4), T(n,psi(n)) > T(n,k) for 1 <= k < psi(n).

			Table starts
n = 1: 1;
n = 2: 0;
n = 3: 0, 1;
n = 4: 0, 1;
n = 5: 0, 1, 0, 3;
n = 6: 0, 0;
n = 7: 0, 1, 2, 1, 0, 5;
n = 8: 0, 2;
n = 9: 0, 0, 2, 0, 0, 4;
n = 10: 0, 0, 0, 0;
n = 11: 0, 1, 0, 1, 4, 1, 0, 1, 0, 9;
n = 12: 0, 1;
n = 13: 0, 1, 2, 3, 0, 5, 0, 3, 2, 1, 0, 11;
n = 14: 0, 0, 0, 0, 0, 0;
n = 15: 0, 1, 0, 3;
n = 16: 0, 0, 0, 4;
n = 17: 0, 1, 0, 3, 0, 1, 0, 7, 0, 1, 0, 3, 0, 1, 0, 15;
n = 18: 0, 0, 0, 0, 0, 0;
n = 19: 0, 1, 2, 1, 0, 5, 0, 1, 8, 1, 0, 5, 0, 1, 2, 1, 0, 17;
n = 20: 0, 1, 0, 3;
...

Jianing Song, Table of n, a(n) for n = 1..8346 (the first 200 rows)

Cf. A354058, A002322, A007431, A354060.

A354257 gives the smallest index for the nonzero terms in each row.

b(n,k)=my(Z=znstar(n)[2]); prod(i=1, #Z, gcd(k, Z[i]));
T(n,k) = sumdiv(n, d, moebius(n/d)*b(d,k))

For odd primes p: T(p,k) = gcd(p-1,k)-1, T(p^e,k*p^(e-1)) = p^(e-2)*(p-1)*gcd(k,p-1), T(p^e,k) = 0 if k is not divisible by p^(e-1). T(2,k) = 0, T(4,k) = 1 for even k and 0 for odd k, T(2^e,k) = 2^(e-2) if k is divisible by 2^(e-2) and 0 otherwise.

T(n,psi(n)) = A007431(n). - Jianing Song, May 24 2022

A354257 a(n) is the smallest k such that there exists a degree-k primitive Dirichlet characters modulo n, or -1 no such k exists.

Original entry on oeis.org

1, -1, 2, 2, 2, -1, 2, 2, 3, -1, 2, 2, 2, -1, 2, 4, 2, -1, 2, 2, 2, -1, 2, 2, 5, -1, 9, 2, 2, -1, 2, 8, 2, -1, 2, 6, 2, -1, 2, 2, 2, -1, 2, 2, 6, -1, 2, 4, 7, -1, 2, 2, 2, -1, 2, 2, 2, -1, 2, 2, 2, -1, 3, 16, 2, -1, 2, 2, 2, -1, 2, 6, 2, -1, 10, 2, 2, -1, 2, 4, 27, -1, 2, 2, 2, -1, 2, 2, 2, -1

Offset: 1

Jianing Song, May 21 2022

sign

For n !== 2 (mod 4), a(n) is the smallest k such that A354058(n,k) != 0 (or the smallest k such that A354061(n,k) != 0).

For n !== 2 (mod 4), a(n) is the smallest k such that Sum_{d|n} mu(n/d)*#{x in (Z/dZ)*: x^k == 1 (mod d)} != 0, where mu = A008683, (Z/dZ)* is the multiplicative group of integers modulo d.

			a(45) = 6: there does not exist a linear, quadratic, cubic, quartic or quintic primitive Dirichlet characters modulo 45, but there are 4 sextic primitive Dirichlet characters.
a(63) = 3: there does not exist a linear or quadratic primitive Dirichlet characters modulo 63, but there are 4 cubic primitive Dirichlet characters.

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

Cf. A354058, A354061, A008683.
A354258 gives the earliest occurrence of each positive integers.
Indices of 2: A003657 U A003658 \ {1}.

a(n) = if(n%4==2, return(-1), my(e_0 = valuation(n,2)); n=n>>e_0; my(L=factor(n),w=omega(n),v=[],M=1); for(j=1, w, if(L[j,2]==1, v=concat(v,j), M*=L[j,1]^(L[j,2]-1))); if(e_0 >= 2, return(2^max(e_0-2,1)*M), for(i=1, #v, if(gcd(M,L[v[i],1]-1)==1, return(2*M))); return(M)))

Write n = 2^(e_0) * (p_1) * ... * (p_r) * (q_1)^(e_1) * ... * (q_s)^(e_s), where (p_i)'s and (q_j)'s are distinct odd primes, e_j >= 2. Let M = Product_{j=1..s} (q_j)^(e_j-1):
(i) if e_0 = 1, then a(n) = -1;
(ii) if e_0 = 2, then a(n) = 2*M;
(iii) if e_0 >= 3, then a(n) = 2^(e_0-2)*M;
(iv) if e_0 = 0, then a(n) = M if for every 1 <= i <= r, there exists 1 <= j <= s such that q_j divides p_i - 1; otherwise a(n) = 2*M.
Let k >= 1. Write k = 2^(e_0) * (q_1)^(e_1) * ... * (q_s)^(e_s), e_j >= 1. Let N = Product_{j=1..s} (q_j)^(e_j+1):
(i) if e_0 = 0, then a(n) = k <=> n = (p_1) * ... * (p_r) * N, where: p_i != q_j, and for every 1 <= i <= r, there exists 1 <= j <= s such that q_j divides p_i - 1.
(ii) if e_0 = 1, then a(n) = k <=> (a) n = (p_1) * ... * (p_r) * N, where: p_i != q_j, and there exists 1 <= i <= r such that none of (q_j)'s divides p_i - 1; or (b) n = (4 or 8) * N * (an odd squarefree number coprime to N);
(iii) if e_0 >= 2, then a(n) = k <=> n = 2^(e_0+2) * N * (an odd squarefree number coprime to N).

cp's OEIS Frontend

A007431 a(n) = Sum_{d|n} phi(d)*mu(n/d).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A354061 Irregular table read by rows: T(n,k) is the number of degree-k primitive Dirichlet characters modulo n, 1 <= k <= psi(n), psi = A002322.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A354257 a(n) is the smallest k such that there exists a degree-k primitive Dirichlet characters modulo n, or -1 no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula