A151800 -id:A151800 - cp's OEIS frontend

A380330 a(n) = A151800(prime(n)*A151800(n)).

5, 11, 29, 37, 79, 97, 191, 211, 257, 331, 409, 487, 701, 733, 809, 907, 1123, 1163, 1543, 1637, 1693, 1823, 2411, 2591, 2819, 2939, 2999, 3109, 3389, 3511, 4703, 4861, 5077, 5147, 5519, 5591, 6449, 6689, 6857, 7103, 7699, 7789, 8999, 9091, 9277, 9371, 11197

Offset: 1

Clark Kimberling, Jan 21 2025

nonn

			a(1) = A151800(prime(1)*A151800(1)) = A151800(2*2) = 5.

Cf. A000040, A151800.

Table[NextPrime[Prime[n]*NextPrime[n]], {n, 1, 80}]

p(n) = nextprime(n+1);
a(n) = p(prime(n)*p(n)); \\ Michel Marcus, Jan 27 2025

A000040 The prime numbers.

Original entry on oeis.org

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

N. J. A. Sloane

See A065091 for comments, formulas etc. concerning only odd primes. For all information concerning prime powers, see A000961. For contributions concerning "almost primes" see A002808.
A number p is prime if (and only if) it is greater than 1 and has no positive divisors except 1 and p.
A natural number is prime if and only if it has exactly two (positive) divisors.
A prime has exactly one proper positive divisor, 1.
The paper by Kaoru Motose starts as follows: "Let q be a prime divisor of a Mersenne number 2^p-1 where p is prime. Then p is the order of 2 (mod q). Thus p is a divisor of q - 1 and q > p. This shows that there exist infinitely many prime numbers." - Pieter Moree, Oct 14 2004
1 is not a prime, for if the primes included 1, then the factorization of a natural number n into a product of primes would not be unique, since n = n*1.
Prime(n) and pi(n) are inverse functions: A000720(a(n)) = n and a(n) is the least number m such that a(A000720(m)) = a(n). a(A000720(n)) = n if (and only if) n is prime.
Second sequence ever computed by electronic computer, on EDSAC, May 09 1949 (see Renwick link). - Russ Cox, Apr 20 2006
Every prime p > 3 is a linear combination of previous primes prime(n) with nonzero coefficients c(n) and |c(n)| < prime(n). - Amarnath Murthy, Franklin T. Adams-Watters and Joshua Zucker, May 17 2006; clarified by Chayim Lowen, Jul 17 2015
The Greek transliteration of 'Prime Number' is 'Protos Arithmos'. - Daniel Forgues, May 08 2009 [Edited by Petros Hadjicostas, Nov 18 2019]
A number n is prime if and only if it is different from zero and different from a unit and each multiple of n decomposes into factors such that n divides at least one of the factors. This applies equally to the integers (where a prime has exactly four divisors (the definition of divisors is relaxed such that they can be negative)) and the positive integers (where a prime has exactly two distinct divisors). - Peter Luschny, Oct 09 2012
Motivated by his conjecture on representations of integers by alternating sums of consecutive primes, for any positive integer n, Zhi-Wei Sun conjectured that the polynomial P_n(x) = Sum_{k=0..n} a(k+1)*x^k is irreducible over the field of rational numbers with the Galois group S_n, and moreover P_n(x) is irreducible mod a(m) for some m <= n(n+1)/2. It seems that no known criterion on irreducibility of polynomials implies this conjecture. - Zhi-Wei Sun, Mar 23 2013
Questions on a(2n) and Ramanujan primes are in A233739. - Jonathan Sondow, Dec 16 2013
From Hieronymus Fischer, Apr 02 2014: (Start)
Natural numbers such that there is exactly one base b such that the base-b alternate digital sum is 0 (see A239707).
Equivalently: Numbers p > 1 such that b = p-1 is the only base >= 1 for which the base-b alternate digital sum is 0.
Equivalently: Numbers p > 1 such that the base-b alternate digital sum is <> 0 for all bases 1 <= b < p-1. (End)
An integer n > 1 is a prime if and only if it is not the sum of positive integers in arithmetic progression with common difference 2. - Jean-Christophe Hervé, Jun 01 2014
Conjecture: Numbers having prime factors <= prime(n+1) are {k|k^f(n) mod primorial(n)=1}, where f(n) = lcm(prime(i)-1, i=1..n) = A058254(n) and primorial(n) = A002110(n). For example, numbers with no prime divisor <= prime(7) = 17 are {k|k^60 mod 30030=1}. - Gary Detlefs, Jun 07 2014
Cramer conjecture prime(n+1) - prime(n) < C log^2 prime(n) is equivalent to the inequality (log prime(n+1)/log prime(n))^n < e^C, as n tend to infinity, where C is an absolute constant. - Thomas Ordowski, Oct 06 2014
I conjecture that for any positive rational number r there are finitely many primes q_1,...,q_k such that r = Sum_{j=1..k} 1/(q_j-1). For example, 2 = 1/(2-1) + 1/(3-1) + 1/(5-1) + 1/(7-1) + 1/(13-1) with 2, 3, 5, 7 and 13 all prime, 1/7 = 1/(13-1) + 1/(29-1) + 1/(43-1) with 13, 29 and 43 all prime, and 5/7 = 1/(3-1) + 1/(7-1) + 1/(31-1) + 1/(71-1) with 3, 7, 31 and 71 all prime. - Zhi-Wei Sun, Sep 09 2015
I also conjecture that for any positive rational number r there are finitely many primes p_1,...,p_k such that r = Sum_{j=1..k} 1/(p_j+1). For example, 1 = 1/(2+1) + 1/(3+1) + 1/(5+1) + 1/(7+1) + 1/(11+1) + 1/(23+1) with 2, 3, 5, 7, 11 and 23 all prime, and 10/11 = 1/(2+1) + 1/(3+1) + 1/(5+1) + 1/(7+1) + 1/(43+1) + 1/(131+1) + 1/(263+1) with 2, 3, 5, 7, 43, 131 and 263 all prime. - Zhi-Wei Sun, Sep 13 2015
Numbers k such that ((k-2)!!)^2 == +-1 (mod k). - Thomas Ordowski, Aug 27 2016
Does not satisfy Benford's law [Diaconis, 1977; Cohen-Katz, 1984; Berger-Hill, 2017]. - N. J. A. Sloane, Feb 07 2017
Prime numbers are the integer roots of 1 - sin(Pi*Gamma(s)/s)/sin(Pi/s). - Peter Luschny, Feb 23 2018
Conjecture: log log a(n+1) - log log a(n) < 1/n. - Thomas Ordowski, Feb 17 2023

			From _David A. Corneth_, Oct 22 2024: (Start)
7 is a prime number as it has exactly two divisors, 1 and 7.
8 is not a prime number as it does not have exactly two divisors (it has 1, 2, 4 and 8 as divisors though it is sufficient to find one other divisor than 1 and 8)
55 is not a prime number as it does not have exactly two divisors. One other divisor than 1 and 55 is 5.
59 is a prime number as it has exactly two divisors; 1 and 59. (End)

M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 2nd. ed., 2001; see p. 3.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.
E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I, Chaps. 8, 9.
D. M. Bressoud, Factorization and Primality Testing, Springer-Verlag NY 1989.
M. Cipolla, "La determinazione asintotica dell'n-mo numero primo.", Rend. d. R. Acc. di sc. fis. e mat. di Napoli, s. 3, VIII (1902), pp. 132-166.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 127-149.
R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 1.
Martin Davis, "Algorithms, Equations, and Logic", pp. 4-15 of S. Barry Cooper and Andrew Hodges, Eds., "The Once and Future Turing: Computing the World", Cambridge 2016.
J.-P. Delahaye, Merveilleux nombres premiers, Pour la Science-Belin Paris, 2000.
J.-P. Delahaye, Savoir si un nombre est premier: facile, Pour La Science, 303(1) 2003, pp. 98-102.
M. Dietzfelbinger, Primality Testing in Polynomial Time, Springer NY 2004.
M. du Sautoy, The Music of the Primes, Fourth Estate / HarperCollins, 2003; see p. 5.
J. Elie, "L'algorithme AKS", in 'Quadrature', No. 60, pp. 22-32, 2006 EDP-sciences, Les Ulis (France);
W. & F. Ellison, Prime Numbers, Hermann Paris 1985
T. Estermann, Introduction to Modern Prime Number Theory, Camb. Univ. Press, 1969.
J. M. Gandhi, Formulae for the nth prime. Proc. Washington State Univ. Conf. on Number Theory, 96-106. Wash. St. Univ., Pullman, Wash., 1971.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, pp. 77-78.
R. K. Guy, Unsolved Problems Number Theory, Section A.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 2.
Peter Hilton and Jean Pedersen, A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, 2010, pp. (260-264).
H. D. Huskey, Derrick Henry Lehmer [1905-1991]. IEEE Ann. Hist. Comput. 17 (1995), no. 2, 64-68. Math. Rev. 96b:01035, cf. http://www.ams.org/mathscinet-getitem?mr=1336709
M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 1972.
D. S. Jandu, Prime Numbers And Factorization, Infinite Bandwidth Publishing, N. Hollywood CA 2007.
E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea, NY, 1974.
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.
W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, Chap. 6.
H. Lifchitz, Table des nombres premiers de 0 à 20 millions (Tomes I & II), Albert Blanchard, Paris 1971.
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, cf http://www.ams.org/mathscinet-getitem?mr=96m:11082
P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag NY 1995.
P. Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004.
H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhäuser Boston, Cambridge MA 1994.
B. Rittaud, "31415879. Ce nombre est-il premier?" ['Is this number prime?'], La Recherche, Vol. 361, pp. 70-73, Feb 15 2003, Paris.
D. Shanks, Solved and Unsolved Problems in Number Theory, 2nd. ed., Chelsea, 1978, Chap. 1.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 107-119.
D. Wells, Prime Numbers: The Most Mysterious Figures In Math, J. Wiley NY 2005.
H. C. Williams and Jeffrey 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

