A280109 a(n) is the decimal value corresponding to the binary representation of the distribution of quadratic residues (value=1) and non-quadratic residues (value=0) mod n, where numbers are ordered left to right from 0 to n-1.

1, 3, 6, 12, 25, 54, 116, 200, 402, 825, 1762, 3204, 6925, 14964, 25904, 51264, 119179, 206226, 424582, 836616, 1648692, 3610338, 8218192, 13125760, 26518825, 56736525, 105587858, 210503748, 434671993, 848848176, 1995529252, 3359686720, 7257392290, 15621149067

Offset: 1

Author

Adnan Baysal, Dec 26 2016

Keywords

• nonn
• base

Comments

Sort mod n numbers {0,1,...,n-1} in ascending order. For each modular number i, write 1 if i is a quadratic residue mod n (i.e., it has a square root), else write 0. The corresponding n-bit number is a(n).

Examples

			For n = 10, quadratic residues are 0, 1, 4, 5, 6, 9 so a(10) is 1100111001 in binary which is 825.
		

Links

• Adnan Baysal, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A055094, A080117, A080146, A096008.

Programs

Mathematica

f[n_] := Total[ 2^(n -1 -Union[ Mod[ Range[0, n - 1]^2, n]] )]; Array[f, 34] (* Robert G. Wilson v, Dec 28 2016 *)

Python

def qr_distribution(N):
    QR = []
    QN = []
    for i in range(N):
        t = (i*i)%N
        if t not in QR: QR.append(t)
    for i in range(N):
        if i not in QR: QN.append(i)
    out = 0
    for i in range(0,N):
        out *= 2
        if i in QR: out += 1
    return out