A336016 - OEIS

%I #16 Aug 17 2020 22:47:02

%S 0,1,3,5,8,19,22,51,89,145,263,453,851,1575,2880,5469,10338,19115,

%T 35782,67569,128601,243600,463840,883589

%N a(n) is the number of primes q less than primorial(n) having k = 2 as the least exponent such that q^k == 1 (mod primorial(n)).

%C a(n) = length of row n of A336015 for n > 1.

%e a(4) = 5 as there are 5 primes q coprime to primorial(4) = 210 such that 2 is the least positive integer exponent k where q^k == 1 (mod 210). Those primes are 29, 41, 71, 139, 181 and indeed we have 29^2 == 1 (mod 210), 41^2 == 1 (mod 210), 71^2 == 1 (mod 210), 139^2 == 1 (mod 210) and 181^2 == 1 (mod 210) and no more below 210. So as these are five such primes in row 4, a(4) = 5. - _David A. Corneth_, Aug 15 2020

%t Table[Block[{P = #, k = 0}, Do[If[MultiplicativeOrder[Prime@ i, P] == 2, k++], {i, PrimePi[n + 1], PrimePi[P - 1]}]; k] &@ Product[Prime@ j, {j, n}], {n, 8}]

%o (PARI) a(n) = {if(n <= 2, return(n-1)); my(pp = vecprod(primes(n))/2, d = divisors(pp), res = 0); for(i = 1, #d, c = lift(chinese(Mod(-1, d[i]), Mod(1, pp/d[i]))); forstep(i = c, pp*2, pp, if(isprime(i), res++ ) ) ); res } \\ _David A. Corneth_, Aug 16 2020

%Y Cf. A000010, A002110, A005867, A131577, A336015.

%K nonn,more

%O 1,3

%A _Michael De Vlieger_, _David James Sycamore_, _David A. Corneth_, Jul 10 2020

%E New name from _David A. Corneth_, Aug 15 2020