A095102 -id:A095102 - cp's OEIS frontend

A095092 Number of 4k+3 primes whose Legendre-vector is a Dyck-path (A095102) in range ]2^n,2^(n+1)].

1, 1, 1, 2, 2, 4, 7, 10, 16, 30, 51, 88, 153, 277, 509, 905, 1660, 3079, 5535, 10234, 19053

Offset: 1

Antti Karttunen, Jun 01 2004

A. Karttunen and J. Moyer, C-program for computing the initial terms of this sequence
Index entries for sequences related to occurrences of various subsets of primes in range ]2^n,2^(n+1)]

is(m) = {if(!isprime(m), return(0)); my(s=0); for(i=1, m-1, if((s+=kronecker(i, m))<0, return(0))); 1; }
a(n) = {my(c=0); forstep(m=2^n+3*(n>1), 2^(n+1), 4, c+=is(m)); c; } \\ Jinyuan Wang, Jul 20 2020

a(n) = A095008(n) - A095093(n).

A095272 a(n) = (A095102(n)-3)/4.

Original entry on oeis.org

0, 1, 2, 5, 7, 11, 14, 17, 19, 20, 25, 32, 37, 41, 47, 49, 59, 62, 65, 67, 77, 89, 95, 104, 107, 109, 119, 125, 140, 149, 151, 161, 164, 179, 185, 187, 209, 215, 221, 227, 229, 242, 245, 247, 257, 259, 265, 272, 275, 287, 305, 307, 319, 329, 349

Offset: 1

Antti Karttunen, Jun 01 2004

nonn

A. Karttunen and J. Moyer, C-program for computing the initial terms of this sequence

Complement of A095273 in A095278, subset of A095274.

A165477 Partial sums of A165476.

Original entry on oeis.org

0, 1, 2, 1, 2, 3, 2, 3, 4, 5, 6, 7, 6, 5, 6, 5, 6, 7, 8, 7, 8, 7, 8, 9, 8, 9, 8, 7, 8, 9, 8, 9, 10, 9, 10, 11, 12, 11, 10, 11, 12, 11, 10, 11, 12, 13, 14, 15, 14, 15, 16, 15, 14, 13, 12, 13, 14, 15, 16, 17, 16, 15, 16, 17, 18, 17, 16, 15, 16, 15, 16, 15, 16, 17, 16, 15, 14, 15, 16, 15

Offset: 0

Antti Karttunen, Sep 21 2009

Period 131071. There are no negative values as 131071 is one of the primes in A095102.

See row 12251 in triangle A226518, A000040(12251) = 131071. - Reinhard Zumkeller, Feb 02 2014

A. Karttunen, Table of n, a(n) for n = 0..131071

A165487 gives the squared version. Positions of zeros: A165478. See also A165479. Compare also to A165472, A165482.

A095100 Integers m of the form 4k+3 for which all sums Sum_{i=1..u} J(i/m) (with u ranging from 1 to (m-1)) are nonnegative, where J(i/m) is Jacobi symbol of i and m.

Original entry on oeis.org

3, 7, 11, 15, 23, 27, 31, 35, 39, 47, 55, 59, 63, 71, 75, 79, 83, 87, 95, 103, 111, 119, 131, 135, 143, 151, 159, 167, 171, 175, 183, 191, 199, 215, 231, 239, 243, 251, 255, 263, 271, 279, 287, 295, 299, 303, 311, 319, 327, 335, 343, 351, 359, 363

Offset: 1

Antti Karttunen, Jun 01 2004

nonn

Integers whose Jacobi-vector forms a valid Motzkin-path.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Antti Karttunen and J. Moyer, C-program for computing the initial terms of this sequence

Subset of A095102. Complement of A095101 in A004767.

Cf. A095090.

