cp's OEIS Frontend

A055095 a(n) = 2*A000120(A003188(A055094(n))) - (n-1) = 2*A005811(A055094(n)) - (n-1).

%I A055095 #28 May 14 2021 15:52:09
%S A055095 0,1,2,1,2,3,2,1,4,1,2,1,2,3,2,-3,2,7,2,-3,4,3,2,-3,14,1,10,-3,2,3,2,
%T A055095 -11,4,1,-2,-7,2,3,2,-11,2,7,2,-7,-4,3,2,-19,8,25,2,-11,2,19,-6,-15,4,
%U A055095 1,2,-19,2,3,-6,-23,-10,7,2,-15,4,-5,2,-27,2,1,6,-15,-4,3,2,-39,28,1,2,-27,-14,3,2,-27,2,-9,-10,-19,4,3,-14,-47,2,15,-14,-19,2,3,2,-35,-24
%N A055095 a(n) = 2*A000120(A003188(A055094(n))) - (n-1) = 2*A005811(A055094(n)) - (n-1).
%C A055095 For all odd primes p, a(p) = +2 because Sum_{a=1..(p-2)} L((a(a+1))/p) = Sum_{a=1..(p-2)} L((1+(a^-1))/p) = -1; i.e. in Gray code expansion of A055094[p], the number of 1-bits is number of 0-bits + 2. However, a(n) = +2 also for some nonprime odd n = A055131.
%D A055095 See problem 9.2.2 in Elementary Number Theory by David M. Burton, ISBN 0-205-06978-9
%H A055095 Indranil Ghosh, <a href="/A055095/b055095.txt">Table of n, a(n) for n = 1..4096</a>
%F A055095 a(n) = (2*wt(GrayCode(qrs2bincode(n))))-(n-1).
%p A055095 A055095 := proc(n)
%p A055095     2*A005811(A055094(n))-n+1 ;
%p A055095 end proc:
%p A055095 seq(A055095(n),n=1..20) ; # _R. J. Mathar_, Mar 10 2015
%t A055095 A005811[n_] := Length[Length /@ Split[IntegerDigits[n, 2]]];
%t A055095 A055094[n_] := With[{rr = Table[Mod[k^2, n], {k, 1, n-1}] // Union}, Boole[ MemberQ[rr, #]]& /@ Range[n-1]] // FromDigits[#, 2]&;
%t A055095 a[1] = 0; a[n_] := 2*A005811[A055094[n]] - (n-1);
%t A055095 Array[a, 105] (* _Jean-François Alcover_, Mar 05 2016 *)
%o A055095 (Python)
%o A055095 from sympy.ntheory.residue_ntheory import quadratic_residues as q
%o A055095 def a055094(n):
%o A055095     Q=q(n)
%o A055095     z=0
%o A055095     for i in range(1, n):
%o A055095         z*=2
%o A055095         if i in Q: z+=1
%o A055095     return z
%o A055095 def a005811(n): return bin(n^(n>>1))[2:].count("1")
%o A055095 def a(n): return 0 if n == 1 else 2*a005811(a055094(n)) - (n - 1) # _Indranil Ghosh_, May 13 2017
%K A055095 sign
%O A055095 1,3
%A A055095 _Antti Karttunen_, Apr 04 2000