# Length of a Sumac sequence [closed]

A Sumac sequence starts with two integers: t1 and t2.

The next term, t3, = t1 - t2

More generally, tn = tn-2 - tn-1

The sequence ends when tn < 0.

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

• t1 and t2 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.

## closed as unclear what you're asking by xnor, Laikoni, Rɪᴋᴇʀ, Erik the Outgolfer, MD XFNov 25 '17 at 1:15

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Closely related, if not a duplicate – Mr. Xcoder Nov 23 '17 at 15:32
• This seems to be a good challenge, but is a little unclear. Are we supposed to take t1 and t2 as input? And what is i in the test cases? – caird coinheringaahing Nov 23 '17 at 15:32
• Is it guaranteed that t1 and t2 are >= 0? – user202729 Nov 23 '17 at 15:33
• @Blacksilver Huh? What's that bonus exactly? Bonus are generally discouraged anyway – Luis Mendo Nov 23 '17 at 15:59
• Do we have to handle t_1 = t_2 = 0? Does "bonus street cred" mean we don't have to handle t_1 < 0 or t_2 < 0? – xnor Nov 23 '17 at 17:16

# 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


# 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

• I think the explanation is less clear than the code itself for once. :P – Sriotchilism O'Zaic Nov 23 '17 at 17:19
• @WheatWizard That's most probably because I suck at explanations. :P – totallyhuman Nov 23 '17 at 17:28

## 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.


# Ruby, 29 bytes

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


Try it online!

• a<b=a-a=b ...How does Ruby parse that..? – totallyhuman Nov 23 '17 at 16:15

# MATL, 13 bytes

yy-y0<~]N2-&


This handles negative inputs (last two 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


# 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


# 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


# Mathematica, 55 bytes

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


and now the regular boring approach by @totallyhuman

# Mathematica, 25 bytes

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


Try it online!

• FYI, the regular boring approach is less than half as long. – totallyhuman Nov 23 '17 at 18:03
• @totallyhuman boring indeed... you can save a byte #1 to # – J42161217 Nov 23 '17 at 18:07

# 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!

# C (gcc), 3227 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!

• 26 bytes since, b<0 evaluates to 1, change ?1:1 to ?:1 – PrincePolka Nov 24 '17 at 18:35

# Python 2, 29 bytes

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


Try it online!

Returns True instead of 1.

# 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

• @totallyhuman Then you would need f(b)(a-b) so no saving. – Mr. Xcoder Nov 23 '17 at 15:40
• What if a<0? (1 more to go) – user202729 Nov 23 '17 at 15:48
• Update: you are no longer required to support negative input, but it's cool if you do. – SIGSTACKFAULT Nov 23 '17 at 16:00

# 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.

# 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


# 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!

# 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


# 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.

• Presumably the non-bonus version uses Loop: ret c instead? – Neil Nov 24 '17 at 10:14
• Yes, checking the sign bit of H would no longer be needed. "bit 7,h" can be removed and "ret nz" replaced by "ret c", with "inc a" moving just in front of it. 8 bytes altogether. – introspec Nov 24 '17 at 10:24
• Yeah; the 2 result is really just a thing with my program. – SIGSTACKFAULT Nov 24 '17 at 12:23
• Do you mean that 0 is an acceptable answer for that test case? Or do you mean that it would be better to modify my program to output 2? – introspec Nov 24 '17 at 13:04

# 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;
};

• I believe this would be shorter as a lambda. – Potato44 Nov 24 '17 at 6:03
• @Potato44 indeed, but I did not have time yesterday to do it, but I did it now and saved 10 bytes. – Luca H Nov 24 '17 at 6:19

# Common Lisp, 59 42 bytes

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


Try it online!

# 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.

• {+(|@_,*-*...^0>*)} – Brad Gilbert b2gills Nov 24 '17 at 16:15
• @BradGilbertb2gills: Thank you. I had a large break with golfing, so I'm a bit rusty. What I don't get, though, is why you must put the space in * <0*, but why you don't need it in 0>*... – Ramillies Nov 24 '17 at 16:27
• The space is needed so it doesn't get confused with %h<a>` – Brad Gilbert b2gills Nov 25 '17 at 0:35