A317357 -id:A317357 - 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

A317058 a(n) is the smallest composite k such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

Original entry on oeis.org

4, 341, 473, 4, 4, 133, 497, 4, 4, 15, 9, 4, 4, 143, 35, 4, 4, 51, 57, 4, 4, 77, 253, 4, 4, 65, 9, 4, 4, 115, 155, 4, 4, 187, 35, 4, 4, 9, 247, 4, 4, 287, 2051, 4, 4, 15, 33, 4, 4, 35, 85, 4, 4, 9, 9, 4, 4, 551, 1711, 4, 4, 713, 21, 4, 4, 55, 77, 4, 4, 35, 35, 4

Offset: 1

Thomas Ordowski, Jul 26 2018

nonn

According to the Agoh-Giuga conjecture, a(n) <> n+1.

a(n) = 4 if and only if n == {0, 1} (mod 4).

Chai Wah Wu, Table of n, a(n) for n = 1..9661 (n = 1..500 from Seiichi Manyama)
Wikipedia, Agoh-Giuga conjecture

Cf. A000790, A133906, A133907, A317357, A317358.

a[n_] := Block[{k = 4}, While[PrimeQ[k] || Mod[Sum[PowerMod[j, k-1, k], {j, n}], k] != Mod[n, k], k++]; k]; Array[a, 72] (* Giovanni Resta, Jul 26 2018 *)

a(n) = forcomposite(k=1,, if (sum(j=1,n, Mod(j,k)^(k-1)) == n, return (k));); \\ Michel Marcus, Jul 26 2018

from sympy import isprime
def g(n,p,q): # compute (-n + sum_{k=1,n} k^p)  mod q
    c = (-n) % q
    for k in range(1,n+1):
        c = (c+pow(k,p,q)) % q
    return c
def A317058(n):
    k = 2
    while isprime(k) or g(n,k-1,k):
        k += 1
    return k # Chai Wah Wu, Jul 30 2018

More terms from Giovanni Resta, Jul 26 2018

A317358 a(n) is the smallest number k > 1 such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

Original entry on oeis.org

2, 3, 5, 2, 2, 7, 11, 2, 2, 3, 3, 2, 2, 17, 17, 2, 2, 3, 3, 2, 2, 23, 29, 2, 2, 5, 3, 2, 2, 31, 37, 2, 2, 37, 35, 2, 2, 3, 41, 2, 2, 43, 47, 2, 2, 3, 3, 2, 2, 5, 5, 2, 2, 3, 3, 2, 2, 59, 61, 2, 2, 67, 3, 2, 2, 55, 71, 2, 2, 35, 35, 2, 2, 3, 5, 2, 2, 5, 5, 2, 2

Offset: 1

Thomas Ordowski, Jul 26 2018

nonn

a(n) = 2 if and only if n == {0, 1} (mod 4).
a(n) <= A151800(n).
A133906(n) <= a(n) <= A133907(n).
The sequence is unbounded.
Numbers n such that a(n-1) = n are 2, 3, 7, 23, 31, 43, 59, 139, 283, ...
By the Agoh-Giuga conjecture, if a(n-1) = n, then n is a prime.
It seems that if a(n) > n, then a(n) is a prime (the next prime after n).
If a(n) = n, then n is in A121707. These numbers are 35, 143, 187, 215, ...
Conjecture: all composite terms of the sequence are A121707.

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (n = 1..1000 from Seiichi Manyama)
Wikipedia, Agoh-Giuga conjecture

Cf. A133906, A133907, A151800, A121707, A317058, A317357.

a[n_] := Block[{k=2}, While[Mod[Sum[PowerMod[j, k-1, k], {j, n}], k] != Mod[n, k], k++]; k]; Array[a, 81] (* Giovanni Resta, Jul 29 2018 *)

a(n) = for(k=2,oo, if (sum(j=1,n, Mod(j,k)^(k-1)) == n, return (k));); \\ Michel Marcus, Jul 26 2018

def g(n,p,q): # compute (-n + sum_{k=1,n} k^p)  mod q
    c = (-n) % q
    for k in range(1,n+1):
        c = (c+pow(k,p,q)) % q
    return c
def A317358(n):
    k = 2
    while g(n,k-1,k):
        k += 1
    return k # Chai Wah Wu, Jul 30 2018

More terms from Michel Marcus, Jul 26 2018

A317587 a(n) is the smallest number m > n such that Sum_{k=1..n-1} k^(m-1) == n-1 (mod m).

Original entry on oeis.org

3, 5, 5, 6, 7, 11, 11, 11, 11, 13, 13, 16, 17, 17, 17, 19, 19, 23, 23, 23, 23, 29, 29, 29, 29, 29, 29, 31, 31, 37, 37, 37, 36, 37, 37, 40, 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

Offset: 2

Thomas Ordowski, Aug 01 2018

nonn

a(n) <= A317357(n-1).
a(n) <= A151800(n), where a(n) < A151800(n) for n = 5, 13, 34, 37, ... with composite terms a(n) = 6, 16, 36, 40, ...
The smallest odd composite term is a(201) = 207. Are there any more? - Michel Marcus, Jul 02 2018
Conjecture: If p is a prime, then odd a(p) is the next prime after p. - Thomas Ordowski, Aug 06 2018

Cf. A065091, A151800, A317357.

Array[Block[{m = # + 1}, While[Mod[Sum[k^(m - 1), {k, # - 1}], m] != # - 1, m++]; m] &, 69, 2] (* Michael De Vlieger, Aug 02 2018 *)

a(n) = for(m=n+1, oo, if (sum(k=1, n-1, Mod(k, m)^(m-1)) == Mod(n-1, m), return (m)); ); \\ Michel Marcus, Aug 01 2018

More terms from Michel Marcus, Aug 01 2018

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

A317058 a(n) is the smallest composite k such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A317358 a(n) is the smallest number k > 1 such that 1^(k-1) + 2^(k-1) + ... + n^(k-1) == n (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A317587 a(n) is the smallest number m > n such that Sum_{k=1..n-1} k^(m-1) == n-1 (mod m).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions