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.

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, 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, 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

Offset: 1

Author

Lekraj Beedassy, Jul 09 2002

Keywords

• nonn

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384

Crossrefs

Cf. A060594.

Cf. A046072. - R. J. Mathar, Dec 15 2008

Programs

Mathematica

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 *)

PARI

A072273(n) = if(n<=2, 0, #znstar(n)[3] ); \\ After Joerg Arndt's code for A060594
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.
\\ Antti Karttunen, Aug 22 2017

Formula

2^a(n) = A060594(n).

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).

Extensions

Corrected and extended by T. D. Noe, Sep 09 2005