A134307 -id:A134307 - cp's OEIS frontend

A242830 For p = prime(n), a(n) = number of bases 1 < b < p such that b^(p-1) == 1 (mod p^2).

0, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 2, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 2, 2, 1, 0, 0, 1, 0, 2, 0, 0, 0, 1, 1, 0, 1, 1, 2, 1, 0, 2, 1, 0, 1, 0, 1, 1, 3, 0, 0, 1, 1, 1, 1, 0, 2, 0, 3, 0, 2, 2, 2, 2, 2, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 2, 0, 0, 4, 0, 1

Offset: 1

Felix Fröhlich, Jul 12 2014

nonn

a(n) > 0 if and only if p is in A134307.

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

Cf. A001220, A039678, A134307, A185103, A244249.

A242830:= proc(n) local p;
  p:= ithprime(n);
  numboccur(1,[seq(b &^ (p-1) mod p^2, b=2..p-1)]);
end proc;
seq(A242830(n),n=1..1000); # Robert Israel, Jul 16 2014

a[n_] := With[{p = Prime[n]}, Length@Select[Range[2, p-1], PowerMod[#, p-1, p^2] == 1&]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 27 2023 *)

i=0; forprime(p=2, 10^3, a=2; while(a

A060503 Primes p that have a primitive root between 0 and p that is not a primitive root of p^2.

Original entry on oeis.org

2, 29, 37, 43, 71, 103, 109, 113, 131, 181, 191, 211, 257, 263, 269, 283, 349, 353, 359, 367, 373, 397, 439, 449, 461, 487, 509, 563, 599, 617, 619, 631, 641, 647, 653, 701, 739, 743, 773, 797, 839, 857, 863, 883, 887, 907, 919, 947, 971, 983, 1019, 1031

Offset: 1

Jud McCranie, Mar 22 2001

nonn

The smallest primitive roots of p that are not primitive roots of p^2 are in A060504.

Except for the initial term 2, this is a subsequence of A134307. - Jeppe Stig Nielsen, Jul 31 2015

			14 is a primitive root of 29 but not of 29^2, so 29 is a term.

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

Cf. A055578, A060504, A134307.

filter:= proc(p) local x;
  if not isprime(p) then return false fi;
  x:= 0;
  do
    x:= numtheory:-primroot(x,p);
    if x = FAIL then return false fi;
    if x &^ (p-1) mod p^2 = 1 then return true fi;
  od
end proc:
select(filter, [2, seq(i,i=3..2000,2)]); # Robert Israel, Dec 01 2016

Reap[For[p = 2, p < 1100, p = NextPrime[p], prp = PrimitiveRootList[p]; prp2 = Select[PrimitiveRootList[p^2], # <= Last[prp]&]; If[AnyTrue[prp, FreeQ[prp2, #]&], Print[p]; Sow[p]]]][[2, 1]] (* Jean-François Alcover, Feb 26 2019 *)

forprime(p=2,,for(a=1,p-1,if(znorder(Mod(a,p))==p-1&Mod(a,p^2)^(p-1)==1,print1(p,", ");break()))) \\ Jeppe Stig Nielsen, Jul 31 2015

A222184 Primes p such that q^(p-1) == 1 (mod p^2) for some prime q < p.

Original entry on oeis.org

11, 43, 59, 71, 79, 97, 103, 137, 263, 331, 349, 359, 421, 433, 487, 523, 653, 659, 743, 859, 863, 907, 919, 983, 1069, 1087, 1091, 1093, 1163, 1223, 1229, 1279, 1381, 1483, 1499, 1549, 1657, 1663, 1667, 1697, 1747, 1777, 1787, 1789, 1877, 1993, 2011, 2213, 2221, 2251, 2281, 2309, 2371, 2393, 2473, 2671, 2719, 2777, 2791, 2803, 2833, 2861, 3037, 3079, 3163, 3251, 3257, 3463, 3511, 3557

Offset: 1

Jonathan Sondow, Feb 11 2013

nonn

Subsequence of A134307; see its interesting heuristics. (What is the analogous heuristic for the present sequence?)

The smallest corresponding primes q are A222185.

			3 is a prime < 11, and 11^2 divides 3^(11-1)-1 = 59048 = 121*488, so 11 is a member.

L. E. Dickson, History of the Theory of Numbers, vol. 1, chap. IV.

Giovanni Resta, Table of n, a(n) for n = 1..10000
W. Keller and J. Richstein, Fermat quotients that are divisible by p.

Cf. A001220, A039678, A134307, A143548, A222185.

Select[ Prime[ Range[500]], Product[ PowerMod[ Prime[k], # - 1, #^2] - 1, {k, 1, PrimePi[#] - 1}] == 0 &]

lista(nn) = {forprime (p=2, nn, ok = 0; forprime(q=2, p-1, if (Mod(q, p^2)^(p-1) == 1, ok=1; break);); if (ok, print1(p, ", ")););} \\ Michel Marcus, Nov 24 2014

A222185(n)^(a(n)-1) == 1 (mod a(n)^2).

A248865 Primes p that set a new record for the number of bases 1 < b < p for which p is a base-b Wieferich prime.

Original entry on oeis.org

2, 11, 269, 487, 653, 1093, 3511, 1006003

Offset: 1

Felix Fröhlich, Mar 07 2015

Primes p where A242830(i) reaches record values, where i is the index of p in A000040.
The corresponding number of bases are 0, 2, 3, 4, 5, 10, 11, 12. - Jianing Song, Feb 07 2019
From Jeppe Stig Nielsen, Sep 06 2020: (Start)
Note that for a(6) and a(7), all the b values (bases) that are counted are powers of 2; and for a(8) all are powers of 3.
See A334048 for a version where bases b that are powers are not allowed.
One candidate for a(9) is 1645333507; it has 14 bases, the first 13 of which are powers of 5. However, excluding all numbers under 1645333507 as candidates for a(9) may be difficult to do.
(End)

Cf. A000040, A175932, A242830, A334048.

Subsequence of A175932. Apart from the first term, subsequence of A134307.

my(r=-1); forprime(p=2, , my(b=2, i=0); while(b < p, if(Mod(b, p^2)^(p-1)==1, i++); b++); if(i > r, print1(p, ", "); r=i)) \\ changed to include a(1) = 2 by Jianing Song, Feb 07 2019

a(1) = 2 inserted by Jianing Song, Feb 07 2019

A267288 Composites c where at least one base b with 1 < b < c exists such that b^(c-1) == 1 (mod c^2), i.e., composites c that are base-b 'Wieferich pseudoprimes' for at least one b between 1 and c.

Original entry on oeis.org

133, 451, 561, 871, 904, 1065, 1105, 1267, 1729, 1891, 2059, 2201, 2501, 2821, 2993, 3145, 4641, 5005, 5551, 5841, 5963, 6409, 6541, 6601, 6697, 7107, 7471, 7501, 8321, 8323, 9637, 10585, 11266, 12209, 12403, 13571, 13585, 16471, 17261, 17466, 17770, 18103

Offset: 1

Felix Fröhlich, Jan 12 2016

nonn

A002808(i) such that A256517(i) < A002808(i).

Any term is also a term of A039769.

			871 is a term of the sequence, since 699^870 == 1 (mod 871^2) and 699 < 871.

Cf. A039769, A134307, A255885, A256517.

forcomposite(c=2, , for(b=2, c-1, if(Mod(b, c^2)^(c-1)==1, print1(c, ", "); break({1}))))

A175932 Smallest prime p such that there exist exactly n integers b such that 1 < b < p and b^(p-1) == 1 (mod p^2) or, equivalently, Fermat quotient q_p(b) == 0 (mod p).

Original entry on oeis.org

2, 29, 11, 269, 487, 653, 5107, 103291, 40487, 2544079, 1093, 3511, 1006003

Offset: 0

Max Alekseyev, Oct 24 2010

a(n) is the smallest prime p such that A242830(PrimePi(p)) = n, PrimePi = A000720. - Jianing Song, Jan 27 2019

			a(5) = 653 since 653 is the smallest prime with exactly five bases b = 84, 120, 197, 287, 410.

Richard Fischer, Extreme first bases

Cf. A001220, A130912, A248865, A242830.
Subset of A134307.
Cf. also A255203, A255204, A255205, A255206, A255207, A255208, A255209, A255210.

first_n_entries(n)=v=vector(n); toGo=n; forprime(p=2, , count=sum(b=2, p-1, Mod(b, p^2)^(p-1)==1); if(count<=(n-1)&!v[count+1], v[count+1]=p; toGo--; if(!toGo, return(v)))) \\ Jeppe Stig Nielsen, Jul 31 2015, changed to include a(0) = 2 by Jianing Song, Feb 05 2019

a(0) = 2 prepended by Jianing Song, Jan 27 2019

A222185 Least prime q with q^(p-1) == 1 (mod p^2), where p = A222184(n).

Original entry on oeis.org

3, 19, 53, 11, 31, 53, 43, 19, 79, 71, 223, 257, 251, 349, 307, 241, 197, 503, 467, 643, 13, 127, 457, 419, 487, 617, 691, 2, 241, 997, 821, 683, 653, 421, 941, 1069, 1481, 709, 463, 461, 1153, 1381, 631, 449, 1091, 277, 1993, 367, 659, 151, 1657, 823, 1493, 431, 1787, 2063, 1487, 59, 2389, 2131, 479, 1907, 79, 173, 1151, 1831, 419, 1193, 2, 3319

Offset: 1

Jonathan Sondow, Feb 12 2013

nonn

			3 is the smallest prime < A222184(1) = 11 such that 11^2 divides 3^(11-1)-1 = 59048 = 121*488, so a(1) = 3.

L. E. Dickson, History of the Theory of Numbers, vol. 1, chap. IV.

Giovanni Resta, Table of n, a(n) for n = 1..10000
Keller and J. Richstein, Fermat quotients that are divisible by p

Cf. A001220, A039678, A134307, A143548, A222184.

L = Select[ Prime[ Range[500]], Product[ PowerMod[ Prime[k], # - 1, #^2] - 1, {k, 1, PrimePi[#] - 1}] == 0 &]; Table[  Min[ Select[ Prime[ Range[ PrimePi[L[[n]]] - 1]], PowerMod[#, L[[n]] - 1, L[[n]]^2] == 1 &]], {n, 1, Length[L]}]

A254444 Largest k such that p = prime(n) satisfies b^(p-1) == 1 (mod p^k) for some base b with 1 < b < p.

Original entry on oeis.org

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

Offset: 2

Felix Fröhlich, May 04 2015

nonn

a(n) > 1 iff p is in A134307.
Meyer proved in 1902 that for any prime p exactly p - 1 bases b with b < p^k exist such that b^(p-1) == 1 (mod p^k) (cf. Keller, Richstein, 2005, page 930).
a(30) = 3 is the first term with a value > 2, corresponding to prime(30) = 113 (see the comment from 2011 in A134307). This is the first case where A249275(n) < A000040(n).
Do the values of this sequence have an upper bound or, more formally, does this sequence have a supremum?

			With p = 113: For all bases b with 1 < b < 113, p (trivially) satisfies b^112 == 1 (mod 113^k) for k = 1 and for no k > 1, with the single exception of b = 68, where p satisfies the congruence for k = 3 (and hence for k = 1 and k = 2). Since 3 is the largest value of k for all 1 < b < 113, a(30) = 3.

Felix Fröhlich, Table of n, a(n) for n = 2..10000
W. Keller and J. Richstein, Solutions of the congruence a^p-1 == 1 (mod p^r), Math. Comp., 74 (2005), 927-936.

Cf. A134307.

forprime(p=3, 400, k=1; maxk=0; for(b=2, p-1, while(Mod(b, p^k)^(p-1)==1, k++); if(k-1 > maxk, maxk=k-1)); print1(maxk, ", "))

A222206 Least prime p such that q^(p-1) == 1 (mod p^2) for n primes q < p.

Original entry on oeis.org

2, 11, 349, 13691, 24329

Offset: 0

Jonathan Sondow, Feb 12 2013

I found no new terms < 5*10^6. - J. Stauduhar, Mar 23 2013

a(5) > 13*10^6, if it exists. Note that, up to 13*10^6, the only other prime p (apart 24329) such that the congruence is satisfied for 4 primes q < p is 9656869. - Giovanni Resta, May 23 2017

			For the prime p = 349, but for no smaller prime, there are 2 primes q = 223 and 317 < p with  q^(p-1) == 1 (mod p^2), so a(2) = 349.

L. E. Dickson, History of the Theory of Numbers, vol. 1, chap. IV.

W. Keller and J. Richstein, Fermat quotients that are divisible by p. [Broken link]
Wilfrid Keller and Jörg Richstein, Solutions of the congruence a^(p-1) == 1 (mod (p^r)), Math. Comp. 74 (2005), 927-936.

Cf. A001220, A039678, A134307, A143548, A222184, A222185.

f[n_] := Block[{p = 2, q = {}}, While[ Count[ PowerMod[ q, p - 1, p^2], 1] != n, q = Join[q, {p}]; p = NextPrime@ p]; p]; Array[f, 5, 0] (* Robert G. Wilson v, Mar 09 2015 *)

a(n) = {nb = 0; p = 2; while (nb != n, p = nextprime(p+1); nb = 0; forprime(q=2, p-1, if (Mod(q, p^2)^(p-1) == 1, nb ++); if (nb > n, break););); p;} \\ Michel Marcus, Mar 08 2015

A143811 Number of numbers k

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 1, 3, 1, 2, 1, 1, 2, 1, 2, 1, 2, 2, 3, 3, 2, 1, 1, 2, 1, 3, 1, 1, 1, 2, 2, 1, 2, 2, 3, 2, 1, 3, 2, 1, 2, 1, 2, 2, 4, 1, 1, 2, 2, 2, 2, 1, 3, 1, 4, 1, 3, 3, 3, 3, 3, 2, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 3, 1, 1, 5, 1, 2, 1, 3, 2, 2, 1, 2, 2, 2, 1, 4

Offset: 1

T. D. Noe, Sep 02 2008

nonn

Note that a(n)>0 because k=1 is always a solution. The primes for which a(n)>1 are given in A134307. The values of k are the terms

A143548. The largest known terms in this sequence are for the Wieferich primes 1093 and 3511, for which we have a(183)=11 and a(490)=12, respectively. It is not hard to show that k=p-1 is never a solution for odd prime p. In fact, (p-1)^(p-1)=p+1 (mod p^2) for odd prime p.

T. D. Noe, Table of n, a(n) for n=1..10000

Table[p=Prime[n]; s=Select[Range[p-1], PowerMod[ #,p-1,p^2]==1&]; Length[s], {n,100}]

cp's OEIS Frontend

A242830 For p = prime(n), a(n) = number of bases 1 < b < p such that b^(p-1) == 1 (mod p^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A060503 Primes p that have a primitive root between 0 and p that is not a primitive root of p^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A222184 Primes p such that q^(p-1) == 1 (mod p^2) for some prime q < p.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A248865 Primes p that set a new record for the number of bases 1 < b < p for which p is a base-b Wieferich prime.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A267288 Composites c where at least one base b with 1 < b < c exists such that b^(c-1) == 1 (mod c^2), i.e., composites c that are base-b 'Wieferich pseudoprimes' for at least one b between 1 and c.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A175932 Smallest prime p such that there exist exactly n integers b such that 1 < b < p and b^(p-1) == 1 (mod p^2) or, equivalently, Fermat quotient q_p(b) == 0 (mod p).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A222185 Least prime q with q^(p-1) == 1 (mod p^2), where p = A222184(n).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

A254444 Largest k such that p = prime(n) satisfies b^(p-1) == 1 (mod p^k) for some base b with 1 < b < p.

Views

Author

Keywords