A039678 -id:A039678 - cp's OEIS frontend

A244249 Table A(n,k) in which n-th row lists in increasing order all bases b to which p = prime(n) is a Wieferich prime (i.e., b^(p-1) is congruent to 1 mod p^2), read by antidiagonals.

5, 9, 8, 13, 10, 7, 17, 17, 18, 18, 21, 19, 24, 19, 3, 25, 26, 26, 30, 9, 19, 29, 28, 32, 31, 27, 22, 38, 33, 35, 43, 48, 40, 23, 40, 28, 37, 37, 49, 50, 81, 70, 65, 54, 28, 41, 44, 51, 67, 94, 80, 75, 62, 42, 14, 45, 46, 57, 68, 112, 89, 110, 68, 63, 41, 115

Offset: 1

Felix Fröhlich, Jun 23 2014

			Table starts with:
p =  2:   5,  9, 13, 17,  21,  25,  29,  33, ...
p =  3:   8, 10, 17, 19,  26,  28,  35,  37, ...
p =  5:   7, 18, 24, 26,  32,  43,  49,  51, ...
p =  7:  18, 19, 30, 31,  48,  50,  67,  68, ...
p = 11:   3,  9, 27, 40,  81,  94, 112, 118, ...
p = 13:  19, 22, 23, 70,  80,  89,  99, 146, ...
p = 17:  38, 40, 65, 75, 110, 131, 134, 155, ...

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A001220, A185103.
First column of table is A039678.
Main diagonal gives A280721.

A:= proc(n, k) option remember; local p, b;
      p:= ithprime(n);
      for b from 1 +`if`(k=1, 1, A(n, k-1))
        while b &^ (p-1) mod p^2<>1
      do od; b
    end:
seq(seq(A(n, 1+d-n), n=1..d), d=1..14);  # Alois P. Heinz, Jul 02 2014

