Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.
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.

This forum is locked: you cannot post, reply to, or edit 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 Smile
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 Very Happy
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

Posted: 20 Jul 2009 07:09:31 am    Post subject:

I should probably post that little Kronecker symbol program I made, but for now...

thornahawk
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 Razz
Back to top
Display posts from previous:   
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
    »
» View previous topic :: View next topic  
Page 1 of 1 » All times are GMT - 5 Hours

 

Advertisement