%I #238 Aug 16 2024 16:42:57
%S 1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,
%T 89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,
%U 179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271
%N Prime numbers at the beginning of the 20th century (today 1 is no longer regarded as a prime).
%C 1 together with the primes; also called the noncomposite numbers.
%C 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]
%C Numbers k whose largest divisor <= sqrt(k) equals 1. (See also A161344, A161345, A161424.) - _Omar E. Pol_, Jul 05 2009
%C Numbers k such that d(k) <= 2. - _Juri-Stepan Gerasimov_, Oct 17 2009
%C Also first column of array in A163280. Also first row of array in A163990. - _Omar E. Pol_, Oct 24 2009
%C 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
%C Where record values of A022404 occur: A086332(n)=A022404(a(n)). - _Reinhard Zumkeller_, Jun 21 2010
%C Positive integers that have no divisors other than 1 and itself (the old definition of prime numbers). - _Omar E. Pol_, Aug 10 2012
%C Conjecture: the sequence contains exactly those k such that sigma(k) > k*BigOmega(k). - _Irina Gerasimova_, Jun 08 2013
%C 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
%C Numbers k such that phi(k) + sigma(k) = 2k. - _Farideh Firoozbakht_, Aug 03 2014
%C isA008578(n) <=> k is prime to n for all k in {1,2,...,n-1}. - _Peter Luschny_, Jun 05 2017
%C 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
%C 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
%C 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
%D 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.
%D Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 84 at pp. 214-217.
%D G. Chrystal, Algebra: An Elementary Textbook. Chelsea Publishing Company, 7th edition, (1964), chap. III.7, p. 38.
%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 11.
%D H. D. Huskey, Derrick Henry Lehmer [1905-1991]. IEEE Ann. Hist. Comput. 17 (1995), no. 2, 64-68. Math. Rev. 96b:01035
%D 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 D. N. Lehmer, "List of Prime Numbers from 1 to 10,006,721", Carnegie Institute, Washington, D.C. 1909.
%D 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
%D 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
%H Charles R Greathouse IV, <a href="/A008578/b008578.txt">Table of n, a(n) for n = 1..10000</a>
%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]
%H Chris K. Caldwell, Angela Reddick, Yeng Xiong, and Wilfrid Keller, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.html">The History of the Primality of One: A Selection of Sources</a>, (a dynamic survey), Journal of Integer Sequences, Vol. 15 (2012), #12.9.8.
%H C. K. Caldwell and Y. Xiong, <a href="http://arxiv.org/abs/1209.2007">What is the smallest prime?</a>, arXiv preprint arXiv:1209.2007 [math.HO], 2012, and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell1/cald5.html">J. Int. Seq. 15 (2012) #12.9.6</a>
%H Leonhard Euler, <a href="http://eulerarchive.maa.org/backup/E175.html">Découverte d’une loi tout extraordinaire des nombres, par rapport à la somme de leurs diviseurs</a>, 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.
%H G. P. Michon, <a href="http://www.numericana.com/answer/numbers.htm#one">Is 1 a prime number?</a>
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poldiv07.jpg">Illustration of initial terms</a>
%H Omar E. Pol, <a href="http://www.polprimos.com/imagenespub/poldiv06.jpg">Illustration of initial terms of A008578, A161344, A161345, A161424</a>
%H PrimeFan, <a href="http://primefan.tripod.com/Prime1ProCon.html">Arguments for and against the primality of 1</a>
%H A. Reddick and Y. Xiong, <a href="http://math.furman.edu/~mwoodard/fuejum/content/2012/paper1_2012.pdf">The search for one as a prime number: from ancient Greece to modern times</a>, Electronic Journal of Undergraduate Mathematics, Volume 16, 1 - 13, 2012. - From _N. J. A. Sloane_, Feb 03 2013
%H J. Todd, <a href="http://www.jstor.org/stable/2001950">Review of Lehmer's tables, Mathematical Tables and Other Aids to Computation, Vol. 11, No. 60, (1957)</a> (on JSTOR.org).
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Complete_sequence">"Complete" sequence</a>. [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]
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Dirichlet_convolution">Dirichlet convolution</a>
%F a(n) = A000040(n-1).
%F m is in the sequence iff sigma(m) + phi(m) = A065387(m) = 2m. - _Farideh Firoozbakht_, Jan 27 2005
%F a(n) = A158611(n+1) for n >= 1. - _Jaroslav Krizek_, Jun 19 2009
%F 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.
%F This = A030014 * A008683. (Dirichlet convolution using offset 1 with A030014)
%F This = A030013 * A000012. (Dirichlet convolution using offset 1 with A030013)
%F This = A034773 * A007427. (Dirichlet convolution)
%F This = A034760 * A023900. (Dirichlet convolution)
%F This = A034762 * A046692. (Dirichlet convolution)
%F This * A000012 = A030014. (Dirichlet convolution using offset 1 with A030014)
%F This * A008683 = A030013. (Dirichlet convolution using offset 1 with A030013)
%F This * A000005 = A034773. (Dirichlet convolution)
%F This * A000010 = A034760. (Dirichlet convolution)
%F This * A000203 = A034762. (Dirichlet convolution)
%F A002033(a(n))=1. - _Juri-Stepan Gerasimov_, Sep 27 2009
%F a(n) = A181363((2*n-1)*2^k), k >= 0. - _Reinhard Zumkeller_, Oct 16 2010
%F a(n) = A001747(n)/2. - _Omar E. Pol_, Jan 30 2012
%F A060448(a(n)) = 1. - _Reinhard Zumkeller_, Apr 05 2012
%F A086971(a(n)) = 0. - _Reinhard Zumkeller_, Dec 14 2012
%F Sum_{n>=1} x^a(n) = (Sum_{n>=1} (A002815(n)*x^n))*(1-x)^2. - _L. Edson Jeffery_, Nov 25 2013
%p A008578 := n->if n=1 then 1 else ithprime(n-1); fi :
%t Join[ {1}, Table[ Prime[n], {n, 1, 60} ] ]
%t NestList[ NextPrime, 1, 57] (* _Robert G. Wilson v_, Jul 21 2015 *)
%t oldPrimeQ[n_] := AllTrue[Range[n-1], CoprimeQ[#, n]&];
%t Select[Range[271], oldPrimeQ] (* _Jean-François Alcover_, Jun 07 2017, after _Peter Luschny_ *)
%o (PARI) is(n)=isprime(n)||n==1
%o (Magma) [1] cat [n: n in PrimesUpTo(271)]; // _Bruno Berselli_, Mar 05 2011
%o (Haskell)
%o a008578 n = a008578_list !! (n-1)
%o a008578_list = 1 : a000040_list
%o -- _Reinhard Zumkeller_, Nov 09 2011
%o (Sage)
%o isA008578 = lambda n: all(gcd(k, n) == 1 for k in (1..n-1))
%o print([n for n in (1..271) if isA008578(n)]) # _Peter Luschny_, Jun 07 2017
%o (GAP)
%o A008578:=Concatenation([1],Filtered([1..10^5],IsPrime)); # _Muniru A Asiru_, Sep 07 2017
%Y The main entry for this sequence is A000040.
%Y The complement of A002808.
%Y Cf. A000732 (boustrophedon transform).
%Y Cf. A000010, A000203.
%Y Cf. A023626 (self-convolution).
%K nonn,easy,nice
%O 1,2
%A _N. J. A. Sloane_