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

To submit your answer (one or more!) please start following this blog and add a comment to this post.

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.

Advertisements

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

      pls give proper answer plsssssss

      • 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s