isMotzkin[n_, k_] := Module[{s = 0, r = True}, Do[s += JacobiSymbol[i, n]; If[s < 0, r = False; Break[]], {i, 1, k}]; r]; A095100[n_] := Select[4*Range[0, n+1]+3, isMotzkin[#, Quotient[#, 2]] &]; A095100[90] (* Jean-François Alcover, Oct 08 2013, translated from Sage *)

isok(m) = {if(m%4<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 is_Motzkin(n, k):
    s = 0
    for i in range(1, k + 1) :
        s += jacobi_symbol(i, n)
        if s < 0: return False
    return True
def A095100_list(n):
    return [m for m in range(3, n + 1, 4) if is_Motzkin(m, m // 2)]
A095100_list(363) # Peter Luschny, Aug 08 2012

a(n) = 4*A095274(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

A095103 4k+3 primes whose Legendre-vector is not valid Dyck-path.

Original entry on oeis.org

19, 43, 67, 107, 127, 139, 163, 179, 211, 223, 227, 283, 307, 331, 347, 367, 379, 443, 463, 467, 487, 491, 499, 523, 547, 571, 587, 619, 631, 643, 683, 691, 727, 739, 787, 811, 823, 827, 859, 883, 907, 947, 967, 1019, 1051, 1087, 1123, 1163

Offset: 1

Antti Karttunen, Jun 01 2004

nonn

A. Karttunen and J. Moyer, C-program for computing the initial terms of this sequence

Intersection of A000040 and A095101. Complement of A095102 in A002145.

Cf. A095093, A095108 (diving indices).

L = {}; Do[p = Prime[k]; If[Mod[p, 4] == 3 && Min[Table[Sum[JacobiSymbol[n, p], {n, 0, m}], {m, 0, p - 1}]] < 0, L = Append[L, p]], {k, 1, 192}]; L (* From Jonathan Sondow, Oct 25 2011 *)

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

def A095103_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(n+1)[3::4])
    return filter(lambda m: not is_Motzkin(m, m//2), P)
A095103_list(1163) # Peter Luschny, Aug 08 2012

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

A165576 Partial sums of A165574.

Original entry on oeis.org

0, 1, 2, 3, 4, 3, 4, 3, 4, 5, 4, 5, 6, 7, 6, 5, 6, 7, 8, 7, 6, 5, 6, 7, 8, 9, 10, 11, 10, 9, 8, 9, 10, 11, 12, 13, 14, 15, 14, 15, 14, 13, 12, 13, 14, 13, 14, 13, 14, 15, 16, 17, 18, 17, 18, 17, 16, 15, 14, 13, 12, 13, 14, 13, 14, 13, 14, 13, 14, 15, 16, 15, 16, 15, 16, 17, 16, 15

Offset: 0

Antti Karttunen, Sep 22 2009

nonn

Period 263. There are no negative values as 263 is one of the primes in A095102.

A. Karttunen, Table of n, a(n) for n = 0..59701

Similar sequences: A165575-A165579, A165472, A165477, A165482, A165582, A165587, A165592, A165597.

Accumulate[JacobiSymbol[Range[0,90],263]] (* Harvey P. Dale, Sep 01 2021 *)

A165580 Primes of the form 4n+3 for which Sum_{i=1..u} J(i,4n+3) is never zero for any u in range [1,(2n+1)], where J(i,m) is the Jacobi symbol.

Original entry on oeis.org

3, 7, 23, 31, 47, 71, 79, 151, 167, 191, 199, 239, 263, 271, 311, 359, 383, 431, 439, 479, 503, 599, 647, 719, 743, 751, 839, 863, 887, 911, 919, 983, 991, 1031, 1039, 1151, 1223, 1231, 1279, 1319, 1399, 1439, 1471, 1487, 1511, 1559, 1583, 1759

Offset: 1

Antti Karttunen, Oct 06 2009

nonn

Setwise difference of A095102 and A165977. Also subset of A165469.

A165977 Primes of the form 4n+3 for which Sum_{i=1..u} J(i,4n+3) is never negative for any u in range [1,2n+1], but obtains at least one value zero, where J(i,m) is the Jacobi symbol.

Original entry on oeis.org

11, 59, 83, 103, 131, 251, 419, 563, 607, 659, 971, 1063, 1091, 1103, 1427, 1447, 1811, 1931, 1979, 2287, 2383, 2411, 2543, 2939, 3251, 3299, 3659, 3779, 3967, 4091, 4259, 4931, 5099, 5171, 5407, 5783, 5939, 6247, 6299, 6607, 6779, 6899

Offset: 1

Antti Karttunen, Oct 06 2009

nonn

Setwise difference of A095102 and A165580.

Subset of A165608.

Definition edited by Jonathan Sondow, Sep 26 2011

A177865 Polya-Vinogradov numbers: a(n) is the maximum over all k > 0 of |#(quadratic residues modulo p up to k) - #(quadratic nonresidues modulo p up to k)| where p is the n-th prime and n > 1.

Original entry on oeis.org

1, 1, 2, 3, 2, 2, 3, 5, 3, 6, 4, 4, 5, 8, 5, 9, 4, 6, 10, 5, 10, 9, 6, 6, 7, 10, 9, 6, 6, 10, 15, 7, 9, 7, 14, 8, 9, 18, 9, 15, 7, 19, 8, 11, 18, 12, 15, 15, 9, 10, 22, 8, 21, 10, 21, 11, 22, 14, 10, 13, 11, 14, 25, 11, 13, 14, 12, 17, 12, 12, 27, 19, 16, 15, 27, 12, 12, 12, 12, 27, 11, 30

Offset: 2

Jonathan Sondow, May 17 2010

In 1918 Polya and Vinogradov (independently) proved an upper bound for a(n) and Schur proved a lower bound:
sqrt(p)/2*pi < a(n) < sqrt(p)*log(p), where p is the n-th prime.
Named after the Hungarian mathematician George Pólya (1887-1985) and the Soviet mathematician Ivan Matveevich Vinogradov (1891-1983). - Amiram Eldar, Jun 22 2021

			The initial term is a(2) = 1 because the 2nd prime is 3 and L(1/3) = 1 and L(2/3) = -1, so |Sum_{i=1..k} L(i/3)| = 1 and 0 for k = 1 and 2, resp., and so max = 1.

I. M. Vinogradov, Über eine asymptotische Formel aus der Theorie der binaeren quadratischen Formen, J. Soc. Phys. Math. Univ. Permi, Vol. 1 (1918), pp. 18-28.
I. M. Vinogradov, Elements of Number Theory, 5th revised ed., Dover, 1954, p. 200.

PlanetMath, Polya Vinogradov Inequality.
G. Polya, Über die Verteilung der quadratischen Reste und Nichtreste, Goettingen Nachr. (1918), 21-29.
I. Schur, Einige Bemerkungen zu der vorstehenden Arbeit des Herrn G. Polya: Über die Verteilung der quadratischen Reste und Nichtreste, Goettingen Nachr. (1918), pp. 30-36.
Eric Weisstein's World of Mathematics, Polya-Vinogradov Inequality.
Wikipedia, Character Sum.
Wikipedia, Legendre symbol.
Wikipedia, Quadratic residue.

Cf. A055088 (Triangle of generalized Legendre symbols L(a/b), with 1's for quadratic residues and 0's for quadratic non-residues [replace the 0's with -1's]).

Cf. also A095102, A165580, A165977, A207291, A207292.

Table[Max[ Table[Abs[Sum[JacobiSymbol[i, Prime[n]], {i, 1, k}]], {k, 1, Prime[n] - 1}]], {n, 2, 100}]

a(n) = my(p=prime(n)); vecmax(vector(p-1, k, vecsum(vector(k, i, issquare(Mod(i, p)))) - vecsum(vector(k, i, !issquare(Mod(i, p)))))); \\ Michel Marcus, Mar 03 2023

a(n) = max_{01, and L(i/p) is the Legendre symbol.

cp's OEIS Frontend

A095092 Number of 4k+3 primes whose Legendre-vector is a Dyck-path (A095102) in range ]2^n,2^(n+1)].

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A095272 a(n) = (A095102(n)-3)/4.

Views

Author

Keywords

Links

Crossrefs

A165477 Partial sums of A165476.

Views

Author

Keywords

Comments

Links

Crossrefs

A095100 Integers m of the form 4k+3 for which all sums Sum_{i=1..u} J(i/m) (with u ranging from 1 to (m-1)) are nonnegative, where J(i/m) is Jacobi symbol of i and m.

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

A095103 4k+3 primes whose Legendre-vector is not valid Dyck-path.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A165576 Partial sums of A165574.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A165580 Primes of the form 4n+3 for which Sum_{i=1..u} J(i,4n+3) is never zero for any u in range [1,(2n+1)], where J(i,m) is the Jacobi symbol.

Views

Author

Keywords

Crossrefs

A165977 Primes of the form 4n+3 for which Sum_{i=1..u} J(i,4n+3) is never negative for any u in range [1,2n+1], but obtains at least one value zero, where J(i,m) is the Jacobi symbol.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A177865 Polya-Vinogradov numbers: a(n) is the maximum over all k > 0 of |#(quadratic residues modulo p up to k) - #(quadratic nonresidues modulo p up to k)| where p is the n-th prime and n > 1.