A088198 Distance LQnR(p_n) (A088196) from p_n.

1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 1, 1, 5, 1, 1, 3, 5, 2, 1, 1, 2, 3, 1, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 5, 2, 1, 1, 1, 1, 2, 3, 1, 7, 1, 3, 1, 2, 1, 2, 3, 1, 2, 1, 1, 5, 2, 1, 5, 1, 2, 3, 1, 1, 2, 1, 1, 2, 2, 3, 7, 1, 2, 1, 5, 1, 1, 3, 5, 2, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 2

Offset: 2

Author

Ferenc Adorjan (fadorjan(AT)freemail.hu), Sep 23 2003

Keywords

• easy
• nonn

Comments

The members of the sequence are either 1's or primes (easily provable).

Links

• Ferenc Adorjan, The sequence of largest quadratic residues modulo the primes.

Crossrefs

Cf. A088192, A088196, A088197, A088199, A088200, A088201.

Programs

Mathematica

qrQ[n_, p_] := Length[ Select[ Table[x^2, {x, 1, Floor[p/2]}], Mod[#, p] == n & , 1]] == 1; LQnR[p_] := Catch[ Do[ If[ !qrQ[k, p], Throw[k]], {k, p-1, 0, -1}]]; a[n_] := (p = Prime[n]; p - LQnR[p]); Table[a[n], {n, 2, 100}] (* Jean-François Alcover, May 14 2012 *)

PARI

qnrp_pm(fr,n)= {/* The distance of primes from the largest QnR modulo the primes */ local(m,p,fl,jj,j,v=[]); fr=max(fr,2); for(i=fr,n,m=0; p=prime(i); jj=0; fl=2^p-1; j=2; while((j<=(p-1)/2),jj=(j^2)%p; fl-=2^jj; j++); j=p-1; while(m==0,if(bitand(2^j,fl),m=j); j--); v=concat(v,p-m)); print(v)}

Formula

a(n) = prime(n)-LQnR(prime(n)) = A000040(n)-A088196(n), where prime(n) is the n-th prime and LQnR(m) is the largest quadratic non-residue modulo m.