18
\$\begingroup\$

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 . Shortest answer in each language wins.

\$\endgroup\$
7
  • \$\begingroup\$ Bonus points for finding(or outgolfing) my 10 byte Husk answer. \$\endgroup\$
    – Razetime
    Jan 28, 2021 at 15:10
  • 1
    \$\begingroup\$ Infinite lists! \$\endgroup\$
    – Razetime
    Jan 28, 2021 at 15:25
  • 1
    \$\begingroup\$ Hey, wait, you've changed your bonus, right? Didn't the original comment say you'd got a 9-byte Husk answer...? Or did I imagine it? I've been struggling to find it for the last few hours... \$\endgroup\$ Jan 28, 2021 at 16:08
  • 1
    \$\begingroup\$ yes, was a mistake. Sorry about that. \$\endgroup\$
    – Razetime
    Jan 28, 2021 at 16:10
  • 4
    \$\begingroup\$ For obvious reasons, decreasing consecutive Fibonacci numbers will yield the longest sequences \$\endgroup\$ Jan 28, 2021 at 17:11

24 Answers 24

8
\$\begingroup\$

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
```
\$\endgroup\$
9
  • 1
    \$\begingroup\$ It appears you are using the wrong encoding for xchg ax, bx (it should be 0x93) and you can use the flags from sub to trip the loop instead of that fat cmp ax, 0. \$\endgroup\$
    – EasyasPi
    Jan 28, 2021 at 12:41
  • \$\begingroup\$ Yeah. If you xchg a register with (e)ax, it should be one byte. If it isn't, you have a bad assembler 😂 \$\endgroup\$
    – EasyasPi
    Jan 28, 2021 at 12:49
  • \$\begingroup\$ @EasyasPi Ahh I see, I should have written xchg bx, ax! My assembler is indeed horrible. \$\endgroup\$
    – user99151
    Jan 28, 2021 at 13:01
  • 1
    \$\begingroup\$ Note that I didn't test that yet \$\endgroup\$
    – EasyasPi
    Jan 28, 2021 at 13:08
  • 1
    \$\begingroup\$ Lol no, it is jump if signed. Although it should be jl, my bad. Try it online! \$\endgroup\$
    – EasyasPi
    Jan 28, 2021 at 13:43
7
\$\begingroup\$

JavaScript (ES6), 24 bytes

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

Try it online!

\$\endgroup\$
7
\$\begingroup\$

convey, 39 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:

71/120 run

\$\endgroup\$
2
  • \$\begingroup\$ How much time do you spend on creating such a program? \$\endgroup\$
    – Danis
    Jan 29, 2021 at 19:05
  • 2
    \$\begingroup\$ @Danis About 10 minutes for the overall solution, then double that for shuffling parts around to golf it a bit, which can be a bit annoying as it's not a simple copy&paste for 2d text. (I really should implement that for the editor.) \$\endgroup\$
    – xash
    Jan 29, 2021 at 20:01
6
\$\begingroup\$

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)
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Parentheses can be omitted if they go up to the end/beginning of the line. (i.e. you can remove the last character from your code) \$\endgroup\$
    – Leo
    Jan 28, 2021 at 22:35
  • \$\begingroup\$ @Leo Thanks! Do you know what it gets parsed as without parentheses? I tried without them entirely and it just hung, presumably because of the infinite list. \$\endgroup\$
    – user
    Jan 28, 2021 at 22:41
  • \$\begingroup\$ I started replying here but then it got too big... I got some great news for you, come to the Husk chatroom :D \$\endgroup\$
    – Leo
    Jan 28, 2021 at 23:20
  • 1
    \$\begingroup\$ Super, and a great primer on fix and scan... \$\endgroup\$ Jan 29, 2021 at 8:36
5
\$\begingroup\$

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice. Some time ago, flags/options were counted too and labels could be empty (before sed 4.3), thus netting you 1 byte less. \$\endgroup\$
    – seshoumara
    Jan 28, 2021 at 19:38
  • \$\begingroup\$ @seshoumara Yes, the rules changed a while back so that sed -r may now be considered its own language, so I clarified that. I'll take the 2 bytes for the unnamed label though - thanks! \$\endgroup\$ Jan 29, 2021 at 17:27
  • \$\begingroup\$ I really love this \$\endgroup\$
    – Jonah
    Sep 10 at 13:56
5
\$\begingroup\$

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
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Very, very sorry, I mistook it as 9 bytes initally when generating my testcases: Try it online! \$\endgroup\$
    – Razetime
    Jan 28, 2021 at 16:12
4
\$\begingroup\$

Charcoal, 33 24 bytes

NθNηW‹⁰θ«⊞υω≦⁻θη≧⁻ηθ»ILυ

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:

NθNη

Input the initial values.

W‹⁰θ«

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.

»ILυ

Finally print the number of iterations.

\$\endgroup\$
4
\$\begingroup\$

Ruby, 25 bytes

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

Attempt This Online!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ You can even use fancy function overloads for the same byte count: ⁽-dḞ‡1<Ǒ \$\endgroup\$
    – Steffan
    Sep 10 at 18:27
  • 1
    \$\begingroup\$ Btw if you add the 2 flag you can get 7: ⁽-Ḟ±ċTh \$\endgroup\$
    – Steffan
    Sep 10 at 18:30
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
2
\$\begingroup\$

Python 3, 29 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

PowerShell, 46 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
2
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ 62 bytes by generalising the 0 case and using an operator as the predicate name \$\endgroup\$
    – Jo King
    Sep 12 at 11:49
  • \$\begingroup\$ Or 32 bytes as a predicate \$\endgroup\$
    – Jo King
    Sep 12 at 12:09
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

PARI/GP, 25 bytes

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

Attempt This Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.