Author 
Message 

Ed H
Member
Joined: 30 Nov 2007 Posts: 138

Posted: 18 Jul 2009 03:20:42 pm Post subject: 


Evaluate the Jacobi symbol (A/N), where A is any integer and N is an odd positive integer. You don't need to Prompt for them, they're already there. Have the program return the answer in Ans.
This is a pretty interesting problem to program. I haven't spent much time on this; but so far I've got it in the 100120 byte range. 

Back to top 


ztrumpet
Active Member
Joined: 06 May 2009 Posts: 555

Posted: 18 Jul 2009 04:51:42 pm Post subject: 


Is 1, 0, or 1 all we return? 

Back to top 


simplethinker snjwffl
Active Member
Joined: 25 Jul 2006 Posts: 700

Posted: 18 Jul 2009 04:58:53 pm Post subject: 


ztrumpet wrote: Is 1, 0, or 1 all we return?
Yes 

Back to top 


ztrumpet
Active Member
Joined: 06 May 2009 Posts: 555

Posted: 18 Jul 2009 05:00:26 pm Post subject: 


After reading the wiki page and examining the steps I still don't get it. Help 

Back to top 


Weregoose Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004 Posts: 3976

Posted: 18 Jul 2009 06:43:53 pm Post subject: 


First attempt: 93 bytes.
Second attempt (incorporating negative values for A): 121 bytes.
Last edited by Guest on 18 Jul 2009 07:23:12 pm; edited 1 time in total 

Back to top 


Igrek
Member
Joined: 23 Aug 2007 Posts: 151

Posted: 18 Jul 2009 06:46:04 pm Post subject: 


I'd better look at that tomorrow because it's almost 2 am (and I have no idea whatsoever a Jacobi symbol is) 

Back to top 


DarkerLine ceci n'est pas une 
Super Elite (Last Title)
Joined: 04 Nov 2003 Posts: 8328

Posted: 18 Jul 2009 07:54:28 pm Post subject: 


Weregoose wrote: First attempt: 93 bytes.
Second attempt (incorporating negative values for A): 121 bytes. Why is the difference that large? Seems like ANint(A/N→A is all you need to account for negative values... 

Back to top 


Igrek
Member
Joined: 23 Aug 2007 Posts: 151

Posted: 19 Jul 2009 06:04:20 am Post subject: 


First attempt 136 bytes and not working :P
Edit: 2nd attempt 149 but working
Edit2: 3rd attempt 131 bytes is the best I get...
Last edited by Guest on 19 Jul 2009 07:54:21 am; edited 1 time in total 

Back to top 


thornahawk μολών λαβέ
Active Member
Joined: 27 Mar 2005 Posts: 569


Back to top 


Ed H
Member
Joined: 30 Nov 2007 Posts: 138

Posted: 21 Jul 2009 09:28:00 pm Post subject: 


Heh, I should probably search the forums before I post my challenges.
Anyway, to explain this challenge to people who don't about the Jacobi symbol:
Basically, the Jacobi symbol is a function on 2 variables, whose only inputs are 1, 0, and 1. The value (A/N) is defined when A is an integer and N is an odd positive integer. It satisfies several identities that make it fairly easy to compute. The important ones are
 (N/1) = 1
 (1/N) = 1
 (0/N) = 0 (if N is not 1)
 (1/N) =
 (2/N) = 1 if N is 1 or 7 mod 8, 1 if N is 3 or 5 mod 8
 (N/M) = (N + KM/M) for any integer K
 (NM/A) = (N/A)(M/A)
 (A/NM) = (A/N)(A/M)
 Quadratic Reciprocity:
When N and M are both odd positive integers,
(N/M) = (M/N) if N and M are 3 mod 4, (M/N) if either N or M are 1 mod 4
Anyway, I have a solution in 97 bytes, but it breaks down for large values of A and N due to floating point errors. Adding 4 bytes makes it more robust. 

Back to top 


Ed H
Member
Joined: 30 Nov 2007 Posts: 138

Posted: 22 Jul 2009 07:18:25 pm Post subject: 


Okay, solution in 95 bytes but fails for large inputs.
Quote: [font="courier new"]:DelVar P
ANint(A/N→A
:While A
:While not(fPart(A/2
:A/2→A
:P+8^{1}(Nē1→P
:End
:P4^{1}prod(3+{A,N→P
:A→M
:NMint(N/M→A
:M→N
:End
:(N=1)e^(πiP
The more robust version takes 99 bytes:
Quote: [font="courier new"][color=#000000]Change
:P+8^{1}(Nē1→P
to
:P+fPart(16^{1}(Nē1→P
:P4^{1}prod(3+{A,N→P
to
:PfPart(8^{1}prod(3+{A,N→P
:(N=1)e^(πiP
to
:(N=1)e^(2πiP
[/color] 

Back to top 


woodswolf
Advanced Newbie
Joined: 26 Feb 2009 Posts: 53

Posted: 28 Aug 2009 06:05:17 pm Post subject: 


I still don't really get it! being dutch doesn't really help in reading advanced mathematical english... I will look into the problem once I get it 

Back to top 


