13
\$\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 at 15:10
  • 1
    \$\begingroup\$ Infinite lists! \$\endgroup\$
    – Razetime
    Jan 28 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 at 16:08
  • 1
    \$\begingroup\$ yes, was a mistake. Sorry about that. \$\endgroup\$
    – Razetime
    Jan 28 at 16:10
  • 4
    \$\begingroup\$ For obvious reasons, decreasing consecutive Fibonacci numbers will yield the longest sequences \$\endgroup\$ Jan 28 at 17:11

21 Answers 21

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 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 at 12:49
  • \$\begingroup\$ @EasyasPi Ahh I see, I should have written xchg bx, ax! My assembler is indeed horrible. \$\endgroup\$
    – user99151
    Jan 28 at 13:01
  • 1
    \$\begingroup\$ Note that I didn't test that yet \$\endgroup\$
    – EasyasPi
    Jan 28 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 at 13:43
6
\$\begingroup\$

JavaScript (ES6), 24 bytes

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

Try it online!

\$\endgroup\$
6
\$\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\$
4
  • \$\begingroup\$ How much time do you spend on creating such a program? \$\endgroup\$
    – Danis
    Jan 29 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 at 20:01
  • \$\begingroup\$ 37 bytes \$\endgroup\$
    – Jo King
    Feb 1 at 4:18
  • \$\begingroup\$ @JoKing Neatly packed – thanks again! \$\endgroup\$
    – xash
    Feb 1 at 15:50
5
\$\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\$
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\$

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 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 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 at 23:20
  • 1
    \$\begingroup\$ Super, and a great primer on fix and scan... \$\endgroup\$ Jan 29 at 8:36
4
\$\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
  • 1
    \$\begingroup\$ Very, very sorry, I mistook it as 9 bytes initally when generating my testcases: Try it online! \$\endgroup\$
    – Razetime
    Jan 28 at 16:12
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\$

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\$
2
  • 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 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 at 17:27
3
\$\begingroup\$

Vyxal, 20 bytes

:£{:0>A|:¯tJ}L‹¥h0>*

Try it Online!

It's long for a lack of better algorithm.

Takes input as a list of t1, t2. Note that you might need to hardcode the input in the header if you try it online...there's a bug with the safe evaluation of input (it works normal in the offline interpreter though)

Explained

:£{:0>A|:¯tJ}L‹¥h0>*
:£                    # Store a copy of the input in the register
  {:0>A|              # While every item in the input list is bigger than 0: 
        :¯t           #     Take the deltas of the input list
           J          #     And join it with the input list.
            }L‹       # Push the length of the input list - 1
               ¥h0>   # Check if the first item in the list is bigger than 0
                   *  # Perform a kind of logical and with the two values
\$\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\$
10
  • 2
    \$\begingroup\$ This is invalid. The function isn't re-runnable as you have to externally re-initialise i=0. You have to do something like this for 47 bytes: i;f(a,b){i=0;g(a,b);}g(a,b){i++,a>0&&g(b,a-b);}I tried it and found a for loop shorter. \$\endgroup\$
    – Noodle9
    Jan 28 at 14:12
  • 1
    \$\begingroup\$ @Noodle9 I added a note and will try to post something shorter than the 47 bytes code. Thank you. \$\endgroup\$ Jan 28 at 14:59
  • \$\begingroup\$ No they have to be self contained, nothing should be outside of the function. But the resetting i=0; is not part of the function per se, as you can see from this program. The resetting is part of a program that needs to use the function many times, but it's stated nowhere that you can create functions only if you need to call them multiple times. \$\endgroup\$ Jan 28 at 15:12
  • \$\begingroup\$ By that argument, anything could be set outside the function. You're using i to store and calculate the function's output, how's that exempt? \$\endgroup\$
    – Noodle9
    Jan 28 at 15:14
  • 3
    \$\begingroup\$ You're overcomplicating it. 27 bytes, with the correct offset. \$\endgroup\$
    – att
    Jan 28 at 18:35
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
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\$

Python 3, 29 bytes

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

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\$
2
  • 1
    \$\begingroup\$ You can simply write a-=b=a-b; making t unnecessary. \$\endgroup\$
    – Neil
    Jan 29 at 11:21
  • \$\begingroup\$ @Neil That's a good one - thanks! :D \$\endgroup\$
    – Noodle9
    Jan 29 at 11:42
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\$
1
\$\begingroup\$

VBScript, 57 bytes

a=101:b=42
Do
b=a-b
a=a-b
i=i+1
Loop While (a>0)
MsgBox i

This will work in VBA too, just wrap inside a Main() Sub

\$\endgroup\$
1
  • \$\begingroup\$ Where are you taking input from? Standard input methods does not allow variables. \$\endgroup\$
    – Razetime
    Apr 11 at 3:38

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.