cp's OEIS Frontend

A005579 a(n) = smallest number k such that Product_{i=1..k} prime(i)/(prime(i)-1) > n.

%I A005579 M0573 #61 Apr 18 2025 09:57:29
%S A005579 0,1,2,3,4,6,9,14,22,35,55,89,142,230,373,609,996,1637,2698,4461,7398,
%T A005579 12301,20503,34253,57348,96198,161659,272124,458789,774616,1309627,
%U A005579 2216968,3757384,6375166,10828012,18409028,31326514,53354259,90945529,155142139
%N A005579 a(n) = smallest number k such that Product_{i=1..k} prime(i)/(prime(i)-1) > n.
%C A005579 Laatsch (1986) proved that for n >= 2, a(n) gives the smallest number of distinct prime factors in even numbers having an abundancy index > n.
%C A005579 The abundancy index of a number k is sigma(k)/k. - _T. D. Noe_, May 08 2006
%C A005579 The first differences of this sequence, A005347, begin the same as the Fibonacci sequence A000045. - _T. D. Noe_, May 08 2006
%C A005579 Equal to A256968 except for n = 2 and n = 3.  See comment in A256968. - _Chai Wah Wu_, Apr 17 2015
%D A005579 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005579 Amiram Eldar, <a href="/A005579/b005579.txt">Table of n, a(n) for n = 0..44</a>
%H A005579 Richard K. Guy, <a href="/A000081/a000081.pdf">Letter to N. J. A. Sloane, 1988-04-12</a> (annotated scanned copy).
%H A005579 Richard K. Guy and N. J. A. Sloane, <a href="/A005180/a005180.pdf">Correspondence</a>, 1988.
%H A005579 Richard Laatsch, <a href="http://www.jstor.org/stable/2690424">Measuring the abundancy of integers</a>, Mathematics Magazine 59 (2) (1986) 84-92.
%H A005579 Popular Computing (Calabasas, CA), <a href="/A256968/a256968.png">Problem 182 (Suggested by Victor Meally)</a>, Annotated and scanned copy of page 10 of Vol. 5 (No. 53, Aug 1977).
%F A005579 a(n) = smallest k such that A002110(k)/A005867(k) > n. - _Artur Jasinski_, Nov 06 2008
%F A005579 a(n) = PrimePi(A091440(n)) = A000720(A091440(n)) for n >= 4. - _Amiram Eldar_, Apr 18 2025
%e A005579 The products Product_{i=1..k} prime(i)/(prime(i)-1) for k >= 0 start with 1, 2, 3, 15/4, 35/8, 77/16, 1001/192, 17017/3072, 323323/55296, 676039/110592, 2800733/442368, 86822723/13271040, 3212440751/477757440, 131710070791/19110297600, 5663533044013/802632499200, ... = A060753/A038110. So a(3) = 3.
%t A005579 (* For speed and accuracy, the second Mathematica program uses 30-digit real numbers and interval arithmetic. *)
%t A005579 prod=1; k=0; Table[While[prod<=n, k++; prod=prod*Prime[k]/(Prime[k]-1)]; k, {n,0,25}] (* _T. D. Noe_, May 08 2006 *)
%t A005579 prod=Interval[1]; k=0; Table[While[Max[prod]<=n, k++; p=Prime[k]; prod=N[prod*p/(p-1),30]]; If[Min[prod]>n, k, "too few digits"], {n,0,38}]
%o A005579 (PARI) a(n)=my(s=1,k); forprime(p=2,, s*=p/(p-1); k++; if(s>n, return(k))) \\ _Charles R Greathouse IV_, Aug 20 2015
%o A005579 (Python)
%o A005579 from sympy import nextprime
%o A005579 def a_list(upto: int) -> list[int]:
%o A005579     L: list[int] = [0]
%o A005579     count = 1; bn = 1; bd = 1; p = 2
%o A005579     for k in range(1, upto + 1):
%o A005579         bn *= p
%o A005579         bd *= p - 1
%o A005579         while bn > count * bd:
%o A005579             L.append(k)
%o A005579             count += 1
%o A005579         p = nextprime(p)
%o A005579     return L
%o A005579 print(a_list(1000))  # _Chai Wah Wu_, Apr 17 2015, adapted by _Peter Luschny_, Jan 25 2025
%Y A005579 A001611 is similar but strictly different.
%Y A005579 Cf. A000720, A001611, A005580, A060753, A023199, A038110, A072986, A091440, A256968.
%K A005579 nonn
%O A005579 0,3
%A A005579 _N. J. A. Sloane_, _R. K. Guy_
%E A005579 Edited by _T. D. Noe_, May 08 2006
%E A005579 a(26) added by _T. D. Noe_, Sep 18 2008
%E A005579 Typo corrected by Vincent E. Yu (yu.vincent.e(AT)gmail.com), Aug 14 2009
%E A005579 a(27)-a(36) from Vincent E. Yu (yu.vincent.e(AT)gmail.com), Aug 14 2009
%E A005579 Comment corrected by _T. D. Noe_, Apr 04 2010
%E A005579 a(37)-a(39) from _T. D. Noe_, Nov 16 2010
%E A005579 Edited and terms a(0)-a(1) prepended by _Max Alekseyev_, Jan 25 2025