Length of a Sumac sequence [closed]

Question

A Sumac sequence starts with two integers: t₁ and t₂.

The next term, t₃, = t₁ - t₂

More generally, t_n = t_n-2 - t_n-1

The sequence ends when t_n < 0.

Your challenge: Write a program or function that prints the length of a Sumac sequence, starting with t₁ and t₂.

• t₁ and t₂ are integers within your language's range.
• Standard loopholes apply.

Test cases

t1  t2       sumac_len(t1,t2)

120  71      5
101  42      3
500  499     4
387  1       3

Bonus street cred:

3    -128    1
-314 73      2

This is code-golf, so shortest answer in bytes wins.

Answer 1

Husk, 8 bytes

→V<¡oG-↔

Takes input as a 2-element list. Try it online!

Explanation

→V<¡oG-↔  Implicit input, say p=[101,42]
   ¡      Iterate on p:
       ↔    Reverse: [42,101]
    oG-     Cumulative reduce by subtraction: [42,59]
          Result is infinite list [[101,42],[42,59],[59,-17],[-17,76],[76,-93]...
 V<       Find the first index where adjacent pairs are lexicographically increasing.
          In our example [42,59] < [59,-17], so this gives 2.
→         Increment: 3

Answer 2

Haskell, 22 bytes

a#b|b<0=1|c<-a-b=1+b#c

Try it online!

I really wish there was a way to pattern match for a negative number...

Explanation

a#b|b<0=1|c<-a-b=1+b#c

a#b                     -- define a function (#) that takes two arguments a and b
   |b<0                 -- if b is negative...
       =1               -- return 1
         |              -- otherwise...
          c<-a-b        -- assign a-b to c...
                =  b#c  -- and return the result of (#) applied to b and c...
                 1+     -- incremented by 1

Answer 3

Husk, 12 11 bytes

V<0t¡ȯF-↑2↔

Try it online!

Takes the bonus street cred for whatever that's worth.

Explanation

    ¡ȯ       Repeatedly apply the function to the right to the list of all
             previous values and collect the results in an infinite list.
          ↔  Reverse the list of previous results.
        ↑2   Take the first two values (last two results).
      F-     Compute their difference (using a fold).
   t         Discard the first element.
V<0          Find the first index of a negative value.

Answer 4

Ruby, 29 bytes

->a,b{(1..a).find{a<b=a-a=b}}

Try it online!

Answer 5

MATL, 13 bytes

`yy-y0<~]N2-&

This handles negative inputs (last two test cases).

Try it online! Or verify all test cases.

Explanation

`        % Do...while
  yy     %   Duplicate top two elements. Implicit inputs first time
  -      %   Subtract
  y      %   Duplicate from below: push previous term
  0<~    %   Is it 0 or greater? This is the loop condition
]        % End. Proceed with next iteration if top of the stack is true
N        % Push number of elements in stack
2-       % Subtract 2
&        % Specify that the next function, namely implicit display, should
         % only display the top of the stack

Answer 6

Brain-Flak, 142 90 bytes

