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

3, 5, 8, 9, 11, 12, 13, 15, 17, 19, 22, 23, 25, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 53, 55, 58, 59, 60, 61, 62, 63, 64, 65, 67, 69, 71, 75, 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

Offset

1,1

Comments

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.

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.

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.

Links

Table of n, a(n) for n=1..72.

User "abacaba", Re: Do we have Sum gcd(1+n!, 1+n^2)/n! = e?, math.StackExchange, Nov. 26, 2022

Example

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.
3^2 + 1 = 10 = 2*5 and 5 > 3, therefore 3 is in this sequence.
5^2 + 1 = 26 = 2*13 and 13 > 5, therefore 5 is in this sequence.
8^2 + 1 = 65 = 5*13 and 13 > 8, therefore 8 is in this sequence.

Mathematica

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

Prog

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

Crossrefs

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

Sequence in context: A190205 A192884 A134427 * A065347 A376428 A085722

Adjacent sequences: A394623 A394624 A394625 * A394627 A394628 A394629

Keyword

nonn

Author

M. F. Hasler, Apr 09 2026

Status

approved