N. J. A. Sloane, Table of n, prime(n) for n = 1..10000
N. J. A. Sloane, Table of n, prime(n) for n = 1..100000
M. Agrawal, N. Kayal & N. Saxena, PRIMES is in P, Annals of Maths., 160:2 (2004), pp. 781-793. [alternative link]
M. Agrawal, A Short History of "PRIMES is in P"
P. Alfeld, Notes and Literature on Prime Numbers
J. W. Andrushkiw, R. I. Andrushkiw and C. E. Corzatt, Representations of Positive Integers as Sums of Arithmetic Progressions, Mathematics Magazine, Vol. 49, No. 5 (Nov., 1976), pp. 245-248.
Anonymous, Prime Number Master Index (for primes up to 2*10^7)
Anonymous, prime number
Juan Arias de Reyna and Jeremy Toulisse, The n-th prime asymptotically, arxiv:1203.5413 [math.NT], 2012.
Christian Axler, New estimates for the n-th prime number, arXiv:1706.03651 [math.NT], 2017.
P. T. Bateman & H. G. Diamond, A Hundred Years of Prime Numbers, Amer. Math. Month., Vol. 103 (9), Nov. 1996, pp. 729-741.
A. Berger and T. P. Hill, What is Benford's Law?, Notices, Amer. Math. Soc., 64: 2 (2017), 132-134.
E. R. Berlekamp, A contribution to mathematical psychometrics, Unpublished Bell Labs Memorandum, Feb 08 1968 [Annotated scanned copy]
D. J. Bernstein, Proving Primality After Agrawal-Kayal-Saxena
D. J. Bernstein, Distinguishing prime numbers from composite numbers
P. Berrizbeitia, Sharpening "Primes is in P" for a large family of numbers, arXiv:math/0211334 [math.NT], 2002.
A. Booker, The Nth Prime Page
F. Bornemann, PRIMES Is in P: A Breakthrough for "Everyman", Notices, Amer. Math. Soc., 50: 5 (2003), 545-552.
A. Bowyer, Formulae for Primes
B. M. Bredikhin, Prime number
R. P. Brent, Primality testing and integer factorization
J. Britton, Prime Number List [Dead link]
D. Butler, The first 2000 Prime Numbers
C. K. Caldwell, The Prime Pages: Tables of primes; Lists of small primes (from the first 1000 primes to all 50,000,000 primes up to 982,451,653.)
C. K. Caldwell, A Primality Test
C. K. Caldwell and Y. Xiong, What is the smallest prime?, J. Integer Seq. 15 (2012), no. 9, Article 12.9.7 and arXiv:1209.2007 [math.HO], 2012.
Chris K. Caldwell, Angela Reddick, Yeng Xiong and Wilfrid Keller, The History of the Primality of One: A Selection of Sources, Journal of Integer Sequences, Vol. 15 (2012), #12.9.8.
Ernesto Cesàro, Sur une formule empirique de M. Pervouchine, Comptes rendus hebdomadaires des séances de l'Académie des sciences (in French), 119 (1894), 848-849.
M. Chamness, Prime number generator (Applet)
Daniel I. A. Cohen and Talbot M. Katz, Prime numbers and the first digit phenomenon, J. Number Theory 18 (1984), 261-268.
P. Cox, Primes is in P
P. J. Davis & R. Hersh, The Mathematical Experience, The Prime Number Theorem
J.-M. De Koninck, Les nombres premiers: mystères et consolation.
J.-M. De Koninck, Nombres premiers: mystères et enjeux.
J.-P. Delahaye, Formules et nombres premiers.
Persi Diaconis, The distribution of leading digits and uniform distribution mod 1, Ann. Probability, 5, 1977, 72--81.
U. Dudley, Formulas for primes, Math. Mag., 56 (1983), 17-22.
Pierre Dusart, Autour de la fonction qui compte le nombre de nombres premiers, Thèse, Université de Limoges, France, (1998).
Pierre Dusart, The k-th prime is greater than k(ln k + ln ln k-1) for k>=2, Mathematics of Computation 68: (1999), 411-415.
J. Elie, L'algorithme AKS ou Les nombres premiers sont de classe P
Seymour B. Elk, Prime Number Assignment to a Hexagonal Tessellation of a Plane That Generates Canonical Names for Peri-Condensed Polybenzenes, J. Chem. Inf. Comput. Sci., vol. 34 (1994), pp. 942-946.
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
Leonhard Euler, Observations on a theorem of Fermat and others on looking at prime numbers, arXiv:math/0501118 [math.HO], 2005-2008.
W. Fendt, Table of Primes from 1 to 1000000000000
P. Flajolet, S. Gerhold and B. Salvy, On the non-holonomic character of logarithms, powers and the n-th prime function, arXiv:math/0501379 [math.CO], 2005.
J. Flamant, Primes up to one million
K. Ford, Expositions of the PRIMES is in P theorem.
H. Furstenberg, On the Infinitude of Primes, The American Mathematical Monthly, Vol. 62, No. 5 (May, 1955), p. 353 (1 page).
L. & Y. Gallot, The Chronology of Prime Number Records
P. Garrett, Big Primes, Factoring Big Integers
P. Garrett, Naive Primality Test
P. Garrett, Listing Primes
N. Gast, PRIMES is in P: Manindra Agrawal, Neeraj Kayal and Nitin Saxena (in French)
D. A. Goldston, S. W. Graham, J. Pintz and C. Y. Yildirim, Small gaps between primes and almost primes, arXiv:math/0506067 [math.NT], 2005.
S. W. Golomb, A Direct Interpretation of Gandhi's Formula, Mathematics Magazine, Vol. 81, No. 7 (Aug. - Sep., 1974), pp. 752-754.
A. Granville, It is easy to determine whether a given integer is prime [alternate link]
G. Hartl Watters, All prime numbers below 2 trillion (compressed `.txt.xz` file). SHA-512 checksum.
P. Hartmann, Prime number proofs (in German) [broken link]
Haskell Wiki, Prime Numbers
ICON Project, List of first 50000 primes grouped within ten columns
James P. Jones, Daihachiro Sato, Hideo Wada and Douglas Wiens, Diophantine representation of the set of prime numbers, The American Mathematical Monthly 83, no. 6 (1976): 449-464. DOI: 10.2307/2318339.
N. Kayal and N. Saxena, A polynomial time algorithm to test if a number is prime or not, Resonance 11-2002.
E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1 and vol. 2, Leipzig, Berlin, B. G. Teubner, 1909.
W. Liang & H. Yan, Pseudo Random test of prime numbers, arXiv:math/0603450 [math.NT], 2006.
J. Malkevitch, Primes
Mathworld Headline News, Primality Testing is Easy
K. Matthews, Generating prime numbers
Y. Motohashi, Prime numbers-your gems, arXiv:math/0512143 [math.HO], 2005.
Kaoru Motose, On values of cyclotomic polynomials. II, Math. J. Okayama Univ. 37 (1995), 27-36.
J. Moyer, Some Prime Numbers
C. W. Neville, New Results on Primes from an Old Proof of Euler's, arXiv:math/0210282 [math.NT], 2002-2003.
L. C. Noll, Prime numbers, Mersenne Primes, Perfect Numbers, etc.
M. A. Nyblom and C. Evans, On the enumeration of partitions with summands in arithmetic progression, Australasian Journal of Combinatorics, Vol. 28 (2003), pp. 149-159.
J. J. O'Connor & E. F. Robertson, Prime Numbers
M. E. O'Neill, The Genuine Sieve of Eratosthenes, J. of Functional Programming, Vol 19 Issue 1, Jan 2009, p. 95ff, CUP NY
M. Ogihara & S. Radziszowski, Agrawal-Kayal-Saxena Algorithm for Testing Primality in Polynomial Time
P. Papaphilippou, Plotter of prime numbers frequency graph (flash object) [From Philippos Papaphilippou (philippos(AT)safe-mail.net), Jun 02 2010]
J. M. Parganin, Primes less than 50000
Matthew Parker, The first billion primes (7-Zip compressed file) [a large file]
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003. [Cached copy, with permission (pdf only)]
I. Peterson, Prime Pursuits
Omar E. Pol, Illustration of initial terms
Omar E. Pol, Sobre el patrón de los números primos, and from Jason Davies, An interactive companion (for primes 2..997)
Popular Computing (Calabasas, CA), Sieves: Problem 43, Vol. 2 (No. 13, Apr 1974), pp. 6-7. [Annotated and scanned copy]
Primefan, The First 500 Prime Numbers and Script to Calculate Prime Numbers.
Project Gutenberg Etext, First 100,000 Prime Numbers
C. D. Pruitt, Formulae for Generating All Prime Numbers
R. Ramachandran, Frontline 19 (17) 08-2000, A Prime Solution
W. S. Renwick, EDSAC log.
F. Richman, Generating primes by the sieve of Eratosthenes
Barkley Rosser, Explicit Bounds for Some Functions of Prime Numbers, American Journal of Mathematics 63 (1941) 211-232.
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. Volume 6, Issue 1 (1962), 64-94.
S. M. Ruiz and J. Sondow, Formulas for pi(n) and the n-th prime, arXiv:math/0210312 [math.NT], 2002-2014.
S. O. S. Math, First 1000 Prime Numbers
A. Schulman, Prime Number Calculator
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 5.
M. Slone, PlanetMath.Org, First thousand positive prime numbers
A. Stiglic, The PRIMES is in P little FAQ
Zhi-Wei Sun, On functions taking only prime values, J. Number Theory, 133 (2013), no. 8, 2794-2812.
Zhi-Wei Sun, A conjecture on unit fractions involving primes, Preprint 2015.
J. Teitelbaum, Review of "Prime numbers:A computational perspective" by R. Crandall & C. Pomerance
J. Thonnard, Les nombres premiers(Primality check; Closest next prime; Factorizer)
J. Tramu, Movie of primes scrolling
A. Turpel, Aesthetics of the Prime Sequence [broken link ?]
S. Wagon, Prime Time: Review of "Prime Numbers:A Computational Perspective" by R. Crandall & C. Pomerance
M. R. Watkins, unusual and physical methods for finding prime numbers
S. Wedeniwski, Primality Tests on Commutator Curves
E. Wegrzynowski, Les formules simples qui donnent des nombres premiers en grande quantité (in French).
Eric Weisstein's World of Mathematics, Prime-Generating Polynomial, Prime Number, and Prime Spiral.
Wikipedia, Prime number and Prime number theorem.
C. P. Willans, On formulae for the nth prime, Math. Gazette 48 (1964), 413-415.
G. Xiao, Primes server, Sequential Batches Primes Listing (up to orders not exceeding 10^308)
G. Xiao, Numerical Calculator, To display p(n) for n up to 41561, operate on "prime(n)"
Index entries for "core" sequences
Index entries for sequences related to Benford's law
Additional (less important) items -- comments, formulas, references, links, programs, etc. -- related to the prime numbers, A000040. [HTML version] - [Plain text (TXT) version].

For is_prime and next_prime, see A010051 and A151800.
Cf. A000720 ("pi"), A001223 (differences between primes), A002476, A002808, A003627, A006879, A006880, A008578, A080339, A233588.
Cf. primes in lexicographic order: A210757, A210758, A210759, A210760, A210761.
Cf. A003558, A179480 (relating to the Quasi-order theorem of Hilton and Pedersen).
Boustrophedon transforms: A000747, A000732, A230953.
a(2n) = A104272(n) - A233739(n).
Related sequences:
Primes (p) and composites (c): A002808, A000720, A065855.
Primes between p(n) and 2*p(n): A063124, A070046; between c(n) and 2*c(n): A376761; between n and 2*n: A035250, A060715, A077463, A108954.
Composites between p(n) and 2*p(n): A246514; between c(n) and 2*c(n): A376760; between n and 2*n: A075084, A307912, A307989, A376759.

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

