A008578 Prime numbers at the beginning of the 20th century (today 1 is no longer regarded as a prime).

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271

Offset

1,2

Comments

1 together with the primes; also called the noncomposite numbers.

Also largest sequence of nonnegative integers with the property that the product of 2 or more elements with different indices is never a square. - Ulrich Schimke (ulrschimke(AT)aol.com), Dec 12 2001 [Comment corrected by Farideh Firoozbakht, Aug 03 2014]

Numbers k whose largest divisor <= sqrt(k) equals 1. (See also A161344, A161345, A161424.) - Omar E. Pol, Jul 05 2009

Numbers k such that d(k) <= 2. - Juri-Stepan Gerasimov, Oct 17 2009

Also first column of array in A163280. Also first row of array in A163990. - Omar E. Pol, Oct 24 2009

Possible values of A136548(m) in increasing order, where A136548(m) = the largest numbers h such that A000203(h) <= k (k = 1,2,3,...), where A000203(h) = sum of divisors of h. - Jaroslav Krizek, Mar 01 2010

Where record values of A022404 occur: A086332(n)=A022404(a(n)). - Reinhard Zumkeller, Jun 21 2010

Positive integers that have no divisors other than 1 and itself (the old definition of prime numbers). - Omar E. Pol, Aug 10 2012

Conjecture: the sequence contains exactly those k such that sigma(k) > k*BigOmega(k). - Irina Gerasimova, Jun 08 2013

Note on the Gerasimova conjecture: all terms in the sequence obviously satisfy the inequality, because sigma(p) = 1+p and BigOmega(p) = 1 for primes p, so 1+p > p*1. For composites, the (opposite) inequality is heuristically correct at least up to k <= 4400000. The general proof requires to show that BigOmega(k) is an upper limit of the abundancy sigma(k)/k for composite k. This proof is easy for semiprimes k=p1*p2 in general, where sigma(k)=1+p1+p2+p1*p2 and BigOmega(k)=2 and p1, p2 <= 2. - R. J. Mathar, Jun 12 2013

Numbers k such that phi(k) + sigma(k) = 2k. - Farideh Firoozbakht, Aug 03 2014

isA008578(n) <=> k is prime to n for all k in {1,2,...,n-1}. - Peter Luschny, Jun 05 2017

In 1751 Leonhard Euler wrote: "Having so established this sign S to indicate the sum of the divisors of the number in front of which it is placed, it is clear that, if p indicates a prime number, the value of Sp will be 1 + p, except for the case where p = 1, because then we have S1 = 1, and not S1 = 1 + 1. From this we see that we must exclude unity from the sequence of prime numbers, so that unity, being the start of whole numbers, it is neither prime nor composite." - Omar E. Pol, Oct 12 2021

a(1) = 1; for n >= 2, a(n) is the least unused number that is coprime to all previous terms. - Jianing Song, May 28 2022

A number p is preprime if p = a*b ==> a = 1 or b = 1. This sequence lists the preprimes in the commutative monoid IN \ {0}. - Peter Luschny, Aug 26 2022

References

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.

G. Chrystal, Algebra: An Elementary Textbook. Chelsea Publishing Company, 7th edition, (1964), chap. III.7, p. 38.

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 11.

H. D. Huskey, Derrick Henry Lehmer [1905-1991]. IEEE Ann. Hist. Comput. 17 (1995), no. 2, 64-68. Math. Rev. 96b:01035

D. H. Lehmer, The sieve problem for all-purpose computers. Math. Tables and Other Aids to Computation, Math. Tables and Other Aids to Computation, 7, (1953). 6-14. Math. Rev. 14:691e

D. N. Lehmer, "List of Prime Numbers from 1 to 10,006,721", Carnegie Institute, Washington, D.C. 1909.

R. F. Lukes, C. D. Patterson and H. C. Williams, Numerical sieving devices: their history and some applications. Nieuw Arch. Wisk. (4) 13 (1995), no. 1, 113-139. Math. Rev. 96m:11082

Williams, H. C.; Shallit, J. O. Factoring integers before computers. Mathematics of Computation 1943-1993: a half-century of computational mathematics (Vancouver, BC, 1993), 481-531, Proc. Sympos. Appl. Math., 48, AMS, Providence, RI, 1994. Math. Rev. 95m:11143

Links

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]

Chris K. Caldwell, Angela Reddick, Yeng Xiong and Wilfrid Keller, The History of the Primality of One: A Selection of Sources, (a dynamic survey), Journal of Integer Sequences, Vol. 15 (2012), #12.9.8.

C. K. Caldwell and Y. Xiong, What is the smallest prime?, arXiv preprint arXiv:1209.2007 [math.HO], 2012, and J. Int. Seq. 15 (2012) #12.9.6

