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 '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? Nov 23 '17 at 15:32
• Is it guaranteed that t1 and t2 are >= 0? Nov 23 '17 at 15:33
• @Blacksilver Huh? What's that bonus exactly? Bonus are generally discouraged anyway 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

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 '17 at 17:19
• @WheatWizard That's most probably because I suck at explanations. :P 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).
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 '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)&

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 '17 at 18:03
• @totallyhuman boring indeed... you can save a byte #1 to # 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 Nov 24 '17 at 18:35

Python 2, 29 bytes

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

Try it online!

JavaScript (ES6), 24 bytes

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 '17 at 15:40
• What if a<0? (1 more to go) Nov 23 '17 at 15:48
• Update: you are no longer required to support negative input, but it's cool if you do. 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, 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 '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. Nov 24 '17 at 10:24
• Yeah; the 2 result is really just a thing with my program. 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? 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. 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. Nov 24 '17 at 6:19
• 59 bytes Jan 14 '20 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 '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>*`... Nov 24 '17 at 16:27
• The space is needed so it doesn't get confused with %h<a> Nov 25 '17 at 0:35