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

0, 1, 2, 3, 4, 6, 9, 14, 22, 35, 55, 89, 142, 230, 373, 609, 996, 1637, 2698, 4461, 7398, 12301, 20503, 34253, 57348, 96198, 161659, 272124, 458789, 774616, 1309627, 2216968, 3757384, 6375166, 10828012, 18409028, 31326514, 53354259, 90945529, 155142139

Offset: 0

Author

N. J. A. Sloane, R. K. Guy

Keywords

• nonn

Comments

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.

The abundancy index of a number k is sigma(k)/k. - T. D. Noe, May 08 2006

The first differences of this sequence, A005347, begin the same as the Fibonacci sequence A000045. - T. D. Noe, May 08 2006

Equal to A256968 except for n = 2 and n = 3. See comment in A256968. - Chai Wah Wu, Apr 17 2015

Examples

			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.
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Amiram Eldar, Table of n, a(n) for n = 0..44
• Richard K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy).
• Richard K. Guy and N. J. A. Sloane, Correspondence, 1988.
• Richard Laatsch, Measuring the abundancy of integers, Mathematics Magazine 59 (2) (1986) 84-92.
• Popular Computing (Calabasas, CA), Problem 182 (Suggested by Victor Meally), Annotated and scanned copy of page 10 of Vol. 5 (No. 53, Aug 1977).

Crossrefs

A001611 is similar but strictly different.

Cf. A000720, A001611, A005580, A060753, A023199, A038110, A072986, A091440, A256968.

Programs

Mathematica

(* For speed and accuracy, the second Mathematica program uses 30-digit real numbers and interval arithmetic. *)
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 *)
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}]

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

Python

from sympy import nextprime
def a_list(upto: int) -> list[int]:
    L: list[int] = [0]
    count = 1; bn = 1; bd = 1; p = 2
    for k in range(1, upto + 1):
        bn *= p
        bd *= p - 1
        while bn > count * bd:
            L.append(k)
            count += 1
        p = nextprime(p)
    return L
print(a_list(1000))  # Chai Wah Wu, Apr 17 2015, adapted by Peter Luschny, Jan 25 2025

Formula

a(n) = smallest k such that A002110(k)/A005867(k) > n. - Artur Jasinski, Nov 06 2008

a(n) = PrimePi(A091440(n)) = A000720(A091440(n)) for n >= 4. - Amiram Eldar, Apr 18 2025

Extensions

Edited by T. D. Noe, May 08 2006

a(26) added by T. D. Noe, Sep 18 2008

Typo corrected by Vincent E. Yu (yu.vincent.e(AT)gmail.com), Aug 14 2009

a(27)-a(36) from Vincent E. Yu (yu.vincent.e(AT)gmail.com), Aug 14 2009

Comment corrected by T. D. Noe, Apr 04 2010

a(37)-a(39) from T. D. Noe, Nov 16 2010

Edited and terms a(0)-a(1) prepended by Max Alekseyev, Jan 25 2025