|
|
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
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
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).
|
|
LINKS
|
|
|
EXAMPLE
|
For n = 10, quadratic residues are 0, 1, 4, 5, 6, 9 so a(10) is 1100111001 in binary which is 825.
|
|
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 *)
|
|
PROG
|
#(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,base
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|