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.

TI-Basic Brain Teasers => TI-BASIC
Author Message
Ed H

Member

Joined: 30 Nov 2007
Posts: 138

 Posted: 11 Dec 2008 08:08:38 pm    Post subject: Create a program that returns all the quadratic residues, modulo N. (No need to Prompt or Input for N, the value's already there.) The output should be a list in Ans, with no duplicates.
Weregoose
Authentic INTJ

Super Elite (Last Title)

Joined: 25 Nov 2004
Posts: 3976

 Posted: 11 Dec 2008 09:28:42 pm    Post subject: Going for sheer size, I have it in 42 bytes.
Ed H

Member

Joined: 30 Nov 2007
Posts: 138

 Posted: 12 Dec 2008 12:31:40 am    Post subject: I have the same size. What about optimizing for speed? What would be an efficient way to do this for large N? One immediate optimization I can see is to only square the numbers from 1 to N/2, since (-a)2 = a2 (mod n). Beyond that you'd probably have to use number theory.
Weregoose
Authentic INTJ

Super Elite (Last Title)

Joined: 25 Nov 2004
Posts: 3976

 Posted: 12 Dec 2008 12:52:58 am    Post subject: Ed H wrote:One immediate optimization I can see is to only square the numbers from 1 to N/2, since (-a)2 = a2 (mod n). Beyond that you'd probably have to use number theory.Then you know as much as I do. In fact, I speculate that coming up with a formula for the lengths of these lists might even make headway into an orderly enumeration of the primes. As for our programs being the same size, the results of past challenges have led me to wonder whether we really did hit upon the same routine. But, there's time yet for more results, I think. Last edited by Guest on 12 Dec 2008 12:55:27 am; edited 1 time in total
Weregoose
Authentic INTJ

Super Elite (Last Title)

Joined: 25 Nov 2004
Posts: 3976

 Posted: 14 Dec 2008 04:46:34 pm    Post subject: Three days later... Time enough for results, or should we wait a week?
simplethinker
snjwffl

Active Member

Joined: 25 Jul 2006
Posts: 700

 Posted: 14 Dec 2008 07:16:03 pm    Post subject: I have 44 bytes. It's a simple routine, but it works.
Ed H

Member

Joined: 30 Nov 2007
Posts: 138

 Posted: 14 Dec 2008 07:55:15 pm    Post subject: 3 solutions seems enough. Here is mine: Quote:[font="courier new"]:{0 :For(X,1,N :If min(Ans≠NfPart(X2/N :augment(Ans,{NfPart(X2/N :End
Weregoose
Authentic INTJ

Super Elite (Last Title)

Joined: 25 Nov 2004
Posts: 3976

 Posted: 14 Dec 2008 09:55:42 pm    Post subject: Well, Ed H posted my solution for me, except that I had used A instead of X. Last edited by Guest on 12 Jul 2010 01:43:16 am; edited 1 time in total
simplethinker
snjwffl

Active Member

Joined: 25 Jul 2006
Posts: 700

 Posted: 14 Dec 2008 09:57:46 pm    Post subject: Mine was the same, except instead of min(Ans≠... I had not(max(Ans=... (and I used A).
Ed H

Member

Joined: 30 Nov 2007
Posts: 138

 Posted: 15 Dec 2008 12:31:08 am    Post subject: Ah yes, De Morgan's laws. Those are useful to remember when optimizing.
 Display posts from previous: All Posts Oldest FirstNewest First
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.

»
 Page 1 of 1 » All times are GMT - 5 Hours