A059957 Sum of number of distinct prime factors of n and n+1, or number of distinct prime factors of n(n+1) or of lcm(n,n+1).

1, 2, 2, 2, 3, 3, 2, 2, 3, 3, 3, 3, 3, 4, 3, 2, 3, 3, 3, 4, 4, 3, 3, 3, 3, 3, 3, 3, 4, 4, 2, 3, 4, 4, 4, 3, 3, 4, 4, 3, 4, 4, 3, 4, 4, 3, 3, 3, 3, 4, 4, 3, 3, 4, 4, 4, 4, 3, 4, 4, 3, 4, 3, 3, 5, 4, 3, 4, 5, 4, 3, 3, 3, 4, 4, 4, 5, 4, 3, 3, 3, 3, 4, 5, 4, 4, 4, 3, 4, 5, 4, 4, 4, 4, 4, 3, 3, 4, 4, 3, 4, 4, 3, 5, 5

Offset

1,2

Comments

If a(n) = 2, then n is in A006549 (Mersenne primes, Fermat primes - 1, or 8).

If a(n) = 2, then n is in A006549, being either a Mersenne prime, a Fermat prime minus one, or n=8, corresponding to the unique solution to Catalan's equation, 3^2 = 2^3 + 1. - Gene Ward Smith, Sep 07 2006

a(n-1), n > 2, is the number of maximal subsemigroups of the monoid of orientation-preserving partial injective mappings on a set with n elements. - Wilf A. Wilson, Jul 21 2017

Links

G. C. Greubel, Table of n, a(n) for n = 1..10000

James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [Wilf A. Wilson, Jul 21 2017]

Formula

a(n) = A001221(A002378(n)) = A001221(n*(n+1)) = A001221(n)+A001221(n+1) because gcd(n, n+1) = 1.

Sum_{k=1..n} a(k) = 2*n * (log(log(n)) + B) + O(n/log(n)), where B is Mertens's constant (A077761). - Amiram Eldar, Sep 29 2024

Example

For n = 30030, n has 6 prime factors, 30031 = 59*509 so a(30030) = 6+2 = 8.
For n = 30029, a(30029) = 1+6 = 7.

Mathematica

Table[ PrimeNu[n*(n + 1)], {n, 1, 100}] (* G. C. Greubel, May 13 2017 *)

Prog

(PARI) a(n) = omega(n*(n+1)) \\ G. C. Greubel, May 13 2017

Crossrefs

Cf. A006549, A001221, A002378, A077761.

Sequence in context: A317369 A096916 A098014 * A382733 A361088 A165924

Adjacent sequences: A059954 A059955 A059956 * A059958 A059959 A059960

Keyword

nonn,easy

Author

Labos Elemer, Mar 02 2001

Extensions

Name corrected by Rick L. Shepherd, Apr 11 2023

Status

approved