A309316 -id:A309316 - cp's OEIS frontend

A366973 Smallest odd prime p such that n^((p+1)/2) == n (mod p).

3, 3, 7, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 13, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 11, 3, 3, 5, 3, 3, 5, 3, 3, 11, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 13, 3, 3, 5, 3, 3, 13, 3, 3, 5, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 17, 3, 3

Offset: 0

Thomas Ordowski, Oct 30 2023

nonn

a(n) is the smallest odd prime p for which the Legendre symbol (n / p) >= 0.
For any set S of odd primes, by Chinese Remainder Theorem, there is n such that n is a primitive root mod each prime p in S, and then n^((p-1)/2) != 1 (mod p). Since n is invertible mod p, n^((p-1)/2) != 1 (mod p) implies n^((p+1)/2) != n (mod p). So this sequence is unbounded. - Robert Israel, Oct 31 2023
From Charles L. Hohn, Sep 27 2024: (Start)
Smallest odd prime p for which n is a square mod p.
Smallest odd prime p for which n mod p is a member of row A096008(p). (End)

Robin Visser, Table of n, a(n) for n = 0..10000

Cf. A309316, A366930, A366982.

Cf. A096008.

f:= proc(n) local p;
  p:= 2;
  do
    p:= nextprime(p);
    if n &^ ((p+1)/2) - n mod p = 0 then return p fi
  od
end proc:
map(f, [$0..100]); # Robert Israel, Oct 30 2023

a[n_] := Module[{p = 3}, While[PowerMod[n, (p + 1)/2, p] != Mod[n, p], p = NextPrime[p]]; p]; Array[a, 100, 0] (* Amiram Eldar, Oct 30 2023 *)

a(n) = my(p=3); while(Mod(n, p)^((p+1)/2) != n, p=nextprime(p+1)); p; \\ Michel Marcus, Oct 30 2023

a(n) = for(i=2, oo, my(p=prime(i)); for(j=0, (p-1)/2, if(n%p==j^2%p, return(p)))) \\ Charles L. Hohn, Sep 27 2024

More terms from Amiram Eldar, Oct 30 2023

A366982 a(n) is the smallest odd k > 1 such that n^((k+1)/2) == n (mod k).

Original entry on oeis.org

3, 3, 7, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 9, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 11, 3, 3, 5, 3, 3, 5, 3, 3, 11, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 9, 3, 3, 5, 3, 3, 13, 3, 3, 5, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 17, 3, 3

Offset: 0

Thomas Ordowski, Oct 30 2023

nonn

If this sequence is bounded, then it is periodic with period P = LCM(A), where A is the set of all (pairwise distinct) terms.
Note that n^((1729+1)/2) == n (mod 1729) for every n >= 0, where 1729 is the smallest absolute Euler pseudoprime (A033181).
Thus a(n) <= 1729. So, as said, this sequence is periodic.
What is its period?
If the largest term of this sequence is indeed 1729, it should be expected that its period P may be longer than the period of Euler primary pretenders (A309316), namely P > 41#*571#/4 (248 digits).

Antti Karttunen, Table of n, a(n) for n = 0..65537

Cf. A033181, A309316, A366930, A366973.

a[n_] := Module[{k = 3}, While[PowerMod[n, (k + 1)/2, k] != Mod[n, k], k += 2]; k]; Array[a, 100, 0] (* Amiram Eldar, Oct 30 2023 *)

a(n) = my(k=3); while (Mod(n, k)^((k+1)/2) != n, k+=2); k; \\ Michel Marcus, Oct 31 2023

More terms from Amiram Eldar, Oct 30 2023

A366930 a(n) is the smallest odd composite k such that n^((k+1)/2) == n (mod k).

Original entry on oeis.org

9, 9, 341, 121, 341, 65, 15, 21, 9, 9, 9, 33, 33, 21, 21, 15, 15, 9, 9, 9, 21, 15, 21, 33, 25, 15, 9, 9, 9, 21, 15, 15, 25, 33, 21, 9, 9, 9, 57, 39, 15, 21, 21, 21, 9, 9, 9, 65, 21, 21, 21, 15, 39, 9, 9, 9, 21, 21, 57, 145, 15, 15, 9, 9, 9, 33, 15, 33, 25, 21

Offset: 0

Thomas Ordowski, Nov 01 2023

nonn

If this sequence is bounded, then it is periodic with period P = LCM(A), where A is the set of all (pairwise distinct) terms.
Note that n^((1729+1)/2) == n (mod 1729) for every n >= 0, where 1729 is the smallest absolute Euler pseudoprime (A033181).
Thus a(n) <= 1729. So, as said, this sequence is periodic.
What is its period?
The period P of this sequence may be longer than the period of Euler primary pretenders (A309316), namely P > 41#*571#/4 (248 digits).

Cf. A033181, A309316, A366973, A366982.

a[n_] := Module[{k = 9}, While[PrimeQ[k] || PowerMod[n, (k + 1)/2, k] != Mod[n, k], k += 2]; k]; Array[a, 100, 0] (* Amiram Eldar, Nov 01 2023 *)

a(n) = my(k=3); while (isprime(k) || Mod(n, k)^((k+1)/2) != n, k+=2); k; \\ Michel Marcus, Nov 01 2023

a(n) >= A309316(n).

cp's OEIS Frontend

A366973 Smallest odd prime p such that n^((p+1)/2) == n (mod p).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Extensions

A366982 a(n) is the smallest odd k > 1 such that n^((k+1)/2) == n (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A366930 a(n) is the smallest odd composite k such that n^((k+1)/2) == n (mod k).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula