A268829 -id:A268829 - cp's OEIS frontend

A112046 a(n) = the least k >= 1 for which the Jacobi symbol J(k,2n+1) is not +1 (thus is either 0 or -1).

2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 5, 5, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 5, 7, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 7, 5, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 5, 5, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 7, 11, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 5, 5, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 5, 13, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 7, 5, 2, 2, 3, 3, 2, 2

Offset: 1

Antti Karttunen, Aug 27 2005

nonn

If we instead list the least k >= 1, for which Jacobi symbol J(k,2n+1) is 0, we get A090368.

It is easy to see that every term is prime. Because the Jacobi symbol is multiplicative as J(ab,m) = J(a,m)*J(b,m) and if for every index i>=1 and < x, J(i,m)=1, then if J(x,m) is 0 or -1, x cannot be composite (say y*z, with both y and z less than x), as then either J(y,m) or J(z,m) would be non-one, which contradicts our assumption that x is the first index where non-one value appears. Thus x must be prime.

Indranil Ghosh and A.H.M. Smeets, Table of n, a(n) for n = 1..20000 (first 1000 terms from Indranil Ghosh)

One more than A112050.
Bisections: A112047, A112048, and their difference: A112053.
Cf. A000040, A053760, A053761, A090368, A112049, A112060, A112070, A268829, A286465, A286466.

A112046(n) = for(i=1, (2*n), if((kronecker(i, (n+n+1)) < 1), return(i))); \\ Antti Karttunen, May 26 2017

from sympy import jacobi_symbol as J
def a(n):
    i=1
    while True:
        if J(i, 2*n + 1)!=1: return i
        else: i+=1
print([a(n) for n in range(1, 103)]) # Indranil Ghosh, May 11 2017

a(n) = A112050(n) + 1 = A000040(A112049(n)).

A112049 a(n) = position of A112046(n) in A000040.

Original entry on oeis.org

1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 3, 4, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 4, 3, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 4, 5, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 3, 6, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 4, 3, 1, 1, 2, 2, 1, 1

Offset: 1

Antti Karttunen, Aug 27 2005

nonn

A112051 gives the first positions of distinct new values in this sequence, that seem also to be the positions of the first occurrence of each n, and thus the positions of the records. Compare also to A084921. - Antti Karttunen, May 26 2017

Indranil Ghosh (terms 1..1000) & Antti Karttunen, Table of n, a(n) for n = 1..32768

Cf. A049084, A112046, A112051, A112060, A165471, A268829, A286465, A286466.

Cf. A286579 (ordinal transform).

a112046[n_]:=Block[{i=1},While[JacobiSymbol[i, 2n + 1]==1, i++]; i];a049084[n_]:=If[PrimeQ[n], PrimePi[n], 0]; Table[a049084[a112046[n]], {n, 102}] (* Indranil Ghosh, May 11 2017 *)

A112049(n) = for(i=1, (2*n), if((kronecker(i, (n+n+1)) < 1), return(primepi(i)))); \\ Antti Karttunen, May 26 2017

from sympy import jacobi_symbol as J, isprime, primepi
def a049084(n):
    return primepi(n) if isprime(n) else 0
def a112046(n):
    i=1
    while True:
        if J(i, 2*n + 1)!=1: return i
        else: i+=1
def a(n): return a049084(a112046(n))
print([a(n) for n in range(1, 103)]) # Indranil Ghosh, May 11 2017

a(n) = A049084(A112046(n)).

Unnecessary fallback-clause removed from the name by Antti Karttunen, May 26 2017

A269158 Square array A(row,col) = F(row,(2*col)-1), where F(0,q) = F(1,q) = 0, F(2p,q) = F(p,q) XOR A003188(q), F(2p+1,q) = F(q mod 2p+1, 2p+1) XOR (2p+1 AND q). Array is read by descending antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 0, 7, 3, 0, 0, 4, 3, 0, 1, 0, 13, 3, 0, 2, 0, 0, 14, 1, 0, 5, 1, 1, 0, 11, 1, 0, 2, 4, 0, 1, 0, 8, 1, 0, 1, 7, 7, 2, 1, 0, 25, 3, 0, 1, 12, 7, 7, 0, 0, 0, 26, 3, 0, 6, 15, 5, 4, 0, 0, 1, 0, 31, 3, 0, 5, 10, 3, 13, 4, 2, 2, 1, 0, 28, 1, 0, 6, 11, 2, 14, 9, 6, 0, 3, 1, 0, 21, 1, 0, 1, 26, 7, 11, 4, 12, 0, 3, 0, 0

Offset: 1

Antti Karttunen, Feb 20 2016

