A271221 -id:A271221 - cp's OEIS frontend

A083876 Least pseudoprime to base 2 through base prime(n).

341, 1105, 1729, 29341, 29341, 162401, 252601, 252601, 252601, 252601, 252601, 252601, 1152271, 2508013, 2508013, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 6733693, 6733693, 6733693

Offset: 1

Robert G. Wilson v, May 06 2003

nonn

Records: 341, 1105, 1729, 29341, 162401, 252601, 1152271, 2508013, 3828001, 6733693, 17098369, 17236801, 29111881, 82929001, 172947529, 216821881, 228842209, 366652201, .... - Robert G. Wilson v, May 11 2012
Conjecture: for n > 1, a(n) is the smallest Carmichael number k with lpf(k) > prime(n). It seems that such Carmichael numbers have exactly three prime factors. - Thomas Ordowski, Apr 18 2017
The conjecture is true if a(n) < A285549(n) for all n > 1. It holds for all a(n) < 2^64. - Max Alekseyev and Thomas Ordowski, Mar 13 2018
If prime(n) < m < a(n), then m is prime if and only if p^(m-1) == 1 (mod m) for every prime p <= prime(n). - Thomas Ordowski, Mar 05 2018
By this conjecture in the second comment, a(n) <= A135720(n+1), with equality for n > 1 iff a(n) < a(n+1), namely for n = 2, 3, 5, 6, 12, 13, 15, 25, 28, 29, ... For such n, a(n) gives all terms of A300629 > 561. - Thomas Ordowski, Mar 10 2018

Giovanni Resta, Table of n, a(n) for n = 1..1000 (first 100 terms from Robert G. Wilson v)

Cf. A002997, A001567, A052155, A083737, A087788, A083739, A135720, A141768, A250199, A271221, A285549, A300629.

k = 4; Do[l = Table[ Prime[i], {i, 1, n}]; While[ PrimeQ[k] || Union[PowerMod[l, k - 1, k]] != {1}, k++ ]; Print[k], {n, 1, 29}]

isps(k, n) = {if (isprime(k), return (0)); my(nbok = 0); for (b=2, prime(n), if (Mod(b, k)^(k-1) == 1, nbok++, break)); if (nbok==prime(n)-1, return (1));}
a(n) = {my(k=2); while (!isps(k, n), k++); return (k);} \\ Michel Marcus, Apr 27 2018

A300629 a(1) = 561; a(n+1) = smallest Fermat pseudoprime to all natural bases up to lpf(a(n)).

Original entry on oeis.org

561, 1105, 1729, 29341, 162401, 252601, 1152271, 2508013, 3828001, 6733693, 17098369, 17236801, 29111881, 82929001, 172947529, 216821881, 228842209, 366652201, 413138881, 2301745249, 2438403661, 5255104513, 5781222721, 8251854001, 12173703001, 13946829751, 15906120889, 23224518901, 31876135201, 51436355851, 57274147841, 58094662081

Offset: 1

Thomas Ordowski, Mar 10 2018

nonn

It is sufficient to consider only prime bases: a(n+1) is the least composite number k such that p^(k-1) == 1 (mod k) for every prime p <= lpf(a(n)), with a(1) = 561.
Conjecture: a(n+1) is the smallest Carmichael number k such that lpf(k) > lpf(a(n)), with a(1) = 561. It seems that such Carmichael numbers have exactly three prime factors.
The above conjecture is true if A083876(n) < A285549(n) for all n > 1, but has not been proven; there is no counterexample up to a(n) < 2^64. - Max Alekseyev and Thomas Ordowski, Mar 13 2018
Carl Pomerance (in a letter to the author) wrote, Mar 13 2018: (Start)
Assuming a strong form of the prime k-tuples conjecture, if there are no small counterexamples, there are likely to be none.
Here's why.
Assuming prime k-tuples, there are infinitely many Carmichael numbers of the form (6k+1)(12k+1)(18k+1), where each factor is prime. And from Bateman-Horn, these are fairly thickly distributed. There are other even better triples such as (60k+41)(90k+61)(150k+101), where "better" means the least prime factor is not so far below the cube root.
So, to get into the sequence, a number needs to be a Fermat pseudoprime for every base up to nearly the cube root.
However, it's a theorem that a sufficiently large number with this property must be a Carmichael number. (End)
Theorem: if lpf(a(n)) < m < a(n), then m is prime if and only if p^(m-1) == 1 (mod m) for every prime p <= lpf(a(n)). - Thomas Ordowski, Mar 13 2018
lpf(a(n)) are listed in A300748. - Max Alekseyev, Mar 13 2018
For m > 1, A135720(m) >= A083876(m-1), with equality iff lpf(a(n)) = prime(m); by this conjecture in the second comment. - Thomas Ordowski, Mar 13 2018

