cp's OEIS Frontend

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.

%I A354257 #13 May 22 2022 00:02:08
%S A354257 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,
%T A354257 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,
%U A354257 -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
%N 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.
%C A354257 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).
%C A354257 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.
%H A354257 Jianing Song, <a href="/A354257/b354257.txt">Table of n, a(n) for n = 1..10000</a>
%F A354257 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):
%F A354257 (i) if e_0 = 1, then a(n) = -1;
%F A354257 (ii) if e_0 = 2, then a(n) = 2*M;
%F A354257 (iii) if e_0 >= 3, then a(n) = 2^(e_0-2)*M;
%F A354257 (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.
%F A354257 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):
%F A354257 (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.
%F A354257 (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);
%F A354257 (iii) if e_0 >= 2, then a(n) = k <=> n = 2^(e_0+2) * N * (an odd squarefree number coprime to N).
%e A354257 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.
%e A354257 a(63) = 3: there does not exist a linear or quadratic primitive Dirichlet characters modulo 63, but there are 4 cubic primitive Dirichlet characters.
%o A354257 (PARI) 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)))
%Y A354257 Cf. A354058, A354061, A008683.
%Y A354257 A354258 gives the earliest occurrence of each positive integers.
%Y A354257 Indices of 2: A003657 U A003658 \ {1}.
%K A354257 sign
%O A354257 1,3
%A A354257 _Jianing Song_, May 21 2022