|
%I #24 Jun 01 2022 08:16:27
%S 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 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 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 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 Antti Karttunen, <a href="/A072273/b072273.txt">Table of n, a(n) for n = 1..16384</a>
%F 2^a(n) = A060594(n).
%F 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 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 (PARI)
%o A072273(n) = if(n<=2, 0, #znstar(n)[3] ); \\ After _Joerg Arndt_'s code for A060594
%o 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 \\ _Antti Karttunen_, Aug 22 2017
%Y Cf. A060594.
%Y Cf. A046072. - _R. J. Mathar_, Dec 15 2008
%K nonn
%O 1,8
%A _Lekraj Beedassy_, Jul 09 2002
%E Corrected and extended by _T. D. Noe_, Sep 09 2005
|
