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? 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? 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. (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.
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. 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. (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.
[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.
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 |
|
|
|