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
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976

Posted: 23 Apr 2007 06:28:42 pm    Post subject:

Teaser/Challenge #14

[font="courier new;font-size:9pt;line-height:100%;color:darkblue"]Ans is a list of terms in a finite continued fraction expansion, ordered such that the rightmost
element holds the integer part. Make a 50-byte program that outputs the appropriate [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]{D,N}.
Back to top
luby
I want to go back to Philmont!!


Calc Guru


Joined: 23 Apr 2006
Posts: 1477

Posted: 23 Apr 2007 07:06:48 pm    Post subject:

Your cryptic speak confuses me. Give an example?
Back to top
thornahawk
μολών λαβέ


Active Member


Joined: 27 Mar 2005
Posts: 569

Posted: 23 Apr 2007 07:29:37 pm    Post subject:

Goose, you did have *simple* continued fractions in mind, right? ;)

If so, luby, here's what Goose wanted:

Say you have the list {15,7,3}. (This is a portion of the SCF expansion for pi, but pretend you didn't know that.)

The 50-byte program you should be writing should return {106,333} since 333/106 = 3+1/(7+1/15) . ;)

If you look hard enough here, you just might find the algorithm you need.

Oh... and another thing, Goose. Should the D and N returned be in lowest terms? ;)

thornahawk
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976

Posted: 23 Apr 2007 07:34:52 pm    Post subject:

thornahawk wrote:
Goose, you did have *simple* continued fractions in mind, right? Wink
I wouldn't want to be evil or something like that. :o

Yes, simple is all I'm asking for. ;)

thornahawk wrote:
Oh... and another thing, Goose. Should the D and N returned be in lowest terms? Wink
That was going to be a requirement, but I seriously can't find an input that doesn't result in an irreducible answer..!

Last edited by Guest on 23 Apr 2007 07:38:16 pm; edited 1 time in total
Back to top
thornahawk
μολών λαβέ


Active Member


Joined: 27 Mar 2005
Posts: 569

Posted: 23 Apr 2007 07:43:45 pm    Post subject:

I can't think of any input that will give a result that is not in lowest terms, but it should be easy to add a line to guarantee that the result is irreducible. Wink (hint: you need one of the little-used built in functions)

thornahawk
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976

Posted: 23 Apr 2007 07:46:58 pm    Post subject:

