A266829 -id:A266829 - cp's OEIS frontend

A297846 Primes p such that p is the largest member of a Wieferich tuple.

71, 359, 487, 863, 1069, 1093, 1483, 1549, 2281, 3511, 4871, 6451, 6733, 7393, 12049, 13691, 14107, 14149, 15377, 17401, 18787, 20771, 29573, 32933, 35747, 39233, 44483, 46021, 48947, 49559, 54787, 54979, 59197, 60493, 69401, 69653, 77263, 77867, 105323, 122327

Offset: 1

Felix Fröhlich, Jan 07 2018

nonn

Let p_1, p_2, p_3, ..., p_u be a set P of distinct prime numbers and let m_1, m_2, m_3, ..., m_u be a set V of variables. Then P is a Wieferich u-tuple if there exists a mapping from the elements of P to the elements of V such that each of the following congruences is satisfied:

m_1^(m_2-1) == 1 (mod (m_2)^2), m_2^(m_3-1) == 1 (mod (m_3)^2), ..., m_u^(m_1-1) == 1 (mod (m_1)^2).

			The primes 31, 79, 251, 263, 421 and 1483 satisfy 31^(79-1) == 1 (mod 79^2), 79^(263-1) == 1 (mod 263^2), 263^(251-1) == 1 (mod 251^2), 251^(421-1) == 1 (mod 421^2), 421^(1483-1) == 1 (mod 1483^2) and 1483^(31-1) == 1 (mod 31^2), so those primes form a Wieferich tuple. Since 1483 is the largest member of the tuple, 1483 is a term of the sequence.

Supersequence of A253683, A266829 and A289899.

Supersequence of column 1 of A271100.

findwiefs(vec, lim) = my(v=[]); for(k=1, #vec, forprime(p=1, lim, if(Mod(vec[k], p^2)^(p-1)==1, v=concat(v, [p])))); vecsort(v, , 8)
newprimes(v, w) = setminus(w, v)
is(n) = my(v=findwiefs([n], n), w=[], np=[]); while(1, w=findwiefs(v, n); if(newprimes(v, w)==[], return(0), if(setsearch(vecsort(newprimes(v, w)), n) > 0, return(1))); v=concat(v, newprimes(v, w)); v=vecsort(v, , 8))
forprime(p=1, , if(is(p), print1(p, ", ")))

More terms from Felix Fröhlich, Jan 22 2018

A271100 Triangular array read by rows: T(n, k) = k-th largest member of lexicographically earliest Wieferich n-tuple that contains no duplicate members, read by rows, or T(n, k) = 0 if no Wieferich n-tuple exists.

Original entry on oeis.org

0, 1093, 2, 71, 11, 3, 3511, 19, 13, 2, 359, 331, 71, 11, 3, 359, 331, 307, 71, 11, 3, 359, 331, 307, 71, 19, 11, 3, 863, 359, 331, 71, 23, 13, 11, 3, 863, 359, 331, 307, 71, 19, 13, 11, 3, 863, 467, 359, 331, 307, 71, 19, 13, 11, 3

Offset: 1

Felix Fröhlich, Mar 30 2016

Let p_1, p_2, p_3, ..., p_u be a set P of distinct prime numbers and let m_1, m_2, m_3, ..., m_u be a set V of variables. Then P is a Wieferich u-tuple if there exists a mapping from the elements of P to the elements of V such that each of the following congruences is satisfied:
m_1^(m_2-1) == 1 (mod (m_2)^2), m_2^(m_3-1) == 1 (mod (m_3)^2), ..., m_u^(m_1-1) == 1 (mod (m_1)^2).
For finding candidate values for m_1 given some m_u, one checks primes higher than m_u for primes satisfying m_u^(m_1-1) == 1 (mod (m_1)^2). For example, to see what we could get if m_u = 2, we check up to say m_1 = 1,000,000 to get candidates for m_1. This would give m_1 in {1093, 3511}. - David A. Corneth, May 14 2016

			For n = 1: There is no Wieferich singleton (1-tuple), because no prime p satisfies the congruence p^(p-1) == 1 (mod p^2), so T(1, 1) = 0.
For n = 4: The primes 3511, 19, 13, 2 satisfy the congruences 3511^(19-1) == 1 (mod 19^2), 19^(13-1) == 1 (mod 13^2), 13^(2-1) == 1 (mod 2^2) and 2^(3511-1) == 1 (mod 3511^2) and thus form a "Wieferich quadruple". Since this is the lexicographically earliest such set of primes, T(4, 1..4) = 3511, 19, 13, 2.
Triangle starts:
  n=1:     0;
  n=2:  1093,   2;
  n=3:    71,  11,   3;
  n=4:  3511,  19,  13,   2;
  n=5:   359, 331,  71,  11,   3;
  n=6:   359, 331, 307,  71,  11,   3;
  n=7:   359, 331, 307,  71,  19,  11,   3;
  n=8:   863, 359, 331,  71,  23,  13,  11,   3;
  n=9:   863, 359, 331, 307,  71,  19,  13,  11,   3;
  n=10:  863, 467, 359, 331, 307,  71,  19,  13,  11,   3;
  ....

Bruce Leenstra, Table of n, a(n) for n = 1..300
Wikipedia, Wieferich pair

Cf. A124121, A124122, A253683, A253684, A253685, A266829.

ulimupto(u,{llim=2}) = {my(l=List());
forprime(i=nextprime(llim+1),u,if(Mod(llim,i^2)^(i-1)==1,listput(l,i)));l} \\ David A. Corneth, May 14 2016
\\tests if a tuple is a valid Wieferich n-tuple.

istuple(v) = {if(#Set(v)==#v,return(0));for(j=0,(#v-1)!-1, w=vector(#v,k,v[numtoperm(#v,j)[k]]); if(sum(i=2,#w,Mod(w[i-1],w[i]^2)^(w[i]-1)==1)+(Mod(w[1],w[#w])^(w[#w]-1)==1)==#w,return(1)));0} \\ David A. Corneth, May 15 2016

wief = DiGraph([prime_range(3600), lambda p, q: power_mod(p, q-1, q^2)==1])
sc = [[0]] + [sorted(c[1:], reverse=1) for c in wief.all_simple_cycles()]
tbl = [sorted(filter(lambda c: len(c)==n, sc))[0] for n in range(1, len(sc[-1]))]
for t in tbl: print('n=%d:'% len(t), ', '.join("%s"%i for i in t)) # Bruce Leenstra, May 18 2016

a(11)-a(15) from Felix Fröhlich, Apr 26 2016

More terms from Bruce Leenstra, May 18 2016

A282293 Two-column array A(n, k) read by rows, where A(n, 1) and A(n, 2) respectively give values of q and p in the n-th double Wieferich prime pair, where p > q. Terms sorted first by increasing size of p, then by increasing size of q.

Original entry on oeis.org

2, 1093, 83, 4871, 2903, 18787, 911, 318917, 3, 1006003, 5, 1645333507

Offset: 1

Felix Fröhlich, Feb 11 2017

Double Wieferich prime pairs are pairs of prime numbers p and q such that p^(q-1) == 1 (mod q^2) and q^(p-1) == 1 (mod p^2).
Pairs of primes p and q such that A274916(x, y) = 2, where x and y are the indices of p and q in A000040 respectively.
This sequence provides a "complete" listing of double Wieferich prime pairs. A124122 omits values of p where a smaller p with the same value of q in A124121 exists, while A266829 lists each value of p exactly once, regardless of how many values of q exist for that p.
There are two ways to retrieve the pair (p, q) from the data when looking at any specific value:
1. Look at the indices i of the terms. If the index is even, a(i) is the larger member p of a pair, so q is a(i-1). If the index is odd, a(i) is the smaller member q of the pair, so p is a(i+1).
2. Look at a term a(i) in the data section. If a(i-1) and a(i+1) are both larger than a(i), then a(i) is the smaller member of a pair and its partner is a(i+1). If a(i-1) and a(i+1) are both smaller than a(i), then a(i) is the larger member of a pair and its partner is a(i-1).
There are no further pairs with p*q <= 10^15 and p < 2^(1/3)*10^10 and only one additional Wieferich pair, namely (5, 188748146801), is known, but its position in the sequence is uncertain (cf. Logan, Mossinghoff, 2015).
Double Wieferich pairs were first mentioned by Inkeri, who showed that if Catalan's Diophantine equation x^p - y^q = 1 has a solution (x, y) for prime numbers p and q both congruent to 3 modulo 4, p > q and h(p) =/= 0 (mod q), where h(p) is the class number of the field k(sqrt(-p)), then (p, q) is a double Wieferich pair (cf. Inkeri, 1964, Theorem 2).
The pairs (2, 1093) and (83, 4871) were apparently first found by Aaltonen and Inkeri, who state that these two and a third one, (3, 1006003), from a table from Brillhart, Tonascia and Weinberger, are the only pairs they are aware of (cf. Aaltonen, Inkeri, 1991, Remark on p. 365).
The pairs (2903, 18787) and (911, 318917) were first found by Mignotte and Roy (cf. Keller, Richstein, 2005, p. 935) and later also by Ernvall and Metsänkylä in a search to 10^6, who also mention the pair (5, 1645333507) found by Montgomery (cf. Ernvall, Metsänkylä, 1997, p. 1360).
Several further conditions connecting double Wieferich pairs to Catalan's equation were obtained by Steiner, for example the result that if both p and q in a solution to the Catalan equation are congruent to 3 modulo 4 or both p and q satisfy either p == 3 (mod 4) and q == 5 (mod 8) or vice versa, then (p, q) is a double Wieferich pair (cf. Steiner, 1998, Theorems 7 and 8).
Mihailescu further showed that if the Catalan equation has a solution with p and q distinct odd primes and xy != 0, then q^2 | x, p^2 | y and p and q form a double Wieferich prime pair (cf. Mihailescu, 2003, Theorem 1).
If the Diophantine equation p^x - q^y = c has more than one solution with q an odd prime incongruent to 1 modulo 12, p < 2*q, gcd(p-1, q-1) even and (p, q, c) not one of (3, 2, 1), (2, 3, 5), (2, 3, 13), (2, 5, 3) or (13, 3, 10), then (p, q) is a double Wieferich pair (cf. Scott, Styer, 2004, pages 218-219).
Corollary to Proposition 4 in Pomerance, Selfridge, Wagstaff, 1980: Let p and q be primes and let c and d be composites such that c and d are base-p and base-q Fermat pseudoprimes, respectively. If p^2 divides d and q^2 divides c, then (p, q) is a double Wieferich pair.

			The primes 83 and 4871 satisfy 83^4870 == 1 (mod 23726641) and 4871^82 == 1 (mod 6889), respectively, so 83 and 4871 are terms of the sequence.

M. Aaltonen and K. Inkeri, Catalan's equation x^p - y^p = 1 and related congruences, Math. Comp. 56 (1991), 359-370.
R. Ernvall and T. Metsänkylä, On the p-divisibility of Fermat quotients, Mathematics of Computation 66 (1997), 1353-1365.
K. Inkeri, On Catalan's problem, Acta Arithmetica 9 (1964), 285-290.
W. Keller and J. Richstein, Solutions of the congruence a^p-1 == 1 (mod p^r), Mathematics of Computation, 74 (2005), 927-936.
B. Logan and M. J. Mossinghoff, Double Wieferich pairs and circulant Hadamard matrices, ResearchGate, 2015.
P. Mihailescu, A class number free criterion for catalan's conjecture, Journal of Number Theory, Vol. 99, No. 2 (2003), 225-231.
C. Pomerance, J. L. Selfridge and S. S. Wagstaff, The pseudoprimes to 25 * 10^9, Mathematics of Computation, 35 (1980), 1003-1026.
R. Scott and R. Styer, On p^x-q^y=c and related three term exponential Diophantine equations with prime bases, Journal of Number Theory, Vol. 105, No. 2 (2004), 212-234.
R. Steiner, Class number bounds and Catalan's equation, Mathematics of Computation 67 (1998), 1317-1322.

Cf. A000040, A124121, A124122, A266829, A274916.

is_dwpp(n, k) = Mod(n, k^2)^(k-1)==1 && Mod(k, n^2)^(n-1)==1
search(x, y) = forprime(p=x, y, forprime(q=1, p-1, if(is_dwpp(p, q), print1(q, ", ", p, ", "))))
search(1, 1e6) \\ search pairs in the interval [1, 10^6]

A274916 Triangle T(n, k) read by rows: sum of residues p^(q-1) (mod q^2) and q^(p-1) (mod p^2), where p = prime(n) and q = prime(k) for k = 1, 2, ...., n-1.

Original entry on oeis.org

7, 17, 13, 18, 47, 44, 59, 5, 94, 38, 41, 112, 25, 133, 242, 223, 172, 226, 74, 188, 204, 61, 344, 250, 249, 128, 344, 317, 395, 399, 339, 306, 262, 347, 398, 412, 31, 440, 355, 835, 757, 737, 300, 713, 772, 190, 535, 301, 808, 137, 1013, 738, 647, 730, 1119

Offset: 1

Felix Fröhlich, Dec 11 2016

T(n, k) = 2 iff (p, q) is a double Wieferich prime pair.

			For n = 652 and k = 23: prime(23) = 83 and prime(652) = 4871. 83 and 4871 form a double Wieferich prime pair, so 83^4870 (mod 4871^2) = 1 and 4871^82 (mod 83^2) = 1, hence T(652, 23) = 1+1 = 2.
Triangle starts
    7;
   17,  13;
   18,  47,  44;
   59,   5,  94,  38;
   41, 112,  25, 133, 242;
  223, 172, 226,  74, 188,  204;
   61, 344, 250, 249, 128,  344, 317;
  395, 399, 339, 306, 262,  347, 398, 412;
   31, 440, 355, 835, 757,  737, 300, 713, 772;
  190, 535, 301, 808, 137, 1013, 738, 647, 730, 1119;

Wikipedia, Wieferich pair

Cf. A124121, A124122, A126432, A266829.

t(n, k) = lift(Mod(prime(n), prime(k)^2)^(prime(k)-1)) + lift(Mod(prime(k), prime(n)^2)^(prime(n)-1))
trianglerows(n) = for(x=2, n+1, for(y=1, x-1, print1(t(x, y), ", ")); print(""))
trianglerows(6) \\ print upper 6 rows of triangle

cp's OEIS Frontend

A317724 Smallest prime q < A266829(n) such that both A266829(n)^(q-1) == 1 (mod q^2) and q^(A266829(n)-1) == 1 (mod A266829(n)^2), i.e., smallest prime q less than A266829(n) such that q and A266829(n) form a double Wieferich prime pair.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A297846 Primes p such that p is the largest member of a Wieferich tuple.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A271100 Triangular array read by rows: T(n, k) = k-th largest member of lexicographically earliest Wieferich n-tuple that contains no duplicate members, read by rows, or T(n, k) = 0 if no Wieferich n-tuple exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Sage

Extensions

A282293 Two-column array A(n, k) read by rows, where A(n, 1) and A(n, 2) respectively give values of q and p in the n-th double Wieferich prime pair, where p > q. Terms sorted first by increasing size of p, then by increasing size of q.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A274916 Triangle T(n, k) read by rows: sum of residues p^(q-1) (mod q^2) and q^(p-1) (mod p^2), where p = prime(n) and q = prime(k) for k = 1, 2, ...., n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI