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

• Closely related, if not a duplicate Nov 23, 2017 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? Nov 23, 2017 at 15:32
• Is it guaranteed that t1 and t2 are >= 0? Nov 23, 2017 at 15:33
• @Blacksilver Huh? What's that bonus exactly? Bonus are generally discouraged anyway Nov 23, 2017 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, 2017 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 Nov 23, 2017 at 17:19
• @WheatWizard That's most probably because I suck at explanations. :P Nov 23, 2017 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..? Nov 23, 2017 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)&


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!

• FYI, the regular boring approach is less than half as long. Nov 23, 2017 at 18:03
• @totallyhuman boring indeed... you can save a byte #1 to # Nov 23, 2017 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 Nov 24, 2017 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. Nov 23, 2017 at 15:40
• What if a<0? (1 more to go) Nov 23, 2017 at 15:48
• Update: you are no longer required to support negative input, but it's cool if you do. Nov 23, 2017 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, DE = t, A is the counter
Loop:   bit 7,h
ret nz          ; stop if HL is negative
inc a
sbc hl,de       ; HL = t, DE = t
ex de,hl        ; HL = t, DE = t
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, 2017 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. Nov 24, 2017 at 10:24
• Yeah; the 2 result is really just a thing with my program. Nov 24, 2017 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? Nov 24, 2017 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. Nov 24, 2017 at 6:03
• @Potato44 indeed, but I did not have time yesterday to do it, but I did it now and saved 10 bytes. Nov 24, 2017 at 6:19
• 59 bytes Jan 14, 2020 at 2:05

# 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>*)} Nov 24, 2017 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>*... Nov 24, 2017 at 16:27
• The space is needed so it doesn't get confused with %h<a>` Nov 25, 2017 at 0:35