A185103 -id:A185103 - cp's OEIS frontend

A353601 Square array read by downward antidiagonals: A(n, 1) = A185103(n) and A(n, k) = A185103(A(n, k-1)) for k > 1.

5, 7, 8, 18, 65, 17, 325, 99, 38, 7, 1432, 485, 1445, 18, 37, 2050625, 5357, 27493, 325, 18, 18, 1299108307, 12807125, 9077774, 1432, 325, 325, 65

Offset: 2

Felix Fröhlich, Apr 29 2022

What is the asymptotic behavior of the rows of the array? Do all rows increase without bound, or do some rows enter a cycle?

			Array starts as follows:
   5,  7,   18,   325,    1432, ...
   8, 65,   99,   485,    5357, ...
  17, 38, 1445, 27493, 9077774, ...
   7, 18,  325,  1432, 2050625, ...
  37, 18,  325,  1432, 2050625, ...
...

Cf. A185103.

a185103(n) = for(b=2, oo, if(Mod(b, n^2)^(n-1)==1, return(b)))
a(n, k) = if(k==1, return(a185103(n)), return(a185103(a(n, k-1))))
array(rows, cols) = for(x=2, rows+1, for(y=1, cols, print1(a(x, y), ", ")); print(""))
array(5, 5) \\ Print initial 5 rows and 5 columns of array

from functools import lru_cache
def A185103(n):
    k, n2 = 2, n*n
    while pow(k, n-1, n2) != 1: k += 1
    return k
@lru_cache()
def T(n, k):
    if k == 1: return A185103(n)
    return A185103(T(n, k-1))
def auptodiag(maxd):
    return [T(d+2-j, j) for d in range(1, maxd+1) for j in range(d, 0, -1)]
print(auptodiag(6)) # Michael S. Branicky, Apr 29 2022

a(16)-a(28) from Michael S. Branicky, Apr 29 2022

A039678 Smallest number m > 1 such that m^(p-1)-1 is divisible by p^2, where p = n-th prime.

Original entry on oeis.org

5, 8, 7, 18, 3, 19, 38, 28, 28, 14, 115, 18, 51, 19, 53, 338, 53, 264, 143, 11, 306, 31, 99, 184, 53, 181, 43, 164, 96, 68, 38, 58, 19, 328, 313, 78, 226, 65, 253, 259, 532, 78, 176, 276, 143, 174, 165, 69, 330, 44, 33, 332, 94, 263, 48, 79, 171, 747, 731, 20, 147, 91, 40

Offset: 1

Felice Russo

Using Fermat's little theorem twice, it is easy to see that m=p^2-1 solves this problem for all odd primes p. In fact, there appear to be exactly p-1 values of m with 1 <= m <= p^2 for which m^(p-1) == 1 (mod p^2). See A096082 for the related open problem. - T. D. Noe, Aug 24 2008
That there are exactly p-1 values of 1 <= m <= p^2 for which m^(p-1) == 1 (mod p^2) follows immediately from Hensel's lifting lemma and Fermat's little theorem - every solution mod p corresponds to a unique solution mod p^2. - Phil Carmody, Jan 10 2011
For n > 2, prime(n) does not divide a(n)^2 - 1, so a(n) is the smallest m > 1 such that (m^(prime(n)-1) - 1)/(m^2 - 1) == 0 (mod prime(n)^2). - Thomas Ordowski, Nov 24 2018

			For n=3, p=5 is the third prime and 5^2 = 25 divides 7^4 - 1 = 2400.

P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, 345-349.

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

Cf. A185103.

dpa[n_]:=Module[{p=Prime[n],a=2},While[PowerMod[a,p-1,p^2]!=1,a++];a]; Array[dpa,70] (* Harvey P. Dale, Sep 05 2012 *)

a(n) = my(p=prime(n)); for(a=2, oo, if(Mod(a, p^2)^(p-1)==1, return(a))) \\ Felix Fröhlich, Nov 24 2018

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

a(n) = A185103(A000040(n)).

More terms from David W. Wilson
Definition adjusted by Felix Fröhlich, Jun 24 2014
Edited by Felix Fröhlich, Nov 24 2018

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.

Original entry on oeis.org

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(""))

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

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

A280199 Numbers n such that a^(n-1) == 1 (mod n^2) has solutions with 1 < a < n^2-1.