-- See also Haskell Wiki Link.
import Data.List (genericIndex)
a000040 n = genericIndex a000040_list (n - 1)
a000040_list = base ++ larger where
base = [2,3,5,7,11,13,17]
larger = p : filter prime more
prime n = all ((> 0) . mod n) $ takeWhile (\x -> x*x <= n) larger
_ : p : more = roll $ makeWheels base
roll (Wheel n rs) = [n * k + r | k <- [0..], r <- rs]
makeWheels = foldl nextSize (Wheel 1 [1])
nextSize (Wheel size bs) p = Wheel (size * p)
[r | k <- [0..p-1], b <- bs, let r = size*k+b, mod r p > 0]
data Wheel = Wheel Integer [Integer]
-- Reinhard Zumkeller, Apr 07 2014

Magma
```
[n : n in [2..500] | IsPrime(n)];
```
Magma
```
a := func< n | NthPrime(n) >;
```

A000040 := n->ithprime(n); [ seq(ithprime(i),i=1..100) ];
# For illustration purposes only:
isPrime := s -> is(1 = sin(Pi*GAMMA(s)/s)/sin(Pi/s)):
select(isPrime, [$2..100]); # Peter Luschny, Feb 23 2018

Mathematica
```
Prime[Range[60]]
```

A000040(n) := block(
if n = 1 then return(2),
return( next_prime(A000040(n-1)))
)$ /* recursive, to be replaced if possible - R. J. Mathar, Feb 27 2012 */

PARI
```
{a(n) = if( n<1, 0, prime(n))};
```

/* The following functions provide asymptotic approximations, one based on the asymptotic formula cited above (slight overestimate for n > 10^8), the other one based on pi(x) ~ li(x) = Ei(log(x)) (slight underestimate): */
prime1(n)=n*(log(n)+log(log(n))-1+(log(log(n))-2)/log(n)-((log(log(n))-6)*log(log(n))+11)/log(n)^2/2)
prime2(n)=solve(X=n*log(n)/2,2*n*log(n),real(eint1(-log(X)))+n)
\\ M. F. Hasler, Oct 21 2013

forprime(p=2, 10^3, print1(p, ", ")) \\ Felix Fröhlich, Jun 30 2014

primes(10^5) \\ Altug Alkan, Mar 26 2018

from sympy import primerange
print(list(primerange(2, 272))) # Michael S. Branicky, Apr 30 2022

a = sloane.A000040
a.list(58)  # Jaap Spies, 2007

prime_range(1, 300)  # Zerinvary Lajos, May 27 2009

The prime number theorem is the statement that a(n) ~ n * log n as n -> infinity (Hardy and Wright, page 10).
For n >= 2, n*(log n + log log n - 3/2) < a(n); for n >= 20, a(n) < n*(log n + log log n - 1/2). [Rosser and Schoenfeld]
For all n, a(n) > n log n. [Rosser]
n log(n) + n (log log n - 1) < a(n) < n log n + n log log n for n >= 6. [Dusart, quoted in the Wikipedia article]
a(n) = n log n + n log log n + (n/log n)*(log log n - log n - 2) + O( n (log log n)^2/ (log n)^2). [Cipolla, see also Cesàro or the "Prime number theorem" Wikipedia article for more terms in the expansion]
a(n) = 2 + Sum_{k = 2..floor(2n*log(n)+2)} (1-floor(pi(k)/n)), for n > 1, where the formula for pi(k) is given in A000720 (Ruiz and Sondow 2002). - Jonathan Sondow, Mar 06 2004
I conjecture that Sum_{i>=1} (1/(prime(i)*log(prime(i)))) = Pi/2 = 1.570796327...; Sum_{i=1..100000} (1/(prime(i)*log(prime(i)))) = 1.565585514... It converges very slowly. - Miklos Kristof, Feb 12 2007
The last conjecture has been discussed by the math.research newsgroup recently. The sum, which is greater than Pi/2, is shown in sequence A137245. - T. D. Noe, Jan 13 2009
A000005(a(n)) = 2; A002033(a(n+1)) = 1. - Juri-Stepan Gerasimov, Oct 17 2009
A001222(a(n)) = 1. - Juri-Stepan Gerasimov, Nov 10 2009
From Gary Detlefs, Sep 10 2010: (Start)
Conjecture:
a(n) = {n| n! mod n^2 = n(n-1)}, n <> 4.
a(n) = {n| n!*h(n) mod n = n-1}, n <> 4, where h(n) = Sum_{k=1..n} 1/k. (End)
For n = 1..15, a(n) = p + abs(p-3/2) + 1/2, where p = m + int((m-3)/2), and m = n + int((n-2)/8) + int((n-4)/8). - Timothy Hopper, Oct 23 2010
a(2n) <= A104272(n) - 2 for n > 1, and a(2n) ~ A104272(n) as n -> infinity. - Jonathan Sondow, Dec 16 2013
Conjecture: Sequence = {5 and n <> 5| ( Fibonacci(n) mod n = 1 or Fibonacci(n) mod n = n - 1) and 2^(n-1) mod n = 1}. - Gary Detlefs, May 25 2014
Conjecture: Sequence = {5 and n <> 5| ( Fibonacci(n) mod n = 1 or Fibonacci(n) mod n = n - 1) and 2^(3*n) mod 3*n = 8}. - Gary Detlefs, May 28 2014
Satisfies a(n) = 2*n + Sum_{k=1..(a(n)-1)} cot(k*Pi/a(n))*sin(2*k*n^a(n)*Pi/a(n)). - Ilya Gutkovskiy, Jun 29 2016
Sum_{n>=1} 1/a(n)^s = P(s), where P(s) is the prime zeta function. - Eric W. Weisstein, Nov 08 2016
a(n) = floor(1 - log(-1/2 + Sum_{ d | A002110(n-1) } mu(d)/(2^d-1))/log(2)) where mu(d) = A008683(d) [Ghandi, 1971] (see Ribenboim). Golomb gave a proof in 1974: Give each positive integer a probability of W(n) = 1/2^n, then the probability M(d) of the integer multiple of number d equals 1/(2^d-1). Suppose Q = a(1)*a(2)*...*a(n-1) = A002110(n-1), then the probability of random integers that are mutually prime with Q is Sum_{ d | Q } mu(d)*M(d) = Sum_{ d | Q } mu(d)/(2^d-1) = Sum_{ gcd(m, Q) = 1 } W(m) = 1/2 + 1/2^a(n) + 1/2^a(n+1) + 1/2^a(n+2) + ... So ((Sum_{ d | Q } mu(d)/(2^d-1)) - 1/2)*2^a(n) = 1 + x(n), which means that a(n) is the only integer so that 1 < ((Sum_{ d | Q } mu(d)/(2^d-1)) - 1/2)*2^a(n) < 2. - Jinyuan Wang, Apr 08 2019
Conjecture: n * (log(n)+log(log(n))-1+((log(log(n))-A)/log(n))) is asymptotic to a(n) if and only if A=2. - Alain Rocchelli, Feb 12 2025
From Stefano Spezia, Apr 13 2025: (Start)
a(n) = 1 + Sum_{m=1..2^n} floor(floor(n/Sum_{j=1..m} A080339(j))^(1/n)) [Willans, 1964].
a(n) = 1 + Sum_{m=1..2^n} floor(floor(n/(1 + A000720(m)))^(1/n)) [Willans, 1964]. (End)

A048673 Permutation of natural numbers: a(n) = (A003961(n)+1) / 2 [where A003961(n) shifts the prime factorization of n one step towards larger primes].