A[n_, k_] := A[n, k] = Module[{p, b}, p = Prime[n]; For[b = 1 + If[k == 1, 1, A[n, k-1]], PowerMod[b, p-1, p^2] != 1, b++]; b]; Table[Table[A[n, 1+d-n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Mar 09 2015, after Alois P. Heinz *)

forprime(p=2, 10^1, print1("p=", p, ": "); for(a=2, 10^2, if(Mod(a, p^2)^(p-1)==1, print1(a, ", "))); print(""))

A134307 Primes p such that A^(p-1) == 1 (mod p^2) for some A in the range 2 <= A <= p-1.

Original entry on oeis.org

11, 29, 37, 43, 59, 71, 79, 97, 103, 109, 113, 127, 131, 137, 151, 163, 181, 191, 197, 199, 211, 223, 229, 233, 241, 257, 263, 269, 281, 283, 293, 307, 313, 331, 347, 349, 353, 359, 367, 373, 379, 397, 401, 419, 421, 433, 439, 449, 461, 463, 487, 499, 509

Offset: 1

Joerg Arndt, Aug 27 2008

nonn

It's worth observing that there are p-1 elements of order dividing p-1 modulo p^2 that are of the form r^(k*p) mod p^2 where r is a primitive element modulo p and k=0,1,...,p-2. Heuristically, one can expect that at least one of them belongs to the interval [2,p-1] with probability about 1 - (1 - 1/p)^(p-1) ~= 1 - 1/e.
Numerically, among the primes below 1000 (out of the total number pi(1000)=168) there are 103 terms of the sequence, and the ratio 103/168 = 0.613 which is already somewhat close to 1-1/e ~= 0.632.
If we replace p^2 with p^3, heuristically it is likely that the sequence is finite (since 1 - (1 - 1/p^2)^(p-1) tends to 0 as p grows). - Max Alekseyev, Jan 09 2009
Replacing p^2 with p^3 gives just the one term (113) for p < 10^6. - Joerg Arndt, Jan 07 2011
If furthermore the number A can be taken to be a primitive root modulo p, i.e., A is a generator of (Z/pZ)*, then that p belongs to A060503. - Jeppe Stig Nielsen, Jul 31 2015
The number of terms not exceeding prime(10^k), for k=1,2,..., are 2, 55, 652, 6303, 63219, ... - Amiram Eldar, May 08 2021

			Examples (pairs [p, A]):
[11, 3]
[11, 9]
[29, 14]
[37, 18]
[43, 19]
[59, 53]
[71, 11]
[71, 26]
[79, 31]
[97, 53]

L. E. Dickson, History of the theory of numbers, vol. 1, p. 105.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Wilfrid Keller and Jörg Richstein Fermat quotients that are divisible by p.

Cf. A001220, A055578, A039678, A143548, A222184, A060503.

Select[ Prime[ Range[100]], Product[ (PowerMod[a, # - 1, #^2] - 1), {a, 2, # - 1}] == 0 &] (* Jonathan Sondow, Feb 11 2013 *)

{ forprime (p=2, 1000,
   for (a=2, p-1, p2 = p^2;
     if( Mod(a, p2)^(p-1) == Mod(1, p2), print1(p, ", ") ;break() );
  ); ); }

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

Original entry on oeis.org

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

A185103 Smallest k > 1 such that k^(n-1) == 1 (mod n^2).

Original entry on oeis.org

5, 8, 17, 7, 37, 18, 65, 80, 101, 3, 145, 19, 197, 26, 257, 38, 325, 28, 401, 197, 485, 28, 577, 182, 677, 728, 177, 14, 901, 115, 1025, 485, 1157, 99, 1297, 18, 1445, 170, 1601, 51, 1765, 19, 1937, 82, 2117, 53, 2305, 1047, 2501, 577, 529, 338, 2917, 1451

Offset: 2

Michel Lagneau, Dec 26 2012

nonn

a(n) <= n^2 + (-1)^n. - Thomas Ordowski, Dec 28 2016
If n = p^k for a prime p > 3 and k > 0, then gcd(n, a(n)^2 - 1) = 1. - Thomas Ordowski, Nov 27 2018
A039678 interleaved with A256517. - Felix Fröhlich, Apr 29 2022

			a(2) = 5 because 2^(2-1) == 2 (mod 2^2), 3^(2-1) == 3 (mod 2^2), 4^(2-1) == 0 (mod 2^2), but 5^(2-1) == 1 (mod 2^2). - _Petros Hadjicostas_, Sep 15 2019

Michel Lagneau and Charles R Greathouse IV, Table of n, a(n) for n = 2..10000 (terms to 500 from Michel Lagneau)
K. Broughan, Relaxations of the ABC Conjecture using integer k'th roots, New Zealand J. Math. 35(2) (2006), 121-136. - _Felix Fröhlich_, Jun 24 2014

Cf. A039678, A105222, A220105, A256517.

with(numtheory):for n from 2 to 100 do:ii:=0:for k from 1 to 10000 while(ii=0) do:x:=k^(n-1)-1:if irem(x,n^2)=0 and k>1 then ii:=1:printf(`%d, `,k):else fi:od:od:

Table[k = 2; While[PowerMod[k, n - 1, n^2] != 1, k++]; k, {n, 2, 100}]

a(n)=my(v=List([1]));for(k=2,n-1,if(Mod(k,n)^(n-1)==1, if(Mod(k,n^2)^(n-1)==1, return(k)); listput(v,k))); v=vector(#v,i, v[i%#v+1]-v[i]); v[#v]+=n;forstep(k=n+1,n^2+1,v,if(Mod(k,n^2)^(n-1)==1, return(k))) \\ Charles R Greathouse IV, Dec 26 2012

a(n) = for(k=2, 200, if(Mod(k, n^2)^(n-1)==1, return(k))) \\ Felix Fröhlich, Apr 29 2022

def a(n):
    k, n2 = 2, n*n
    while pow(k, n-1, n2) != 1: k += 1
    return k
print([a(n) for n in range(2, 56)]) # Michael S. Branicky, Apr 29 2022

from sympy.ntheory.residue_ntheory import nthroot_mod
def A185103(n):
    z = nthroot_mod(1,n-1,n**2,True)
    return int(z[0]+n**2 if len(z) == 1 else z[1]) # Chai Wah Wu, May 18 2022

Definition adjusted by Felix Fröhlich, Jun 24 2014

A257833 Table T(k, n) of smallest bases b > 1 such that p = prime(n) satisfies b^(p-1) == 1 (mod p^k), read by antidiagonals.

Original entry on oeis.org

5, 8, 9, 7, 26, 17, 18, 57, 80, 33, 3, 18, 182, 242, 65, 19, 124, 1047, 1068, 728, 129, 38, 239, 1963, 1353, 1068, 2186, 257, 28, 158, 239, 27216, 34967, 32318, 6560, 513, 28, 333, 4260, 109193, 284995, 82681, 110443, 19682, 1025, 14, 42, 2819, 15541, 861642, 758546, 2387947, 280182, 59048, 2049

Offset: 2

Felix Fröhlich, May 10 2015

			T(3, 5) = 124, since prime(5) = 11 and the smallest b such that b^10 == 1 (mod 11^3) is 124.
Table starts
  k\n|    1     2       3        4       5       6         7
  ---+----------------------------------------------------------
   2 |    5     8       7       18       3      19        38 ...
   3 |    9    26      57       18     124     239       158 ...
   4 |   17    80     182     1047    1963     239      4260 ...
   5 |   33   242    1068     1353   27216  109193     15541 ...
   6 |   65   728    1068    34967  284995  861642    390112 ...
   7 |  129  2186   32318    82681  758546 6826318  21444846 ...
   8 |  257  6560  110443  2387947 9236508 6826318 112184244 ...
   9 |  513 19682  280182 14906455 ....
  10 | 1025 59048 3626068 ....
  ...

Chai Wah Wu, Table of n, a(n) for n = 2..10000

Column 1 of table is A000051.
Column 2 of table is A024023 (with offset 2).
Column 3 of table is A034939 (with offset 2).
Rows k=2-10 give: A039678, A249275, A353937, A353938, A353939, A353940, A353941, A353942, A353943.

for(k=2, 10, forprime(p=2, 25, b=2; while(Mod(b, p^k)^(p-1)!=1, b++); print1(b, ", ")); print(""))

T(k,n) = my(p=prime(n), v=List([2])); if(n==1, return(2^k+1)); for(i=1, k, w=List([]); for(j=1, #v, forstep(b=v[j], p^i-1, p^(i-1), if(Mod(b, p^i)^p==b, listput(w, b)))); v=Vec(w)); vecmin(v); \\ Jinyuan Wang, May 17 2022

from itertools import count, islice
from sympy import prime
from sympy.ntheory.residue_ntheory import nthroot_mod
def A257833_T(n,k): return 2**k+1 if n == 1 else int(nthroot_mod(1,(p:= prime(n))-1,p**k,True)[1])
def A257833_gen(): # generator of terms
    yield from (A257833_T(n,i-n+2) for i in count(1) for n in range(i,0,-1))
A257833_list = list(islice(A257833_gen(),50)) # Chai Wah Wu, May 17 2022

A143548 Irregular triangle of numbers k < p^2 such that p^2 divides k^(p-1)-1, with p=prime(n).

Original entry on oeis.org

1, 1, 8, 1, 7, 18, 24, 1, 18, 19, 30, 31, 48, 1, 3, 9, 27, 40, 81, 94, 112, 118, 120, 1, 19, 22, 23, 70, 80, 89, 99, 146, 147, 150, 168, 1, 38, 40, 65, 75, 110, 131, 134, 155, 158, 179, 214, 224, 249, 251, 288, 1, 28, 54, 62, 68, 69, 99, 116, 127, 234, 245, 262, 292, 293, 299, 307, 333, 360

Offset: 1

T. D. Noe, Aug 24 2008

Row n begins with 1 and has prime(n)-1 terms. The first differences of each row are symmetric. For k > p^2, the solutions are just shifted by m*p^2 for m > 0. An open question is whether every integer appears in this sequence. For instance, 2 does not appear until the prime 1093 and 5 does not appear until the prime 20771.
For row n > 1, the sum of the terms in row n is (p-1)*p^2*(p+1)/2, which is A138416. - T. D. Noe, Aug 24 2008, corrected by Robert Israel, Sep 27 2016
Max Alekseyev points out that there is a much faster method of computing these numbers. Let p=prime(n) and let r be a primitive root of p (see A001918 and A060749). Then the terms in row n are r^(k*p) (mod p^2) for k=0..p-2. - T. D. Noe, Aug 26 2008
The numbers in this sequence are the bases to Euler pseudoprimes q, which are squares of prime numbers, such that n^((q-1)/2) == +-1 mod q. An exception is the first number 9 = 3*3, which is, following the strict definition in Crandall and Pomerance, no Fermat pseudoprime and hence no Euler pseudoprime. - Karsten Meyer, Jan 08 2011
For row n > 1, the sum is zero modulo p^2 (rows are antisymmetric due to Binomial Theorem). - Peter A. Lawrence, Sep 11 2016

			(2)   1,
(3)   1, 8,
(5)   1, 7, 18, 24,
(7)   1, 18, 19, 30, 31, 48,
(11)  1, 3, 9, 27, 40, 81, 94, 112, 118, 120,
(13)  1, 19, 22, 23, 70, 80, 89, 99, 146, 147, 150, 168,
(17)  1, 38, 40, 65, 75, 110, 131, 134, 155, 158, 179, 214, 224, 249, 251, 288,

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2005

T. D. Noe, Rows n=1..50 of triangle, flattened

Cf. A039678, A056020, A056021, A056022, A056024, A056025, A056027, A056028, A056031, A056034, A056035, A096082, A138416.

f:= proc(n) local p,j,x;
  p:= ithprime(n);
  x:= numtheory:-primroot(p);
  op(sort([seq(x^(i*p) mod p^2, i=0..p-2)]))
end proc:
map(f, [$1..20]); # Robert Israel, Sep 27 2016

Flatten[Table[p=Prime[n]; Select[Range[p^2], PowerMod[ #,p-1,p^2]==1&], {n,50}]] (* T. D. Noe, Aug 24 2008 *)
Flatten[Table[p=Prime[n]; r=PrimitiveRoot[p]; b=PowerMod[r,p,p^2]; Sort[NestList[Mod[b*#,p^2]&,1,p-2]], {n,50}]] (* Faster version from T. D. Noe, Aug 26 2008 *)

A249275 a(n) is the smallest b > 1 such that p = prime(n) satisfies b^(p-1) == 1 (mod p^3).

Original entry on oeis.org

9, 26, 57, 18, 124, 239, 158, 333, 42, 1215, 513, 691, 1172, 3038, 295, 1468, 2511, 15458, 3859, 6372, 923, 1523, 5436, 1148, 412, 4943, 4432, 5573, 476, 68, 21304, 30422, 6021, 8881, 33731, 25667, 3868, 3170, 17987, 26626, 43588, 7296, 14628, 22076, 138057

Offset: 1

Felix Fröhlich, Oct 24 2014

nonn

a(n) >= A039678(n) for all n.

Vincenzo Librandi, Table of n, a(n) for n = 1..100

Cf. A039678, A242742.

Array[Block[{b = 2}, While[PowerMod[b, # - 1, #^3] != 1, b++]; b] &@ Prime@ # &, 45] (* Michael De Vlieger, Nov 25 2018 *)
dpa[n_]:=Module[{p=Prime[n], a=9}, While[PowerMod[a, p - 1, p^3]!=1, a++]; a]; Array[dpa, 50] (* Vincenzo Librandi, Nov 30 2018 *)

a(n) = my(p=prime(n)); for(b=2, oo, if(Mod(b, p^3)^(p-1)==1, return(b)))

from sympy import prime
def a(n):
    b, p = 2, prime(n)
    p3 = p**3
    while pow(b, p-1, p3) != 1: b += 1
    return b
print([a(n) for n in range(1, 46)]) # Michael S. Branicky, Sep 26 2021

from sympy import prime
from sympy.ntheory.residue_ntheory import nthroot_mod
def A249275(n): return 2**3+1 if n == 1 else int(nthroot_mod(1,(p:= prime(n))-1,p**3,True)[1]) # Chai Wah Wu, May 17 2022

Edited by Felix Fröhlich, Nov 24 2018

A256517 Let c be the n-th composite number. Then a(n) is the smallest base b > 1 such that b^(c-1) == 1 (mod c^2), i.e., such that c is a 'Wieferich pseudoprime'.

Original entry on oeis.org

17, 37, 65, 80, 101, 145, 197, 26, 257, 325, 401, 197, 485, 577, 182, 677, 728, 177, 901, 1025, 485, 1157, 99, 1297, 1445, 170, 1601, 1765, 1937, 82, 2117, 2305, 1047, 2501, 577, 529, 2917, 1451, 3137, 721, 3365, 3601, 3845, 244, 4097, 99, 1945, 4625, 530

Offset: 1

Felix Fröhlich, Apr 01 2015

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms 1..3000 from Felix Fröhlich)

Cf. A039678, A242742, A244752, A255885.

Cf. A185103, A002808.

c = Select[Range@ 69, CompositeQ]; f[c_] := Block[{b = 2}, While[Mod[b^(c - 1), c^2] != 1, b++]; b]; f /@ c (* Michael De Vlieger, Apr 03 2015 *)

forcomposite(c=1, 1e3, b=2; while(Mod(b, c^2)^(c-1)!=1, b++); print1(b, ", "))

from sympy import composite
from sympy.ntheory.residue_ntheory import nthroot_mod
def A256517(n):
    z = nthroot_mod(1,(c := composite(n))-1,c**2,True)
    return int(z[0]+c**2 if len(z) == 1 else z[1]) # Chai Wah Wu, May 18 2022

a(n) = A185103(A002808(n)-1). - Bill McEachen, Nov 27 2021

A259075 Smallest base b > 1 such that both prime(n) and prime(n+1) are base-b Wieferich primes, i.e., p = prime(n) satisfies b^(p-1) == 1 (mod p^2) and q = prime(n+1) satisfies b^(q-1) == 1 (mod q^2).

Original entry on oeis.org

17, 26, 18, 148, 239, 249, 423, 28, 63, 374, 117, 787, 2059, 1085, 655, 4586, 4153, 3147, 10056, 4559, 2092, 18692, 19487, 3018, 19343, 14285, 164, 31469, 6817, 7916, 16128, 4505, 18768, 2752, 26664, 16717, 129702, 46171, 1040, 3608, 9479, 4840, 42348, 14128

Offset: 1

Felix Fröhlich, Jun 18 2015

nonn

Does b exist for all n?

a(n) == A039678(n) iff A039678(n) == A039678(n+1). The smallest n where those equalities hold is n = 8.

Felix Fröhlich, Table of n, a(n) for n = 1..1000

Cf. A039678.

a[n_] := Block[{b=2, p = Prime@{n, n+1}}, While[{1,1} != PowerMod[ b, p-1, p^2], b++]; b]; Array[a, 40] (* Giovanni Resta, Jun 23 2015 *)

a(n) = p=prime(n); q=prime(n+1); b=2; while(Mod(b, p^2)^(p-1)!=1 || Mod(b, q^2)^(q-1)!=1, b++); b

A353937 Smallest b > 1 such that b^(p-1) == 1 (mod p^4) for p = prime(n).

Original entry on oeis.org

17, 80, 182, 1047, 1963, 239, 4260, 2819, 19214, 2463, 15714, 51344, 20677, 3038, 224444, 189323, 11550, 397575, 201305, 15384, 840838, 1372873, 1576656, 278454, 1721322, 48072, 281007, 119551, 252595, 1001934, 3489507, 2489004, 598987, 3082551, 6136759, 3928984

Offset: 1

Felix Fröhlich, May 12 2022

nonn

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

Row k = 4 of A257833.

Cf. similar sequences for p^k: A039678 (k=2), A249275 (k=3), A353938 (k=5), A353939 (k=6), A353940 (k=7), A353941 (k=8), A353942 (k=9), A353943 (k=10).

f:= proc(j) local p,b,i;
  p:= ithprime(j);
  b:= numtheory:-primroot(p^4) &^ (p^3) mod p^4;
  min(seq(b &^i mod p^4, i=1..p-2))
end proc:
f(1):= 17:
map(f, [$1..40]); # Robert Israel, Dec 19 2024

a[n_] := Module[{p = Prime[n], b = 2}, While[PowerMod[b, p - 1, p^4] != 1, b++]; b]; Array[a, 20] (* Amiram Eldar, May 12 2022 *)

a(n) = my(p=prime(n)); for(b=2, oo, if(Mod(b, p^4)^(p-1)==1, return(b)))

from sympy import prime
from sympy.ntheory.residue_ntheory import nthroot_mod
def A353937(n): return 2**4+1 if n == 1 else int(nthroot_mod(1,(p:= prime(n))-1,p**4,True)[1]) # Chai Wah Wu, May 17 2022

cp's OEIS Frontend

A244249 Table A(n,k) in which n-th row lists in increasing order all bases b to which p = prime(n) is a Wieferich prime (i.e., b^(p-1) is congruent to 1 mod p^2), read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A134307 Primes p such that A^(p-1) == 1 (mod p^2) for some A in the range 2 <= A <= p-1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

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

A185103 Smallest k > 1 such that k^(n-1) == 1 (mod n^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Extensions

A257833 Table T(k, n) of smallest bases b > 1 such that p = prime(n) satisfies b^(p-1) == 1 (mod p^k), read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Python

A143548 Irregular triangle of numbers k < p^2 such that p^2 divides k^(p-1)-1, with p=prime(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A249275 a(n) is the smallest b > 1 such that p = prime(n) satisfies b^(p-1) == 1 (mod p^3).

Views

Author

Keywords

Comments

Links