A055094 -id:A055094 - cp's OEIS frontend

A055095 a(n) = 2A000120(A003188(A055094(n))) - (n-1) = 2A005811(A055094(n)) - (n-1).

0, 1, 2, 1, 2, 3, 2, 1, 4, 1, 2, 1, 2, 3, 2, -3, 2, 7, 2, -3, 4, 3, 2, -3, 14, 1, 10, -3, 2, 3, 2, -11, 4, 1, -2, -7, 2, 3, 2, -11, 2, 7, 2, -7, -4, 3, 2, -19, 8, 25, 2, -11, 2, 19, -6, -15, 4, 1, 2, -19, 2, 3, -6, -23, -10, 7, 2, -15, 4, -5, 2, -27, 2, 1, 6, -15, -4, 3, 2, -39, 28, 1, 2, -27, -14, 3, 2, -27, 2, -9, -10, -19, 4, 3, -14, -47, 2, 15, -14, -19, 2, 3, 2, -35, -24

Offset: 1

Antti Karttunen, Apr 04 2000

sign

For all odd primes p, a(p) = +2 because Sum_{a=1..(p-2)} L((a(a+1))/p) = Sum_{a=1..(p-2)} L((1+(a^-1))/p) = -1; i.e. in Gray code expansion of A055094[p], the number of 1-bits is number of 0-bits + 2. However, a(n) = +2 also for some nonprime odd n = A055131.

See problem 9.2.2 in Elementary Number Theory by David M. Burton, ISBN 0-205-06978-9

Indranil Ghosh, Table of n, a(n) for n = 1..4096

A055095 := proc(n)
    2*A005811(A055094(n))-n+1 ;
end proc:
seq(A055095(n),n=1..20) ; # R. J. Mathar, Mar 10 2015

A005811[n_] := Length[Length /@ Split[IntegerDigits[n, 2]]];
A055094[n_] := With[{rr = Table[Mod[k^2, n], {k, 1, n-1}] // Union}, Boole[ MemberQ[rr, #]]& /@ Range[n-1]] // FromDigits[#, 2]&;
a[1] = 0; a[n_] := 2*A005811[A055094[n]] - (n-1);
Array[a, 105] (* Jean-François Alcover, Mar 05 2016 *)

from sympy.ntheory.residue_ntheory import quadratic_residues as q
def a055094(n):
    Q=q(n)
    z=0
    for i in range(1, n):
        z*=2
        if i in Q: z+=1
    return z
def a005811(n): return bin(n^(n>>1))[2:].count("1")
def a(n): return 0 if n == 1 else 2*a005811(a055094(n)) - (n - 1) # Indranil Ghosh, May 13 2017

a(n) = (2*wt(GrayCode(qrs2bincode(n))))-(n-1).

A080146 Binary encoding of quadratic residue set for each prime. a(n) = A055094(A000040(n)).

Original entry on oeis.org

1, 2, 9, 52, 738, 2829, 53643, 162438, 4023888, 166236537, 921787428, 48034254669, 935251837851, 2558696229078, 68055676507664, 2655011771373417, 210067141980993186, 831463105466530077, 42882922858578320598

Offset: 1

Antti Karttunen, Feb 11 2003

nonn

Cf. A000040, A055094, A080117, A080148.

with(numtheory,ithprime); A080146 := n -> A055094(ithprime(n));

A055094[n_] := With[{rr = Table[Mod[k^2, n], {k, 1, n-1}] // Union}, Boole[MemberQ[rr, #]]& /@ Range[n-1]] // FromDigits[#, 2]&;
a[n_] := A055094[Prime[n]];
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Sep 20 2022 *)

a(n) = my(p=prime(n)); sum(k=1, p-1, 2^(k-1)*(0Michel Marcus, Sep 20 2022; after A055094

a(A080148(n)) = A080117(A080148(n)).

A095102 Odd primes p for which all sums Sum_{i=1..u} L(i/p) (with u ranging from 1 to (p-1)) are nonnegative, where L(i/p) is Legendre symbol of i and p, defined to be 1 if i is a quadratic residue (mod p) and -1 if i is a quadratic non-residue (mod p).

Original entry on oeis.org

3, 7, 11, 23, 31, 47, 59, 71, 79, 83, 103, 131, 151, 167, 191, 199, 239, 251, 263, 271, 311, 359, 383, 419, 431, 439, 479, 503, 563, 599, 607, 647, 659, 719, 743, 751, 839, 863, 887, 911, 919, 971, 983, 991, 1031, 1039, 1063, 1091, 1103, 1151

Offset: 1

Antti Karttunen, Jun 01 2004

nonn

All 4k+3 primes whose Legendre-vector (cf. A055094) forms a valid Dyck-path (cf. A014486).

T. D. Noe, Table of n, a(n) for n=1..1000
Peter Borwein, Stephen K.K. Choi and Michael Coons, Completely multiplicative functions taking values in {-1,1}, arXiv:0809.1691 [math.NT], 2008.
A. Karttunen and J. Moyer, C-program for computing the initial terms of this sequence

Intersection of A000040 and A095100. Subset of A080114 (see comments there). Complement of A095103 in A002145.

Cf. A095092.

isMotzkin[n_, k_] := Module[{s = 0, r = True}, Do[s += JacobiSymbol[i, n]; If[s < 0, r = False; Break[]], {i, 1, k}]; r]; A095102[max_] := Select[ Range[3, max, 4], PrimeQ[#] && isMotzkin[#, Quotient[#, 2]]&]; A095102[1151] (* Jean-François Alcover, Feb 16 2018, after Peter Luschny *)

isok(m) = {if(!isprime(m-(m<3)), return(0)); my(s=0); for(i=1, m-1, if((s+=kronecker(i, m))<0, return(0))); 1; } \\ Jinyuan Wang, Jul 20 2020

def A095102_list(n) :
    def is_Motzkin(n, k):
        s = 0
        for i in (1..k):
            s += jacobi_symbol(i, n)
            if s < 0: return False
        return True
    P = filter(is_prime, range(3, n+1, 4))
    return filter(lambda m: is_Motzkin(m, m//2), P)
A095102_list(1151) # Peter Luschny, Aug 09 2012

a(n) = 4*A095272(n) + 3.

A080114 Odd primes p for which all sums Sum_{j=1..u} L(j/p) (with u ranging from 1 to (p-1)/2) are nonnegative, where L(j/p) is Legendre symbol of j and p.

Original entry on oeis.org

3, 5, 7, 11, 13, 23, 31, 37, 47, 59, 71, 79, 83, 103, 131, 151, 167, 191, 199, 239, 251, 263, 271, 311, 359, 383, 419, 431, 439, 479, 503, 563, 599, 607, 647, 659, 719, 743, 751, 839, 863, 887, 911, 919, 971, 983, 991, 1031, 1039, 1063, 1091, 1103, 1151, 1223

Offset: 1

Antti Karttunen, Feb 11 2003

nonn

This sequence contains those 4k+1 primes p for which the first half (the (p-1)/2 most significant bits) of A055094(p) is in A014486 and those 4k+3 primes q, for which the whole A055094(q) is in A014486.
Are the 2nd, 5th and 8th primes (5,13,37) only terms of this sequence that are of the form 4k+1? [Searched up to a(211)=7927 by AK.]
No other such terms up to 19997. - Michel Marcus, Sep 21 2022

Michel Marcus, Table of n, a(n) for n = 1..430
Antti Karttunen, Illustration of Legendre's candelabras
Eric Weisstein's World of Mathematics, Legendre Symbol
Wikipedia, Legendre symbol

Cf. A080112, A080115. These are the primes for which a "Legendre's candelabra" can be constructed, see A080120.

Supersequence of A095102.

with(numtheory); # For ithprime and legendre.
A080114 := n -> ithprime(A080112(n));
A080114v2 := proc(upto_n) local j,a,p,i,s; a := []; for i from 2 to upto_n do p := ithprime(i); s := 0; for j from 1 to (p-1)/2 do s := s + legendre(j,p); if(s < 0) then break; fi; od; if(s >= 0) then a := [op(a),p]; fi; od; RETURN(a); end;

s[p_, u_] := Sum[JacobiSymbol[j, p], {j, 1, u}]; Select[Prime[Range[2, 200] ], (p = #; AllTrue[Range[(p - 1)/2], s[p, #] >= 0 &]) &] (* Jean-François Alcover, Mar 04 2016 *)

isok(p) = if (isprime(p) && (p>2), for (u=1, (p-1)/2, if (sum(j=1, u, kronecker(j, p)) < 0, return(0));); return(1);); \\ Michel Marcus, Sep 20 2022

def A080114_list(n) :
    a = []
    for i in (2..n) :
        s = 0
        p = nth_prime(i)
        for j in (1..(p-1)/2) :
            s += legendre_symbol(j, p)
            if s < 0 : break
        if s >= 0 : a.append(p)
    return a
A080114_list(200) # Peter Luschny, Aug 08 2012

A080117 Binary encoding of quadratic residue set formed for n-th prime, coerced to "complementarily symmetric binary sequence" with A080261 if the prime is of the form 4k+1.

Original entry on oeis.org

2, 10, 52, 738, 2866, 53620, 162438, 4023888, 166243974, 921787428, 48034443442, 935251508324, 2558696229078, 68055676507664, 2655011787909270, 210067141980993186, 831463106366605026, 42882922858578320598

Offset: 2

Antti Karttunen, Feb 11 2003

nonn

Cf. A080118, A080146, A080148.

with(numtheory,ithprime); A080117 := proc(n) local c,p; p := ithprime(n); c := A055094(p); if(3 = (p mod 4)) then RETURN(c); else RETURN(A080261(c)); fi; end;

A055094[n_] := With[{rr = Table[Mod[k^2, n], {k, 1, n-1}] // Union}, Boole[ MemberQ[rr, #]] & /@ Range[n-1]] // FromDigits[#, 2]&;
A080261[n_] := Module[{bb = IntegerDigits[n, 2]}, lg = Length[bb]; Do[ bb[[i]] = 1 - bb[[i]], {i, lg, lg - Floor[lg/2] + 1, -1}]; FromDigits[ bb, 2]];
a[n_] := Module[{c, p = Prime[n]}, c = A055094[p]; If[Mod[p, 4] == 3, c, A080261[c]]]; Table[a[n], {n, 2, 20}] (* Jean-François Alcover, Mar 05 2016, adapted from Maple *)

# uses[A080261]
def A080117(n) :
    p = nth_prime(n)
    c = A055094(p)
    return c if 3 == p%4 else A080261(c)
[A080117(n) for n in (2..19)] # Peter Luschny, Aug 09 2012

a(A080148(n)) = A080146(A080148(n))

A055088 Triangle of generalized Legendre symbols L(a/b) read by rows, with 1's for quadratic residues and 0's for quadratic non-residues.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0

Offset: 1

Antti Karttunen, Apr 18 2000

L(a/b) is 1 if an integer c exists such that c^2 is congruent to a (mod b) and 0 otherwise.

For every prime of the form 4k+1 (A002144) the row is symmetric and for every prime of the form 4k+3 (A002145) the row is "complementarily symmetric".

			The tenth row gives the quadratic residues and non-residues of 11 (see A011582) and the twelfth row gives the same information for 13 (A011583), with -1's replaced by zeros.
.
Triangle starts:
  [ 1] [1]
  [ 2] [1, 0]
  [ 3] [1, 0, 0]
  [ 4] [1, 0, 0, 1]
  [ 5] [1, 0, 1, 1, 0]
  [ 6] [1, 1, 0, 1, 0, 0]
  [ 7] [1, 0, 0, 1, 0, 0, 0]
  [ 8] [1, 0, 0, 1, 0, 0, 1, 0]
  [ 9] [1, 0, 0, 1, 1, 1, 0, 0, 1]
  [10] [1, 0, 1, 1, 1, 0, 0, 0, 1, 0]
  [11] [1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0]
  [12] [1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1]

Cf. A002144, A002145, A011582, A011583.

Each row interpreted as a binary number: A055094.

# See A054431 for one_or_zero and trinv.
with(numtheory,quadres); quadres_0_1_array := (n) -> one_or_zero(quadres((n-((trinv(n-1)*(trinv(n-1)-1))/2)), (trinv(n-1)+1)));

row[n_] := With[{rr = Table[Mod[k^2, n + 1], {k, 1, n}] // Union}, Boole[ MemberQ[rr, #]]& /@ Range[n]];
Array[row, 14] // Flatten (* Jean-François Alcover, Mar 05 2016 *)

def A055088_row(n) :
    Q = quadratic_residues(n+1)
    return [int(i in Q) for i in (1..n)]
for n in (1..14) : print(A055088_row(n))  # Peter Luschny, Aug 08 2012

A080120 Dyck path encodings of Legendre's candelabras formed for primes in A080114. (I.e., symmetric rooted plane trees constructed from their quadratic residue sets.)

Original entry on oeis.org

10, 1010, 110100, 1011100010, 101100110010, 1111010110011001010000, 110110111100010101110000100100, 101100101111000100110111000010110010, 1111011110010101110010011011000101011000010000

Offset: 1

Antti Karttunen, Feb 11 2003

nonn

For the 2nd, 5th and 8th term of the sequence, the quadratic residue set of the corresponding prime (5,13,37, of the form 4k+1) has been converted from symmetric to complementarily symmetric as 1001->1010, 101100001101->101100110010, 101100101111000100001000111101001101->101100101111000100110111000010110010, for the others (of the form 4k+3), it is the quadratic residue set encoded as in A055094 (with +1 mapped to 1 and -1 to 0).

Antti Karttunen, Illustration of initial terms

Same sequence in decimal: A080118. Cf. A080114.

A080120 := n -> convert(A080118(n),binary);

a(n) = A063171(A080119(n)).

A055131 Those composite s for which A055095[s] = 2.

Original entry on oeis.org

15, 39, 51, 87, 111, 123, 159, 183, 219, 267, 291, 303, 327, 339, 411, 447, 471, 519, 543, 579, 591, 687, 699, 723, 771, 807, 831, 843, 879, 939, 951, 1011, 1047, 1059, 1119, 1167, 1191, 1203, 1227, 1263, 1299, 1347, 1371, 1383, 1527, 1563, 1623, 1671

Offset: 0

Antti Karttunen, Apr 04 2000

nonn

find_A055095_is_2_composites := proc(upto_n) local j,a; a := []; for j from 1 to upto_n do if(-1 = (j - wt(GrayCode(qrs2bincode((2*j)+1))))) then if(not isprime((2*j)+1)) then a := [op(a),((2*j)+1)]; fi; fi; od; RETURN(a); end;

A005811[n_] := Length[Length /@ Split[IntegerDigits[n, 2]]];
A055094[n_] := With[{rr = Table[Mod[k^2, n], {k, 1, n-1}] // Union}, Boole[MemberQ[rr, #]] & /@ Range[n-1]] // FromDigits[#, 2]&;
A055095[1] = 0; A055095[n_] := 2*A005811[A055094[n]] - (n-1);
A055131 = Position[Array[A055095, 2000], 2] // Flatten // Select[#, CompositeQ]& (* Jean-François Alcover, Mar 06 2016 *)

a(n) = 3*((4*A005098[n])+1) = 3*A002144[n] ??? (Conjecture, not yet proved)

More terms from James Sellers, Apr 21 2000

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.

Original entry on oeis.org

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

Adnan Baysal, Dec 26 2016

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

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

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

Cf. A055094, A080117, A080146, A096008.

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

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

cp's OEIS Frontend

A055095 a(n) = 2*A000120(A003188(A055094(n))) - (n-1) = 2*A005811(A055094(n)) - (n-1).

Views

Author

Keywords

Comments

References

Links

Programs

Maple

Mathematica

Python

Formula

A080146 Binary encoding of quadratic residue set for each prime. a(n) = A055094(A000040(n)).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A095102 Odd primes p for which all sums Sum_{i=1..u} L(i/p) (with u ranging from 1 to (p-1)) are nonnegative, where L(i/p) is Legendre symbol of i and p, defined to be 1 if i is a quadratic residue (mod p) and -1 if i is a quadratic non-residue (mod p).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A080114 Odd primes p for which all sums Sum_{j=1..u} L(j/p) (with u ranging from 1 to (p-1)/2) are nonnegative, where L(j/p) is Legendre symbol of j and p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

A080117 Binary encoding of quadratic residue set formed for n-th prime, coerced to "complementarily symmetric binary sequence" with A080261 if the prime is of the form 4k+1.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A055088 Triangle of generalized Legendre symbols L(a/b) read by rows, with 1's for quadratic residues and 0's for quadratic non-residues.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Sage

A080120 Dyck path encodings of Legendre's candelabras formed for primes in A080114. (I.e., symmetric rooted plane trees constructed from their quadratic residue sets.)

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A055131 Those composite s for which A055095[s] = 2.

Views

A055095 a(n) = 2A000120(A003188(A055094(n))) - (n-1) = 2A005811(A055094(n)) - (n-1).