((()){{}<(({}({}))[({}[{}])({})])([(({})<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}>}<>)

Try it online!

Not very short. Takes input backwards.

Explanation

(
 (())   #Push 1
 {      #Until 0
  {}    #Pop (+1 to counter)
  <(({}({}))[({}[{}])({})])  #tn = tn-1 - tn-2
  ([(({})<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}>  #Greater than 0?
 }      #End loop
 <>     #Get rid of everything
)       #Push result

Answer 7

05AB1E, 11 bytes

[DŠ-D0‹#]NÌ

Try it online!

Explanation

Takes input as t2, t1

[             # start a loop
 DŠ           # duplicate top of stack and move it down 2 positions
   -          # subtract the top 2 values
    D0‹#      # if a copy of the top value is negative, break loop
        ]     # end loop
         NÌ   # push iteration index+2

Answer 8

Mathematica, 55 bytes

(t=1;While[Last@LinearRecurrence[{-1,1},#,t++]>0];t-2)&

Try it online!

and now the regular boring approach by @totallyhuman

Mathematica, 25 bytes

If[#2<0,1,1+#0[#2,#-#2]]&

Try it online!

Answer 9

J, 22 bytes

[:#({:,-/)^:(0<{:)^:a:

How it works:

                  ^:a: - Repeat until the result stops changing, store the results in a list
          ^:(0<{:)     - repeat if the second term is positive
   ({:,-/)             - makes a tuple (second, first minus second)
[:#                    - number of elements in the list ([: caps the fork)

Try it online!

Answer 10

C (gcc), 32 27 26 bytes

-5 bytes thanks to totallyhuman's abuse of gcc (seems to work on tcc too)
-1 byte thanks to PrincePolka

f(a,b){a=b<0?:1+f(b,a-b);}

Try it online!

Answer 11

Python 2, 29 bytes

f=lambda a,b:b<0 or-~f(b,a-b)

Try it online!

Returns True instead of 1.

Answer 12

JavaScript (ES6), 24 bytes

Returns true instead of 1.

f=(a,b)=>b<0||1+f(b,a-b)

Test cases

f=(a,b)=>b<0||1+f(b,a-b)

console.log(f(120,  71  )) //    5
console.log(f(101,  42  )) //    3
console.log(f(500,  499 )) //    4
console.log(f(387,  1   )) //    3

console.log('Bonus street cred:')
console.log(f(3,    -128)) //    1
console.log(f(-314, 73 ))  //    2

Answer 13

Pyth, 11 bytes

This is a recursive function that takes two arguments, G and H. The link is slightly modified in order to actually call the function on the given input.

M|<H0hgH-GH

Test suite.

Answer 14

APL (Dyalog), 23 bytes

2∘{0>-/⍵:⍺⋄(⍺+1)∇-⍨\⌽⍵}

Try it online!

How?

2∘ - with an initial accumulator of 2,

-/⍵ - if the next term

0> - is below 0,

⍺ - return the accumulator. otherwise,

(⍺+1) - increase the accumulator

∇ - and recurse with

-⍨\⌽⍵ - the last two items reversed and differenced.

      {⍵} 8 2
8 2
      {⌽⍵} 8 2
2 8
      {-⍨\⌽⍵} 8 2
2 6

Answer 15

Java (OpenJDK 8), 44 bytes

int f(int a,int b){return b<0?1:1+f(b,a-b);}

Try it online!

Shortest iterative I found (50 bytes)

(a,b)->{int c=1;for(;b>=0;c++)b=a-(a=b);return c;}

Try it online!

Answer 16

dc, 24 bytes

?[dsb-1rlbrd0<a]dsaxz1-p

Try it online!

Explanation

?                         # read input                | 71 120
 [dsb-1rlbrd0<a]          # push string               | [string] 71 120
                dsa       # copy top to register a    | [string] 71 120
                   x      # execute the string        | -5 27 1 1 1 1
                    z     # push length of stack      | 6 -5 27 1 1 1 1
                     1-   # decrement top by 1        | 5 -5 27 1 1 1 1
                       p  # print top

 # string in register a:

  dsb                     # copy top to register b    | 71 120
     -                    # subtract                  | 49
      1                   # push 1                    | 1 49
       r                  # swap top two elements     | 49 1
        lb                # load register b           | 71 49 1
          r               # swap top two elements     | 49 71 1
           d0<a           # if top < 0 execute register a

Answer 17

Z80 Assembly, 10 bytes

This version attempts to do the "street cred" version of the task. However, for the suggested test case where t1=-314, t2=73 this program produces answer "0", which, frankly, makes a little bit more sense than "2".

SumacLen:
        xor a           ; HL = t[1], DE = t[2], A is the counter
Loop:   bit 7,h
        ret nz          ; stop if HL is negative
        inc a
        sbc hl,de       ; HL = t[3], DE = t[2]
        ex de,hl        ; HL = t[2], DE = t[3]
        jr Loop

The test program for ZX Spectrum 48K written using Sjasmplus assembler can be downloaded here. A compiled snapshot is also available.

Answer 18

Java (OpenJDK 8), 85 75 bytes

(b,c)->{int d,k=1;for(;;){if(c<0)break;else{d=c;c=b-c;b=d;k++;}}return k;};

Try it online!

ungolfed:

(b,c)->{
    int d,k=1;
    for(;;){
        if(c<0)
            break;
        else{
            d=c;
            c=b-c;
            b=d;
            k++;
        }
    }
    return k;
};

Answer 19

Common Lisp, 59 42 bytes

(defun f(a b)(if(< b 0)1(1+(f b(- a b)))))

Try it online!

Answer 20

Perl 6, 24 19 bytes

-5 bytes thanks to Brad Gilbert b2gills.

{+(|@_,*-*...^0>*)}

Try it online!

Explanation: The whole thing in the parentheses is exactly the sequence in question (|@_ are the first 2 terms (= the two parameters), *-* is a function that takes two arguments and returns their difference, and * <0 is the stopping condition (term less than 0). We omit the last term with ^ after the ...). We then force the numerical context by the + operator, which yields the length of the sequence.