A110676 Number of prime factors with multiplicity of 1 + n^(n+1).

1, 2, 2, 3, 3, 4, 3, 6, 3, 5, 4, 5, 4, 9, 3, 4, 9, 3, 6, 10, 6, 7, 6, 11, 5, 11, 10, 5, 10, 8, 3, 12, 6, 10, 8, 5, 6, 13, 8, 6, 11, 6, 10, 16, 4, 4, 6, 9, 6, 11, 8, 4, 10, 10, 5, 13, 10, 7, 11, 6, 6, 21, 4, 23, 8, 6, 8, 16, 15, 7, 12, 7, 8, 19, 8, 13, 14, 5, 6, 20, 6, 10, 13, 12, 7, 9, 9, 6, 21

Offset

1,2

Comments

As also noticed by T. D. Noe, for odd n: 2 | a(n), for even n: (n+1)^2 | a(n). Coincidentally, a(74) includes 13 multidigit prime factors all of which end with the digit 1. There is no upper limit to this sequence, which rapidly becomes slow to compute. The derived sequences of n such that a(n) = k for any constant k > 2 do not yet appear in the OEIS. For instance, a(n) = 3 for n = 4, 5, 7, 9, 15, 18, 31, ... Is each such derived sequence finite?

Links

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

Formula

a(n) = A001222(A110567(n)) = A001222(1 + A007778(n)) = A001222(1 + (n^(n+1))).

Trivially a(n) << n log n. At most n^(n+1) + 1 is of the form 2*3^k. - Charles R Greathouse IV, Jun 24 2024

Example

a(1) = 1 because 1+1^2 = 2 is prime (and the only such prime).
a(2) = 2 because 1 + 2^3 = 9 = 3^2 which has (with multiplicity) two prime factors.
a(3) = 2 because 1 + 3^4 = 82 = 2 * 41 (the last such semiprime?).
a(4) = 3 because 1 + 4^5 = 1025 = 5^2 * 41 which has (with multiplicity) 3 prime factors.
a(8) = 6 because 1 + 8^9 = 134217729 = 3^4 * 19 * 87211.
a(14) = 9 because 1 + 14^15 = 155568095557812225 = 3^2 * 5^2 * 61 * 71 * 101 * 811 * 1948981.
a(1000) > 52.

Prog

(PARI) a(n) = bigomega(1+(n^(n+1))) \\ Georg Fischer, Jun 21 2024

Crossrefs

Cf. A001222, A007778, A110567.

Sequence in context: A291268 A242767 A027833 * A117171 A325356 A304706

Adjacent sequences: A110673 A110674 A110675 * A110677 A110678 A110679

Keyword

easy,nonn

Author

Jonathan Vos Post, Sep 14 2005

Extensions

a(13) and 3 other terms corrected by Georg Fischer, Jun 21 2024

Status

approved