$i = 1;
print "$i,";
print($i++,',') for(;;);
[download]

                - Ant
                - Some of my best work - Fish Dinner

I agree with jeroenes. This is very possible to do.

Yes, it is. To reduce the problem size, the following program is likely to eventually print out any Fibonacci numbers between 0 and N-1, where N is the command line argument. In order, even. However, you must find them buried in all the other numbers, and it will take an indeterminate amount of time. It will not stop upon hitting a sequence of fibonacci numbers. (Hint: The output is random.)

#!/usr/bin/perl -w
use strict;my$N=$_[0];$\=' ';for (;;){print int rand$N}
[download]

Well, no I don't think anybody can do it. I had trouble getting my daughter to write just a 'hello world' program. But you might be able to do it by just writing a program that generates a sequence that follows these rules:

i₀=0, i₁=1, i_{n, n>=2}=i_n-1+i_n-2

Now, why should we show you? Is this for a homework assignment? Go do your own work!

If not, how about a google search?

Or how about a Super Search on this site?

Mastering Algorithms with Perl has two solutions on page 494.

jeffa

Yves
--
You are not ready to use symrefs unless you already know why they are bad. -- tadmc (CLPM)

print "1,1,2,3,5,8,13,21,...\n";
[download]

print join( ",", qw( 1 1 2 3 5 8 13 21 ... ) );
[download]

xoxo,
Andy
--
<megaphone> Throw down the gun and tiara and come out of the float! </megaphone>

I would advise against using them if you can't explain on demand how they work.

#!/usr/bin/perl -w
use strict;

*prev = sub { 
    my $a = $_[0] || 0;
    sub { $a };
};

*fib = sub {
    ($a, $b) = ($_[0] + $_[1]->(), $_[0]);
    printf "%d$/", $a;
    $_ = sub { fib( $a, prev($b) ) };
};

print "$_$/" for ++$|;
fib(1, prev(0)); 
for my $var (1 .. shift || 10) {
    $_->();
}
[download]

--
Tatsuhiko Miyagawa
miyagawa@cpan.org

$a=1;
$b=1;
$c=$a+$b;

while($a <=100){
     print("$a\n");
     print("$b\n");
     print("$c\n");
     $a=$b+$c;
     $b=$a+$c;
    }
[download]

OK, if you're going to make an attempt at it, then we can help

Lets see....at the start you set $a and $b to 1, and $c to $a+$b = 2

Then, on each iteration round the loop, you print out all three variables, then add 2 ($c from your initialisation) to $a and $b, then repeat.

The assignment of $c=$a+$b simply sets $c according to the values of $a and $b at the time of assignment, and does not 'recalculate' on each trip around the loop.

You will also have to rethink the calculation, as it doesn't quite work.

p.s. try using strict and warnings.

foreach (1..10) { print fibo($_), "\n" }

sub fibo {
  $_ = '1'.'2'x($_[0]).'1';

  while (/[1568]$/)
    {s=([2-589]?[01358])=int(abs((67*$1-1467)*$1+1423)/140)=eg}
  y/02678//d;
  return length
}
[download]

Whoa, thats wild... I'm still picking it apart, but I've got a slight obfu change, if that's what you're going for. Replace the 'return length' line with:

s;.;+1;g;eval;
[download]

now, back to figuring out exactly what the rest of that sub is doing....

-Blake

This is one of my two submissions to OPC-5. And now, here is the solution file:

Solution
--------

This program computes the Fibonacci numbers, using regexps.

First, I'll prove that $_ contains only 0's, 1's and 2's, and
that all other digits are there for obfuscation purpose only.

Then, I'll prove that the numbers of 0's and 1's are 
Fibonacci numbers.

Lastly, I'll explain the result.

1 Which digits?
---------------

We start with a string which looks like "12222221" (with six 2's, 
because we want to compute fib(6)).

This string contains substrings belonging to the following set:
"0", "1", "2", "00", "01", "10", "11", "02", "12", "22" and "21".

Of these substrings, only "0", "1", and "21" can match the regexp.
For these three substrings, the formula gives:
    0  -> 10
    1  ->  0
    21 ->  1
The resulting string will therefore contain substrings belonging to
the same set. And the de-obfuscated lines would read:
    while (/1$/){s=(2?[01])=int(abs((67*$1-1467)*$1+1423)/140)=eg}
    y/02//d;

2 How Fibonacci is computed
---------------------------

Theorem: at the end of the i-th iteration, the string contains
           fib(i-1) "1"s
mixed with fib(i) "0"s
      then (n-i) "2"s
      then either a "1" or a "0"

Demonstration: at the start of the program, the string contains a
single "1", n "2"s and another "1". After the first iteration,
the string contains a single "0", (n-1) "2"s and a "1".
That is, the first part of the string contains 0 "1"s (and 
fib(1-1) = 0) and only one "0" (fib(1) = 1).

Suppose this is true for i, we show it remains true for j=i+1.

- In the first part of the resulting  string, all "1"s come 
from the substitution 0 -> 10. There were fib(i) "0"s in the
original string, therefore there are fib(i) = fib(j-1) "1"s in
the resulting string.

- In the first part of the resulting string, all "0"s come
either from the substitution 1 -> 0 (fib(i-1) such substitutions), 
or from 0 ->10 (fib(i) such substitutions). Therefore, in the
resulting string, there are fib(i-1) + fib(i) "0"s, that is
fib(i+1) or fib(j).

- In the second part of the original string, only the last "2"
match the regexp. Actually, this "2" and the last "1" match
"21". Both digits are replaced with a single "1", in effect
deleting this "2". The number n-i becomes n-i-1, that is, n-j.

3 How many iterations?
----------------------
We start with n "2"s. Each iteration removes one "2". So, after
n iterations, we have a string consisting of:
           fib(n-1) "1"s
mixed with fib(n) "0"s
and then   a single "1", no longer prefixed by any "2"s.

After this iteration, the loop condition (end with "1") is still
true. So there is a (n+1)-th iteration, which produces:
           fib(n) "1"s
mixed with fib(n+1) "0"s
and then   a single "0", because of the 1 -> 0 substitution (used 
for a different purpose).

Then, we remove the (fib(n+1)+1) "0"s, with y/02//d, and the last 
string now contains only fib(n) "1"s.

By the way, y/02//d could even be replaced by y/0//d, because 
there are no "2"s anymore.

4 Comments
----------
Where did the formula come from?
I needed a formula producing:
    0  -> 10
    1  ->  0
    21 ->  1
I tried a polynom y = a x**2 + b x + c, and I found
    y = (67 x**2 - 1467 x + 1400)/140
or, with the Horner formula
    y = ((67 x - 1467) x + 1400)/140
The problem is, only the three values give an positive integer 
result, which would be an indication that these three values 
are the important ones, and the other values can be 
discarded. So I introduced the functions "abs" and "int". 
Since I had done that, I could alter a bit the 
polynom, and therefore I changed it to
    y = ((67 x - 1467) x + 1423)/140

Duration of the program.
This program is very inefficient. During the i-th iteration, 
you have:
fib(i-1) substitutions "1 -> 0"
  fib(i) substitutions "0 -> 10" (which extends the string)
   and 1 substitution "21 -> 1".
Therefore, the i-th iteration has fib(i+1)+1 substitutions, that is
0.723 x 1.618 ** i + small quantity.
The total cost is 0.723 x sum(1.618 ** i + small quantities),
that is O(1.618**n). Not very good, but much fun.
[download]

This is covered in some depth in an article that Dominus wrote about caching.

"The first rule of Perl club is you don't talk about Perl club."

$a=0;
$b=1;
while($a <=200)
    {print("$a\n");
     ($a,$b)=($b,$a+$b);
    }
[download]

How does this statement

($a,$b)=($a,$a+$b);
[download]

does the trick? I couldn't understand...can somebody explain?

Perhaps you can't see it because you've got the statement wrong. It should be

($a,$b)=($b,$a+$b);
[download]

It's a simple list assignment. $a gets the value of $b and $b gets $a+$b.

Incidently, it can be a bad idea to use $a and $b in Perl scripts as they are "special" variables because of their use in sorting.

Blessed Be
The Pixel

Dear Anonymous, It's very simple. In every iteration the $a receives the earlier value of $b...that's the trick. Bye the way, u can see my ealier attempt, which had one serious mistake... that can be rewritten to give the desired result. See:

$a=1;
$b=1;

while($a <=200)
    {$c=$a+$b;
     print("$a\n$b\n$c\n");
    $a=$b+$c;
    $b=$c+$a;
    }
[download]

Thanks.

Oh, for goodness sake. This is homework, right?

For the answer to this latest question, see the first answer in the thread...

(Alternatively, read what you're quoting: it might make more sense then.)