Get the length of a Sumac Sequence

Question

Heavily based on this closed challenge.

Codidact post, Sandbox

Description

A Sumac sequence starts with two non-zero integers \$t_1\$ and \$t_2.\$

The next term, \$t_3 = t_1 - t_2\$

More generally, \$t_n = t_{n-2} - t_{n-1}\$

The sequence ends when \$t_n ≤ 0\$. All values in the sequence must be positive.

Challenge

Given two integers \$t_1\$ and \$t_2\$, compute the Sumac sequence, and output its length.

If there is a negative number in the input, remove everything after it, and compute the length.

You may take the input in any way (Array, two numbers, etc.)

Test Cases

(Sequence is included for clarification)

[t1,t2]   Sequence          n
------------------------------
[120,71]  [120,71,49,22,27] 5
[101,42]  [101,42,59]       3
[500,499] [500,499,1,498]   4
[387,1]   [387,1,386]       3
[3,-128]  [3]               1
[-2,3]    []                0
[3,2]     [3,2,1,1]         4

Scoring

This is code-golf. Shortest answer in each language wins.

Answer 1

x86 machine code (8086), 15 13 bytes

-2 bytes thanks to @EasyasPi.

00000000  31 C9 48 7C 07 40 41 29-D8 93 EB F6 C3            1.H|.@A).....

Callable function.

Expects AX = t1, BX = t2. Output is to CX.

Disassembly:

31C9          XOR     CX,CX    ; Set CX to 0
          LOP:
48            DEC     AX       ; --AX
7C07          JL      END      ; If AX < 0, jump to 'END'
40            INC     AX       ; ++AX
41            INC     CX       ; ++CX
29D8          SUB     AX,BX    ; AX -= BX
93            XCHG    BX,AX    ; Swap AX and BX
EBF6          JMP     LOP      ; Jump to tag 'LOP'
          END:
C3            RET              ; Return to caller

Example run

Tested with DOS debug:

-r
AX=0078  BX=0047  CX=0000  DX=0000  SP=FFEE  BP=0000  SI=0000  DI=0000
DS=0B17  ES=0B17  SS=0B17  CS=1000  IP=0000   NV UP EI PL NZ NA PO NC
1000:0000 31C9          XOR     CX,CX
-t

AX=0078  BX=0047  CX=0000  DX=0000  SP=FFEE  BP=0000  SI=0000  DI=0000
DS=0B17  ES=0B17  SS=0B17  CS=1000  IP=0002   NV UP EI PL ZR NA PE NC
1000:0002 48            DEC     AX
...
-t

AX=FFFA  BX=0020  CX=0005  DX=0000  SP=FFEE  BP=0000  SI=0000  DI=0000
DS=0B17  ES=0B17  SS=0B17  CS=1000  IP=000C   NV UP EI NG NZ NA PE CY
1000:000C C3            RET
```

Answer 2

JavaScript (ES6), 24 bytes

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

Try it online!

Answer 3

convey, ³⁹ 37 bytes

-2 thanks to Jo King!

{0(>>"!+?`}
,?"-v>^0^
^>>", 8~^
^<<<<

Try it online!

