login
Smallest number m such that m*(m+1) has at least n distinct prime factors.
6

%I #81 Jun 24 2023 04:16:41

%S 1,2,5,14,65,209,714,7314,38570,254540,728364,11243154,58524465,

%T 812646120,5163068910,58720148850,555409903685,4339149420605,

%U 69322940121435,490005293940084,5819629108725509,76622240600506314

%N Smallest number m such that m*(m+1) has at least n distinct prime factors.

%C The original definition left unclear whether "at least" or "exactly" n prime factors are required. Now the "at least" variant was chosen, for the other variant ("exactly"), see A069354: At least up to a(18), both criteria yield the same number, and therefore a(n) = A069354(n) - 1, since m and m+1 are always coprime. - _M. F. Hasler_, Jan 15 2014

%C 10^13 < a(19) <= 69322940121435. - _Giovanni Resta_, Mar 24 2020

%C Terms a(1)-a(10) appear in Erdős and Nicolas (1978-1979). - _Amiram Eldar_, Jun 24 2023

%H Michael S. Branicky, <a href="/A059958/a059958.py.txt">Python program</a>.

%H Paul Erdős and Jean-Louis Nicolas, <a href="http://www.numdam.org/item/?id=SDPP_1978-1979__20_2_A9_0">Sur la fonction "nombre de facteurs premiers de n"</a>, Séminaire Delange-Pisot-Poitou, Théorie des nombres, Vol. 20, No. 2 (1978-1979), Talk no. 32, pp. 1-19. See p. 10.

%F a(n) = Min_{ m | A001221(m*(m+1)) >= n }.

%F a(n) <= A002110(n) - 1 because A001221((q-1)*q) >= n+1 for q = A002110(n).

%F Conjecture: a(n) = A069354(n) - 1. - _Robert G. Wilson v_, Feb 18 2014

%e For n = 9, a(9)*(a(9) + 1) = 38570*38571 = (2*5*7*19*29)*(3*13*23*43) with 9 distinct prime factors.

%t With[{s = Map[PrimeNu[Times @@ #] &, Partition[Range[10^6], 2, 1]]}, Array[FirstPosition[s, n_/; n>=#][[1]] &, Max@ s]] (* _Michael De Vlieger_, Nov 02 2017 *)

%o (PARI) a(n) = my(m=1); while(omega(m*(m+1)) < n, m++); m; \\ _Michel Marcus_, Jul 09 2018

%Y Cf. A001221, A002110, A006549, A054989, A083002, A232096, A232097.

%K nonn,more

%O 1,2

%A _Labos Elemer_, Mar 02 2001

%E More terms from _William Rex Marshall_, Mar 18 2001

%E Offset corrected and a(15)-a(16) from _Donovan Johnson_, Jan 31 2009

%E a(17) from _Donovan Johnson_, Sep 15 2010

%E a(18) from _Don Reble_, Jan 15 2014

%E Edited by _M. F. Hasler_, Jan 15 2014

%E a(19)-a(20) from _Michael S. Branicky_, Feb 08 2023

%E a(21) from _Michael S. Branicky_, Feb 10 2023

%E a(22) from _Michael S. Branicky_, Feb 23 2023