Thanks. We already have script ~addons/math/misc/legendre.ijs. Should this be added to that directory?
On 5 January 2016 at 02:50, 'Jon Hough' via Programming < [email protected]> wrote: > In case anyone is interested, I wrote a verb to calculate the Jacobi > symbol for positive integers n,m (n/m), although my J syntax is pretty > awkward: > > NB. Jacobi symbol (x/y) > NB. x is numerator (positive int, or zero) > NB. y is denominator (positive int) > jac=: 4 : 0 > numer=. x > denom=. y > jacobi=. 1 > if. numer = 0 do. > 0 > return. > end. > if. numer < 0 do. > numer=. numer * _1 > > end. > > while. 0 < numer do. > while. 0 = 2 | numer do. > numer=. numer % 2 > if. 3 5 e.~ 8 | denom do. > jacobi=. jacobi * _1 > end. > end. > if. numer = 1 do. > jacobi > return. > end. > > if. 3 3 -: 4 | numer , denom do. > jacobi=. jacobi * _1 > end. > tempy=. numer | denom > denom=. numer > numer=. tempy > end. > > jacobi > > ) > > e.g. find the x values that give jacobi symbol of 1, when y = 23, and x is > in {0, ..., 22} > > >:I.-:>:}. (i. 23) jac"(0 0) 23 NB. get rid of zero) > 1 2 3 4 6 8 9 12 13 16 18 > > The jacobi symbol's meaning is weaker than I remembered. If it gives 1, > that doesn't necessarily mean that x is a quadratic residue of y (unless y > is prime). > e.g. > (i.16) jac"(0 0) 16 > 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 > because (a/16) = (a/2)*(a/2)*(a/2)*(a/2), so any -1's cancel each other > out. > > > -------------------------------------------- > On Tue, 1/5/16, 'Pascal Jasmin' via Programming <[email protected]> > wrote: > > Subject: Re: [Jprogramming] Prime-based selection oddity > To: "[email protected]" <[email protected]> > Date: Tuesday, January 5, 2016, 12:24 PM > > Also, > > all odd numbers mod 16 are 1 3 5 7 9 11 13 15, > and squared have 1 of 2 results. > > > #/.~ 16 | *: 3 + 2 * > i.2000 > 1000 1000 > > > similarly to odd numbers mod > 10 squared are 1 and 9 and 5. > > Its a bit interesting that there are slightly > more 9s than 1s and it increases somewhat irregularly in > each range. > > > #/.~ 16 | *: p: >: i.1000 > 506 494 > > > #/.~ 16 | *: p: >: i.2000 > 1005 995 > > #/.~ 16 | *: p: >: > i.3000 > 1508 1492 > #/.~ 16 > | *: p: >: i.4000 > 2018 1982 > #/.~ 16 | *: p: >: i.5000 > 2522 2478 > > > ----- Original Message ----- > From: Devon McCormick <[email protected]> > To: J-programming forum <[email protected]> > Sent: Monday, January 4, 2016 9:13 PM > Subject: [Jprogramming] Prime-based selection > oddity > > Recently I was > looking at how I might generate something that look like > an > encryption key and noticed this > oddity: > > #val=. > '0123456789ABCDEF' > 16 > val{~(#val)|2^~p:i.128 > > > 49919919191919199991119119199119199199199911919199111911919199911991991119919911991119119191199191999991919111191911919991999991 > > frtab > val{~(#val)|2^~p:i.128 > +--+-+ > |1 |4| > +--+-+ > |68|9| > +--+-+ > |59|1| > +--+-+ > > Where "frtab" is a > frequency table generator: > > frtab=: 3 : 0 > cts=. #&>y</.y > NB. # unique items... > if. > -.isNum y do. NB. Special case enclosed, > text mat, text vec, > if. > (L.=0:) y do. (<"0 cts),.<"0 ~.y else. > if. 2=#$y do. > (<"0 cts),.<"1 ~.y else. (<"0 > cts),.<"0 ~.y end. > > end. > else. > cts,.~.y end. NB. and simple numeric vec. > NB.EG (1 2 3 2 1,. 11 22 33 222 99) -: frtab 11 > 22 22 33 33 33 222 222 99 > ) > > Any obvious reason why the 16| > of squares of primes should return only "1" > and "9" for this sample? > > > -- > > Devon McCormick, CFA > > Quantitative Consultant > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