The Sumac Sequence gets calculated in the lower left part, with { taking the input and copying the sequence into ( via " (copy):

{ (
,?"-v
^>>",
^<<<<

The sequence then gets converted to – is it greater than 0 0(? Taking ! that by itself, only 1s gets passed through into +:

0(>>"!+
    >^

There the accumulator loops around, waiting 8 steps 8~ so both the generating loop and the accumulator loop have the same speed. If there is an input waiting for +, ? pushes the accumulator into +, otherwise – if the sequence stopped thanks to a 0 – it gets pushed into the output }.

 +?}
 0^
8~^

Everything put together:

Answer 4

05AB1E, 7 bytes

λ-}(d1k

Try it online! or Try all cases!

Commented:

λ }      # start a recursive environment:
         #   this produces an infinite sequence starting with input
 -       #   and calculates t_n according to t_n = t_{n-2} - t_{n-1}
   (     # negate every value
    d    # for every value: is it non-negative?
     1k  # find the first index of a 1 (smallest n such that -t_n >= 0)

Answer 5

Husk, 16 13 12 11 9 bytes

Saved 1 2 4 bytes thanks to Leo!

L↑>0ƒ·:G-

Try it online!

I wish it would parse the correct function without parentheses. Leo found a 9-byte solution that doesn't use parentheses or even composition!

This my first time using ƒ (fix from Haskell).

I'm told fix looks something like this:

fix :: (a -> a) -> a
fix f = let x = f x in x

Supposing the first argument (²) is 120, and the second argument (⁰) is 71, f (o:²G-⁰) would be something like prevSequence -> 120 : scanl (-) 71 prevSequence. So the x from above would become

x = 120 : scanl (-) 71 x
x = 120 : 71 : scanl (-) (120 - 71) (drop 1 x) //where drop 1 x is 71 : scanl (-) ...
x = 120 : 71 : 49 : scanl (-) (71 - 49) (drop 2 x)
...

and so on until it makes an infinite sequence.

Then ↑>0 takes (↑) while each element is positive, and L finds the length of that sequence.

Answer 6

sed -r 4.2.2, 44

• Thanks to @seshoumara for -2 bytes

:
s/^(1+) \1(1+)/\2 &/
t
s/1+ ?/1/g
s/.*-1//

Try it online!

Explanation

The inputs are space-separated unary. Term 2 is given before term 1. E.g. (5, 3) would be 111 11111; (5, -3) would be -111 11111.

• Line 1: loop label (unnamed - works in 4.2.2)
• Line 2: generate term n+2 by removing term n+1 from term n; Prefix term n+2 to the beginning of the pattern space
• Line 3: if the substitution on line 2 was successful, jump back to the loop label
• Line 4: Count the terms by replacing each term (followed by optional space) with 1
• Line 5: Handle negative inputs
• End of program: Implicit output of counter

Answer 7

Husk, 10 bytes

L↑>0¡(→Ẋ`-

Try it online!

...still haven't managed to get Razetime's (edit: non-existant) 9-byte answer (unless zero-based indexing is Ok), but I'm trying... (edit: I've now given-up).
(Edit 2: ...but a 9-byte answer has now been found by user & Leo!)

Commented code:

L            # length of
 ↑>0         # initial elements that are greater than zero of
    ¡(       # infinite list by repeatedly appending list with
      →      # last element of
       Ẋ`-   # pairwise differences between elements of list so far

Answer 8

Charcoal, 33 24 bytes

ＮθＮηＷ‹⁰θ«⊞υω≦⁻θη≧⁻ηθ»ＩＬυ

Try it online! Link is to verbose version of code. Edit: Saved 9 bytes when @Razetime pointed out I was using an inefficient algorithm. Explanation:

ＮθＮη

Input the initial values.

Ｗ‹⁰θ«

Repeat while the first value is positive.

⊞υω

Keep count of the number of iterations.

≦⁻θη

Subtract the second number from the first number, storing the result in the second number.

≧⁻ηθ

Subtract that result from the first number, resulting in the original second number.

»ＩＬυ

Finally print the number of iterations.

Answer 9

Ruby, 25 bytes

f=->a,b{a>0?f[b,a-b]+1:0}

Attempt This Online!

Answer 10

Vyxal 2, 20 8 7 bytes

⁽-Ḟ±ċTh

Try it Online!

Wow it's a been a while since I posted this, and a lot of things have been added/changed since.

Explained

⁽-dḞ±ċTh
⁽-d       # lambda x, y: x - y
   Ḟ      # Using the input as an initial vector, apply the above lambda infinitely, using all previously generated items as its stack
    ±ċ    # Is the sign of each item not 1?
      Th  # First occurrence of 1

Answer 11

TI-BASIC, 27 Bytes

While A>0
A-B->B
A-B->A
N+1->N
End
N

Takes t1 and t2 as input in A and B. Nothing fancy, the key is that when A is updated, B is the previous t1-t2, so the third line is able to recover t2 via t1-(t1-t2)->A without juggling a 3rd variable. There's a way to generate the sequence in 27 bytes as well with input as a list in Ans and dim( calls, but it proves too complex to trim out negative input and retrieve the true length of the sequence.

Answer 12

Raku, 20 bytes

-4 bytes thanks to Jo King

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

Try it online!

The parenthesized expression is a list where the first terms are the two arguments to the function (|@_), successive terms are generated by subtracting the previous two terms (* - *), and the list stops just before the term (...^) for which zero is greater than or equal to it (0 >= *). Then the + operator converts that list to a number, its length.

Answer 13

Retina 0.8.2, 31 bytes

\d+
$*
+`(1+)¶\1$
$&¶$%`
\G1+¶?

Try it online! Takes the integers on separate lines but link includes test suite that splits on comma for convenience. Explanation:

\d+
$*

Convert to unary. Note that the signs are ignored at this stage, so that if the first number is negative, the next stage uselessly computes the sequence as if it was positive.

+`(1+)¶\1$
$&¶$%`

Compute additional terms until the last number is zero or greater than the absolute value of the previous number.

\G1+¶?

Count the number of leading positive terms.

Answer 14

C (gcc), 27 bytes

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

This is the C equivalent of Arnauld's JavaScript answer

Try it online!

A and that's actually the work of att. My function was initially 28 bytes and non-reusable.

Answer 15

Python 3, 29 bytes

f=lambda a,b:a>0and-~f(b,a-b)

Try it online!

Answer 16

PowerShell, 46 bytes

param($a,$b)for(;$a-gt0;$i++){$a-=$b=$a-$b}+$i

Try it online!

Answer 17

Python 3, 141 125 bytes

def F(I):
 i=1
 if I[0]<0:
  return 0
 if I[1]<0:
  return 1
 while I[i-1]-I[i]>0:
  I.append(I[i-1]-I[i])
  i+=1
 return i+1

Thanks to @Razetime for pointing out the sequence itself didn't need to be returned.

Answer 18

Prolog (SWI), 102 93 bytes

d(A,B,C):-B<1,write(C);E is C+1,F is A-B,d(B,F,E).
:-read(A),(A<0,write(0);read(B),d(A,B,1)).

Try it online!

Answer 19

MathGolf, 12 bytes

æ`‼->▲](mσb=

Takes the two inputs in reversed order.

Try it online.

Explanation:

     ▲        # Do-while true with pop,
æ             # using the following four commands:
 `            #  Duplicate the top two values on the stack
  ‼           #  Apply the following two commands separated on the current stack:
   -          #   Subtract the top two items from one another
    >         #   Check if the second top item is larger than the top item
      ]       # After the do-while, wrap everything on the stack into a list
       (      # Decrease each value by 1
        m     # Map over each value:
         σ    #  And take its sign: 1 if >0; 0 if ==0; -1 if <0
           =  # And then get the first 0-based index in this list of
          b   # value -1
              # (after which the entire stack joined together is output implicitly)

Answer 20

R, 43 37 bytes

Edit: -6 bytes after peeking at Arnauld's answer: please upvote that one!

f=function(a,b)`if`(a>0,1+f(b,a-b),0)

Try it online!

Answer 21

Batch, 65 bytes

@set/aa=%1-%2,b=%3+1,c=b-1
@if %1 gtr 0 %0 %2 %a% %b%
@echo %c%

c is provided so that the output is zero if the first parameter is negative, otherwise @echo %3 would work. (On the first pass %3 is the empty string, but b=+1 still computes the correct value for b. c=%3+0,b=c+1 would also work.)

Answer 22

C (gcc), 42 35 bytes

Saved 7 bytes thanks to Neil!!!

n;f(a,b){for(n=0;a>0;++n)a-=b=a-b;}

Try it online!

Answer 23

Jelly, 9 bytes

Rȧ_@Rп@L

Try it online!

As posted on Codidact

Takes \$t_1\$ on the left and \$t_2\$ on the right. R}ȧ_@RпL works given the arguments in the opposite order.

R            Ascending range from 1 to t_1 (truthy if positive),
 ȧ           and:
     п      collecting intermediate results, loop while
    R        positive
       @     on the reversed arguments:
  _          subtract
   @         the first from the second.
        L    Return the length of the conjunction.

¿ and family, given a dyad, replace the right argument with the previous left argument on each successive iteration. This is incredibly bothersome for some tasks, but perfect for working with this exact kind of sequence.

Answer 24

PARI/GP, 25 bytes

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

Attempt This Online!