Max Alekseyev, Table of n, a(n) for n = 1..138

Cf. A002997, A020639, A083876, A271221, A285549, A300748.

Subsequence of A087788 and of A135720.

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

Original entry on oeis.org

4, 341, 473, 6, 10, 133, 497, 14, 12, 15, 15, 16, 18, 143, 35, 20, 32, 51, 57, 38, 28, 77, 253, 36, 30, 65, 39, 36, 58, 115, 155, 62, 36, 187, 119, 40, 74, 57, 247, 52, 80, 287, 2051, 86, 55, 69, 69, 94, 54, 175, 85, 65, 65, 159, 69, 70, 64, 551, 1711, 72

Offset: 1

Thomas Ordowski, Jul 26 2018

nonn

According to the Agoh-Giuga conjecture, a(n) > n+1.
a(n) > A151800(n) for all n < 33.
a(n) <= A271221(n) for n > 1.

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

Cf. A151800, A271221, A317058, A317358.

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

a(n) = forcomposite(k=n+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 A317357(n):
    k = n+1
    while isprime(k) or g(n,k-1,k):
        k += 1
    return k # Chai Wah Wu, Jul 31 2018

More terms from Giovanni Resta, Jul 26 2018

A007324 Least number for which Solovay-Strassen primality test on bases < prime(n) fails.

Original entry on oeis.org

9, 561, 1729, 1729, 399001, 399001, 1857241, 1857241, 6189121, 14469841, 14469841, 14469841

Offset: 1

N. J. A. Sloane, Eric Bach (bach(AT)cs.wisc.edu)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Wikipedia, Solovay-Strassen primality test

Cf. A083876, A271221, A329726.

a(n) = my(b, p=factorback(primes(n-1))); forcomposite(k=9, oo, if(gcd(k, p)==1, b=2; while(Mod(b, k)^(k\2) == kronecker(b, k), b++); if(b>=prime(n), return(k)))); \\ Jinyuan Wang, Jun 04 2022

Offset changed to 1 and a(1) corrected by Jinyuan Wang, Jun 04 2022

A354694 Least Euler pseudoprime to base 2 through base prime(n).

Original entry on oeis.org

341, 1729, 1729, 46657, 46657, 162401, 399001, 399001, 399001, 399001, 488881, 3057601, 3057601, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 3828001, 17098369, 17098369, 17098369, 17098369, 17236801, 17236801

Offset: 1

Jinyuan Wang, Jun 04 2022

nonn

a(n) is coprime to A002110(n).

Eric Weisstein's World of Mathematics, Euler Pseudoprime.

Cf. A002110, A007324, A083876, A271221.

a(n) = my(b, m, p=factorback(primes(n))); forcomposite(k=9, oo, if(gcd(k, p)==1, b=2; while((m=Mod(b, k)^(k\2)) == 1 || m == k-1, b++); if(b>prime(n), return(k))));

A348258 Records in A083876.

Original entry on oeis.org

341, 1105, 1729, 29341, 162401, 252601, 1152271, 2508013, 3828001, 6733693, 17098369, 17236801, 29111881, 82929001, 172947529, 216821881, 228842209, 366652201, 413138881, 2301745249, 2438403661, 5255104513, 5781222721, 8251854001, 12173703001, 13946829751, 15906120889, 23224518901

Offset: 1

Robert G. Wilson v, Oct 08 2021

nonn

Cf. A083876, A271221, A300629.

f[1] = 341; f[2] = 1105; f[3] = 1729; f[n_] := f[n] = Block[{k = f[n -1], lp = Prime@ Range[2, n -1], p = Prime@ n}, While[ PrimeQ@ k || PowerMod[2, k -1, k] != 1 || PowerMod[p, k -1, k] != 1 || Union[ PowerMod[lp, k -1, k]] != {1}, k += 2]; k]; Union[ Table[ f@n, {n, 1012}]]

cp's OEIS Frontend

A083876 Least pseudoprime to base 2 through base prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A300629 a(1) = 561; a(n+1) = smallest Fermat pseudoprime to all natural bases up to lpf(a(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

A317357 a(n) is the smallest composite k > n 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

A007324 Least number for which Solovay-Strassen primality test on bases < prime(n) fails.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

A354694 Least Euler pseudoprime to base 2 through base prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A348258 Records in A083876.

Views

Author

Keywords

Crossrefs

Programs

Mathematica