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,3

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

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.

Formula

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

Example

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.

Prog

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

Crossrefs

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

Sequence in context: A337983 A332003 A145015 * A186422 A165027 A342341

Adjacent sequences: A085720 A085721 A085722 * A085724 A085725 A085726

Keyword

nonn,hard

Author

Jason Earls, Jul 20 2003

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

Status

approved