This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's
TI-BASIC subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.
TI-Basic Brain Teasers =>
TI-BASIC
| 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 100-120 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 A-Nint(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
A-Nint(A/N→A
:While A
:While not(fPart(A/2
:A/2→A
:P+8-1(N²-1→P
:End
:P-4-1prod(3+{A,N→P
:A→M
:N-Mint(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
:P-4-1prod(3+{A,N→P
to
:P-fPart(8-1prod(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 |
|
|
|
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.
»
Go to Registration page
