Find the Fibonacci Patterns

Question

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

• Input and Output can be in any standard format
• Standard loopholes are forbidden
• This is code-golf so the shortest code in bytes wins

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]  
[3189,826] , [888888888]    

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

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

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

[1976,123] , [123, 2222, 4321, 6543, 45678]   

Answer 1

MATL, 14 bytes

Thanks to Emigna for pointing out a mistake, now corrected

`yVdd~?yD]wy+T

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.

Explanation

Let F(n) and F(n+1) denote two generic consecutive terms of the Fibonacci sequence. Each iteration of the loop starts with the stack containing F(n), F(n+1) for some n.

`         % Do...while
  y       %   Duplicate from below. Takes the two inputs F(0), F(1) (implicitly)
          %   in the first iteration
          %   STACK: F(n), F(n+1), F(n)
  V       %   Convert to string. Let the digits of F(n) be '3579' for example
          %   STACK: F(n), F(n+1), '3579'
  d       %   Consecutive differences (of ASCII codes)
          %   STACK: F(n), F(n+1), [2 2 2]
  d       %   Consecutive differences
          %   STACK: F(n), F(n+1),  [0 0]
  ~       %   Logical negate, element-wise
          %   STACK: F(n), F(n+1), [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')
          %   STACK: F(n), F(n+1)
    y     %     Duplicate from below
          %     STACK: F(n), F(n+1), F(n)
    D     %     Display immediately. This prints the copy of F(n)
          %     STACK: F(n), F(n+1)
  ]       %   End
  w       %   Swap
          %   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)
  T       %   Push true. This will be used as loop condition
          %   STACK: F(n+1), F(n+2), true
          % End (implicit). The top of the stack is consumed as loop condition.
          % Since it is true, a new iteration will begin, with the stack
          % containing F(n+1), F(n+2)

Answer 2

05AB1E, 17 16 15 bytes

тFÂ2£O¸«}ʒS¥¥_W

Try it online!

Explanation

                  # implicitly input list of F(0) and F(1)
тF      }         # 100 times do:
  Â               # bifurcate current list
   2£             # take the first 2 items
     O            # sum
      ¸«          # append to list
         ʒ        # filter, keep only elements that are true after:
          S¥¥     # delta's of delta's of digits
             _    # logically negate each
              W   # min

Answer 3

JavaScript (ES6), 85 84 81 bytes

f=(p,q,a=[])=>p|q?f(q,p+q,![...p+''].some(x=d=n=>r=d-(d=x-(x=n)))/r?[...a,p]:a):a

Try it online!

Testing adjacent digits

![...p + ''].some(x = d = n => r = d - (d = x - (x = n))) / r

Both x and d are initialized to an anonymous function, which forces NaN for all arithmetic operations they're involved in. The first iteration of some() always gives (d = [function] - n) === NaN and (r = [function] - d) === NaN (falsy). On the second iteration, we have d = x - n (an integer) and (r = NaN - d) === NaN (falsy again). Starting from the third iteration, r is set to an integer which is non-zero if the difference between digit #3 and digit #2 is not equal to the difference between digit #2 and digit #1.

The number p is meeting the required criteria if and only if some() is falsy (all adjacent digits have the same difference) and the final value of r is 0 (there were at least 3 iterations). This gives !false / 0 === true / 0 === Infinity (truthy).

We may otherwise have:

• !true / r with r > 0 or r < 0, which gives false / r === 0 (falsy)
• !false / NaN, which gives true / NaN === NaN (falsy)

Halting condition

The recursion stops when p | q evaluates to 0. This is guaranteed to happen when both p and q reach values around 10²⁵ which are 84-bit long. Because JS has 52 bits of mantissa, the last 32 bits are zeroed. So, the 32-bit bitwise OR evaluates to 0.

Due to the fast growing rate of the sequence, this happens rather quickly.

Answer 4

Java 8, 151 144 140 136 130 bytes

(a,b)->{for(long n,m,d,p;;System.out.print(m>99&p==d?m+" ":""),m=a+b,a=b,b=m)for(m=n=a,d=p=10;n>9&d==p|p>9;d=n%10-(n/=10)%10)p=d;}

Infinite loop outputting the numbers when it finds them.
Try it online (times out after 60 sec).

136 bytes version with added 10¹⁰ limit (a<1e10):

(a,b)->{for(long n,m,d,p;a<1e10;System.out.print(m>99&p==d?m+" ":""),m=a+b,a=b,b=m)for(m=n=a,d=p=10;n>9&d==p|p>9;d=n%10-(n/=10)%10)p=d;}

Try it online.

Explanation:

(a,b)->{         // Method with two long parameters and no return-type
  for(long n,m,  //  Temp numbers
           d,p;  //  Current and previous differences
      a<1e10;    //  Loop as long as `a` is still below 10^10
      ;          //    After every iteration:
       System.out.print(
                 //     Print:
        m>99     //      If the number has at least three digits,
        &p==d?   //      and the previous and current differences are still the same
         m+" "   //       Print the current number with a space delimiter
        :        //      Else:
         ""),    //       Print nothing
                 //     Go to the next Fibonacci iteration by:
       m=a+b,    //      Setting the temp-number `m` to `a+b`
       a=b,      //      Replacing `a` with `b`
       b=m)      //      And then setting `b` to the temp number `m`
    for(m=n=a,   //   Set both `m` and `n` to `a`
        d=p=10;  //   Set both `d` and `p` to 10
        n>9      //   Inner loop as long as `n` has at least two digits,
        &d==p    //   and `p` and `d` are still the same,
         |p>9    //   or `p` is still 10
        ;        //     After every iteration:
         d=n%10-(n/=10)%10)
                 //      Set `d` to the difference between the last two digits of `n`
                 //      And integer-divide `n` by 10 at the same time
      p=d;}      //    Set the previous difference `p` to `d`

