Continued Fractions and Fibonacci Numbers

[Weregoose]

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}.

[luby]

Your cryptic speak confuses me. Give an example?

[thornahawk]

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

[Weregoose]

[thornahawk]

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

[Weregoose]

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

[thornahawk]

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→L₁
dim(L₁)→N
[[L₁(N),1]]^T→[B]
[[1,0]]^T→[C]
For(I,N–1,1,-1)
[[L₁(I),1][1,0]]→[A]
[A][B]→[B]
[A][C]→[C]
End
{[C](1,1),[B](1,1)}


:D

thornahawk

[Harrierfalcon]

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...

[Weregoose]

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

[thornahawk]

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→L₁
identity(2
For(I,1,dim(L₁
Ans[[L₁(I),1][1,0
End
Matr►list(Ans,L₂
L₂


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.

[Weregoose]

Nice. The [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]L1

[thornahawk]

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

[DarkerLine]

[Weregoose]

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:

[DarkerLine]

My answer for the continued fraction:

[thornahawk]

@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

[justm3]

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.

[Weregoose]

Already listed. (Threads merged.)