A306615 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, 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, 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, 2, 1, 1, 1, 2, 10, 1, 1, 2, 1, 3, 2, 1, 6, 2, 2, 1, 1, 1, 1, 1, 2

Offset: 1

Author

Juri-Stepan Gerasimov, Feb 28 2019

Keywords

• nonn

Comments

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

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

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

Examples

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

Crossrefs

Cf. A306261.

Programs

Mathematica

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

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)););}
a(n) = {if (n < 4, return(0)); my(k=1); while (!isok(n, k), k++); k;} \\ Michel Marcus, Mar 02 2019