A055095 - OEIS

%I #28 May 14 2021 15:52:09

%S 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 -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 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 a(n) = 2*A000120(A003188(A055094(n))) - (n-1) = 2*A005811(A055094(n)) - (n-1).

%C 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 See problem 9.2.2 in Elementary Number Theory by David M. Burton, ISBN 0-205-06978-9

%H Indranil Ghosh, <a href="/A055095/b055095.txt">Table of n, a(n) for n = 1..4096</a>

%F a(n) = (2*wt(GrayCode(qrs2bincode(n))))-(n-1).

%p A055095 := proc(n)

%p     2*A005811(A055094(n))-n+1 ;

%p end proc:

%p seq(A055095(n),n=1..20) ; # _R. J. Mathar_, Mar 10 2015

%t A005811[n_] := Length[Length /@ Split[IntegerDigits[n, 2]]];

%t A055094[n_] := With[{rr = Table[Mod[k^2, n], {k, 1, n-1}] // Union}, Boole[ MemberQ[rr, #]]& /@ Range[n-1]] // FromDigits[#, 2]&;

%t a[1] = 0; a[n_] := 2*A005811[A055094[n]] - (n-1);

%t Array[a, 105] (* _Jean-François Alcover_, Mar 05 2016 *)

%o (Python)

%o from sympy.ntheory.residue_ntheory import quadratic_residues as q

%o def a055094(n):

%o     Q=q(n)

%o     z=0

%o     for i in range(1, n):

%o         z*=2

%o         if i in Q: z+=1

%o     return z

%o def a005811(n): return bin(n^(n>>1))[2:].count("1")

%o def a(n): return 0 if n == 1 else 2*a005811(a055094(n)) - (n - 1) # _Indranil Ghosh_, May 13 2017

%K sign

%O 1,3

%A _Antti Karttunen_, Apr 04 2000