The array gives the values of bivariate function F(p,q) which is well-defined only when q is odd, thus while here its argument p obtains all integer values from 1 onward, argument q gets only odd numbers 1, 3, 5, 7, 9, ... as its values.

Any row n occurs also as row (4^k * n), for all k >= 0.

			The top left [1 .. 16] x [1 .. 25] section of the array:
0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
1,  2,  7,  4, 13, 14, 11,  8, 25, 26, 31, 28, 21, 22, 19, 16
1,  3,  3,  3,  1,  1,  1,  3,  3,  3,  1,  1,  1,  3,  3,  3
0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
1,  2,  5,  2,  1,  1,  6,  5,  6,  1,  5,  6,  1,  6,  5,  5
0,  1,  4,  7, 12, 15, 10, 11, 26, 25, 30, 29, 20, 21, 16, 19
1,  0,  7,  7,  5,  3,  2,  7,  2,  1,  5,  3,  1,  4,  5,  4
1,  2,  7,  4, 13, 14, 11,  8, 25, 26, 31, 28, 21, 22, 19, 16
1,  0,  0,  4,  9,  4,  9,  5, 12,  1,  0,  0, 12,  9,  4,  9
0,  0,  2,  6, 12, 15, 13, 13, 31, 27, 26, 26, 20, 16, 22, 21
1,  2,  0,  0, 13, 11,  7, 11, 14, 13, 14,  3,  8, 10, 10, 15
1,  3,  3,  3,  1,  1,  1,  3,  3,  3,  1,  1,  1,  3,  3,  3
1,  0,  3,  7,  0, 14, 13,  6,  1, 11, 14,  8,  8,  9, 12, 11
0,  2,  0,  3,  8, 13,  9, 15, 27, 27, 26, 31, 20, 18, 22, 20
1,  0,  0,  0, 12,  0, 11, 15,  9,  3, 14, 15,  4,  8,  2, 15
0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
1,  2,  7,  3, 13, 15,  0,  8, 17,  8, 17, 11,  8, 14, 18, 10
0,  2,  7,  0,  4, 10,  2, 13, 21, 27, 31, 28, 25, 31, 23, 25
1,  0,  0,  2,  0, 14, 10,  0, 25, 19, 11, 19,  8,  9, 10, 16
1,  2,  5,  2,  1,  1,  6,  5,  6,  1,  5,  6,  1,  6,  5,  5
1,  0,  0,  0,  1, 15, 11, 11,  0, 26, 21, 10, 17, 15, 10, 15
0,  0,  7,  4,  0,  5, 12,  3, 23, 23, 17, 31, 29, 28, 25, 31
1,  2,  3,  4,  1,  0, 13,  8, 26,  0, 31, 23, 13, 19,  8, 11
0,  1,  4,  7, 12, 15, 10, 11, 26, 25, 30, 29, 20, 21, 16, 19
1,  0,  0,  0,  5,  1,  1, 13, 25, 25,  0, 28, 25, 12, 25, 13

Antti Karttunen, Table of n, a(n) for n = 1..32896; the first 256 antidiagonals of the array

Transpose: A269159.
Column 1: Seems to be 0 followed by A039982.
Column 32769: A268819.
Cf. A065621 (occurs as row 2, row 8, and in general, as any row 2^(2n+1) for n >= 0. Seems to be also present as a slanted diagonal F(2n+1,2n-1).)
Cf. A268816 (row 6, row 24, etc.).
Cf. arrays A268829 and A268728 (variants), and also A268931.
Cf. A003188, A003987, A004198.