Original entry on oeis.org

1, 2, 3, 5, 4, 8, 6, 14, 13, 11, 7, 23, 9, 17, 18, 41, 10, 38, 12, 32, 28, 20, 15, 68, 25, 26, 63, 50, 16, 53, 19, 122, 33, 29, 39, 113, 21, 35, 43, 95, 22, 83, 24, 59, 88, 44, 27, 203, 61, 74, 48, 77, 30, 188, 46, 149, 58, 47, 31, 158, 34, 56, 138, 365, 60, 98, 36, 86, 73

Offset: 1

Antti Karttunen, Jul 14 1999

nonn

Inverse of sequence A064216 considered as a permutation of the positive integers. - Howard A. Landman, Sep 25 2001
From Antti Karttunen, Dec 20 2014: (Start)
Permutation of natural numbers obtained by replacing each prime divisor of n with the next prime and mapping the generated odd numbers back to all natural numbers by adding one and then halving.
Note: there is a 7-cycle almost right in the beginning: (6 8 14 17 10 11 7). (See also comments at A249821. This 7-cycle is endlessly copied in permutations like A250249/A250250.)
The only 3-cycle in range 1 .. 402653184 is (2821 3460 5639).
For 1- and 2-cycles, see A245449.
(End)
The first 5-cycle is (1410, 2783, 2451, 2703, 2803). - Robert Israel, Jan 15 2015
From Michel Marcus, Aug 09 2020: (Start)
(5194, 5356, 6149, 8186, 10709), (46048, 51339, 87915, 102673, 137205) and (175811, 200924, 226175, 246397, 267838) are other 5-cycles.
(10242, 20479, 21413, 29245, 30275, 40354, 48241) is another 7-cycle. (End)
From Antti Karttunen, Feb 10 2021: (Start)
Somewhat artificially, also this permutation can be represented as a binary tree. Each child to the left is obtained by multiplying the parent by 3 and subtracting one, while each child to the right is obtained by applying A253888 to the parent:
                                       1
                                       |
                    ................../ \..................
                   2                                       3
         5......../ \........4                   8......../ \........6
        / \                 / \                 / \                 / \
       /   \               /   \               /   \               /   \
      /     \             /     \             /     \             /     \
    14       13         11       7          23       9          17       18
  41 10    38  12     32  28   20 15      68  25   26 63      50  16   53  19
etc.
Each node's (> 1) parent can be obtained with A253889. Sequences A292243, A292244, A292245 and A292246 are constructed from the residues (mod 3) of the vertices encountered on the path from n to the root (1).
(End)

			For n = 6, as 6 = 2 * 3 = prime(1) * prime(2), we have a(6) = ((prime(1+1) * prime(2+1))+1) / 2 = ((3 * 5)+1)/2 = 8.
For n = 12, as 12 = 2^2 * 3, we have a(12) = ((3^2 * 5) + 1)/2 = 23.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences that are permutations of the natural numbers.

Inverse: A064216.
Row 1 of A251722, Row 2 of A249822.
One more than A108228, half the terms of A243501.
Fixed points: A048674.
Positions of records: A029744, their values: A246360 (= A007051 interleaved with A057198).
Positions of subrecords: A247283, their values: A247284.
Cf. A246351 (Numbers n such that a(n) < n.)
Cf. A246352 (Numbers n such that a(n) >= n.)
Cf. A246281 (Numbers n such that a(n) <= n.)
Cf. A246282 (Numbers n such that a(n) > n.), A252742 (their char. function)
Cf. A246261 (Numbers n for which a(n) is odd.)
Cf. A246263 (Numbers n for which a(n) is even.)
Cf. A246260 (a(n) reduced modulo 2), A341345 (modulo 3), A341346, A292251 (3-adic valuation), A292252.
Cf. A246342 (Iterates starting from n=12.)
Cf. A246344 (Iterates starting from n=16.)
Cf. also A003602, A003961 (A045965), A108951, A151800, A245449, A249735, A249821, A250471, A250249, A250250.
Cf. A245447 (This permutation "squared", a(a(n)).)
Other permutations whose formulas refer to this sequence: A122111, A243062, A243066, A243500, A243506, A244154, A244319, A245605, A245608, A245610, A245612, A245708, A246265, A246267, A246268, A246363, A249745, A249824, A249826, and also A183209, A254103 that are somewhat similar.
Cf. also prime-shift based binary trees A005940, A163511, A245612 and A244154.
Cf. A253888, A253889, A292243, A292244, A292245 and A292246 for other derived sequences.
Cf. A323893 (Dirichlet inverse), A323894 (sum with it), A336840 (inverse Möbius transform).

a048673 = (`div` 2) . (+ 1) . a045965
-- Reinhard Zumkeller, Jul 12 2012

f:= proc(n)
local F,q,t;
  F:= ifactors(n)[2];
  (1 + mul(nextprime(t[1])^t[2], t = F))/2
end proc:
seq(f(n),n=1..1000); # Robert Israel, Jan 15 2015