Answer 5

Jelly, 20 19 18 bytes

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

Try it online!

+ƝḢ;Ɗȷ¡ produces the first thousand (ȷ) terms in the series which will always be sufficient. I think there is probably a shorter way to do this. +ȷ¡ gets close but only works if the first term is zero.

I am assuming we can take in the two numbers in reverse which allows one byte to DIE.

If we aren't required to output either of the inputs:

Jelly, 15 bytes

>ȷ2ȧDIEƊ
+ṄÇ¡ß@

Try it online!

Answer 6

Octave, 91 90 83 bytes

Saved 7 bytes thanks to Luis Mendo!

@(t)eval"for i=3:99,if~diff(diff(+num2str(t(1))))disp(t(1))end,t=[t(2) sum(t)];end"

Try it online!

Well, it works!

eval with for loop inside to save a few bytes. Skipping colons and semicolons to save a few. Uses the fact that a vector is considered truthy iff all elements are non-zero to save any or all.

Other than that, it's pretty much a straight forward implementation of Fibonacci.

Answer 7

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

Answer 8

Haskell, 105 bytes

u%v|let s=u:scanl(+)v s=[n|n<-s,d<-[f(-).map fromEnum.show$n],length d>1,and$f(==)d]
f g=zipWith g=<<tail

Defines the operator (%) which returns an infinite list with all the solutions. To actually see the result on stdout we need to disable buffering (or run it in ghci or with runhaskell), try it online!

Explanation/Ungolfed

The function f is just a helper function that expects a binary function and a list, it applies the function g to all adjacent pairs. It's essentially the same as:

adjacent g xs = zipWith (tail xs) xs

The operator (%) is just a list comprehension that does some filtering (making sure that there are at least 3 digits & that the adjacent digits have the same distance):

u % v
  -- recursively define s as the "Fibonacci sequence" with f(0) = u and f(1) = v
  | let sequence = u : scanl (+) v sequence
  -- take all numbers from that sequence using the filters below
  = [ number | number <- sequence
  -- convert to string, get the ASCII codepoints and build a list of the adjacent differences
        , let differences = adjacent (-) . map fromEnum . show $ number
  -- numbers with > 3 digits have >= 2 adjacent digits (or rather differences of digits)
        , length differences > 1
  -- make sure all of these are equal by comparing them and reducing with logical and
        , and $ adjacent (==) differences
    ]

Answer 9

CJam, 55 bytes

q~{1$_99>"_`2\ew{{-}*}%""3,"?~_(+="0$p"*~;_@+_11_#<}g;;

Try it online!

My first CJam submission, not very short but a lot of fun. Any suggestions are welcome!

Answer 10

Stax, 26 24 bytes

Ç╕SôεPN^:·░ßⁿ {@ÿ}Ü╫╣1╣X

Run and debug it

Explanation

E{b+}99*L{E%2>|cd_E:-u%1=!C_Qf    # Full program, unpacked, implicit input
E                                 # Push all elements from array onto stack.
 {b+}99*L                         # Generate the first 99 numbers of the  Fibonacci sequence given the input
         {                   f    # Loop through all Fibonacci elements
          E                       # Array of decimal digit
           %2>                    # Does the array have at least 3 digits
              |c                  # Assume Truthy past this point
                d                 # discard top of stack
                 _E               # Copy the current element of the Fibonacci sequence and Digitize it
                  :-              # Pairwise difference of array.
                    :u            # Is there exactly 1 unique number
                        !C        # Flip the comparison, if truthy proceed
                          _Q      # Copy the current element of the Fibonacci sequence and Peek and print with a newline.

Not as short as I would like it and can probably be golfed a bit more, but it works.

Answer 11

Ruby, 79 bytes

->a,b{loop{a>99&&!(a.digits.each_cons(2).map{|a,b|a-b}|[])[1]&&p(a);a,b=b,a+b}}

Try it online!

Answer 12

Julia 0.6, 86 81 bytes

a<b=b>=0&&((n->n>99&&2>endof(∪(diff(digits(n))))&&println(n)).([a,b]);a+b<a+2b)

Try it online!

Pretty straightforward - check if input has at least 3 digits (n>99), then take the difference between each digit pair in the number (diff(digits(n))), check that the length of (endof) a unique set of (∪) those differences is 1 (i.e. all the differences are the same), and if so print the number. Do that for both the given numbers, then recursively call the function with the next two numbers.

(Unfortunately, it looks like ± has higher precedence than +, or else the final call could have been a+b±a+2b, saving 3 bytes.) Now overloads the < operator, thus saving on both the operator bytes and the precedence brackets. (Can't use < in our code though, so just rearranged endof(...)<2 to 2>endof(...)).

If some extraneous output is allowed, we can save 2 bytes using @show instead of println, printing n = 987 instead of just 987. We could even use dump for 1 byte lower than that, but dump prints the type information along with the value, so output will be Int64 987 instead of just 987.