A005867 a(0) = 1; for n > 0, a(n) = (prime(n)-1)*a(n-1).

1, 1, 2, 8, 48, 480, 5760, 92160, 1658880, 36495360, 1021870080, 30656102400, 1103619686400, 44144787456000, 1854081073152000, 85287729364992000, 4434961926979584000, 257227791764815872000, 15433667505888952320000

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Local minima of Euler's phi function. - Walter Nissen

Number of potential primes in a modulus primorial(n+1) sieve. - Robert G. Wilson v, Nov 20 2000

Let p=prime(n) and let p# be the primorial (A002110), then it can be shown that any p# consecutive numbers have exactly a(n-1) numbers whose lowest prime factor is p. For a proof, see the "Proofs Regarding Primorial Patterns" link. For example, if we let p=7 and consider the interval [101,310] containing 210 numbers, we find the 8 numbers 119, 133, 161, 203, 217, 259, 287, 301. - Dennis Martin (dennis.martin(AT)dptechnology.com), Jul 16 2006

From Gary W. Adamson, Apr 21 2009: (Start)

Equals (-1)^n * (1, 1, 1, 2, 8, 48, ...) dot (-1, 2, -3, 5, -7, 11, ...).

a(6) = 480 = (1, 1, 1, 2, 8, 48) dot (-1, 2, -3, 5, -7, 11) = (-1, 2, -3, 10, -56, 528). (End)

It can be proved that there are at least T prime numbers less than N, where the recursive function T is: T = N - N*Sum_{i=0..T(sqrt(N))} A005867(i)/A002110(i). This can show for example that at least 0.16*N numbers are primes less than N for 29^2 > N > 23^2. - Ben Paul Thurston, Aug 23 2010

First column of A096294. - Eric Desbiaux, Jun 20 2013

Conjecture: The g.f. for the prime(n+1)-rough numbers (A000027, A005408, A007310, A007775, A008364, A008365, A008366, A166061, A166063) is x*P(x)/(1-x-x^a(n)+x^(a(n)+1)), where P(x) is an order a(n) polynomial with symmetric coefficients (i.e., c(0)=c(n), c(1)=c(n-1), ...). - Benedict W. J. Irwin, Mar 18 2016

a(n)/A002110(n+1) (primorial(n+1)) is the ratio of natural numbers whose smallest prime factor is prime(n+1); i.e., prime(n+1) coprime to A002110(n). So the ratio of even numbers to natural numbers = 1/2; odd multiples of 3 = 1/6; multiples of 5 coprime to 6 (A084967) = 2/30 = 1/15; multiples of 7 coprime to 30 (A084968) = 8/210 = 4/105; etc. - Bob Selcoe, Aug 11 2016

The 2-adic valuation of a(n) is A057773(n), being sum of the 2-adic valuations of the product terms here. - Kevin Ryde, Jan 03 2023

For n > 1, a(n) is the number of prime(n+1)-rough numbers in [1, primorial(prime(n))]. - Alexandre Herrera, Aug 29 2023

Examples

			a(3): the mod 30 prime remainder set sieve representation yields the remainder set: {1, 7, 11, 13, 17, 19, 23, 29}, 8 elements.
		

References

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

Links

• T. D. Noe, Table of n, a(n) for n = 0..99
• Larry Deering, The Black Key Sieve, Box 275, Bellport NY 11713-0275, 1998.
• Alphonse de Polignac, Six propositions arithmologiques déduites du crible d'Ératosthène, Nouvelles annales de mathématiques : journal des candidats aux écoles polytechnique et normale, Série 1, Tome 8 (1849), pp. 423-429. See p. 425.
• Frank Ellermann, Illustration for A002110, A005867, A038110, A060753.
• Ken Hicks and Kevin Ward, Series and Product Relations Made from Primes, arXiv:2108.03268 [math.NT], 2021.
• Dennis Martin, Proofs Regarding Primorial Patterns [via Internet Archive Wayback-machine]
• Dennis Martin, Proofs Regarding Primorial Patterns [Cached copy, with permission of the author]
• Francis E. Masat, Letter to N. J. A. Sloane with attachment: "A note on prime number sequences" (unpublished manuscript), Apr. 1991.
• Travis Near, Improving MATLAB's isprime performance without arbitrary-precision arithmetic, arXiv:2108.04791 [cs.MS], 2021.
• John K. Sellers, Distribution of twin primes in repeating sequences of prime factors, arXiv:2108.00288 [math.GM], 2021. See Table 1 p. 11.
• Andrew V. Sutherland, Order Computations in Generic Groups, Ph. D. Dissertation, Math. Dept., M.I.T., 2007.

Crossrefs

Cf. A000010, A002110, A006093, A054640, A058254, A055768, A070918, A101301, A058251, A060753.

Cf. A057773 (2-adic valuation).

Column 1 of A281890.

Cf. A016035, A345974.

Programs

Haskell

a005867 n = a005867_list !! n
a005867_list = scanl (*) 1 a006093_list
-- Reinhard Zumkeller, May 01 2013

Maple

A005867 := proc(n)
    mul(ithprime(j)-1,j=1..n) ;
end proc: # Zerinvary Lajos, Aug 24 2008, R. J. Mathar, May 03 2017

Mathematica

Table[ Product[ EulerPhi[ Prime[ j ] ], {j, 1, n} ], {n, 1, 20} ]
RecurrenceTable[{a[0]==1,a[n]==(Prime[n]-1)a[n-1]},a,{n,20}] (* Harvey P. Dale, Dec 09 2013 *)
EulerPhi@ FoldList[Times, 1, Prime@ Range@ 18] (* Michael De Vlieger, Mar 18 2016 *)

PARI

for(n=0, 22, print1(prod(k=1,n, prime(k)-1), ", "))

Formula

a(n) = phi(product of first n primes) = A000010(A002110(n)).

a(n) = Product_{k=1..n} (prime(k)-1) = Product_{k=1..n} A006093(n).

Sum_{n>=0} a(n)/A002110(n+1) = 1. - Bob Selcoe, Jan 09 2015

a(n) = A002110(n)-((1/A000040(n+1) - A038110(n+1)/A038111(n+1))*A002110(n+1)). - Jamie Morken, Mar 27 2019

a(n) = |Sum_{k=0..n} A070918(n,k)|. - Alois P. Heinz, Aug 18 2019

a(n) = A058251(n)/A060753(n+1). - Jamie Morken, Apr 25 2022

a(n) = A002110(n) - A016035(A002110(n)) - 1 for n >= 1. - David James Sycamore, Sep 07 2024

Sum_{n>=0} 1/a(n) = A345974. - Amiram Eldar, Jun 26 2025

Extensions

Offset changed to 0, Name changed, and Comments and Examples sections edited by T. D. Noe, Apr 04 2010