Original entry on oeis.org

5, 7, 11, 13, 15, 17, 19, 21, 23, 25, 28, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 52, 53, 55, 57, 59, 61, 63, 65, 66, 67, 69, 70, 71, 73, 75, 76, 77, 79, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 112, 113, 115, 117, 119, 121, 123, 124, 125

Offset: 1

Robert Israel and Thomas Ordowski, Dec 28 2016

nonn

Numbers n such that A185103(n) < n^2 + (-1)^n.
Complement of A280196.
Even terms are A039772.
Odd terms are all odd numbers that are not powers of 3.
Conjecture: composite terms are A181780.

			a(4) = 13 is in the sequence because 19^12 == 1 (mod 13^2), and 1 < 19 < 13^2-1.

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

Cf. A000244, A039772, A185103, A280196.

Aeven:= remove(t -> igcd(t-1, numtheory:-phi(t^2))=1, {seq(i,i=2..1000,2)}):
Aodd:= {seq(i,i=3..1000,2)} minus {seq(3^i,i=0..floor(log[3](1000)))}:
sort(convert(Aeven union Aodd,list));

Aeven = DeleteCases[Range[2, 1000, 2], t_ /; GCD[t-1, EulerPhi[t^2]] == 1];
Aodd = Complement[Range[3, 1000, 2], Table[3^i, {i, 0, Floor[Log[3, 1000]]} ]];
Union[Aeven, Aodd] (* Jean-François Alcover, Apr 24 2019, after Robert Israel *)

A280196 Numbers n such that a^(n-1) == 1 (mod n^2) has no solutions with 1 < a < n^2-1.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24, 26, 27, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 54, 56, 58, 60, 62, 64, 68, 72, 74, 78, 80, 81, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 114, 116, 118, 120, 122, 126, 128, 132, 134, 136, 138

Offset: 1

Robert Israel and Thomas Ordowski, Dec 28 2016

nonn

1 and numbers n such that A185103(n) = n^2 + (-1)^n.
Complement of A280199.
Union of A000244 and A209211.

			a(4) = 4 is in the sequence because a^3 == 1 (mod 4^2) has no solutions except a == 1 (mod 4^2).
a(7) = 9 is in the sequence because a^8 == 1 (mod 9^2) has no solutions except a == 1 (mod 9^2) and a == 80 (mod 9^2), and 80 = 9^2-1.

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

Cf. A000244, A185103, A209211, A280199.

Aeven:= select(t -> igcd(t-1, numtheory:-phi(t^2))=1, {seq(i,i=2..1000,2}}):
Aodd:= {seq(3^i,i=0..floor(log[3](1000)))}:
sort(convert(Aeven union Aodd, list));

