A066169 -id:A066169 - cp's OEIS frontend

A151800 Least prime > n (version 2 of the "next prime" function).

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, 79

Offset: 0

N. J. A. Sloane, Jun 29 2009

Version 1 of the "next prime" function is A007918: smallest prime >= n.
Maple's nextprime() is this version 2; PARI/GP's nextprime() is version 1.
See A007918 for references and further information.
a(n) is the smallest number greater than one that is not divisible by any 1 < k <= n. Consider a multi-round election in which, in each round, voters each cast one vote for one of the remaining candidates. Then, any candidates which receive the fewest votes in that round are eliminated. This repeats until either one candidate remains, who wins the election, or no candidates remain. a(n) is the smallest nontrivial number of voters that can guarantee a winner if the election initially has n > 0 candidates. This is a consequence of the first fact. - Thomas Anton, Mar 30 2020
Conjecture: if n > 3, then a(n) < n^(n^(1/n)). - Thomas Ordowski, Feb 23 2023

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

Cf. A000040, A007917, A007918, A061558, A066169, A151799, A317357, A036234.

a151800 = a007918 . (+ 1)  -- Reinhard Zumkeller, Jul 26 2012

[NextPrime(n): n in [0..80]]; // Vincenzo Librandi, Jan 14 2016

map(nextprime,[$0..100]); # Robert Israel, Jul 15 2015

NextPrime[Range[0,80]] (* Harvey P. Dale, May 21 2011 *)

makelist(next_prime(n), n, 0, 73); /* Bruno Berselli, May 20 2011 */

a(n)=nextprime(n+1) \\ Charles R Greathouse IV, Apr 28 2015

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

a(n) = A007918(n+1).
a(n) = 1 + Sum_{k=1..2n} (floor((n!^k)/k!) - floor(((n!^k)-1)/k!)). - Anthony Browne, May 11 2016
a(n) = A000040(A036234(n)). - Ridouane Oudra, Sep 30 2024

A057237 Maximum k <= n such that 1, 2, ..., k are all relatively prime to n.

Original entry on oeis.org

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 2, 1, 16, 1, 18, 1, 2, 1, 22, 1, 4, 1, 2, 1, 28, 1, 30, 1, 2, 1, 4, 1, 36, 1, 2, 1, 40, 1, 42, 1, 2, 1, 46, 1, 6, 1, 2, 1, 52, 1, 4, 1, 2, 1, 58, 1, 60, 1, 2, 1, 4, 1, 66, 1, 2, 1, 70, 1, 72, 1, 2, 1, 6, 1, 78, 1, 2, 1, 82, 1, 4, 1, 2, 1, 88, 1, 6, 1, 2, 1

Offset: 1

Leroy Quet, Sep 20 2000

nonn

In reduced residue system for n [=RRS(n)] the [initial] segment of consecutive integers, i.e. of which no number is missing is {1,2,....,a[n]}. The first missing term from RRS(n) is 1+a(n), the least prime divisor.. E.g. n=121 : RRS[121] = {1,2,3,4,5,6,7,8,9,10,lag,12,..}, i.e. no 11 is in RRS; a[n] is the length of longest lag-free number segment consisting of consecutive integers, since A020639[n] divides n. - Labos Elemer, May 14 2003

a(n) is also the difference between the smallest two divisors of n, (the column 1 of A193829), if n >= 2. - Omar E. Pol, Aug 31 2011

			a(25) = 4 because 1, 2, 3 and 4 are relatively prime to 25.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A020639, A083218.

Cf. A066169.

Join[{1},Table[Length[Split[Boole[CoprimeQ[n,Range[n-1]]]][[1]]],{n,2,100}]] (* Harvey P. Dale, Dec 28 2021 *)

a(n) = if (n==1, 1, factor(n)[1,1] - 1); \\ Michel Marcus, May 29 2015

For n >= 2, a(n) = (smallest prime dividing n) - 1 = A020639(n) - 1.

