cp's OEIS Frontend

A055094 Binary encoding of quadratic residue set of n. L(1/n) is the most significant bit, L(n-1/n) is the least significant bit, i.e., the rows of A055088 interpreted as binary numbers.

%I A055094 #19 Mar 05 2016 06:04:12
%S A055094 0,1,2,4,9,22,52,72,146,313,738,1156,2829,6772,9520,18496,53643,75154,
%T A055094 162438,312328,600116,1513186,4023888,4737152,9741609,23182093,
%U A055094 38478994,76286020,166236537,311977264,921787428,1212203072,2962424994
%N A055094 Binary encoding of quadratic residue set of n. L(1/n) is the most significant bit, L(n-1/n) is the least significant bit, i.e., the rows of A055088 interpreted as binary numbers.
%C A055094 L(a/n) stands for generalized Legendre symbol, with value = 1 only if a is a quadratic residue of n.
%F A055094 a(n) = qrs2bincode(n)
%p A055094 A055094 := proc(n)
%p A055094     local i, z;
%p A055094     z := 0;
%p A055094     for i from 1 to n-1 do
%p A055094         z := z*2;
%p A055094         if (1 = numtheory[quadres](i, n)) then
%p A055094             z := z + 1;
%p A055094         fi;
%p A055094     od;
%p A055094     return z;
%p A055094 end proc:
%t A055094 a[n_] := With[{rr = Table[Mod[k^2, n], {k, 1, n - 1}] // Union}, Boole[ MemberQ[rr, #]]& /@ Range[n - 1]] // FromDigits[#, 2]&; Array[a, 40] (* _Jean-François Alcover_, Mar 05 2016*)
%o A055094 (PARI) {a(n)=sum(k=1, n-1, 2^(k-1)*(0<sum(i=1, n-1, i^2%n==n-k)))} /* _Michael Somos_, Oct 14 2006 */
%o A055094 (Sage)
%o A055094 def A055094(n) :
%o A055094     Q = quadratic_residues(n)
%o A055094     z = 0
%o A055094     for i in (1..n-1)  :
%o A055094         z = z*2
%o A055094         if i in Q : z += 1
%o A055094     return z
%o A055094 [A055094(n) for n in (1..33)] # _Peter Luschny_, Aug 08 2012
%Y A055094 Cf. A055088, A054432, A055095.
%K A055094 nonn
%O A055094 1,3
%A A055094 _Antti Karttunen_, Apr 04 2000