Re: Fibonacci string



John W. Krahn <someone@xxxxxxxxxxx> wrote:

> John W. Krahn wrote:
>> David K. Wall wrote:
>>
>>> Here's a fun fact I ran across in the book _The Golden Ratio_,
>>> by Mario Livio. Take the string '1' and replace it with '10'.
>>> Thereafter, replace any occurrence of '1' with '10' and '0' with
>>> '1'. Then count the number of 0s and 1s in the string. You get
>>> a Fibonacci sequence for each count (offset by one iteration).
>>>
>>> Here's Perl code to do it. You get about the same results if
>>> you start with '0', just offset a little.
>>>
>>> use strict;
>>> use warnings;
>>>
>>> my $v = '1';
>>> for (1 .. 20) {
>>> my ($n0, $n1) = (0, 0);
>>> $v = join '',
>>> map {
>>> if ($_) {
>>> $n1++;
>>> '10';
>>> }
>>> else {
>>> $n0++;
>>> '1';
>>> }
>>> } split //, $v;
>>> printf "%10d %10d\n", $n0, $n1;
>>> }
>>
>> You can make that shorter and faster:
>>
>> my $v = '1';
>> for ( 1 .. 20 ) {
>> printf "%10d %10d\n", $v =~ y/0//, $v =~ y/1//;
>> $v =~ s/([01])/ $1 ? '10' : '1' /eg;
>> }
>
> A bit faster. :-)
>
> my $v = '1';
> for ( 1 .. 20 ) {
> printf "%10d %10d\n", $v =~ y/0//, $v =~ y/1//;
> $v =~ s/./ $& ? '10' : '1' /eg;
>}

I bow to greater perl-fu, but with the caveat that I was more
interested in making the idea clear than in coming up with a fast
implementation. I'd accuse you of having too much time on your hands
if I weren't guilty of the same sort of thing myself.
.