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

Links

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

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

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

Prog

(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

Crossrefs

Cf. A060594.

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

Sequence in context: A359306 A332761 A046072 * A157230 A034380 A328966

Adjacent sequences: A072270 A072271 A072272 * A072274 A072275 A072276

Keyword

nonn

Author

Lekraj Beedassy, Jul 09 2002

Extensions

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

Status

approved