Only all too often: [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]Ans/gcd(Ans(1),Ans(2

Plus, I like to be able to say "50" bytes instead of "61"; I think it's more well-rounded. Smile

Last edited by Guest on 23 Apr 2007 07:50:47 pm; edited 1 time in total
Back to top
thornahawk
μολών λαβέ


Active Member


Joined: 27 Mar 2005
Posts: 569

Posted: 23 Apr 2007 08:17:15 pm    Post subject:

The following isn't the solution Goose had in mind because this is more than 50 bytes in size; however, 1) the algorithm is cute; and 2) it might inspire someone else taking the challenge:

Solution (highlight below):

Ans→L1
dim(L1)→N
[[L1(N),1]]T→[B]
[[1,0]]T→[C]
For(I,N–1,1,-1)
[[L1(I),1][1,0]]→[A]
[A][B]→[B]
[A][C]→[C]
End
{[C](1,1),[B](1,1)}


:D

thornahawk
Back to top
Harrierfalcon
The Raptor of Calcs


Super Elite (Last Title)


Joined: 25 Oct 2006
Posts: 2535

Posted: 23 Apr 2007 08:24:35 pm    Post subject:

That started as 116 bytes but was optimized to 93% of it's original size, 108 bytes.

I still don't get it, but whatever...
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976

Posted: 27 Apr 2007 11:34:50 pm    Post subject:

I'll give a hint:
    [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]a___c___a·d + b·c
    ─ + ─ = ─────────
    b___d______b·d
Back to top
thornahawk
μολών λαβέ


Active Member


Joined: 27 Mar 2005
Posts: 569

Posted: 28 Apr 2007 05:23:20 am    Post subject:

The following *still* isn't the solution Goose had in mind because this is *still* more than 50 bytes in size; however, 1) the algorithm is cute; and 2) this is now shorter than the program I previously posted:

Solution (highlight below):

Ans→L1
identity(2
For(I,1,dim(L1
Ans[[L1(I),1][1,0
End
Matr►list(Ans,L2
L2


However, this one now assumes that the list that is supposed to be given as input should be now in reverse order. That, and the output is now of the form {N,D}

:D

thornahawk

P.S. Coincidentally, I have now an additional teaser that makes use of results related to that given above: Make a 30-byte program for computing the Fibonacci numbers. ;)

P.P.S. (4/30/2007) The solution was edited to correct an omission.


Last edited by Guest on 29 Apr 2007 11:58:23 pm; edited 1 time in total
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976

Posted: 28 Apr 2007 06:22:09 am    Post subject:

Nice. The [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]L1 in the loop needs to be replaced with [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]L1(I) for it to work, though.

thornahawk wrote:
Make a 30-byte program for computing the Fibonacci numbers.
How many? I have a program that will display the [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]Nth Fibonacci number in 22 bytes.

[EDIT]

I now have a program that displays the first [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]N+1 Fibonacci numbers in 29 bytes.

Well... excluding the zero.

[EDIT×2]

Now at 30 bytes, with the zero.

And no, mine doesn't use matrices, sorry to say.

[EDIT×3]

I have some new code that displays every convergent [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]{N,D} to the Golden Ratio in 26 bytes.

There are probably several more ways in which this problem could be handled!

[EDIT×4]

Got a method using matrices at 28 bytes. Looking for more approaches yet..!

[EDIT×5]

Hehehe... Fn+1 using the binomial coefficient in 27 bytes.

And, a new recursion which displays all of them greater than one using 26 bytes.

This is what happens when not much is specified in the terms, but it is
interesting in that it yields more methods to achieve the same results!

Last edited by Guest on 28 Apr 2007 11:56:00 am; edited 1 time in total
Back to top
thornahawk
μολών λαβέ


Active Member


Joined: 27 Mar 2005
Posts: 569

Posted: 29 Apr 2007 11:57:08 pm    Post subject:

Ah, Goose, you are right about that mistake. I'll edit my previous post to correct it.

It seems you found a lot of curiosities related to Fibonacci and the golden ratio. Wink Maybe make a separate topic for that?

thornahawk
Back to top
DarkerLine
ceci n'est pas une |


Super Elite (Last Title)


Joined: 04 Nov 2003
Posts: 8328

Posted: 30 Apr 2007 04:51:41 pm    Post subject:

thornahawk wrote:
I can't think of any input that will give a result that is not in lowest terms, but it should be easy to add a line to guarantee that the result is irreducible. Wink (hint: you need one of the little-used built in functions)

thornahawk
[post="101679"]<{POST_SNAPBACK}>[/post]

Weregoose wrote:
Only all too often: [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]Ans/gcd(Ans(1),Ans(2

Plus, I like to be able to say "50" bytes instead of "61"; I think it's more well-rounded. Smile
[post="101680"]<{POST_SNAPBACK}>[/post]


Although I haven't thought of a good way to approach the problem itself, I have I think determined that all results will be irreducible, assuming integer input. Now if only I could wrap my mind around the real teaser...

[Edit] Okay, I did the obvious thing and now I'm at 55 bytes with a 2-byte name.

[Edit] I think I've got it! (52 bytes, with a 2-byte name, which I'm pretty sure is what you meant) It's pure luck that it works, though...

[Edit] You could get it to be one byte less by using LX or some such instead of L1 (for then, you can store simply to X), but that leaves a mess behind.


Last edited by Guest on 30 Apr 2007 05:15:25 pm; edited 1 time in total
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976

Posted: 30 Apr 2007 11:46:27 pm    Post subject:

I think it's only fair that I provide the results I got for both challenges—then we
can compare answers. But I don't want to hear, "We didn't have enough time!"

For the reverse continued fraction:
Spoiler wrote:
[font="courier new;font-size:9pt;line-height:100%;color:darkblue"]Ans->X
{0,1
For(X,1,dim(LX
{Ans(2),Ans(1)+Ans(2)LX(X
End
Ans

The seven programs I wrote for calculating Fibonacci Numbers—each
under 30 bytes—in the same order as the edits from my earlier post:
Spoiler wrote:
[font="courier new;font-size:9pt;line-height:100%;color:darkblue"]int(.5+√(.2)e^(Nsinh‾¹(.5

int(.5+√(.2)e^(Nsinh‾¹(.5)cumSum(binomcdf(N,0

int(.5+√(.2)e^(Nsinh‾¹(.5)cumSum(not(binompdf(N,0

{1:Repeat 0
Pause {sum(Ans),Ans(1
End

1:Repeat 0
Pause Ans[[1,1][1,0
End

sum(seq((N-K) nCr K,K,0,int(.5N

1:Repeat 0
Pause int(.5+Ne^(sinh‾¹(.5
End


Last edited by Guest on 30 Apr 2007 11:47:12 pm; edited 1 time in total
Back to top
DarkerLine
ceci n'est pas une |


Super Elite (Last Title)


Joined: 04 Nov 2003
Posts: 8328

Posted: 01 May 2007 03:27:19 pm    Post subject:

My answer for the continued fraction:
Quote:
augment({1},Ans→X
For(I,3,dim(Ans
{Ans(2),Ans(1)+LX(I)Ans(2
End
Ans


An optimization to your binomial Fibonacci program (of sorts - it's now twice as slow, but smaller):
Quote:
sum(seq((Ans-K) nCr K,K,0,Ans


And another solution I discovered during physics class when I was supposed to be paying attention to induced currents instead...
Quote:
int(round(√(.8)cosh(Ansln(.5+√(.2

...optimized further after reading some of your solutions:
Quote:
int(round(√(.8)cosh(Anssinh-1(.5


This is actually the optimized version of a more interesting Fibonacci identity I found, which also works for negative Fibonacci numbers (such as F-5) though the above two don't:

Quote:
Fn = (2/√5)sinh(n*ln(φ))  (when n is even)
Fn = (2/√5)cosh(n*ln(φ))  (when n is odd)


Last edited by Guest on 01 May 2007 03:29:44 pm; edited 1 time in total
Back to top
thornahawk
μολών λαβέ


Active Member


Joined: 27 Mar 2005
Posts: 569

Posted: 01 May 2007 10:42:48 pm    Post subject:

@Goose: ...and with only a few modifications to those Fibonacci programs you gave, the Lucas numbers also become accessible.

That reminds me, in light of the recent activity in this topic, I will now be posting the modification I devised for the rationalization program I gave earlier in the forums.

thornahawk
Back to top
justm3


Newbie


Joined: 17 Feb 2010
Posts: 5

Posted: 01 Mar 2010 07:29:45 pm    Post subject:

Try and create the shortest Fibonacci number getter that you can. Have the user input a number, and then find that fibonacci number. So, if you input 5, you will get 8. My current size is 56, excluding title. One other thing: it must pause the answer. Good luck! I will post mine later if people want. Smile

Last edited by Guest on 01 Mar 2010 07:30:30 pm; edited 1 time in total
Back to top
Weregoose
Authentic INTJ


Super Elite (Last Title)


Joined: 25 Nov 2004
Posts: 3976

Posted: 01 Mar 2010 07:35:22 pm    Post subject:

Already listed. (Threads merged.)

Last edited by Guest on 01 Mar 2010 07:36:15 pm; edited 1 time in total
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