Table[(Times @@ Power[If[# == 1, 1, NextPrime@ #] & /@ First@ #, Last@ #] + 1)/2 &@ Transpose@ FactorInteger@ n, {n, 69}] (* Michael De Vlieger, Dec 18 2014, revised Mar 17 2016 *)

A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
A048673(n) = (A003961(n)+1)/2; \\ Antti Karttunen, Dec 20 2014

A048673(n) = if(1==n,n,if(n%2,A253888(A048673((n-1)/2)),(3*A048673(n/2))-1)); \\ (Not practical, but demonstrates the construction as a binary tree). - Antti Karttunen, Feb 10 2021

from sympy import factorint, nextprime, prod
def a(n):
    f = factorint(n)
    return 1 if n==1 else (1 + prod(nextprime(i)**f[i] for i in f))//2 # Indranil Ghosh, May 09 2017

(define (A048673 n) (/ (+ 1 (A003961 n)) 2)) ;; Antti Karttunen, Dec 20 2014

From Antti Karttunen, Dec 20 2014: (Start)
a(1) = 1; for n>1: If n = product_{k>=1} (p_k)^(c_k), then a(n) = (1/2) * (1 + product_{k>=1} (p_{k+1})^(c_k)).
a(n) = (A003961(n)+1) / 2.
a(n) = floor((A045965(n)+1)/2).
Other identities. For all n >= 1:
a(n) = A108228(n)+1.
a(n) = A243501(n)/2.
A108951(n) = A181812(a(n)).
a(A246263(A246268(n))) = 2*n.
As a composition of other permutations involving prime-shift operations:
a(n) = A243506(A122111(n)).
a(n) = A243066(A241909(n)).
a(n) = A241909(A243062(n)).
a(n) = A244154(A156552(n)).
a(n) = A245610(A244319(n)).
a(n) = A227413(A246363(n)).
a(n) = A245612(A243071(n)).
a(n) = A245608(A245605(n)).
a(n) = A245610(A244319(n)).
a(n) = A249745(A249824(n)).
For n >= 2, a(n) = A245708(1+A245605(n-1)).
(End)
From Antti Karttunen, Jan 17 2015: (Start)
We also have the following identities:
a(2n) = 3*a(n) - 1. [Thus a(2n+1) = 0 or 1 when reduced modulo 3. See A341346]
a(3n) = 5*a(n) - 2.
a(4n) = 9*a(n) - 4.
a(5n) = 7*a(n) - 3.
a(6n) = 15*a(n) - 7.
a(7n) = 11*a(n) - 5.
a(8n) = 27*a(n) - 13.
a(9n) = 25*a(n) - 12.
and in general:
a(x*y) = (A003961(x) * a(y)) - a(x) + 1, for all x, y >= 1.
(End)
From Antti Karttunen, Feb 10 2021: (Start)
For n > 1, a(2n) = A016789(a(n)-1), a(2n+1) = A253888(a(n)).
a(2^n) = A007051(n) for all n >= 0. [A property shared with A183209 and A254103].
(End)
a(n) = A003602(A003961(n)). - Antti Karttunen, Apr 20 2022
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/4) * Product_{p prime} ((p^2-p)/(p^2-nextprime(p))) = 1.0319981... , where nextprime is A151800. - Amiram Eldar, Jan 18 2023

New name and crossrefs to derived sequences added by Antti Karttunen, Dec 20 2014

A053669 Smallest prime not dividing n.

Original entry on oeis.org

2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 7, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 7, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 7, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 3, 2

Offset: 1

Henry Bottomley, Feb 15 2000

Smallest prime coprime to n.
Smallest k >= 2 coprime to n.
a(#(p-1)) = a(A034386(p-1)) = p is the first appearance of prime p in sequence.
a(A005408(n)) = 2; for n > 2: a(n) = A112484(n,1). - Reinhard Zumkeller, Sep 23 2011
Average value is 2.920050977316134... = A249270. - Charles R Greathouse IV, Nov 02 2013
Differs from A236454, "smallest number not dividing n^2", for the first time at n=210, where a(210)=11 while A236454(210)=8. A235921 lists all n for which a(n) differs from A236454. - Antti Karttunen, Jan 26 2014
For k >= 0, a(A002110(k)) is the first occurrence of p = prime(k+1). Thereafter p occurs whenever A007947(n) = A002110(k). Thus every prime appears in this sequence infinitely many times. - David James Sycamore, Dec 04 2024

			a(60) = 7, since all primes smaller than 7 divide 60 but 7 does not.
a(90) = a(120) = a(150) = a(180) = 7 because 90,120,150,180 all have same squarefree kernel = 30 = A002110(3), and 7 is the smallest prime which does not divide 30. - _David James Sycamore_, Dec 04 2024

T. D. Noe, Table of n, a(n) for n = 1..10000
Dylan Fridman, Juli Garbulsky, Bruno Glecer, James Grime and Massi Tron Florentin, A Prime-Representing Constant, The American Mathematical Monthly, Vol. 126, No. 1 (2019), pp. 70-73; ResearchGate link.
James Grime and Brady Haran, 2.920050977316, Numberphile video (2020)
Igor Rivin, Geodesics with one self-intersection, and other stories, Advances in Mathematics, Vol. 231, No. 5 (2012), pp. 2391-2412; arXiv preprint, arXiv:0901.2543 [math.GT], 2009-2011.

One more than A071222(n-1).
Cf. A000040, A020639, A053670, A053671, A053672, A053673, A053674, A055874, A079578, A087560, A096014, A235921, A236454, A249270, A257993 (the indices of these primes), A276086, A324895, A353526, A353528, A353529, A358754, A358755, A370125.
Cf. A002110, A007947.

a053669 n = head $ dropWhile ((== 0) . (mod n)) a000040_list
-- Reinhard Zumkeller, Nov 11 2012

f:= proc(n) local p;
p:= 2;
while n mod p = 0 do p:= nextprime(p) od:
p
end proc:
map(f, [$1..100]); # Robert Israel, May 18 2016

Table[k := 1; While[Not[GCD[n, Prime[k]] == 1], k++ ]; Prime[k], {n, 1, 60}] (* Stefan Steinerberger, Apr 01 2006 *)
With[{prs=Prime[Range[10]]},Flatten[Table[Select[prs,!Divisible[ n,#]&,1],{n,110}]]] (* Harvey P. Dale, May 03 2012 *)

a(n)=forprime(p=2,,if(n%p,return(p))) \\ Charles R Greathouse IV, Nov 20 2012

from sympy import nextprime
def a(n):
    p = 2
    while True:
        if n%p: return p
        else: p=nextprime(p) # Indranil Ghosh, May 12 2017

# using standard library functions only
import math
def a(n):
    k = 2
    while math.gcd(n,k) > 1: k += 1
    return k # Ely Golden, Nov 26 2020

(define (A053669 n) (let loop ((i 1)) (cond ((zero? (modulo n (A000040 i))) (loop (+ i 1))) (else (A000040 i))))) ;; Antti Karttunen, Jan 26 2014

a(n) = A071222(n-1)+1. [Because the right hand side computes the smallest k >= 2 such that gcd(n,k) = gcd(n-1,k-1) which is equal to the smallest k >= 2 coprime to n] - Antti Karttunen, Jan 26 2014
a(n) = 1 + Sum_{k=1..n}(floor((n^k)/k!)-floor(((n^k)-1)/k!)) = 2 + Sum_{k=1..n} A001223(k)*( floor(n/A002110(k))-floor((n-1)/A002110(k)) ). - Anthony Browne, May 11 2016
a(n!) = A151800(n). - Anthony Browne, May 11 2016
a(2k+1) = 2. - Bernard Schott, Jun 03 2019
Asymptotic mean: lim_{n->oo} (1/n) * Sum_{k=1..n} a(k) = A249270. - Amiram Eldar, Oct 29 2020
a(n) = A000040(A257993(n)) = A020639(A276086(n)) = A276086(n) / A324895(n). - Antti Karttunen, Apr 24 2022
a(n) << log n. For every e > 0, there is some N such that for all n > N, a(n) < (1 + e)*log n. - Charles R Greathouse IV, Dec 03 2022
A007947(n) = A002110(k) ==> a(n) = prime(k+1). - David James Sycamore, Dec 04 2024

More terms from Andrew Gacek (andrew(AT)dgi.net), Feb 21 2000 and James Sellers, Feb 22 2000

Entry revised by David W. Wilson, Nov 25 2006

A151799 Version 2 of the "previous prime" function: largest prime < n.

Original entry on oeis.org

2, 3, 3, 5, 5, 7, 7, 7, 7, 11, 11, 13, 13, 13, 13, 17, 17, 19, 19, 19, 19, 23, 23, 23, 23, 23, 23, 29, 29, 31, 31, 31, 31, 31, 31, 37, 37, 37, 37, 41, 41, 43, 43, 43, 43, 47, 47, 47, 47, 47, 47, 53, 53, 53, 53, 53, 53, 59, 59, 61, 61, 61, 61, 61, 61, 67, 67, 67, 67, 71, 71, 73, 73, 73, 73

Offset: 3

N. J. A. Sloane, Jun 29 2009

Version 1 of the "previous prime" function is "largest prime <= n". This produces A007917, the same sequence of numerical values, except the offset (or indexing) starts at 2 instead of 3.
Maple's "prevprime" function uses version 2.
See A007917 for references and further information.

Daniel Forgues, Table of n, a(n) for n = 3..100000

Cf. A000040, A007917, A007918, A060265, A151800.

a151799 = a007917 . (subtract 1)  -- Reinhard Zumkeller, Jul 26 2012

A151799:=n->prevprime(n): seq(A151799(n), n=3..100);

Table[NextPrime[n, -1], {n, 3, 77}] (* Jean-François Alcover, May 27 2011 *)

makelist(prev_prime(n), n, 3, 79); /* Bruno Berselli, May 20 2011 */

a(n)=precprime(n-1) \\ Charles R Greathouse IV, Jul 12 2016

from sympy import prevprime
def A151799(n):
    return prevprime(n) # Chai Wah Wu, Feb 28 2018

a(n) = A000040(A000720(n-1)). - Enrique Pérez Herrero, Jul 23 2011
a(n) = n + 1 - Sum_{k=1..n}( floor(k!^(n-1)/(n-1)!)-floor((k!^(n-1)-1)/(n-1)!) ). - Anthony Browne, May 17 2016
a(n) = A060265(floor(n/2)) for n >= 4. - Georg Fischer, Nov 29 2022

A007918 Least prime >= n (version 1 of the "next prime" function).

Original entry on oeis.org

2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13, 13, 17, 17, 17, 17, 19, 19, 23, 23, 23, 23, 29, 29, 29, 29, 29, 29, 31, 31, 37, 37, 37, 37, 37, 37, 41, 41, 41, 41, 43, 43, 47, 47, 47, 47, 53, 53, 53, 53, 53, 53, 59, 59, 59, 59, 59, 59, 61, 61, 67, 67, 67, 67, 67, 67, 71, 71, 71, 71, 73, 73

Offset: 0

R. Muller and Charles T. Le (charlestle(AT)yahoo.com)

Version 2 of the "next prime" function is "smallest prime > n". This produces A151800.
Maple uses version 2.
According to the "k-tuple" conjecture, a(n) is the initial term of the lexicographically earliest increasing arithmetic progression of n primes; the corresponding common differences are given by A061558. - David W. Wilson, Sep 22 2007
It is easy to show that the initial term of an increasing arithmetic progression of n primes cannot be smaller than a(n). - N. J. A. Sloane, Oct 18 2007
Also, smallest prime bounded by n and 2n inclusively (in accordance with Bertrand's theorem). Smallest prime >n is a(n+1) and is equivalent to smallest prime between n and 2n exclusively. - Lekraj Beedassy, Jan 01 2007
Run lengths of successive equal terms are given by A125266. - Felix Fröhlich, May 29 2022
Conjecture: if n > 1, then a(n) < n^(n^(1/n)). - Thomas Ordowski, Feb 23 2023

T. D. Noe, Table of n, a(n) for n = 0..10000
Jens Kruse Andersen, Records for primes in arithmetic progressions
K. Atanassov, On Some of Smarandache's Problems
K. Atanassov, On the 37th and 38th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 2, 83-85.
Henry Bottomley, Prime number calculator
J. Castillo, Other Smarandache Type Functions: Inferior/Superior Smarandache f-part of x, Smarandache Notions Journal, Vol. 10, No. 1-2-3, 1999, 202-204.
Andrew Granville, Prime Number Patterns
Hans Gunter, Puzzle 145. The Inferior Smarandache Prime Part and Superior Smarandache Prime Part functions; Solutions by Jean Marie Charrier, Teresinha DaCosta, Rene Blanch, Richard Kelley and Jim Howell.
Jonathan Sondow and Eric Weisstein, Bertrand's Postulate, World of Mathematics.
Eric Weisstein's World of Mathematics, Next Prime, k-tuple conjecture
Index entries for sequences related to primes in arithmetic progressions

Cf. A000040, A007917, A008407, A020497, A061558, A125266, A151799, A151800, A171400.

a007918 n = a007918_list !! n
a007918_list = 2 : 2 : 2 : concat (zipWith
              (\p q -> (replicate (fromInteger(q - p)) q))
                                   a000040_list $ tail a000040_list)
-- Reinhard Zumkeller, Jul 26 2012

[2] cat [NextPrime(n-1): n in [1..80]]; // Vincenzo Librandi, Jan 14 2016

A007918 := n-> nextprime(n-1); # M. F. Hasler, Apr 09 2008

NextPrime[Range[-1, 72]] (* Jean-François Alcover, Apr 18 2011 *)

A007918(n)=nextprime(n)  \\ M. F. Hasler, Jun 24 2011

for(x=0,100,print1(nextprime(x)",")) \\ Cino Hilliard, Jan 15 2007

from sympy import nextprime
def A007918(n): return nextprime(n-1) # Chai Wah Wu, Apr 22 2022

For n > 1: a(n) = A000040(A049084(A007917(n)) + 1 - A010051(n)). - Reinhard Zumkeller, Jul 26 2012

a(n) = A151800(n-1). - Seiichi Manyama, Apr 02 2018

A003973 Inverse Möbius transform of A003961; a(n) = sigma(A003961(n)), where A003961 shifts the prime factorization of n one step towards the larger primes.

Original entry on oeis.org

1, 4, 6, 13, 8, 24, 12, 40, 31, 32, 14, 78, 18, 48, 48, 121, 20, 124, 24, 104, 72, 56, 30, 240, 57, 72, 156, 156, 32, 192, 38, 364, 84, 80, 96, 403, 42, 96, 108, 320, 44, 288, 48, 182, 248, 120, 54, 726, 133, 228, 120, 234, 60, 624, 112, 480, 144, 128, 62, 624, 68

Offset: 1

Marc LeBrun

Sum of the divisors of the prime shifted n, or equally, sum of the prime shifted divisors of n. - Antti Karttunen, Aug 17 2020

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Index entries for sequences computed from indices in prime factorization.
Index entries for sequences related to sigma(n).

Cf. A000203, A000290 (positions of odd terms), A003961, A007814, A048673, A108228, A151800, A295664, A336840.
Permutation of A008438.
Used in the definitions of the following sequences: A326042, A336838, A336841, A336844, A336846, A336847, A336848, A336849, A336850, A336851, A336852, A336856, A336931, A336932.
Cf. also A003972.

b[1] = 1; b[p_?PrimeQ] := b[p] = Prime[ PrimePi[p] + 1]; b[n_] := b[n] = Times @@ (b[First[#]]^Last[#] &) /@ FactorInteger[n]; a[n_] := Sum[ b[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 70}]  (* Jean-François Alcover, Jul 18 2013 *)

aPrime(p,e)=my(q=nextprime(p+1));(q^(e+1)-1)/(q-1)
a(n)=my(f=factor(n));prod(i=1,#f~,aPrime(f[i,1],f[i,2])) \\ Charles R Greathouse IV, Jul 18 2013

A003973(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); sigma(factorback(f)); }; \\ Antti Karttunen, Aug 06 2020

from math import prod
from sympy import factorint, nextprime
def A003973(n): return prod(((q:=nextprime(p))**(e+1)-1)//(q-1) for p,e in factorint(n).items()) # Chai Wah Wu, Jul 05 2022

Multiplicative with a(p^e) = (q^(e+1)-1)/(q-1) where q = nextPrime(p). - David W. Wilson, Sep 01 2001
From Antti Karttunen, Aug 06-12 2020: (Start)
a(n) = Sum_{d|n} A003961(d) = Sum_{d|A003961(n)} d.
a(n) = A000203(A003961(n)) = A000593(A003961(n)).
a(n) = 2*A336840(n) - A000005(n) = 2*Sum_{d|n} (A048673(d) - (1/2)).
a(n) = A008438(A108228(n)) = A008438(A048673(n)-1).
a(n) = A336838(n) * A336856(n).
a(n) is odd if and only if n is a square.
(End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/2) * Product_{p prime} p^3/((p+1)*(p^2-nextprime(p))) = 3.39513795..., where nextprime is A151800. - Amiram Eldar, Dec 08 2022, May 30 2025

More terms from David W. Wilson, Aug 29 2001

Secondary name added by Antti Karttunen, Aug 06 2020

A262038 Least palindrome >= n.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 11, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77

Offset: 0

M. F. Hasler, Sep 08 2015

Could be called nextpalindrome() in analogy to the nextprime() function A007918. As for the latter (A151800), there is the variant "next strictly larger palindrome" which equals a(n+1), and thus differs from a(n) iff n is a palindrome; see PARI code.

Might also be called palindromic ceiling function in analogy to the name "palindromic floor" proposed for A261423.

M. F. Hasler, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Palindromic Number
Wikipedia, Palindromic number
Index entries for sequences related to palindromes

Cf. A002113, A261423, A262037.

Sequences related to palindromic floor and ceiling: A175298, A206913, A206914, A261423, A262038, and the large block of consecutive sequences beginning at A265509.

a262038 n = a262038_list !! n
a262038_list = f 0 a002113_list where
   f n ps'@(p:ps) = p : f (n + 1) (if p > n then ps' else ps)
-- Reinhard Zumkeller, Sep 16 2015

palQ[n_] := Block[{d = IntegerDigits@ n}, d == Reverse@ d]; Table[k = n; While[! palQ@ k, k++]; k, {n, 0, 80}] (* Michael De Vlieger, Sep 09 2015 *)

{A262038(n, d=digits(n), p(d)=sum(i=1, #d\2, (10^(i-1)+10^(#d-i))*d[i],if(bittest(#d,0),10^(#d\2)*d[#d\2+1])))= for(i=(#d+3)\2,#d,d[i]>d[#d+1-i]&&break;(d[i]9||return(p(d));d[i]=0);10^#d+1} \\ For a function "next strictly larger palindrome", delete the i==#d and n<10... part. - M. F. Hasler, Sep 09 2015

def A262038(n):
    sl = len(str(n))
    l = sl>>1
    if sl&1:
        w = 10**l
        n2 = w*10
        for y in range(n//(10**l),n2):
            k, m = y//10, 0
            while k >= 10:
                k, r = divmod(k,10)
                m = 10*m + r
            z = y*w + 10*m + k
            if z >= n:
                return z
    else:
        w = 10**(l-1)
        n2 = w*10
        for y in range(n//(10**l),n2):
            k, m = y, 0
            while k >= 10:
                k, r = divmod(k,10)
                m = 10*m + r
            z = y*n2 + 10*m + k
            if z >= n:
                return z # Chai Wah Wu, Sep 14 2022

A013632 Difference between n and the next prime greater than n.

Original entry on oeis.org

2, 1, 1, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 2, 1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 2, 1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3

Offset: 0

N. J. A. Sloane

Alternatively, a(n) is the smallest positive k such that n + k is prime. - N. J. A. Sloane, Nov 18 2015
Except for a(0) and a(1), a(n) is the least k such that gcd(n!, n + k) = 1. - Robert G. Wilson v, Nov 05 2010
This sequence uses the "strictly larger" variant A151800 of the nextprime function, rather than A007918. Therefore all terms are positive and a(n) = 1 if and only if n + 1 is a prime. - M. F. Hasler, Sep 09 2015
For n > 0, a(n) and n are of opposite parity. Also, by Bertrand's postulate (actually a theorem), for n > 1, a(n) < n. - Zak Seidov, Dec 27 2018

			a(30) = 1 because 31 is the next prime greater than 30 and 31 - 30 = 1.
a(31) = 6 because 37 is the next prime greater than 31 and 37 - 31 = 6.

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
Brăduţ Apostol, Laurenţiu Panaitopol, Lucian Petrescu, and László Tóth, Some properties of a sequence defined with the aid of prime numbers, arXiv:1503.01086 [math.NT], 2015.
Brăduţ Apostol, Laurenţiu Panaitopol, Lucian Petrescu, and László Tóth, Some Properties of a Sequence Defined with the Aid of Prime Numbers, J. Int. Seq. 18 (2015) # 15.5.5.

Cf. A007918, A007920, A084695, A151800.

[NextPrime(n) - n: n in [0..100]]; // Vincenzo Librandi, Dec 27 2018

Maple
```
[ seq(nextprime(i)-i,i=0..100) ];
```

Array[NextPrime[#] - # &, 105, 0] (* Robert G. Wilson v, Nov 05 2010 *)

a(n) = nextprime(n+1) - n; \\ Michel Marcus, Mar 04 2015

[next_prime(n) - n for n in range(121)] # G. C. Greubel, May 12 2023

a(n) = Prime(1 + PrimePi(n)) - n = A084695(n, 1) (for n > 0). - G. C. Greubel, May 12 2023

Incorrect comment removed by Charles R Greathouse IV, Mar 18 2010

More terms from Robert G. Wilson v, Nov 05 2010

A366833 Number of times n appears in A362965 (number of primes <= the n-th prime power).

Original entry on oeis.org

1, 2, 1, 3, 1, 2, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Paolo Xausa, Oct 25 2023

nonn

Conjecture: a(n) can be only 1, 2, or 3 (with the first occurrences of 3 appearing at n = 4, 9, 30, 327 and 3512).

One less than the number of prime powers between prime(n) and prime(n+1), inclusive. - Gus Wiseman, Jan 09 2025

Paolo Xausa, Table of n, a(n) for n = 1..10000
Paolo Xausa, 1200 X 1200 raster image of a(n), n = 1..1440000, read left to right, top to bottom, showing a(n) = 1 in blue, a(n) = 2 in white and a(n) = 3 in red.

Run lengths of A362965.
Subtracting one gives A080101.
For non prime powers we have A368748.
Positions of terms > 1 are A377057.
Positions of 1 are A377286.
Positions of 2 are A377287.
For perfect powers we have A377432.
For squarefree we have A373198.
A000015 gives the least prime power >= n, difference A377282.
A000040 lists the primes, differences A001223.
A000961 lists the powers of primes, differences A057820.
A024619 and A361102 list the non prime powers, differences A375708 and A375735.
A031218 gives the greatest prime power <= n, difference A276781.
A046933(n) counts the interval from A008864(n) to A006093(n+1).
A246655 lists the prime powers not including 1.
A366835 counts primes between prime powers.
Cf. A053607, A053706, A065514, A068435, A080102, A304521, A345531, A377289.
Cf. A024620, A027883, A067871, A075526, A080769, A151800, A377436, A379157.

With[{upto=1000},Map[Length,Most[Split[PrimePi[Select[Range[upto],PrimePowerQ]]]]]] (* Considers prime powers up to 1000 *)

a(n) = A080101(n) + 1. - Gus Wiseman, Jan 09 2025

cp's OEIS Frontend

A380330 a(n) = A151800(prime(n)*A151800(n)).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

A000040 The prime numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Magma

Maple

Mathematica

Maxima

PARI

PARI

PARI

PARI

Python

Sage

Sage

Formula

A048673 Permutation of natural numbers: a(n) = (A003961(n)+1) / 2 [where A003961(n) shifts the prime factorization of n one step towards larger primes].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Scheme

Formula

Extensions

A053669 Smallest prime not dividing n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Scheme

Formula

Extensions

A151799 Version 2 of the "previous prime" function: largest prime < n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell