cp's OEIS Frontend

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

%I A309090 #13 Jul 12 2019 02:38:55
%S A309090 1,2,2,3,3,172,213,213,333,333,1228,1438,2152,3832,3832,3832,5792,
%T A309090 22732,22732,37342,37342,37342,37342,37342,545408,629247,629247,
%U A309090 629247,629247,629247,629247,629247,629247,1423713,8136838,8136838
%N A309090 a(n) is the least x such that x^2 mod prime(i), i=1..n, are all distinct.
%C A309090 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.
%e A309090 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).
%p A309090 P:= NULL:
%p A309090 v:= 1:
%p A309090 for n from 1 to 35 do
%p A309090   P:= P ,ithprime(n);
%p A309090   for k from v do
%p A309090     if nops({seq(k^2 mod P[i],i=1..n)}) = n then
%p A309090       v:= k;
%p A309090       A[n]:= k;
%p A309090       break
%p A309090     fi
%p A309090   od
%p A309090 od:
%p A309090 seq(A[n],n=1..35);
%o A309090 (PARI) isok(k, n) = my(v=vector(n, j, lift(Mod(k, j)^2))); #v == #Set(v);
%o A309090 a(n) = {my(k=1); while(!isok(k, n), k++); k;} \\ _Michel Marcus_, Jul 12 2019
%Y A309090 Cf. A279073.
%K A309090 nonn
%O A309090 1,2
%A A309090 _Robert Israel_, Jul 11 2019