Find the Fibonacci Patterns

Engineer Toast 05/15/2018. 5 answers, 135 views
code-golf fibonacci

You are probably familiar with the Fibonacci sequence where the first two terms are 0, 1 (or sometimes 1, 1) and every term after that is the sum of the previous two. It starts like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Sometimes, the sequence contains numbers that have a particular pattern that I find interesting: the difference between any pair of adjacent digits is the same as any other pair. For instance, in the sequence starting with 0, 1, the 18th term is 987. 9-8=1 and 8-7=1. I am mildly satisfied.

Challenge

Given two initial values F(0) and F(1), output every number in the sequence generated by F(n) = F(n-1) + F(n-2) that meets the following criteria:

  • The difference between any pair of adjacent digits is the same as any other pair
  • It is as least three digits long (1 and 2 digit numbers are not interesting for this pattern)

Input

  • Two non-negative integers less than 10**10 (10 billion)

Output

  • All integers that are less than 10**10 and meet the criteria in the Challenge section
  • It is acceptable to output digits greater than 10**10 but it is not a requirement
  • Given that repeated digits meet the pattern (e.g. 777), it is possible that there are infinite numbers that meet the criteria but your program is not required to output forever
  • If no such integers exist, output whatever you want so long as it's not a number (nothing, null, empty array, error message, sad face, etc.)
  • If a number matching the pattern appears more than once in the sequence, you can output it once or as many times as it occurs
  • If any input meets the criteria, it should be included in the output

Rules

Examples / Test Cases

Input , Output   
[1,10] , []   

[0,1] , [987]   
[2,1] , [123]   
[2,3] , [987]   

[61,86] , [147]   
[75,90] , [420]   
[34,74] , [1234]   
[59,81] , [2468]   
[84,85] , [7531]   

[19,46] , [111]   
[60,81] , [222]   
[41,42] , [333]   
[13,81] , [444]   
[31,50] , [555]   
[15,42] , [666]   
[94,99] , [777]   
[72,66] , [888]   

[15,3] , [159,258]   
[22,51] , [321,1357]   
[74,85] , [159,4444]   
[27,31] , [147,11111]   

[123,0] , [123,123,246,369]   
[111,0] , [111,111,222,333,555,888]
[111,222] , [111,222,333,555,888]      

[3894621507,5981921703] , [9876543210]
[765432099,111111111] , [111111111,876543210,987654321]   

5 Answers


Stewie Griffin 05/15/2018.

Octave, 145 bytes

@(a,x=0)eval('do++x;t{x}=(a*[1,1;1,0]^x)(1);until t{x}>1e11,for i=1:x,if t{i}>99,if diff(k=+num2str(t{i}))==diff(k(1:2)),disp(t{i}),end,end,end')

Try it online!

Good night! Explanation tomorrow! :)


Chas Brown 05/15/2018.

Python 2, 102 98 bytes

f=lambda x,y:x<1e10and[x]*(len(set(int(a)-int(b)for a,b in zip(`x`,`x`[1:])))<2<99<x)+f(y,x+y)or[]

Try it online!

Thx for 4 bytes from ovs


dylnan 05/15/2018.

Jelly, 20 19 bytes

>ȷ2ȧDIEƊ
;+ƝṪ$$ȷ¡ÇƇ

Try it online!


Luis Mendo 05/15/2018.

MATL, 13 bytes

`wy+ttVdd~?tD

Infinite loop that outputs the numbers as they are found.

Try it online! Note that in the online interpreter the results are displayed after the 1-minute time-out.

Let F(n) and F(n+1) denote two generic consecutive terms of the Fibonacci sequence.

Explanation

`         % Do...while
  w       %   Swap. Takes the two inputs (implicitly) the first time
          %   STACK: F(n+1), F(n)
  y       %   Duplicate from below
          %   STACK: F(n+1), F(n), F(n+1)
  +       %   Add. Note that F(n)+F(n+1) is F(n+2) 
          %   STACK: F(n+1), F(n+2)
  tt      %   Duplicate twice
          %   STACK: F(n+1), F(n+2), F(n+2), F(n+2)
  V       %   Convert to string. Let the digits of F(n+2) be '3579' for example
          %   STACK: F(n+1), F(n+2), F(n+2), '3579'
  d       %   Consecutive differences (of ASCII codes)
          %   STACK: F(n+1), F(n+2), F(n+2), [2 2 2]
  d       %   Consecutive differences
          %   STACK: F(n+1), F(n+2), F(n+2), [0 0]
  ~       %   Logical negate, element-wise
          %   STACK: F(n+1), F(n+2), F(n+2), [1 1]
  ?       %   If top of the stack is non-empty and only contains non-zero entries
          %   (this is the case for digits '3579', but not for '3578' or '33')
    t     %     Duplicate
          %     STACK: F(n+1), F(n+2), F(n+2), F(n+2)
    D     %     Display immediately. This prints the top-most copy of F(n+2)
          %     STACK: F(n+1), F(n+2), F(n+2)
          %   End (implicit)
          % End (implicit). The top of the stack is consumed as loop condition.
          % Since it is non-zero, and thus truthy, a new iteration will begin,
          % with the stack containing F(n+1), F(n+2)

Arnauld 05/15/2018.

JavaScript (ES6), 85 bytes

f=(p,q,a=[])=>p<1e10?f(q,p+q,p<100|[...p+''].some(x=d=n=>d-(d=x-(x=n)))?a:[...a,p]):a

Try it online!


HighResolutionMusic.com - Download Hi-Res Songs

1 Martin Garrix

Yottabyte flac

Martin Garrix. 2018. Writer: Martin Garrix.
2 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
3 Sia

I'm Still Here flac

Sia. 2018. Writer: Sia.
4 Blinders

Breach (Walk Alone) flac

Blinders. 2018. Writer: Dewain Whitmore;Ilsey Juber;Blinders;Martin Garrix.
5 Dyro

Latency flac

Dyro. 2018. Writer: Martin Garrix;Dyro.
6 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
7 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
8 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
9 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
10 Kelsea Ballerini

This Feeling flac

Kelsea Ballerini. 2018. Writer: Andrew Taggart;Alex Pall;Emily Warren.
11 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
12 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
13 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
14 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
15 Charli XCX

1999 flac

Charli XCX. 2018. Writer: Charli XCX;Troye Sivan;Leland;Oscar Holter;Noonie Bao.
16 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.
17 Diplo

Electricity flac

Diplo. 2018. Writer: Diplo;Mark Ronson;Picard Brothers;Wynter Gordon;Romy Madley Croft;Florence Welch.
18 Jonas Blue

Polaroid flac

Jonas Blue. 2018. Writer: Jonas Blue;Liam Payne;Lennon Stella.
19 Lady Gaga

Look What I Found flac

Lady Gaga. 2018. Writer: DJ White Shadow;Nick Monson;Mark Nilan Jr;Lady Gaga.
20 Avril Lavigne

Head Above Water flac

Avril Lavigne. 2018. Writer: Stephan Moccio;Travis Clark;Avril Lavigne.

Related questions

Hot questions

Language

Popular Tags