For n >= 2, a(n) = (n-1) mod (smallest prime dividing n); cf. A083218. - Reinhard Zumkeller, Apr 22 2003

A159477 a(n) = smallest prime >= n, if 1 is counted as a prime.

Original entry on oeis.org

1, 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

Offset: 1

Jaroslav Krizek, Apr 13 2009

nonn

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A000040, A002808.
Cf. A008578.
Essentially the same as A066169 and A007918.

a159477 n = a159477_list !! (n-1)
a159477_list = 1 : concat
   (zipWith (\p q -> replicate (fromInteger $ (q - p)) q)
            a008578_list $ tail a008578_list)
-- Reinhard Zumkeller, Nov 09 2011

Join[{1},NextPrime[Range[60]]] (* Harvey P. Dale, Jan 04 2012 *)

For n >= 2, a(n) = A007918(n). a(p) = p, a(c) = a(c+1), for p = primes (A000040), c = composite numbers (A002808).

A270753 The least prime q > p for which n = p + q - r for some prime r, where p = A270003(n).

Original entry on oeis.org

5, 3, 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

Offset: 1

Clark Kimberling, Apr 26 2016

			n   p   q   r
1   3   5   7
2   2   3   3
3   2   3   2
4   2   5   3
5   2   5   2
6   2   7   3
7   2   7   2

Clark Kimberling, Table of n, a(n) for n = 1..10000

Cf. A000040, A270003, A271353.

