## Puzzle of the Week #10: Fibonacci

Puzzle: With a single SELECT statement calculate first 20 Fibonacci numbers without using Binet’s formula.

Expected Result:

```   N     Fib(n)
---- ----------
1          1
2          1
3          2
4          3
5          5
6          8
7         13
8         21
9         34
10         55
11         89
12        144
13        233
14        377
15        610
16        987
17       1597
18       2584
19       4181
20       6765
```

A correct answer (and workarounds!) will be published here in a week.

If you like this post, you may want to join my new Oracle group on Facebook: https://www.facebook.com/groups/sqlpatterns/

For more tricks and cool techniques check my book “Oracle SQL Tricks and Workarounds” for instructions.

### 18 thoughts on “Puzzle of the Week #10: Fibonacci”

1. sajith May 2, 2016 / 9:47 am

with temp (n, n1, n2) as
(
select 1, 0,1 from dual union all
select n + rownum, n2, n1+n2 from temp where n 0

• Zahar Hilkevich May 2, 2016 / 10:05 am

The solution seems to be right but cut off

• Zahar Hilkevich May 2, 2016 / 11:19 am

Please correct the query. WordPress may have removed some of the “” characters.

• sajith May 2, 2016 / 8:37 pm

with temp (n, n1, n2) as
(
select 1, 0,1 from dual union all
select n + rownum, n2, n1+n2 from temp where n 0

• sajith May 2, 2016 / 8:39 pm

query is breaking off, when i paste it here. i am putting it as an image here

• sajith May 2, 2016 / 8:41 pm

with temp (n, n1, n2) as (select 1, 0,1 from dual union all select n + rownum, n2, n1+n2 from temp where n 0

2. sajith May 2, 2016 / 10:25 am

SELECT level “N”,ROUND(POWER((1 + sqrt (5))/2,LEVEL) / POWER(5,0.5)) “Fib(n)” FROM DUAL CONNECT BY LEVEL < =20

• Zahar Hilkevich May 2, 2016 / 11:21 am

This is Binet’s formula – it should not be used here – it was explicitely noted in the puzzle.

3. Ashwin Kumar Padhy May 2, 2016 / 10:49 am

SELECT ‘F’ || TO_CHAR(Level – 1) AS FibonacciOrdinal,
( (POWER(1 + SQRT(5), Level – 1)
– POWER(1 – SQRT(5), Level – 1))
/ (POWER(2, Level – 1) * SQRT(5))) AS FibonacciNumber
FROM Dual d
CONNECT BY Level <= 20;

• Zahar Hilkevich May 2, 2016 / 11:20 am

This is Binet’s formula – it should not be used here – it was explicitely noted in the puzzle.

4. Ashwin Kumar Padhy May 2, 2016 / 10:58 am

with data as (select level levels from dual
connect by level 2]=f[cv(levels)-2]+f[cv(levels)-1]
);

• Ashwin Kumar Padhy May 2, 2016 / 11:02 am

with data as (select level levels from dual
connect by level 2]=f[cv(levels)-2]+f[cv(levels)-1]);

• Zahar Hilkevich May 2, 2016 / 11:19 am

Please correct the query. WordPress may have removed some of the “” characters.

5. Krishna Jamal May 4, 2016 / 11:38 am

WITH FibNum (RowN, N, FibN) AS
( SELECT 1 AS RowN, 0 AS N, 1 AS FibN FROM Dual
UNION ALL
SELECT t.RowN+1, t.FibN, t.N+t.FibN FROM FibNum t
WHERE t.RowN<20)
SELECT RowN "Seq", FibN "Fib_Num" FROM FibNum;

• pankaj May 5, 2016 / 9:00 am

• Zahar Hilkevich May 5, 2016 / 9:19 am

Solutions will be published tomorrow

6. Pawan Kumar Khowal June 1, 2016 / 5:19 am

T-SQL , SQL Server 2012

–Solution 1 , Numbers Table

SELECT 0 Fibonacci
UNION ALL
SELECT
ROUND((POWER(((1 + Sqrt(5))/2), Number) – POWER(-1/((1 + Sqrt(5))/2), Number )) / Sqrt(5) ,1)
FROM Numbers
WHERE Number < 20

–Solution 2 , While Loop

DECLARE @Fibonacci TABLE (Number INT NOT NULL)
INSERT @Fibonacci (Number) SELECT 0 UNION ALL SELECT 1

WHILE (SELECT COUNT(*) FROM @Fibonacci) < 20
BEGIN
INSERT INTO @Fibonacci (Number)
SELECT SUM(Number)
FROM (SELECT TOP 2 Number FROM @Fibonacci ORDER BY Number DESC)t
END

SELECT Number Fibonacci FROM @Fibonacci

–Solution 3 , Recursive CTE

;WITH CTE AS
(
SELECT
0 AS Level,
0 AS Start,
1 AS Next
UNION ALL
SELECT a.Level + 1 AS RecursionLevel,
a.Next AS FibonacciNumber,
a.Start + a.Next AS NextNumber
FROM CTE a
WHERE a.Level < ( 20 – 1 )
)
SELECT Start Fibonacci FROM CTE
OPTION ( MAXRECURSION 10000 )

Pawan Kumar Khowal