A085723 Number of prime divisors of n^n+1 (counted with multiplicity).

1, 1, 3, 1, 3, 3, 5, 3, 4, 3, 7, 4, 5, 6, 9, 2, 4, 9, 6, 3, 6, 4, 10, 6, 7, 5, 12, 6, 7, 10, 11, 4, 11, 6, 15, 5, 7, 8, 10, 10, 6, 10, 9, 8, 14, 8, 13, 6, 8, 10, 12, 5, 10, 14, 13, 7, 13, 13, 10, 12, 8, 7, 24, 4, 12, 8, 8, 7, 17, 10, 11, 12, 4, 8, 25, 7, 9, 14, 10, 5, 12, 7, 13, 8

Offset: 1

Author

Jason Earls, Jul 20 2003

Keywords

• nonn
• hard

Comments

16^16+1 = 274177 * 67280421310721 is a semiprime. Where is the next?

a(73) >= 4. - Donovan Johnson, Sep 27 2010

According to factordb there are currently no other known candidates for semiprimes, with 781^781+1 being the largest fully factored number of this form. - Hugo Pfoertner, Aug 24 2019

Examples

			a(3) = 3: 3^3 + 1 = 28 = 2^2 * 7.
a(4) = 1: 4^4 + 1 = 257 is prime.
a(5) = 3: 5^5 + 1 = 3126 = 2 * 3 * 521.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..148 (terms 1..123 from Chai Wah Wu)
• factordb, Factors of n^n+1.

Crossrefs

Cf. A001222, A007571, A014566, A055385, A121270, A309941, A344869.

Programs

PARI

for(k=1, 60, print1(bigomega(k^k+1),", ")) \\ Hugo Pfoertner, Aug 24 2019

Formula

a(n) = A001222(A014566(n)). - Amiram Eldar, Sep 27 2024

Extensions

More terms from Ray G. Opao, Aug 25 2004

Corrected 8 existing terms and a(46)-a(72) from Donovan Johnson, Sep 27 2010

a(73)-a(84) added by Hugo Pfoertner, Aug 24 2019