F[p_, q_] := F[p, q] = Which[p <= 1, 0, p > 1 && OddQ[p], F[Mod[q, p], p] ~BitXor~ BitAnd[p, q], True, F[p/2, q] ~BitXor~ BitXor[q, Floor[q/2]]];
A[n_, k_] := F[n, 2 k - 1];
Table[A[n - k, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 11 2017 *)

(define (A269158 n) (A269158auxbi (A002260 n) (+ -1 (* 2 (A004736 n)))))
;; A269158auxbi can be implemented either as a tail-recursive loop:
(define (A269158auxbi p q) (if (not (odd? q)) (error "A269158bi: the second argument should be odd: " p q) (let loop ((p p) (q q) (s 0)) (cond ((<= p 1) s) ((odd? p) (loop (modulo q p) p (A003987bi s (A004198bi p q)))) (else (loop (/ p 2) q (A003987bi s (A003987bi q (/ (- q 1) 2)))))))))
;; Or a recurrence (reflecting the given recursive formula):
(define (A269158auxbi p q) (cond ((<= p 1) 0) ((even? p) (A003987bi (A269158auxbi (/ p 2) q) (A003188 q))) (else (A003987bi (A269158auxbi (modulo q p) p) (A004198bi p q)))))

A(row,col) = F(row,(2*col)-1), where function F is defined as: If p <= 1, F(p,q) = 0, otherwise if p is an odd number > 1, F(p,q) = F(q mod p, p) XOR (p AND q), otherwise [when p is an even number] F(p,q) = F(p/2,q) XOR A003188(q).

A268728 Square array A(row,col) = B(row,(2*col)-1), where B(p,2q-1) = 0 if gcd(p,2q-1) > 1, and A269158(p,q) otherwise. Array is read by descending antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 0, 7, 0, 0, 0, 4, 3, 0, 1, 0, 13, 3, 0, 2, 0, 0, 14, 0, 0, 0, 0, 1, 0, 11, 1, 0, 2, 4, 0, 1, 0, 8, 1, 0, 1, 7, 7, 2, 1, 0, 25, 0, 0, 1, 0, 0, 7, 0, 0, 0, 26, 3, 0, 6, 15, 5, 4, 0, 0, 1, 0, 31, 3, 0, 0, 10, 3, 13, 4, 0, 2, 1, 0, 28, 0, 0, 6, 0, 2, 14, 0, 6, 0, 0, 1, 0, 21, 1, 0, 1, 26, 7, 11, 4, 12, 0, 3, 0, 0

Offset: 1

Antti Karttunen, Feb 19 2016

The array gives the values of bivariate function B(p,q) which is well-defined only when q is odd, thus while here its argument p obtains all integer values from 1 onward, argument q gets only odd numbers 1, 3, 5, 7, 9, ... as its values.

Any row n occurs also as row (4^k * n), for all k >= 0.

			The top left [1 .. 16] x [1 .. 25] section of the array:
  0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
  1, 2, 7, 4, 13, 14, 11,  8, 25, 26, 31, 28, 21, 22, 19, 16
  1, 0, 3, 3,  0,  1,  1,  0,  3,  3,  0,  1,  1,  0,  3,  3
  0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
  1, 2, 0, 2,  1,  1,  6,  0,  6,  1,  5,  6,  0,  6,  5,  5
  0, 0, 4, 7,  0, 15, 10,  0, 26, 25,  0, 29, 20,  0, 16, 19
  1, 0, 7, 0,  5,  3,  2,  7,  2,  1,  0,  3,  1,  4,  5,  4
  1, 2, 7, 4, 13, 14, 11,  8, 25, 26, 31, 28, 21, 22, 19, 16
  1, 0, 0, 4,  0,  4,  9,  0, 12,  1,  0,  0, 12,  0,  4,  9
  0, 0, 0, 6, 12, 15, 13,  0, 31, 27, 26, 26,  0, 16, 22, 21
  1, 2, 0, 0, 13,  0,  7, 11, 14, 13, 14,  3,  8, 10, 10, 15
  1, 0, 3, 3,  0,  1,  1,  0,  3,  3,  0,  1,  1,  0,  3,  3
  1, 0, 3, 7,  0, 14,  0,  6,  1, 11, 14,  8,  8,  9, 12, 11
  0, 2, 0, 0,  8, 13,  9, 15, 27, 27,  0, 31, 20, 18, 22, 20
  1, 0, 0, 0,  0,  0, 11,  0,  9,  3,  0, 15,  0,  0,  2, 15
  0, 0, 0, 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
  1, 2, 7, 3, 13, 15,  0,  8,  0,  8, 17, 11,  8, 14, 18, 10
  0, 0, 7, 0,  0, 10,  2,  0, 21, 27,  0, 28, 25,  0, 23, 25
  1, 0, 0, 2,  0, 14, 10,  0, 25,  0, 11, 19,  8,  9, 10, 16
  1, 2, 0, 2,  1,  1,  6,  0,  6,  1,  5,  6,  0,  6,  5,  5
  1, 0, 0, 0,  0, 15, 11,  0,  0, 26,  0, 10, 17,  0, 10, 15
  0, 0, 7, 4,  0,  0, 12,  3, 23, 23, 17, 31, 29, 28, 25, 31
  1, 2, 3, 4,  1,  0, 13,  8, 26,  0, 31,  0, 13, 19,  8, 11
  0, 0, 4, 7,  0, 15, 10,  0, 26, 25,  0, 29, 20,  0, 16, 19
  1, 0, 0, 0,  5,  1,  1,  0, 25, 25,  0, 28,  0, 12, 25, 13

Antti Karttunen, Table of n, a(n) for n = 1..32896; the first 256 antidiagonals of the array

Transpose: A268729.
Column 1: Seems to be 0 followed by A039982.
Cf. A065621 (occurs as row 2, row 8, and in general, as any row 2^(2n+1) for n >= 0).
Cf. A268829, A269158 (variants).
Cf. A003188, A003987, A004198.

(define (A268728 n) (A268728bi (A002260 n) (+ -1 (* 2 (A004736 n)))))
(define (A268728bi p q) (if (not (odd? q)) (error "A268728bi: the second argument should be odd: " p q) (let loop ((p p) (q q) (s 0)) (cond ((zero? p) 0) ((= 1 p) s) ((odd? p) (loop (modulo q p) p (A003987bi s (A004198bi p q)))) (else (loop (/ p 2) q (A003987bi s (A003987bi q (/ (- q 1) 2)))))))))
;; Alternative implementation using the definition given in A269158:
(define (A268728 n) (let ((p (A002260 n)) (q (+ -1 (* 2 (A004736 n))))) (if (< 1 (gcd p q)) 0 (A269158auxbi p q))))

A(row,col) = B(row,(2*col)-1), where function B(p,q) [only odd values allowed for q] is defined as: If gcd(p,q) > 1, B(p,q) = 0, otherwise B(p,q) = F(p,q) = A269158(p,(q+1)/2), function F defined as in A269158.

A053761 Least positive integer k for which the Jacobi symbol (k|2n-1) is less than 1, where 2n-1 is a nonsquare; a(n)=0 if 2*n-1 is a square.

Original entry on oeis.org

0, 2, 2, 3, 0, 2, 2, 3, 3, 2, 2, 5, 0, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 5, 0, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 7, 5, 2, 2, 3, 0, 2, 2, 3, 3, 2, 2, 5, 5, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 7, 0, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 5, 5, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 5, 0, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 7, 5, 2, 2, 3

Offset: 1

Steven Finch, Apr 05 2000

nonn

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 443-448.
Paulo Ribenboim, The New Book of Prime Number Records, 3rd ed., Springer-Verlag 1996; Math. Rev. 96k:11112.

Antti Karttunen, Table of n, a(n) for n = 1..10000
R. Baillie and S. S. Wagstaff, Lucas pseudoprimes, Math. Comp. 35 (1980) 1391-1417; Math. Rev. 81j:10005
Steven R. Finch, Quadratic Residues [Broken link]
Steven R. Finch, Quadratic Residues [From the Wayback machine]

Cf. A010052, A053760, A112046, A112049, A268829.

A053761 := proc(n) if issqr(2*n-1) then return 0 ; else for k from 1 do if numtheory[jacobi](k,2*n-1) < 1 then return k; end if; end do: end if; end proc: seq(A053761(n),n=1..100) ; # R. J. Mathar, Aug 08 2010

a[n_] := If[IntegerQ[Sqrt[2*n - 1]], Return[0], For[ k = 1, True, k++, If[ JacobiSymbol[k, 2*n - 1] < 1 , Return[k]]]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jun 20 2013, after R. J. Mathar *)

A112046(n) = for(i=1,(2*n),if((kronecker(i,(n+n+1)) < 1),return(i)));
A053761(n) = if(issquare((2*n)-1),0,A112046(n-1));
for(n=1, 10000, write("b053761.txt", n, " ", A053761(n))); \\ Antti Karttunen, May 10 2017

(define (A053761 n) (if (= 1 n) 0 (* (- 1 (A010052 (+ n n -1))) (A112046 (- n 1))))) ;; Antti Karttunen, May 10 2017

a(1) = 0; for n > 1, a(n) = (1-A010052((2*n)-1)) * A112046(n-1). - Antti Karttunen, May 10 2017

More terms from R. J. Mathar, Aug 08 2010

cp's OEIS Frontend

A112046 a(n) = the least k >= 1 for which the Jacobi symbol J(k,2n+1) is not +1 (thus is either 0 or -1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Formula

A112049 a(n) = position of A112046(n) in A000040.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A269158 Square array A(row,col) = F(row,(2*col)-1), where F(0,q) = F(1,q) = 0, F(2p,q) = F(p,q) XOR A003188(q), F(2p+1,q) = F(q mod 2p+1, 2p+1) XOR (2p+1 AND q). Array is read by descending antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A268728 Square array A(row,col) = B(row,(2*col)-1), where B(p,2q-1) = 0 if gcd(p,2q-1) > 1, and A269158(p,q) otherwise. Array is read by descending antidiagonals as A(1,1), A(1,2), A(2,1), A(1,3), A(2,2), A(3,1), ...

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula

A053761 Least positive integer k for which the Jacobi symbol (k|2*n-1) is less than 1, where 2*n-1 is a nonsquare; a(n)=0 if 2*n-1 is a square.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Scheme

Formula

Extensions

A053761 Least positive integer k for which the Jacobi symbol (k|2n-1) is less than 1, where 2n-1 is a nonsquare; a(n)=0 if 2*n-1 is a square.