A309090 a(n) is the least x such that x^2 mod prime(i), i=1..n, are all distinct.

1, 2, 2, 3, 3, 172, 213, 213, 333, 333, 1228, 1438, 2152, 3832, 3832, 3832, 5792, 22732, 22732, 37342, 37342, 37342, 37342, 37342, 545408, 629247, 629247, 629247, 629247, 629247, 629247, 629247, 629247, 1423713, 8136838, 8136838

Offset

1,2

Comments

There are more than n squares mod prime(n+1); therefore given a(n)=k we can choose a square r mod prime(n+1) that is not a(n)^2 mod prime(i) for i <= n, and using Chinese Remainder Theorem find x such that x == a(n) (mod prime(i)) for i <= n and x^2 == r (mod prime(n+1)), and then a(n+1) <= x. In particular a(n) exists for all n.

Links

Table of n, a(n) for n=1..36.

Example

a(5) = 3 because 3^2 mod 2 = 1, 3^2 mod 3 = 0, 3^2 mod 5 = 4, 3^2 mod 7 = 2 and 3^2 mod 11 = 9 are all distinct, while this is not the case for 1^2 or 2^2 (e.g. 2^2 mod 5 = 2^2 mod 7 = 4).

Maple

P:= NULL:
v:= 1:
for n from 1 to 35 do
  P:= P , ithprime(n);
  for k from v do
    if nops({seq(k^2 mod P[i], i=1..n)}) = n then
      v:= k;
      A[n]:= k;
      break
    fi
  od
od:
seq(A[n], n=1..35);

Prog

(PARI) isok(k, n) = my(v=vector(n, j, lift(Mod(k, j)^2))); #v == #Set(v);
a(n) = {my(k=1); while(!isok(k, n), k++); k; } \\ Michel Marcus, Jul 12 2019

Crossrefs

Cf. A279073.

Sequence in context: A196080 A124516 A205958 * A091048 A347326 A071478

Adjacent sequences: A309087 A309088 A309089 * A309091 A309092 A309093

Keyword

nonn

Author

Robert Israel, Jul 11 2019

Status

approved