Aeven = Select[Range[2, 1000, 2], GCD[#-1,EulerPhi[#^2]] == 1&];
Aodd = 3^Range[0, Floor[Log[3, 1000]]];
Union[Aeven, Aodd] (* Jean-François Alcover, Apr 27 2019, from Maple *)

A250206 Least base b > 1 such that b^A000010(n) = 1 (mod n^2).

Original entry on oeis.org

2, 5, 8, 7, 7, 17, 18, 15, 26, 7, 3, 17, 19, 19, 26, 31, 38, 53, 28, 7, 19, 3, 28, 17, 57, 19, 80, 19, 14, 107, 115, 63, 118, 65, 18, 53, 18, 69, 19, 7, 51, 19, 19, 3, 26, 63, 53, 17, 18, 57, 134, 19, 338, 161, 3, 31, 28, 41, 53, 107, 264, 115, 19, 127, 99, 161, 143, 65, 28, 99, 11, 55

Offset: 1

Eric Chen, Feb 21 2015

nonn

a(n) = least base b > 1 such that n is a Wieferich number (see A077816).
At least, b = n^2+1 can satisfy this equation, so a(n) is defined for all n.
Least Wieferich number (>1) to base n: 2, 1093, 11, 1093, 2, 66161, 4, 3, 2, 3, 71, 2693, 2, 29, 4, 1093, 2, 5, 3, 281, 2, 13, 4, 5, 2, ...; each is a prime or 4. It is 4 if and only if n mod 72 is in the set {7, 15, 23, 31, 39, 47, 63}.
Does every natural number (>1) appear in this sequence? If yes, do they appear infinitely many times?
For prime n, a(n) = A185103(n), does there exist any composite n such that a(n) = A185103(n)?

			a(30) = 107 since A000010(30) = 8, 30^2 = 900, and 107 is the least base b > 1 such that b^8 = 1 (mod 900).

Eric Chen, Table of n, a(n) for n = 1..1000

Cf. A039678, A185103, A125636, A039951, A247154, A001220, A014127, A123692, A212583, A123693, A045616, A111027, A128667, A234810, A242741, A128668, A244260, A090968, A242982, A128669, A077816, A242958, A242959, A241978, A242960, A241977, A253016, A245529.

f[n_] := Block[{b = 2, m = EulerPhi[n]}, While[ PowerMod[b, m, n^2] != 1, b++]; b]; f[1] = 2; Array[f, 72] (* Robert G. Wilson v, Feb 28 2015 *)

a(n)=for(k=2,2^24,if((k^eulerphi(n))%(n^2)==1, return(k)))

a(prime(n)) = A039678(n) = A185103(prime(n)).
a(A077816(n)) = 2.
a(A242958(n)) <= 3.

A287147 Primes p that set a new record for the size of the smallest b > 1 such that b^(p-1) == 1 (mod p^2).

Original entry on oeis.org

2, 3, 7, 13, 17, 31, 53, 179, 271, 311, 503, 569, 587, 1231, 1307, 1543, 1931, 2647, 2711, 3089, 3917, 4919, 5879, 6491, 8933, 9137, 11437, 13411, 14431, 16657, 21599, 26053, 29129, 57367, 58481, 62071, 62971, 68351, 70639, 109721, 156967, 193811, 216211

Offset: 1

Felix Fröhlich, May 20 2017

nonn

Primes p such that A039678(i) reaches record values, where i is the index of p in A000040.

Records of (A185103 restricted to primes). - Joerg Arndt, May 29 2017

Cf. A000040, A039678, A185103, A248865, A278611.

Function[s, Prime@ Position[s, #][[1, 1]] & /@ Union@ FoldList[Max, s]]@ Table[Function[p, b = 2; While[PowerMod[b, p - 1, p^2] != 1, b++]; b]@ Prime@ n, {n, 10^3}] (* Michael De Vlieger, May 21 2017 *)

minb(n) = my(b=2); while(Mod(b, n^2)^(n-1)!=1, b++); b
my(r=0); forprime(p=1, , if(minb(p) > r, print1(p, ", "); r=minb(p)))

from itertools import islice
from sympy import nextprime
from sympy.ntheory.residue_ntheory import nthroot_mod
def A287147_gen(): # generator of terms
    c, p = 5, 3
    yield 2
    while True:
        d = nthroot_mod(1,p-1,p**2,True)[1]
        if d > c:
            c = d
            yield p
        p = nextprime(p)
A287147_list = list(islice(A287147_gen(),15)) # Chai Wah Wu, May 18 2022

A353600 Second-smallest Wieferich base of n, i.e., second-smallest b > 1 such that b^(n-1) == 1 (mod n^2).

Original entry on oeis.org

9, 10, 33, 18, 73, 19, 129, 82, 201, 9, 289, 22, 393, 199, 513, 40, 649, 54, 801, 244, 969, 42, 1153, 443, 1353, 730, 753, 41, 1801, 117, 2049, 604, 2313, 1126, 2593, 76, 2889, 1351, 3201, 148, 3529, 75, 3873, 568, 4233, 67, 4609, 1048, 5001, 2024, 1329, 406

Offset: 2

Felix Fröhlich, Apr 29 2022

nonn

Cf. A039678, A185103, A256517. Column 2 of A353602.

a(n) = my(i=0); for(b=2, oo, if(Mod(b, n^2)^(n-1)==1, if(i==0, i++, return(b))))

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

cp's OEIS Frontend

A353601 Square array read by downward antidiagonals: A(n, 1) = A185103(n) and A(n, k) = A185103(A(n, k-1)) for k > 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Python

Extensions

A039678 Smallest number m > 1 such that m^(p-1)-1 is divisible by p^2, where p = n-th prime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

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

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

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'.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A280199 Numbers n such that a^(n-1) == 1 (mod n^2) has solutions with 1 < a < n^2-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A280196 Numbers n such that a^(n-1) == 1 (mod n^2) has no solutions with 1 < a < n^2-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs