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.
In reply to Re: Re: Re: Fibonacci numbers
by Sweeper
in thread Fibonacci numbers
by Anonymous Monk
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |