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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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.
• Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 84 at pp. 214-217.
• 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
• H. C. Williams and J. O. Shallit, 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

Crossrefs

The main entry for this sequence is A000040.

The complement of A002808.

Cf. A000732 (boustrophedon transform).

Cf. A000010, A000203.

Cf. A023626 (self-convolution).

Programs

GAP

A008578:=Concatenation([1],Filtered([1..10^5],IsPrime)); # Muniru A Asiru, Sep 07 2017

Haskell

a008578 n = a008578_list !! (n-1)
a008578_list = 1 : a000040_list
-- Reinhard Zumkeller, Nov 09 2011

Magma

[1] cat [n: n in PrimesUpTo(271)];  // Bruno Berselli, Mar 05 2011

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 *)

PARI

is(n)=isprime(n)||n==1

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

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