login
Least positive k such that 2n - p is prime where p is some prime divisor of n^k - 1, or 0 if no such k exists.
0

%I #19 Apr 09 2019 05:09:42

%S 0,0,0,1,2,1,1,2,2,1,1,1,1,2,1,1,2,1,6,2,1,1,2,2,1,1,1,1,2,1,1,2,4,2,

%T 1,1,1,2,1,1,2,1,1,2,1,1,1,2,3,2,1,1,2,2,1,1,1,1,1,1,3,10,3,3,2,1,1,2,

%U 2,1,1,1,2,10,1,1,2,1,3,2,1,6,2,2,1,1,1,1,1,2

%N Least positive k such that 2n - p is prime where p is some prime divisor of n^k - 1, or 0 if no such k exists.

%C Conjecture: a(n) >= 1 for n >= 4.

%C Records: a(4) = 1, a(5) = 2, a(19) = 6, a(62) = 10, a(166) = 18, ...

%C For n >= 4, a(n) < b(n) where b(n) is the smallest m > 1 such that q(2n - q) is some semiprime divisor of n^m - 1, or 0 if no such m exists: 0, 0, 0, 2, 6, 2, 10, 4, 6, 6, 6, 2, 11, 22, 22, 7, 4, 2, 30, 35, 18, 30, 20, 42, 9, 40, 8, 13, 26, 2, 42, 12, 20, 10, 52, 21, 3, 36, 42, 11, 26, 2, 24, 82, 21, 12, 44, 88, 39, 8, 32, 25, 88, 24, 30, 25, 20, 96, 88, 2, 54, 220, 48, 6, ... (from Goldbach's problem).

%e a(4) = 1 because 4^1 - 1 = 3 where 3 is some prime divisor of 3 and 2*4 - 3 = 5 is prime;

%e a(5) = 2 because 5^2 - 1 = 24 where 3 is some prime divisor of 24 and 2*5 - 3 = 7 is prime.

%t Table[If[n < 4, 0, Block[{k = 1}, While[NoneTrue[FactorInteger[n^k - 1][[All, 1]], PrimeQ[2 n - #] &], k++]; k]], {n, 104}] (* _Michael De Vlieger_, Mar 11 2019 *)

%o (PARI) isok(n,k) = {my(pf=factor(n^k-1, 2*n)[,1]); for (j=1, #pf, if (isprime(2*n-pf[j]), return (1)););}

%o a(n) = {if (n < 4, return(0)); my(k=1); while (!isok(n, k), k++); k;} \\ _Michel Marcus_, Mar 02 2019

%Y Cf. A306261.

%K nonn

%O 1,5

%A _Juri-Stepan Gerasimov_, Feb 28 2019