t = Join[{{1, {3, 5, 7}}, {2, {2, 3, 3}}}, Table[If[PrimeQ[n], {n, {2, n, 2}}, p = If[EvenQ[2 + NextPrime[n, 1] - n], 3, 2]; NestWhile[# + 1 &, 1, ! PrimeQ[r = (p + (q = NextPrime[n, #])) - n] &]; {n, {p, q, r}}], {n, 3, 300}]];
Map[#[[2]][[1]] &, t] (* p, A270003 *)
Map[#[[2]][[2]] &, t] (* q, A270753 *)
Map[#[[2]][[3]] &, t] (* r, A271353 *)
(* Peter J. C. Moses, Apr 26 2016 *)

Conjecture: a(n) = A066169(n-1) for n>2. - R. J. Mathar, Jun 21 2025

A266620 a(n) = least non-divisor of n!.

Original entry on oeis.org

2, 3, 4, 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

Offset: 1

Jeffrey Shallit, Jan 01 2016

It appears that a(n) = A151800(n) with the exception of n = 3. - Robert Israel, Jan 13 2016

			For n = 4 the least non-divisor of 4! = 24 = 2^3 * 3 is 5.
For n = 5 the least non-divisor of 5! = 120 = 2^3 * 3 * 5 is 7.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A007918, A007978, A066169, A115627, A151800.

N:= 100: # to get a(1)..a(N)
m:= 1 + numtheory:-pi(N):
Primes:= [seq(ithprime(i),i=1..m)]:
for i from 1 to m do pindex[Primes[i]]:= i od:
V:= Vector(m):
k:= 0:
for n from 1 to N do
  for f in ifactors(n)[2] do
    q:= pindex[f[1]];
    V[q]:= V[q] + f[2];
    k:= max(k, q);
  od:
  a[n]:= min(seq(Primes[i]^(1+V[i]),i=1..k),Primes[k+1]);
od:
seq(a[n],n=1..N); # Robert Israel, Jan 13 2016

Table[Complement[Range[2n], Divisors[n!]][[1]], {n, 30}] (* Alonso del Arte, Sep 23 2017 *)
Table[Block[{m = n!, k = n + 1}, While[Divisible[m, k], k++]; k], {n, 67}] (* Michael De Vlieger, Sep 23 2017 *)

from sympy import nextprime
def A266620(n): return 4 if n == 3 else nextprime(n) # Chai Wah Wu, Feb 22 2023

a(n) = min_{k >= 1} prime(k)^(1 + v(n!, prime(k))) where v(m, p) is the p-adic order of m. - Robert Israel, Jan 13 2016

a(n) = prime(pi(n) + 1) except for n = 3, in which case the least non-divisor of 3! is 4, not 5. - Alonso del Arte, Sep 23 2017

A093702 a(n) = smallest prime p>a(n-1) such that n divides (p-1) and (p-1)/n > (a(n-1)-1)/(n-1), a(1) = 2.

Original entry on oeis.org

2, 5, 13, 29, 41, 61, 113, 137, 163, 191, 331, 373, 443, 491, 541, 593, 647, 739, 1103, 1181, 1303, 1409, 1657, 1753, 1901, 2003, 2161, 2269, 2437, 2551, 2729, 3041, 3169, 3299, 3571, 3709, 3923, 4219, 4447, 4721, 5003, 5167, 5333, 5501, 5851

Offset: 1

Reinhard Zumkeller, Apr 10 2004

nonn

A093701(n) = (a(n)-1)/n.

Cf. A066169.

A263981 Least even k such that phi(k) >= n.

Original entry on oeis.org

2, 4, 8, 8, 14, 14, 16, 16, 22, 22, 26, 26, 32, 32, 32, 32, 38, 38, 44, 44, 46, 46, 52, 52, 58, 58, 58, 58, 62, 62, 64, 64, 74, 74, 74, 74, 82, 82, 82, 82, 86, 86, 92, 92, 94, 94, 104, 104, 106, 106, 106, 106, 116, 116, 116, 116, 118, 118, 122, 122, 128, 128

Offset: 1

Charles R Greathouse IV, Oct 30 2015

nonn

Representation number of the bipartite graph K_{1,n} (the n-pointed star graph), see Akhtar, Evans, & Pritikin. A graph G is said to have a representation mod r if each of its vertices can be given a unique label mod r such that two vertices are adjacent if and only if the difference of their representation numbers is coprime to r. The representation number of G is the least r for which G has a representation mod r, see Erdős & Evans.

			The star graph with center C and other points P1, P2, P3 can be labeled with C = 0 mod 8, P1 = 1 mod 8, P2 = 3 mod 8, and P3 = 5 mod 8 so that two points are adjacent iff their difference is odd (=coprime to 8), so a(3) <= 8.

Reza Akhtar, Anthony B. Evans, and Dan Pritikin, Representation number of stars, Integers 10 (2010), pp. 733-745. #A54
P. Erdős and A. B. Evans, Representations of graphs and orthogonal Latin square graphs, J. Graph Theory 13:5 (1989), pp. 593-595.

Cf. A066169, A151800.

Table[k = 2; While[EulerPhi@ k < n, k += 2]; k, {n, 62}] (* Michael De Vlieger, Nov 16 2015 *)

/* oo = 10^10; */ /* uncomment for earlier pari versions */ a(n)=forstep(k=2*n,oo,2,if(eulerphi(k)>=n,return(k))) \\ Charles R Greathouse IV, Oct 30 2015

a(n)=my(k=2*n); while(eulerphi(k)Charles R Greathouse IV, Nov 02 2015

2n <= a(n) <= 2*A151800(n).

cp's OEIS Frontend

A151800 Least prime > n (version 2 of the "next prime" function).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

Python

Formula

A057237 Maximum k <= n such that 1, 2, ..., k are all relatively prime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A159477 a(n) = smallest prime >= n, if 1 is counted as a prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A270753 The least prime q > p for which n = p + q - r for some prime r, where p = A270003(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A266620 a(n) = least non-divisor of n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A093702 a(n) = smallest prime p>a(n-1) such that n divides (p-1) and (p-1)/n > (a(n-1)-1)/(n-1), a(1) = 2.

Views

Author

Keywords

Comments

Crossrefs

A263981 Least even k such that phi(k) >= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI