cp's OEIS Frontend

A072273 Index of powers of 2 that equal the number of noncongruent roots to the congruence x^2 == k (mod n) for (k,n)=1 and assuming solvability.

%I A072273 #24 Jun 01 2022 08:16:27
%S A072273 0,0,1,1,1,1,1,2,1,1,1,2,1,1,2,2,1,1,1,2,2,1,1,3,1,1,1,2,1,2,1,2,2,1,
%T A072273 2,2,1,1,2,3,1,2,1,2,2,1,1,3,1,1,2,2,1,1,2,3,2,1,1,3,1,1,2,2,2,2,1,2,
%U A072273 2,2,1,3,1,1,2,2,2,2,1,3,1,1,1,3,2,1,2,3,1,2,2,2,2,1,2,3,1,1,2,2,1,2,1,3,3
%N A072273 Index of powers of 2 that equal the number of noncongruent roots to the congruence x^2 == k (mod n) for (k,n)=1 and assuming solvability.
%H A072273 Antti Karttunen, <a href="/A072273/b072273.txt">Table of n, a(n) for n = 1..16384</a>
%F A072273 2^a(n) = A060594(n).
%F A072273 a(n) = A005087(n) + i, where i may be 0, 1 or 2 according as 2^j divides n, respectively with j <= 1, j = 2 or j >= 3, (i.e., i=0 when n is not divisible by 4; i=1 when n is divisible by 4 but not by 8; i=2 when n is divisible by 8).
%t A072273 Log[2, Table[cnt=0; Do[If[Mod[k^2-1, n]==0, cnt++ ], {k, n}]; cnt, {n, 150}]] (* _T. D. Noe_, Sep 09 2005 *)
%o A072273 (PARI)
%o A072273 A072273(n) = if(n<=2, 0, #znstar(n)[3] ); \\ After _Joerg Arndt_'s code for A060594
%o A072273 A072273(n) = {my(o=valuation(n, 2)); (omega(n>>o)+max(min(o-1, 2), 0)); }; \\ Or after _Charles R Greathouse IV_ code for A060594.
%o A072273 \\ _Antti Karttunen_, Aug 22 2017
%Y A072273 Cf. A060594.
%Y A072273 Cf. A046072. - _R. J. Mathar_, Dec 15 2008
%K A072273 nonn
%O A072273 1,8
%A A072273 _Lekraj Beedassy_, Jul 09 2002
%E A072273 Corrected and extended by _T. D. Noe_, Sep 09 2005