Leonhard Euler, Découverte d’une loi tout extraordinaire des nombres, par rapport à la somme de leurs diviseurs, in Bibliothèque impartiale, 3, 1751, pp. 10-31. Reprinted in Opera Postuma, 1, 1862, p.76-84. Number 175 in the Eneström index.

G. P. Michon, Is 1 a prime number?

Omar E. Pol, Illustration of initial terms

Omar E. Pol, Illustration of initial terms of A008578, A161344, A161345, A161424

PrimeFan, Arguments for and against the primality of 1

A. Reddick and Y. Xiong, The search for one as a prime number: from ancient Greece to modern times, Electronic Journal of Undergraduate Mathematics, Volume 16, 1 { 13, 2012. - From N. J. A. Sloane, Feb 03 2013

J. Todd, Review of Lehmer's tables, Mathematical Tables and Other Aids to Computation, Vol. 11, No. 60, (1957) (on JSTOR.org).

Wikipedia, "Complete" sequence. [Wikipedia calls a sequence "complete" (sic) if every positive integer is a sum of distinct terms. This name is extremely misleading and should be avoided. - N. J. A. Sloane, May 20 2023]

Wikipedia, Dirichlet convolution

Formula

a(n) = A000040(n-1).

m is in the sequence iff sigma(m) + phi(m) = A065387(m) = 2m. - Farideh Firoozbakht, Jan 27 2005

a(n) = A158611(n+1) for n >= 1. - Jaroslav Krizek, Jun 19 2009

In the following formulas (based on emails from Jaroslav Krizek and R. J. Mathar), the star denotes a Dirichlet convolution between two sequences, and "This" is A008578.

This = A030014 * A008683. (Dirichlet convolution using offset 1 with A030014)

This = A030013 * A000012. (Dirichlet convolution using offset 1 with A030013)

This = A034773 * A007427. (Dirichlet convolution)

This = A034760 * A023900. (Dirichlet convolution)

This = A034762 * A046692. (Dirichlet convolution)

This * A000012 = A030014. (Dirichlet convolution using offset 1 with A030014)

This * A008683 = A030013. (Dirichlet convolution using offset 1 with A030013)

This * A000005 = A034773. (Dirichlet convolution)

This * A000010 = A034760. (Dirichlet convolution)

This * A000203 = A034762. (Dirichlet convolution)

A002033(a(n))=1. - Juri-Stepan Gerasimov, Sep 27 2009

a(n) = A181363((2*n-1)*2^k), k >= 0. - Reinhard Zumkeller, Oct 16 2010

a(n) = A001747(n)/2. - Omar E. Pol, Jan 30 2012

A060448(a(n)) = 1. - Reinhard Zumkeller, Apr 05 2012

A086971(a(n)) = 0. - Reinhard Zumkeller, Dec 14 2012

Sum_{n>=1} x^a(n) = (Sum_{n>=1} (A002815(n)*x^n))*(1-x)^2. - L. Edson Jeffery, Nov 25 2013

Maple

A008578 := n->if n=1 then 1 else ithprime(n-1); fi :

Mathematica

Join[ {1}, Table[ Prime[n], {n, 1, 60} ] ]
NestList[ NextPrime, 1, 57] (* Robert G. Wilson v, Jul 21 2015 *)
oldPrimeQ[n_] := AllTrue[Range[n-1], CoprimeQ[#, n]&];
Select[Range[271], oldPrimeQ] (* Jean-François Alcover, Jun 07 2017, after Peter Luschny *)

Prog

(PARI) is(n)=isprime(n)||n==1
(Magma) [1] cat [n: n in PrimesUpTo(271)];  // Bruno Berselli, Mar 05 2011
(Haskell)
a008578 n = a008578_list !! (n-1)
a008578_list = 1 : a000040_list
-- Reinhard Zumkeller, Nov 09 2011
(Sage)
isA008578 = lambda n: all(gcd(k, n) == 1 for k in (1..n-1))
print([n for n in (1..271) if isA008578(n)]) # Peter Luschny, Jun 07 2017
(GAP)
A008578:=Concatenation([1], Filtered([1..10^5], IsPrime)); # Muniru A Asiru, Sep 07 2017

Crossrefs

The main entry for this sequence is A000040.

The complement of A002808.

Cf. A000732 (boustrophedon transform).

Cf. A000010, A000203.

Cf. A023626 (self-convolution).

Sequence in context: A226159 A182986 A000040 * A216883 A216884 A216885

Adjacent sequences: A008575 A008576 A008577 * A008579 A008580 A008581

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved