A394626 - OEIS

%I #18 Apr 21 2026 09:08:20

%S 3,5,8,9,11,12,13,15,17,19,22,23,25,27,28,29,30,31,32,33,34,35,37,39,

%T 42,44,45,46,48,49,50,51,52,53,55,58,59,60,61,62,63,64,65,67,69,71,75,

%U 76,77,78,79,80,81,82,85,86,87,88,89,91,92,93,95,96,97,98,100,101,102,103,104,105

%N Numbers k such that k^2 + 1 has a prime factor between k and k^2.

%C Equivalently, k such that k^2 + 1 is composite (cf. A134407) and has a prime factor > k, or: such that k < gpf(k^2 + 1) < k^2, where gpf = A006530 = greatest prime factor.

%C The sequence starts similar to A134427 (numbers such that k^2 + 1 is composite and squarefree), but for example 21 is in that but not in this sequence, since 21^2 + 1 = 2*13*17.

%C This sequence could be relevant for searching a number k such that gcd(k^2+1, k!+1) > 1: any such common divisor must be a prime between k and k^2. It is known that there is no small example, but probably there are, maybe around k ~ 10^17, cf. StackExchange link.

%H User "abacaba", <a href="https://math.stackexchange.com/a/4585306/">Re: Do we have Sum gcd(1+n!, 1+n^2)/n! = e?</a>, math.StackExchange, Nov. 26, 2022

%e 1^2 + 1 = 2, 2^2 + 1 = 5 and 4^2 + 1 = 17 are prime and therefore 1, 2 and 4 are not in this sequence.

%e 3^2 + 1 = 10 = 2*5 and 5 > 3, therefore 3 is in this sequence.

%e 5^2 + 1 = 26 = 2*13 and 13 > 5, therefore 5 is in this sequence.

%e 8^2 + 1 = 65 = 5*13 and 13 > 8, therefore 8 is in this sequence.

%t q[k_]:=AnyTrue[First/@FactorInteger[k^2+1],#>=k&&#<=k^2&];Select[Range[105],q] (* _James C. McMahon_, Apr 20 2026 *)

%o (PARI) select( {is_A394626(n)=n<(n=factor(n^2+1)[,1])[#n]&&#n>1}, [1..105]) \\ _M. F. Hasler_, Apr 09 2026

%Y Cf. A002522 (n^2 + 1), A134407 (n^2 + 1 composite), A005574 (n^2 + 1 prime), A006530 (gpf: greatest prime factor).

%K nonn

%O 1,1

%A _M. F. Hasler_, Apr 09 2026