title: Detect round trips on a hyperbolic grid

text:
# Question
Title: Detect round trips on a hyperbolic grid
You're driving a car in an infinite city whose blocks are pentagons arranged in the order-4 pentagonal tiling. At each step, you proceed to the next intersection and choose whether to continue left, right, or straight. A sequence of choices that returns you to your initial state (street segment and direction) is called a *round trip*.

Write a function (or program) that takes a string of `L`/`R`/`S`s and returns (or outputs) one of two values, indicating whether the input represents a round trip.

Examples:

```
LLLLL -> yes (this is a drive around one pentagonal block)
LLLLSRRRRS -> yes
SRRSRRSRRSRR -> yes
(empty sequence) -> yes
R -> no
LLLLLL -> no (starts with a round trip but leaves initial state)
SLLLLR -> no (returns to initial street but opposite direction)

```

(Note that `L` and `R` are not in-place rotations; every move includes entering *and exiting* the next intersection.)

# Answer
# Python, 259 bytes

```
from numpy import*
k=kron
u=lambda x:fromiter(base_repr(x,3),int).reshape(4,4)-1
s=k(u(25952008),u(27752297))+k(u(21543856),u(18501071))
t=k(u(21169798),i:=eye(4,4,0,object))
a=b=2*k(i,i)
for c in input():b=[s@t,s,s@t@t@t][-ord(c)%4]@b//2
print(all(a*a==b*b))

```

Attempt This Online!

### How it works

Uses only big integer linear algebra. This is probably not the golfiest solution method, but OP said they’re interested in this approach.

The rigid motions of the hyperbolic plane are isomorphic to \\$\mathrm{PSL}(2, \mathbb R)\\$, which can be represented by 2×2 matrices acting on \\$\mathbb R^2\\$.

\begin{gather\*} S = \begin{bmatrix} \frac1{\sqrt 2}(-\sqrt φ + φ + \sqrt φ^3) & 0 \\ 0 & \frac1{\sqrt 2}(\sqrt φ + φ - \sqrt φ^3) \end{bmatrix}, \\ T = \begin{bmatrix} \frac1{\sqrt2} & -\frac1{\sqrt2} \\ \frac1{\sqrt2} & \frac1{\sqrt2} \end{bmatrix}, \quad L = ST, \quad R = ST^3. \end{gather\*}

However, in the hyperbolic plane, floating-point errors accumulate exponentially with distance, so we need a way to do the same calculation exactly. For our purposes, we only need to work in the 16-dimensional sublattice \\$M\mathbb Z^{16} ⊂ \mathbb R^2\\$ generated by the columns of

$$M = \left\[\begin{smallmatrix} 1 & \sqrt φ & φ & \sqrt φ^3 & \frac{1}{\sqrt 2} & \frac{\sqrt φ}{\sqrt 2} & \frac{φ}{\sqrt 2} & \frac{\sqrt φ^3}{\sqrt 2} & 0 & 0 & 0 & 0 & -\frac{1}{\sqrt 2} & -\frac{\sqrt φ}{\sqrt 2} & -\frac{φ}{\sqrt 2} & -\frac{\sqrt φ^3}{\sqrt 2} \\ 0 & 0 & 0 & 0 & \frac{1}{\sqrt 2} & \frac{\sqrt φ}{\sqrt 2} & \frac{φ}{\sqrt 2} & \frac{\sqrt φ^3}{\sqrt 2} & 1 & \sqrt φ & φ & \sqrt φ^3 & \frac{1}{\sqrt 2} & \frac{\sqrt φ}{\sqrt 2} & \frac{φ}{\sqrt 2} & \frac{\sqrt φ^3}{\sqrt 2} \end{smallmatrix}\right\].$$

In order for \\$L, S, R\\$ to act on this lattice, we need it to be closed under multiplication by \\$\sqrt2\\$ and \\$\sqrt φ\\$, which it is; for example:

$$ \sqrt2 \begin{bmatrix}1 \\ 0\end{bmatrix} = \begin{bmatrix}\frac1{\sqrt 2} \\ \frac1{\sqrt 2}\end{bmatrix} - \begin{bmatrix}-\frac1{\sqrt 2} \\ \frac1{\sqrt 2}\end{bmatrix}, \quad \sqrt φ\begin{bmatrix}\sqrt φ^3 \\ 0\end{bmatrix} = \begin{bmatrix}1 \\ 0\end{bmatrix} + \begin{bmatrix}φ \\ 0\end{bmatrix}. $$

We also need to multiply some points by \\$\frac12\\$, but it turns out that as long as we use \\$2I\\$ as the initial matrix rather than \\$I\\$, those points always have even coefficients. The resulting actions are given by

\begin{gather\*} SM = \frac12 M\left\[\begin{smallmatrix} 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & 0 \\ 0 & 0 & 0 & 0 & -1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & -1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & -1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & -1 & -1 & 0 & -1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 \\ -1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & -1 \\ 0 & 0 & 0 & 0 & -1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 1 \\ 0 & -1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & -1 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & 1 & 0 & 0 & 0 & 0 \\ -1 & 0 & -1 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ -1 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \end{smallmatrix}\right\], \\ TM = M\left\[\begin{smallmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{smallmatrix}\right\], \end{gather\*}

which we compress slightly using the Kronecker product.
> 18 votes

# Answer
# Retina 0.8.2, 55 bytes

```
\d
$*RF
FRRRFRRRF
RFRFR
FRFRF
RRRFRRRFRRR
}`FF|RRRR

^$

```

Try it online! Takes input as `123` but test suite converts from `LSR` for convenience. Explanation: Similar approach to @AndrovT's Vyxal answer, but reduces the problem further to two movements, `R` (rotate on the spot without moving) and `F` (flip around and move to the next intersection).

```
\d
$*RF

```

Convert digits to the appropriate `R` and `F` movements.

```
FRRRFRRRF
RFRFR
FRFRF
RRRFRRRFRRR

```

Simplify moving along three sides of the same pentagon to moving along the other two sides.

```
FF|RRRR

```

Remove redundant multiples of `F` and `R` movements.

```
}`

```

Repeat until the path cannot be simplified further.

```
^$

```

Check whether the path is now empty.
> 10 votes

# Answer
# Vyxal, 26 bytes

```
fC‹\1꘍›ṅ»¬½ẆZ¶ẋḞ≥P»3R2€yøV

```

Try it Online!

Port of *@Neil's* Retina answer. Returns a falsey value if the path is closed and truthy otherwise.

```
fC                   # covert to a list of charcodes
  ‹                  # decrement
   \1꘍               # prepend that many spaces to "1"
      ›              # replace spaces with zeros
       ṅ             # join by nothing
        »...»        # push the compressed integer 36932780194571550874
             3R      # convert to base 3 "100010001201010210101200010001000200002211"
               2€    # split on 2 ["100010001", "01010", "10101", "00010001000", "0000", "", "11"]
                 y   # uninterleave ["100010001", "10101", "0000", "11"], ["01010", "00010001000", ""]
                  øV # replace strings from the first list with corresponding strings from the second list while it's possible

```

## Old:

# Vyxal, 44 bytes

```
‹‹C‹λ2Ẏk₁⁼[ḢḢǔk₁-3Y]₌ǔh¬[3₌ȯẎ∑J]:hċßN4%;İṪta

```

Try it Online!

Returns `0` for closed paths and `1` otherwise.

First it represents the turns right, straight, left and backwards with numbers 1, 2, 3 and 0 respectively.

If the path is closed with length greater than 1, then it can be reduced to path `0, 0` with the following transformations:

1. Rotating the path (e. g. `0, 1, 2, 1, 3 -> 3, 0, 1, 2, 1`)
2. Changing right turns to left turns and vice versa (e. g. `0, 1, 2, 1, 3 -> 0, 3, 2, 3, 1`)
3. If the path contains the pattern `a, 0, b` replacing it with `a+b mod 4` (e. g. `2, 0, 1, 3 -> 3, 3`)
4. If the path contains the pattern `a, 1, 1, b` replacing it with `(a-1 mod 4), 3, (b-1 mod 4)` (e. g. `1, 1, 1, 2 -> 0, 3, 1`)

This is because a closed path has at least one of `0`, `[1, 1]` and `[3, 3]` so we can always use the transformations to shorten it.

## Code explanation

Append "--" representing two backwards turns to avoid cases where the path is too short.

```
‹‹

```

Replace L, R, S and - with the corresponding numbers.

```
C    # get the ascii value
 ‹   # decrement
     # eventually when mod 4 gets applied it will transform into the correct numbers

```

Apply the a function repeatedly and collect unique results

```
λ ... ;İ

```

where the function is:

* Use the fourth transformation

```
  2Ẏk₁⁼           # are the first two items equal to 1?
       [        ] # if they are:
        ḢḢ        #   remove first two items
          ǔ       #   rotate right
           k₁-    #   subtract 1 from the first two items
              3Y  #   insert 3 into the second position

```
* Use the third transformation and rotate

```
  ₌ǔh          # push the list rotated to the right and then the first item of the original list
     ¬[      ] # if it's equal to 0:
       3₌ȯẎ    #   push a[3:] and a[:3]
           ∑   #   sum
            J  #   join

```
* Mirror the turns such that the first turn is not 3

```
  :hċß    # if the first item is not 1:
      N   #   negate each
       4% # mod 4

```

Finally check if the second to last item in the list is `[0, 0]`.

```
Ṫ   # remove last item
 t  # last item
  a # is any truthy

```
> 9 votes

# Answer
# Charcoal, 52 bytes

```
≔⭆ＳＸχ⊕⌕LSRιθＷ⌊ΦＥ⪪”←“tU≧*h？λêQ✳x”¶⪪κ №θ⌈κ≔⪫⪪θ⌈ι⌊ιθ¬θ

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a round trip, nothing if not. Explanation: Based on my Retina 0.8.2 answer, but using `1` instead of `F` and `0` instead of `R` because it's golfier in Charcoal.

```
≔⭆ＳＸχ⊕⌕LSRιθ

```

Change `L` to `10`, `S` to `100` and `R` to `1000` in the input. (These are actually reversed from my Retina answer but it doesn't matter because round trips are reversible.)

```
Ｗ⌊ΦＥ⪪”...”¶⪪κ №θ⌈κ

```

While the string contains one of the patterns `100010001`, `10101`, `11` or `0000`...

```
≔⪫⪪θ⌈ι⌊ιθ

```

... replace all matches with the `01010`, `00010001000` or the empty string respectively.

```
¬θ

```

Test whether the string is now empty.
> 4 votes

# Answer
# 05AB1E, ~~27~~ 26 (or 23) bytes

```
Ç<°JΔ•6o₁EAÛr£ð•3B2¡ι`:}õQ

```

Port of *AndrovT*'s top Vyxal answer, which in turn is a port of *@Neil*'s Retina answer, which in turn is inspired by *AndrovT*'s bottom Vyxal answer.
-1 byte thanks to *@Neil*.

Outputs `1`/`0` for truthy/falsey respectively. If outputting an empty string for truthy and a bunch of `0`s and/or `1`s as falsey is acceptable, the last three bytes could be removed.

Try it online or verify all test cases.
Try it online or verify all test cases with the last three bytes removed.

**Explanation:**

```
Ç                      # Convert the (implicit) input-string to a list of codepoint integers
 <                     # Decrease each by 1
  °                    # Take 10 to the power each
   J                   # Join them together
Δ                 :}   # Keep doing the following replacements as long as it's possible:
 •6o₁EAÛr£ð•           #  Push compressed integer 110798340583714652624
            3B         #  Convert it to base-3: 1000100012010102101012000100010002000022112
              2¡       #  Split it on 2s: [100010001,"01010",10101,"00010001000","0000","",11,""]
                ι      #  Uninterleave it into 2 parts: [[100010001,10101,"0000",11],["01010","00010001000","",""]]
                 `     #  Pop and push both lists separately to the stack
                   }   # After the changes loop:
                    õQ # Check if what remains is an empty string
                       # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•6o₁EAÛr£ð•` is `110798340583714652624`.
> 3 votes

# Answer
# Octave, ~~381~~ ~~309~~ ~~286~~ ~~284~~ ~~282~~ ~~266~~ ~~264~~ ~~259~~ ~~253~~ 247 bytes

(381 -\> 247) Saved 134 bytes thanks to the comment of @ceilingcat

---

Golfed version. Try it online!

```
pkg load symbolic;function R=f(S),u=@(x)reshape(str2num(dec2base(x,3)(:)),4,4)-1;a=b=eye(16);for c=S;b=(kron(u(25952008),u(27752297))+kron(u(21543856),u(18501071)))*kron(u(21169798),eye(4))^{1,0,3}{mod(-toascii(c),4)+1}*b/2;end;R=all(a*a==b*b);end

```

Ungolfed version, modified from @Anders Kaseorg's answer. Try it online!

```
pkg load symbolic

function mat = u(x)
  base3_repr = dec2base(x, 3);
  mat = reshape(str2num(base3_repr(:)), 4, 4) - 1;
endfunction

function result = check_input(input_str)
  s = kron(u(25952008), u(27752297)) + kron(u(21543856), u(18501071));
  t = kron(u(21169798), eye(4, 4));
  a = b = 2 * kron(eye(4, 4), eye(4, 4));

  for c = input_str
    idx = mod(-toascii(c), 4) + 1;
    b = {s * t, s, s * t^3}{idx} * b / 2;
  endfor

  result = all(all(a == b)) || all(all(a == -b));
endfunction

test_cases = {
  "LLLLL",
  "LLLLSRRRRS",
  "SRRSRRSRRSRR",
  "",
  "R",
  "LLLLLL",
  "SLLLLR"
};

expected_results = [
  true,
  true,
  true,
  true,
  false,
  false,
  false
];

for i = 1:length(test_cases)
  input_str = test_cases{i};
  result = check_input(input_str);
  assert(result == expected_results(i), sprintf("Test case %d failed: input = %s, expected = %d, actual = %d", i, input_str, expected_results(i), result));
  fprintf("Test case %d passed: input = %s\n", i, input_str);
end

```
> 1 votes

---
Tags: code-golf, math, decision-problem, geometry, abstract-algebra
---


title: Bumping Series Implementation

text:
# Question
Title: Bumping Series Implementation
I have a follow-up question here from my previous question on Math SE. I am lazy enough to explain the content again, so I have used a paraphraser to explain it below:

I was considering arbitrary series, springing up as a top priority, when I considered one potential series in my mind. It is as per the following:

The essential thought is, take a line of regular numbers \\$\mathbb{N}\\$ which goes till boundlessness, and add them. Something apparent here is that the most greatest biggest number \\$\mathbb{N}\_{max}\\$ would be \\$\mathbb{N}\_{i}\\$. In essential words, on the off chance that we go till number 5, \\$\mathbb{N}\_5\\$ the level it comes to by summation is 5.

Further, continuing, we can get:

The essential ramifications here is that we knock the numbers by unambiguous \\$\mathbb{N}\\$. At start, we take the starting number, for our situation it is 1, we move once up and afterward once down. Then we do it two times, threefold, etc. So `1 3 2` as per my outline is one knock. At the closure \\$\mathbb{N}\\$ which is 2 here, we will hop it by 2 and make it low by 2. So it gets `2 5 12 7 4`. Here, expect \\$\mathbb{N}\_i\\$ as the quantity of incrementation, before it was 1, presently it is 2. We get various sets, with various terms, however absolute number of terms we overcome this would be \\$2 \mathbb{N}\_i + 1\\$. Presently, it will begin from 4, continue taking 3 leaps prior to arriving by three terms. By this, we get series featured by circles in that three-sided exhibit as:

```
1, 3, 2, 5, 12, 7, 4, 9, 20, 44, 24, 13, 7, 15, 32, 68, 144, 76, 40, 21, 11, 23, 48, 100, 208, 432, 224, 116, 60, 31, 16...

```

The series appear to be disparate, my particular inquiry this is the way to address this series in Numerical terms.

Challenge: Implement the algorithm which can build this series.

Scoring Criteria: It is ranked by fastest-algorithm so the answer with lowest time complexity is considered (time complexity is loosely allowed to be anywhere) but the program must have been running accurate result.

# Answer
# Charcoal, 21 bytes

```
ＮθＩ⊘×⊕θＸ²↔⁻θ⊕×⊖⌈₂θ⌈₂θ

```

Try it online! Link is to verbose version of code. Outputs the `n`th term. Explanation:

```
Ｎθ                      First input as a number
      θ                 First input
     ⊕                  Incremented
    ×                   Multiplied by
        ²               Literal integer `2`
       Ｘ                Raised to power
           θ            First input
         ↔⁻             Absolute difference with
                 θ      First input
                ₂       Square root
               ⌈        Ceiling
              ⊖         Decremented
             ×          Multiplied by
                    θ   First input
                   ₂    Square root
                  ⌈     Ceiling
   ⊘                    Halved
  Ｉ                     Cast to string

```

30 bytes in integer arithmetic:

```
ＮθＩ⊘×⊕θＸ²↔⁻θ⊕×⊖⌈₂θ⌈₂θ

```

Try it online! Link is to verbose version of code.
> 11 votes

# Answer
# Jelly, 13 bytes

Port of Neil's answer (I was working towards it myself but he nailed it).

Unsure of the complexity of this closed-form formula, but *think* it is \\$O(M(B(n))B(n))\\$ where \\$n\\$ is the input, \\$M(x)\\$ is the multiplication of two \\$x\\$ bit numbers and \\$B(x)\\$ is the bit-length of \\$x\\$.

```
½Ċ’×$‘ạ⁸’2*×‘

```

A monadic Link that accepts \\$n\\$ and yields \\$a(n)\\$.

**Try it online!**

### How?

```
½Ċ’×$‘ạ⁸’2*×‘ - Link: positive integer, n
½             - square-root
 Ċ            - ceiling
    $         - last two links as a monad - f(x=that):
  ’           -   decrement (x)
   ×          -   (that) multiply (x)
     ‘        - increment (that) -> A
       ⁸      - chain's left argument = n
      ạ       - (A) absolute difference (n)
        ’     - decrement (that) -> E
         2    - two
          *   - (2) exponentiate (E)
           ×  - (that) multiply (n)
            ‘ - increment

```

---

To avoid floating point arithmetic we could instead do it in  ~~17 16~~  14 bytes (-2 thanks to Neil!):

```
’Æ½‘×$‘ạ⁸2*×‘H

```

**Try it online!**

This replaces `½Ċ’×$` with `’Æ½‘×$` and moves the decrement out of the exponent, instead halving at the end (`H`).

```
’Æ½‘×$ - chain: integer n
’      - decrement -> n-1
 Æ½    - integer-square-root (n-1) (uses only integer arithmetic)
     $ - last two links as a monad - f(x=that):
   ‘   -   increment (x)
    ×  -   (that) multiply (x)

```
> 5 votes

# Answer
# C (gcc), 97 + 3 bytes

+3 bytes from `-lm`. Runs in O(n) time, where n is the index.

```
f(M,n,v,l,c){l=0;for(n=c=1;M--;l+=v&&v--?:-1)n=((v=l?v:c++)?2*n:n/2+.5)+pow(2,v?l:l-2);return n;}

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 13 bytes

```
tîD<*-<ÄoI>*;

```

Another port of *@Neil*'s Charcoal answer, so make sure to upvote him as well!

Try it online or verify all test cases.
The TIO-links use the legacy version of 05AB1E, because the regular 05AB1E on TIO is out-of-date, and still contains an already fixed bug when using `o` on decimal values ending with `.0`.

**Explanation:**

Basically implements the formula found by *@Neil*:

$$a(n) = \frac{(n+1)\times 2^{\left|n-\left\lceil\sqrt{n}\right\rceil\times(\left\lceil\sqrt{n}\right\rceil-1)-1\right|}}{2}$$

```
t              # Get the square root of the (implicit) input-integer
 î             # Ceil it
  D            # Duplicate it
   <           # Decrease the copy by 1
    *          # Multiply the two together
     -         # Subtract this from the (implicit) input-integer
      <        # Decrease that by 1
       Ä       # Get the absolute value of that
        o      # Take 2 to the power that
         I>    # Push the input+1
           *   # Multiply the two together
            ;  # Halve it
               # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Mathematica, 53 bytes

Formula:

$$ f(n)=\frac{(n+1) \times 2^{|n-\lceil\sqrt{n}\rceil \times(\lceil\sqrt{n}\rceil-1)-1|}}{2} $$

```
f=((#+1)*2^Abs[#-⌈Sqrt@#⌉*(⌈Sqrt@#⌉-1)-1])/2&

```

Try it online!
> 1 votes

# Answer
# JavaScript, 49 bytes

Port of Neil's answer

```
n=>-~n*2**~-Math.abs(n+(c=(n**=.5)%1?~n:-n)*~c-1)

```

Formula:

$$ f(n) = \frac{(n+1)\times 2^{\left|n-\left\lceil\sqrt{n}\right\rceil\times(\left\lceil\sqrt{n}\right\rceil-1)-1\right|}}{2} $$

Try it:

```
f=n=>-~n*2**~-Math.abs(n+(c=(n**=.5)%1?~n:-n)*~c-1)

for(i=0;i<20;)console.log(f(++i))
```

## Upd 54 -\> 49

Thanks to Arnauld for the tip to reduce bytes count
> 0 votes

---
Tags: sequence, subsequence, fastest-algorithm
---


title: How to find the counterfeit coin?

text:
# Question
Title: How to find the counterfeit coin?
You are the treasurer and you have received information that a counterfeit coin has entered the treasury. All you know is that the counterfeit coin is lighter than the original.

Knowing how many coins you have in total and using only a balance scale, you need to determine the minimum number of weighings to determine which coin is counterfeit before it disappears from the treasury.

---

Your function must accept only one integer (which will be more than 1) and must output 2 things:

* the minimum number of weighings without lucky chances
* steps on how to find counterfeit coin

**Step** \- a moment when you use balance scale

**Without lucky chances** means that your number must be the maximum among the minimum steps required. For example let's say that you have 5 coins:

1. You can split them to 3 groups by 2, 2 and 1 (this isn't a step)
2. Weighing the groups 2 and 2 (this is a step)

2.1 If they are equal then the remaining coin is counterfeit

2.2. If one of the groups is lighter then the counterfeit coin is in that group
3. Weigh each remaining coin (this is a step)

3.1 The coin that is lighter is the counterfeit coin

So the minimum number of weighings without lucky chances is 2 but with lucky chances it is 1 because we can find the counterfeit coin at step 2.

The output steps must be easy to understand. Please add a detailed explanation of how to read the output steps. For example the previous example can be represented like this:

```
[5(2,2) 2(1,1)] - 2

```

Where the:

* `[]` \- means the possible scenarios
* `x(y,z)` \- `x` means remaining coins after previous step, `(y,z)` means how many coins (from `x`) on each side of balance scale I am weighing
* `'space'` \- means the next step/scenario
* `- x` \- means the minimum number of weighings without lucky chances

Here is an example with `8`. The output can be shown like this:

```
[8(3,3) [2(1,1)] [3(1,1)]] - 2

```

After first step we have two different scenarios because:

1. if the 2 groups of 3 are equal then the counterfeit coin is in the group of 2 coins
2. if the 2 groups of 3 aren't equal then the counterfeit coin is on one of the groups of 3

It is enough to to weigh only 2 different coins in each scenario to find the counterfeit coin. Regardless of the scenario, the minimum number of weighings without lucky chances is 2

Here are the possible outputs for 2 to 9 coins:

```
2 --> [2(1,1)] - 1

3 --> [3(1,1)] - 1

4 --> [4(2,2) 2(1,1)] - 2

5 --> [5(2,2) 2(1,1)] - 2

6 --> [6(2,2) 2(1,1)] - 2

7 --> [7(3,3) 3(1,1)] - 2

8 --> [8(3,3) [2(1,1)] [3(1,1)]] - 2

9 --> [9(3,3) 3(1,1)] - 2

```

You can output any of the possible steps of how to find the counterfeit coin. For example for `10` we have 5 different scenarios. You can output any of them:

```
10 --> [10(5,5) 5(2,2) 2(1,1)] - 3
10 --> [10(4,4) [2(1,1)] [4(2,2) 2(1,1)]] - 3
10 --> [10(3,3) [3(1,1)] [4(2,2) 2(1,1)]] - 3
10 --> [10(2,2) [2(1,1)] [6(3,3) 3(1,1)]] - 3
10 --> [10(1,1) 8(3,3) [2(1,1)] [3(1,1)]] - 3

```

The shortest code in each programming language wins!

# Answer
> 3 votes
# Python, 77 bytes

*-4 from @TheThonnu*

```
f=lambda n:n<4and[1]or(m:=-~n//3,p:=n-2*m,f(m),f(p),max(f(m)[-1],f(p)[-1])+1)

```

Attempt This Online!

If input is 2 or 3, returns `[1]` meaning only one trivial weighing is required, otherwise returns a 5-tuple (number of coins to weigh on each side at this step, number of coins to set aside at this step, steps to follow with the lighter side of coins if there was a lighter side, steps to follow with the set-aside pile if the scale balanced, worst-case number of steps required). Naturally the third and fourth elements of the tuple recurse.

# Answer
> 2 votes
# Charcoal, 44 bytes

```
⊞υＮＷ⊖⌈υ«≔⊕÷⊖ι³θ≔⁺⁻υ⟦⊕ι⟧⟦θ⁻⊕ι⊗θ⟧υ⟦⪫⟦⊕ιθＬ↨ι³⟧

```

Try it online! Link is to verbose version of code. Outputs sets of three integers: coins left, coins to weigh (per side), worst case number of remaining weighings. Explanation: Inspired by @ParclyTaxel's Python answer.

```
⊞υＮ

```

Start with `n` coins.

```
Ｗ⊖⌈υ«

```

Repeat until there is only `1` coin left.

```
≔⊕÷⊖ι³θ

```

Calculate how many coins to weigh.

```
≔⁺⁻υ⟦⊕ι⟧⟦θ⁻⊕ι⊗θ⟧υ

```

Update the set of possible numbers of remaining coins.

```
⟦⪫⟦⊕ιθＬ↨ι³⟧

```

Output the coins left, coins to weigh and steps left.

# Answer
> 1 votes
# Mathematica, 106 bytes

Modified from @Parcly Taxel's answer

---

Golfded version, try it online!

```
Module[{m,p,fm,fp,maxF},If[n<4,{1},m=-⌈BitNot[n]/3⌉;p=n-2*m;{m,p,f@m,f@p,Max[Last@*f@m,Last@*f@p]+1}]]

```

Ungolfed version

```
f[n_] := Module[
  {m, p, fm, fp, maxF},
  If[n < 4,
    {1},
    m = -Ceiling[BitNot[n]/3];
    p = n - 2*m;
    fm = f[m];
    fp = f[p];
    maxF = Max[Last[fm], Last[fp]] + 1;
    {m, p, fm, fp, maxF}
  ]
]

f[73]//Print

```

# Answer
> 0 votes
# Python, 2551 bytes,

```
import math

def find_counterfeit_coin(num_coins):
    steps = []

    # Base case
    if num_coins == 2:
        steps.append((2, (1, 1)))
        return 1, steps

    # Determine the largest power of 3 less than num_coins
    power = math.floor(math.log(num_coins - 1, 3))
    group_size = 3 ** power

    # First weighing
    remaining_coins = num_coins
    while remaining_coins > 2 * group_size:
        steps.append((remaining_coins, (group_size, group_size)))
        remaining_coins -= 2 * group_size

    # Split remaining coins into groups of size group_size or less
    group_sizes = []
    while remaining_coins > group_size:
        group_sizes.append(group_size)
        remaining_coins -= group_size
    if remaining_coins > 0:
        group_sizes.append(remaining_coins)

    # Weigh each group
    for group in group_sizes:
        if group == group_size:
            steps.append((group, (group_size, group_size)))
        else:
            steps.append((group, (1, 1)))

    # Determine which group contains the counterfeit coin
    if len(group_sizes) == 1:
        num_weighings = power + 1
        return num_weighings, steps

    elif len(group_sizes) == 2:
        if group_sizes[0] == group_sizes[1]:
            num_weighings = power + 1
            return num_weighings, steps
        else:
            num_weighings = power + 2
            steps.append((group_sizes[0], (1, 1)))
            return num_weighings, steps

    else:
        # Combine two groups of equal size to create a larger group
        combined_group_size = group_size * 2
        combined_groups = [sum(group_sizes[i:i+2]) for i in range(0, len(group_sizes), 2)]

        # Recursively find the counterfeit coin in the larger group
        recursive_weighings, recursive_steps = find_counterfeit_coin(sum(group_sizes))
        num_weighings = power + recursive_weighings

        # Add steps for weighing the smaller groups
        for group in combined_groups:
            steps.append((group, (1, 1)))

        # Add steps from recursive call
        steps += recursive_steps

        # Weigh the two groups that produced the combined group
        for i in range(0, len(group_sizes), 2):
            if group_sizes[i] == group_sizes[i+1]:
                steps.append((combined_group_size, (group_sizes[i], group_sizes[i+1])))
            else:
                steps.append((combined_group_size, (group_sizes[i], combined_group_size - group_sizes[i])))

        return num_weighings, steps

```

Attempt This Online!

---

Though it can be considered as an algorithm, it is a pathway for others to write short code from it.

This solution uses a recursive approach to find the minimum number of weighings required to find the counterfeit coin. The algorithm works by dividing the coins into groups and weighing the groups against each other, gradually reducing the number of remaining coins until the counterfeit coin is found. The number of groups and their sizes are chosen so that the maximum number of coins are weighed at each step.

The output of the function is a tuple containing the minimum number of weighings and a list of tuples representing the steps taken to find the counterfeit coin. Each tuple in the list represents a weighing, and contains the number of coins weighed and the sizes of the groups weighed against each other. The steps can be interpreted as a tree, where each level represents

---
Tags: code-golf
---


title: Human oriented string comparison

text:
# Question
Title: Human oriented string comparison
Traditionally when you compare two strings you use lexicographical comparison. That can be described by the recursive algorithm:

$$ f(x, y)= \left\\{\begin{array}\[rr\] \\ \mathrm{EQ} & \mathrm{if}\\,\mid x\mid=0\\,\mathrm{and}\\,\mid y\mid=0 \\ \mathrm{GT} & \mathrm{if}\\,\mid x\mid\>0\\,\mathrm{and}\\,\mid y\mid=0 \\ \mathrm{LT} & \mathrm{if}\\,\mid x\mid=0\\,\mathrm{and}\\,\mid y\mid\>0 \\ \mathrm{GT} & \mathrm{if}\\,x\_0 \> y\_0 \\ \mathrm{LT} & \mathrm{if}\\,x\_0 \< y\_0 \\ f(\mathrm{tail}(x),\mathrm{tail}(y)) & \mathrm{if}\\,x\_0 = y\_0 \end{array}\right. $$

This has many advantages, however it does have some drawbacks. In particular it doesn't work like we might want it with our base 10 numerals. For example `9` is "greater than" `852` with lexicographical comparison because its first digit is larger.

So for more human oriented sorting we can use a modified algorithm:

* Break each string into runs of consecutive digits (`0-9`) and individual non-digit characters. For example `abc29em3jdd` -\> `a b c 29 e m 3 j d d`
* Compare each of the two broken strings with lexicographical comparison treating each piece as a single symbol. Compare two individual characters as normal. When comparing two runs of digits, consider the one which is longer to be greater, otherwise compare them lexicographically. When comparing a run of digits with a individual character treat the run of digits as if it were its first digit.

This produces some pretty nice results. `852` is greater than `9`, and `b15` is greater than `a16`.

## Task

Implement this human oriented comparison by taking two strings as input and outputting one of three distinct values. One if the two strings are equal, one if the first input is "greater" than the second and the last if the second input is "greater" than the first.

You can assume that the strings are finite and consist of only characters on the range of 32 to 127.

This is the goal is to minimize the size of your source code as measured in bytes.

## Test cases

```
"abc" "abx" => LT
"abx" "abc" => GT
"abx" "abx" => EQ
"ab" "abc" => LT
"ab" "ab10" => LT
"ab10c" "ab9x" => GT
"ab9x" "ab10c" => LT
"15x" "16b" => LT
"16b" "15x" => GT
"852" "9" => GT
"1,000" "9" => LT
"1.000" "9" => LT
"20.15.12" "20.19.12" => LT
"20.15.12" "6.99.99" => GT
"15k19" "15w12" => LT
"9w" "10" => LT
"10" "9w" => GT
"a123" "123a" => GT
"#123" "123#" => LT
"3-2" "3-1" => GT
"a000" "a0" => GT
"a001" "a0" => GT
"a000" "a1" => GT
"0xa" "0x10" => GT
"0_10" "0_4" => GT
"/" "*" => GT

```

# Answer
# C (GCC), 230 178 176 bytes

edit: - bytes thank to c--, -6 thanks to pan

```
*p="1234567890";i,j;f(char*x,char*y){x[i=strcspn(x,p)]+y[j=strcspn(y,p)]?strncmp(x,y,i>j?j:i)?:i-j?:(i=strspn(x+=i,p))-strspn(y+=j,p)?:atoi(x)-atoi(y)?:f(x+i,y+i):strcmp(x,y);}

```

Returns positive for GT, negative for LT and 0 for EQ (same output as strcmp)

```
* p = "1234567890";
i, j;
f(char * x, char * y) {
  x[i = strcspn(x, p)] + y[j = strcspn(y, p)] ? // find first digit in each string
    strncmp(x, y, i > j ? j : i) ? : // return strcmp if strings are different before first digit
    i - j? : // return longer string before the first digit
    (i = strspn(x += i, p)) - strspn(y += j, p) ? : // return longer number
    atoi(x) - atoi(y) ? : // return larger number if both have the same length
    f(x + i, y + i) : // otherwise compare the string after the numbers
    strcmp(x, y); // return strcmp if there are no digits
}

```

Attempt This Online!

Previous attempt:

```
int f(char*x,char*y){int c,i,j;for(;;){i=strcspn(x,"1234567890");j=strcspn(y,"1234567890");if(!*(x+i)&&!*(y+j)) return strcmp(x,y);if(c=strncmp(x,y,i>j?j:i))return c;if(c=atoi(x+=i)-atoi(y+=j))return c;for(;isdigit(*x);x++,y++);}}

```
> 5 votes

# Answer
# JavaScript (Node.js), ~~74~~ 72 bytes

*Saved 2 bytes thanks to Arnauld! Bugfix thanks to \[tsh\]*

```
x=>y=>((a=(g=s=>b=s.replace(/\d+/g,n=>0+n.padStart(16)))(x))>g(y))-(a<b)

```

Try it online! Gives `-1` for `LT`, `0` for `EQ`, and `1` for `GT`. Call as `f(a)(b)`.

Assumes the strings' integers are safe integers (in this case, positive integers ≤ \\$2^{53}-1\\$, i.e., 16 decimal digits or less. This transforms both input strings by left padding such integers with spaces, prepending a zero, and using the native string comparison sort, which gives us the correct results. (This method, as opposed to padding with 0s, distinguishes `0` and `000`, as in such cases, the length of the string should be taken into consideration.)
> 4 votes

# Answer
# APL(Dyalog Unicode), 27 bytes SBCS

```
(⍋>⍒)-⍤⌈⍥≢/↑¨¨'\d+|.'⎕S'&'¨

```

Try it on APLgolf!

Tacit function that returns `0 1`, `0 0`, `1 0` for `LT`, `EQ`, `GT`, respectively. Input `f x y`.

```
              '\d+|.'⎕S'&'¨ split into numbers/others
     -⍤    ↑¨¨               left-pad splits to
       ⌈⍥≢/                    max length of inputs
(⍋>⍒)                       compare

```
> 4 votes

# Answer
# Python, 95 bytes

-X bytes thanks to WheatWizzard and Conor O'Brian

```
def f(x):a,b=[[(len(i),i)for i in re.findall('\d+|.',y)]for y in x];return(a>b)-(a<b)
import re

```

Attempt This Online!
> 2 votes

# Answer
# Raku, 39 bytes

```
&[cmp]o*».&{[m:g/\d+|./».&{+$_//$_}]}

```

Try it online!

* `*».&{ ... }` is an anonymous function that maps its list-of-strings argument over the braced expression.
* `m:g/\d+|./` breaks a string up into a list of matches, each either a group of digits, or a single other character.
* `».&{ ... }` maps each of those lists over the braced expression.
* `+$_ // $_` tries to convert each match into a number with the `+` operator. If that fails, the defined-or operator `//` replaces the error with the original value.
* `[ ... ]` wraps each list in an `Array`.
* `&[cmp]` is a reference to the built-in `cmp` operator, which operates on arrays of heterogeneous data types just as specified in the problem statement. It returns one of the enumerated values `Less`, `Same`, or `More`.
* `o` composes those two functions together.
> 2 votes

# Answer
# Retina 0.8.2, 49 bytes

```
\d+
$.&$*10$&
^
$%'¶
O`¶.*
^(.*)(¶\1)*(¶.*)*$
$#2

```

Try it online! Takes newline-separated input and outputs `0`, `1` or `2` for `GT`, `LT` and `EQ` but link is to test suite that splits on tabs and translates the output to `>`, `<` or `=` for convenience. Explanation:

```
\d+
$.&$*10$&

```

Prefixes each run of digits with a run of `1`s of the same length and a `0`. This maintains lexicographical sort order when comparing numbers with non-numbers while making numbers sort by length and then lexicographically.

See below for the explanation of the rest of the program. Previous 44 byte version compared digit strings numerically rather than by length:

```
\d+
$*10
^
$%'¶
O`¶.*
^(.*)(¶\1)*(¶.*)*$
$#2

```

Try it online! Takes newline-separated input and outputs `0`, `1` or `2` for `GT`, `LT` and `EQ` but link is to test suite that splits on tabs and translates the output to `>`, `<` or `=` for convenience. Explanation:

```
\d+
$*10

```

Replace all embedded runs of digits with a run of that number of `1`s followed by a `0`. This maintains lexicographical sort order when comparing numbers with non-numbers while making numbers sort numerically.

```
^
$%'¶

```

Make a copy of the first string.

```
O`¶.*

```

Sort the modified strings lexicographically.

```
^(.*)(¶\1)*(¶.*)*$
$#2

```

Count how many strings match the first string. If both strings were equal, then they will both match. If the first string was less than the second, then it will match and the other string will not. If the first string was greater than the second, then there will not be any additional matches.

I include the previous newline in the sort string as non-empty strings are easier to process in Retina, but note that the above rule works whether or not the copy is included in the sort; with the copy, the possible results are `EEE` (all equal), `FFS` (first sorts before second), `SFF` (first sorts after second), while without the copy, the third result is `FSF`, where the first two strings are still different.
> 2 votes

# Answer
# 05AB1E, ~~16~~ 15 bytes

```
ÙΣ.γd}εÐdigs»]k

```

Input as a pair of strings. Outputs `[0,1]` for \\$LT\\$; `[1,0]` for \\$GT\\$; and `[0]` for \\$EQ\\$.

Try it online or verify all test cases.

**Explanation:**

```
Ù            # Uniquify the (implicit) input-pair (for the EQ test cases)
 Σ           # Sort the pair by:
  .γ         #  Adjacent group the substrings by:
    d        #   Is it a (non-negative) number
   }ε        #  After the adjacent-group-by: map over each part:
     Ð       #   Triplicate the current part
      di     #   Pop one, and if it's a (non-negative) number:
        g    #    Pop another, and push its length
         s   #    Swap so the number is before the length on the stack
          »  #    Join the stack (the length & number) with newline delimiter
 ]           # Close the if-statement, map, and sort-by
  k          # Get the indices of this sorted pair into the (implicit) input-pair
             # (which is output implicitly as result)

```
> 2 votes

# Answer
# Perl 5, 41 bytes

```
sub{s/\d+/$&+1e9.$&/ge for@_;pop cmp pop}

```

Returns -1 for GT, 0 for EQ and 1 for LT.

Try it online!
> 1 votes

# Answer
# Jelly, ~~23~~ ~~20~~ 18 bytes

```
œ-œlLɗÐƤ€ØDoṚ$ż"¹Ġ

```

Try it online!

Takes a list of two inputs, and returns `[[1], [2]]` for LT, `[[1, 2]]` for EQ, and `[[2], [1]]` for GT. (The test footer converts these because my brain couldn't handle checking the test cases otherwise.)

A band-aid fix to a solution that otherwise always compares digits as greater than non-digits.

```
      ÐƤ              For every prefix (largest first) of
        €             each of the inputs,
    L                 get the length of
œ-                    the multiset difference of the suffix and
  œl ɗ   ØD           the suffix with leading digits removed.
           o          Replace zeroes in either result with
            Ṛ$        corresponding elements of the other result,
              ż"¹     then zip each result with the corresponding input.
                 Ġ    Group indices, sorted by value.

```
> 1 votes

# Answer
# Tcl, 506 bytes

Modified from @Kjetil S's answer

---

Golfed version, try it online!

```
proc increment_numbers {str} {set result ""; set idx 0; foreach match [regexp -all -inline -indices -- {\d+} $str] {set start [lindex $match 0]; set end [lindex $match 1]; append result [string range $str $idx [expr {$start - 1}]]; set num [string range $str $start $end]; append result [expr {$num + 1e9}].$num; set idx [expr {$end + 1}]}; append result [string range $str $idx end]; return $result}; proc f {x y} {set x [increment_numbers $x]; set y [increment_numbers $y]; return [string compare $x $y]}

```

Ungolfed version

```
proc increment_numbers {str} {
    set result ""
    set idx 0
    foreach match [regexp -all -inline -indices -- {\d+} $str] {
        set start [lindex $match 0]
        set end [lindex $match 1]
        append result [string range $str $idx [expr {$start - 1}]]
        set num [string range $str $start $end]
        append result [expr {$num + 1e9}].$num
        set idx [expr {$end + 1}]
    }
    append result [string range $str $idx end]
    return $result
}

proc f {x y} {
    set x [increment_numbers $x]
    set y [increment_numbers $y]
    return [string compare $x $y]
}

foreach test {
    {abc      abx        LT}
    {abx      abc        GT}
    {abx      abx        EQ}
    {ab       abc        LT}
    {ab       ab10       LT}
    {ab10c    ab9x       GT}
    {ab9x     ab10c      LT}
    {15x      16b        LT}
    {16b      15x        GT}
    {852      9          GT}
    {1,000    9          LT}
    {1.000    9          LT}
    {20.15.12 20.19.12   LT}
    {20.15.12 6.99.99    GT}
    {15k19    15w12      LT}
} {
    lassign $test x y exp
    set got [f $x $y]
    switch $got {
        -1 {set got LT}
        0 {set got EQ}
        1 {set got GT}
    }
    set status [expr {$exp eq $got ? "ok" : "NOT OK"}]
    puts [format "%-6s   x: %-8s   y: %-8s   expected: %s   got: %s" $status $x $y $exp $got]
}

```
> 0 votes

---
Tags: code-golf, string
---


title: Simplify a Cycle

text:
# Question
Title: Simplify a Cycle
*Alternatively: That one challenge I forgot I had in the sandbox and is about stuff from Discrete Mathematics I learned like 5-6 months ago and kinda don't remember*

Given a path of vertices that form a cycle on a graph, output a simple version of the cycle. That is, if a vertex appears twice, snip out the part in between the two appearances.

## Context

Let \\$u\\$ and \\$v\\$ be vertices of graph \\$G\\$. If there is a cycle from \\$u\\$ to \\$v\\$ of length \\$n\\$, then there exists a simple cycle from \\$u\\$ to \\$v\\$ with length \\$\le n\\$.

This is because any cycle \\$v\_1, e\_1, v\_2, e\_2, ..., e\_m, v\_m\\$ with a vertex visited twice (that is, \\$v\_i = v\_j\\$ for some \\$v\_i\\$ and \\$v\_j\\$ in \\$G\\$, where \\$ i \< j\\$), can be reduced to \\$v\_1, e\_1, ..., e\_i, v\_j, e\_{j+1}\\$ and still be a valid cycle between \\$u\\$ and \\$v\\$.

For the sake of this challenge, the edges connecting vertices will be ignored, as the edge taken when going between vertices will be assumed arbitrary.

## Worked Example

Take the graph \\$K\_5\\$:

One cycle between vertices \\$1\\$ and \\$3\\$ might look like:

That is, the path taken is `[1, 2, 5, 4, 2, 3, 5]`. However, that cycle can be simplified to:

Which has path `[1, 2, 3, 5]`. This cycle is a simple cycle, as only the first and last vertices are equal.

Note that cycles are snipped in the order they come.

## Rules

* There will always be a simpler cycle in the input.
* The input will be a list of vertices in a graph. Whether you take those as numbers, characters or some other way is up to you.
* There will always be at least 2 vertices.
* Each vertex has degree \>= 2.
* Input and output can be given in any reasonable and convenient format.
* As the input represents a cycle, the vertex that is the start and end of the cycle will not be in the input.
* There won't be multiple overlapping simplified paths in the input.
* There'll be one and only one output for each input.

Note that the simple cycle may not be the shortest cycle, and the shortest cycle may not be the simple cycle.

## Test Cases

*Assuming that numbers are used as vertex labels*

```
[1,2,3,4,2,5] -> [1,2,5]
[4,3,6,2,3,8,5,2,8,7] -> [4,3,8,7]
[1,1,2] -> [1,2]
[1,2,7,2,7,2,3,7] -> [1,2,3,7]

```

This is code golf, so make sure you simplify the byte count of your answers.

# Answer
# Wolfram Mathematica, ~~36~~ 35 bytes

```
#//.{a___,b_,___,b_,c___}:>{a,b,c}&

```

-1 byte thanks to @att.

Explanation:

* `#` and `&` define an anonymous function, e.g., `#+1&` is a function that adds 1 to its argument.
* `//.` is `ReplaceRepeated`, and keeps applying the pattern on the right to the expression on the left until its no longer changing
* `:>` is pattern replacement, it replaces the expression on the left with the expression on the right
* Finally, `_` means "any element" and `___` means any sequence of elements (including empty sequences). The variable before `_` or `___` assigns the matched expression to the variable.
> 11 votes

# Answer
# \>\<\> (Fish), ~~43~~ 39 bytes

```
i:0(?v:l3p:l$4p
  /2~/
1+>3g:?!;:nao:4g

```

Try it

## Explanation

Top row copies every element. The raw data will be stored in the third row of the code box. (`:l2-3p`) The fourth row stores the last index each character is encountered. (`l2-$4p`).

The third row prints the data based on the value stored. First, get the number at the specified position. `3g`. Check if it's 0, if so exit. `?!;`. Print the number followed by a line break `nao`. Then we jump to the last occurrence of that character plus one `4g1+`
> 8 votes

# Answer
# Vyxal, ~~9~~ 7 bytes

```
≬h€÷↔∩h

```

Try it Online!

```
≬       # three element lambda:
 h      #   head
  €     #   split by
   ÷    #   push each item to stack

```

This lambda takes a list. If length \> 0 it splits by the first element and returns the last chunk. If length == 0 it does nothing.

```
    ↔   # apply the lambda and collect results until the the result doesn't change
     ∩  # transpose
      h # head

```
> 7 votes

# Answer
# Retina 0.8.2, 11 bytes

```
(\w).*\1
$1

```

Try it online! Link includes test cases. Takes input as a list of letters (or digits or `_`). If input as a string of non-newline characters is acceptable, then for 10 bytes:

```
(.).*\1
$1

```

Try it online! Link includes test cases.
> 4 votes

# Answer
# Nibbles, 6 bytes (12 nibbles)

```
.`.$/%$/$$@/

```

Approach based on AndrovT's Vyxal answer: upvote that!

Vertices are represented by characters.

```
 `.             # iterate while unique
   $            # (starting with input):
     %$         #   split the result-so-far
       /$$      #   on its first element
    /     @     #   and get the last part
.               # now map over results of each iteration
           /    # returning the first element each time.

```
> 4 votes

# Answer
# JavaScript (Node.js), 35 bytes

```
f=a=>a&&a[0]+f(a.split(a[0]).pop())

```

Try it online! Link includes test cases. Takes input as a string of characters.
> 4 votes

# Answer
# Python 3.8 (pre-release), 67 bytes

```
f=lambda x,b=[]:x and f(x[len(x)-x[::-1].index(x[0]):],b+x[:1])or b

```

Try it online!

Reverse lookup approach. We find the last occurrence and jump to it

# Python 3.8 (pre-release), 78 bytes

```
f=lambda x,b=[]:x and f(x[1:],(b[:b.index(x[0])]if x[0]in b else b)+x[:1])or b

```

Try it online!

Takes a list of integers.

Idea is if we encounter an element we already passed through, we prune all elements between them
> 3 votes

# Answer
# 05AB1E, 14 bytes

```
.œR.Δε¬Qθ}P}€н

```

Try it online or verify all test cases.

**Explanation:**

```
.œ         # Get all partitions of the (implicit) input-list
  R.Δ      # Find the last one (first one of the reversed list) that's truthy for:
     ε     #  Map over each part of the current partition:
      ¬    #   Get the head (without popping the list)
       Qθ  #   Check if it's equal to the last item in the list
     }P    #  After the map: check if all parts were truthy by taking the product
    }€     # After the findFirst, map over the parts of the found partition:
      н    #  Only leave their first integer
           # (after which this list is output implicitly as result)

```
> 3 votes

# Answer
# Haskell, 53 bytes

```
q(_,_:y)=f y
q(y,_)=f y
f(a:b)=a:q(break(==a)b)
f x=x

```

Try it online!
> 3 votes

# Answer
# JavaScript (Node.js), ~~53~~ 52 bytes

```
a=>a.filter(u=(x,i)=>a.lastIndexOf(u=+u||x)-i?0:u=a)

```

Try it online!
> 2 votes

# Answer
# Charcoal, ~~17~~ 13 bytes

```
ＷΦθ¬λ«ι≔⊟⪪θιθ

```

Try it online! Link is to verbose version of code. Explanation:

```
ＷΦθ¬λ«

```

Repeat until the input string is empty, but calculated as the input string excluding any characters with a non-zero index, so that the result of the calculation becomes the loop variable.

```
ι

```

Output the first character of the input string.

```
≔⊟⪪θιθ

```

Split the string on its first character and take the last part. Edit: Saved 4 bytes by copying this approach from @DominicvanEssen (who based it on another answer but I found his answer clearer).
> 2 votes

# Answer
# Curry (PAKCS), 40 bytes

```
f(a:_++a:b?a:b)|notElem a b=a:f b
f[]=[]

```

Attempt This Online!
> 2 votes

# Answer
# Scala, 121 bytes

Golfed version, try it online!

```
def f(l:List[Int])=l.foldLeft(List.empty[Int]){(a,i)=>if(a.contains(i))a.dropRight(a.length-a.lastIndexOf(i)-1)else a:+i}

```

Ungolfed version

```
object Main {
  def main(args: Array[String]): Unit = {
    val testCases = List(
      List(1, 2, 3, 4, 2, 5),
      List(4, 3, 6, 2, 3, 8, 5, 2, 8, 7),
      List(1, 1, 2),
      List(1, 2, 7, 2, 7, 2, 3, 7)
    )

    testCases.foreach { input =>
      val result = f(input)
      println(s"Input: $input, Result: $result")
    }
  }

  def f(input: List[Int]): List[Int] = {
    input.foldLeft(List.empty[Int]) { (acc, item) =>
      if (acc.contains(item)) {
        acc.dropRight(acc.length - acc.lastIndexOf(item) - 1)
      } else {
        acc :+ item
      }
    }
  }
}

```
> 2 votes

# Answer
# JavaScript (ES6), 53 bytes

### Version 1

```
f=(a,i=0,v=a[i])=>v?[v,...f(a,a.lastIndexOf(v)+1)]:[]

```

Try it online!

### Version 2

```
f=a=>a+a?[v=a[0],...f(a.slice(a.lastIndexOf(v)+1))]:a

```

Try it online!
> 1 votes

---
Tags: code-golf, graph-theory
---


title: Turn Two Dice Into One

text:
# Question
Title: Turn Two Dice Into One
A neat trick is if you ever need a nine-sided die, it is possible to make one using two six-sided dice using the numbers below. This is assuming you either have a way to rewrite the faces on the dice, or use some algorithm to map the numbers on a normal die onto these new numbers.

```
  0 0 3 3 6 6
  -----------
1|1 1 4 4 7 7
1|1 1 4 4 7 7
2|2 2 5 5 8 8
2|2 2 5 5 8 8
3|3 3 6 6 9 9
3|3 3 6 6 9 9

```

The challenge is:

* You are given two fair dice, die1 with A faces and die2 with B faces, where A may not necessarily equal B. You need to write numbers on the faces of those dice to create a "target die" with N faces. The numbers of the faces of die1 and die2 will be such that, if rolled and their results summed, it would yield a fair target die. The new numbers written on the dice must greater than or equal to zero (that is, no negative numbers can be on the new dice).
* Results should be a list (or whatever appropriate and reasonable format) of new faces for both die1 and die2. The numbers in those lists are not required to be in any sorted order.
* Assume A, B, and N are all given as positive integers, and that N is a divisor of A\*B.
* The target die is a regular, fair die with numbers 1 to N on its faces.
* If there are multiple solutions (such as when creating a one-sided die), you only need to return one solution from any of the possible solutions.

## Examples

```
input:                     input:
die1 = 6                   die1 = 5
die2 = 6                   die2 = 12
target = 9                 target = 20

output:                    output:
[0,0,3,3,6,6]              [1,2,3,4,5]
[1,1,2,2,3,3]              [0,0,0,5,5,5,10,10,10,15,15,15]

input:                     input:
die1 = 6                   die1 = 12
die2 = 4                   die2 = 12
target = 8                 target = 18

output:                    output:
[0,0,0,4,4,4]              [1,1,2,2,3,3,4,4,5,5,6,6]
[1,2,3,4]                  [0,0,0,0,6,6,6,6,12,12,12,12]

```

Normal code golf rules apply. Shortest answer in bytes wins.

# Answer
# Python NumPy, 67 bytes

```
lambda n,m,o:(x:=r_[:n]*m%o,r_[:m]%(o-max(x))+1)
from numpy import*

```

Attempt This Online!

# Python, 77 bytes

```
lambda n,m,o,r=range:(x:=[a*m%o for a in r(n)],[b%(o-max(x))+1for b in r(m)])

```

Attempt This Online!

Just saw that output is not required to be sorted.

### Python NumPy, 75 bytes

```
lambda n,m,o:(x:=sort(r_[:n]*m%o),r_[:m]*(o-x[-1])//m+1)
from numpy import*

```

Attempt This Online!

### Python, 85 bytes

```
lambda n,m,o,r=range:(x:=sorted(a*m%o for a in r(n)),[b*(o-x[-1])//m+1for b in r(m)])

```

Attempt This Online!
> 9 votes

# Answer
# JavaScript (ES6), 116 bytes

Expects `(die1,die2)(target)`.

```
(a,b,d=b+1)=>g=c=>c%--d||a%d&&b%d?g(c):[a,b].map((n,j)=>[...Array(n)].map((_,i)=>~~(i*(j?d:c/d)/n+j)*(j||d),j^=a<b))

```

Try it online!
> 5 votes

# Answer
# Python 3, 93 bytes

```
import math
def f(a,b,t):A=math.gcd(a,t);return[*range(1,A+1)]*(a//A),([*range(0,t,A)]*b)[:b]

```

Try it online!
> 5 votes

# Answer
# Japt, ~~17~~ 15 bytes

Output is `[d1.1,...,d1.n,[d2.1,...,d2.n]]`

```
Ç*V%WÃpVogVyW õ

```

Try it (footer splits & sorts output) or run all test cases

```
Ç*V%WÃpVogVyW õ     :Implicit input of integers U=a, V=b & W=n
Ç                   :Map the range [0,U)
 *V%W               :  Multiply by V and modulo by W
     Ã              :End map
      p             :Push
       Vo           :  Range [0,V)
         g          :  Index (0-based and modular) each into
          VyW       :    GCD of V & W
              õ     :    Range [1,VyW]

```
> 5 votes

# Answer
# Charcoal, 27 bytes

```
ＮθＮηＮζ≔﹪×…⁰θηζεＩ⟦ε⊕﹪…⁰η⁻ζ⌈ε

```

Try it online! Link is to verbose version of code. Explanation: Port of @loopywalt's Python answer.

```
ＮθＮηＮζ

```

Input the dice.

```
≔﹪×…⁰θηζε

```

Multiply all of the digits on a regular first die by the size of the second die and reduce modulo the size of the third die.

```
Ｉ⟦ε

```

Output that as the first die, and as the second die output...

```
⊕﹪…⁰η⁻ζ⌈ε

```

... the digits on a regular second die modulo the minimum step in values on the output first die (calculated as the size of the third die minus the maximum value on the output first die, although the minimum nonzero value also works), plus one.
> 4 votes

# Answer
# Go, 139 bytes

```
func f(a,b,t int)(l,r[]int){i,j,x,y:=0,0,b,t
for y!=0{g:=y;y,x=x%y,g}
for;i<a;i++{l=append(l,i*b%t)}
for;j<b;j++{r=append(r,j%x+1)}
return}

```

Attempt This Online!

Port of Shaggy's answer.
> 4 votes

# Answer
# Rust, ~~170~~ ~~159~~ 151 bytes

* -8 bytes thanks to corvus\_192

```
|a,b,c|(1..a).filter(move|d|a%d+b%d+c%(a/d)<1).flat_map(|d|[(d,1),(a/d,d)]).zip([b,c]).map(move|((u,w),e)|(0..e).map(|v|v/(e/u)*w).collect()).collect()

```

Attempt This Online!
> 3 votes

# Answer
# JavaScript (Node.js), 81 bytes

```
(a,b,x)=>(g=i=>x%i|b%i?g(--i):[a,b].map(Z=n=>n--?[n*i%x+1||n%i,...Z(n)]:x=''))(b)

```

Try it online!
> 3 votes

# Answer
# Nibbles, 12 bytes (24 nibbles)

```
`:;.*@,_%$@+~.,_%$`/|@$[

```

Same approach as Neil's answer (which apparently is a port of loopy walt's answer): upvote those!

Input is target, die1, die2.

```
`:;.*@,_%$@+~.,_%$`/|@$[
`:                          # output list of 2 lists:
  ;                         #   save list 1:
    *                       #     multiply
     @                      #     sides of die1 by
      ,_                    #     each value of die2
   .                        #     and map over each of thes values
        %$                  #       modulo it by
          @                 #       sides of the target die
                            #   now make list 2:
                    |@$     #     remove nonzero values from list 1
                  `/        #     and fold over this
                       [    #     getting the minimum;
             .,_            #     now map over values of die1
                %$          #       moduloing each by
                            #       minimum nonzero value of list 1
           +~               #     and add 1 to each

```
> 3 votes

# Answer
# 05AB1E, 13 bytes

```
L*I%=αß²Ls%>?

```

Port of *@loopyWalt*'s Python answer.

Three loose inputs in the order \\$die1,die2,target\\$, output printed as two separated lists.

Try it online or verify all test cases.

Could alternatively be output as a pair of lists:

```
L*I%ZIα²Ls%>‚

```

Try it online or verify all test cases.

**Explanation:**

```
L         # Push a list in the range [1, first (implicit) input die1]
 *        # Multiply each value by the second (implicit) input die2
  I%      # Modulo each by the third input target
    =     # Print it with trailing newline (without popping)
α         # Take the absolute difference between the third (implicit) input target and
          # each value in the list
 ß        # Pop and push the minimum
  ²L      # Push a list in the range [1, input die2]
    s     # Swap so the minimum absolute difference is at the top
     %    # Modulo each value in the list by this
      >   # Increase each by 1
       ?  # Pop and output it (without trailing newline) as well

```
> 3 votes

# Answer
# Japt, 27 bytes

```
k
[V=ogVk fU2 ×õ)WogU×o*VÌ]

```

Try it

Input as `target die1 die2`, Output as `[[<die1 sides>],[<die2 sides>]]`, unsorted.

Explanation:

```
k
k              # Get the prime factors of <target>
               # Store as U

[...]          # Return the enclosed statements as an array:

V=ogVk fU2 ×õ)
    Vk         #  Prime factors of <die1>
       fU2     #  Remove and return from U numbers that are in both
           ×   #  Multiply them together
            õ  #  Get the range [1...N]
   g         ) #  Index into that range (wrapping):
  o            #   Numbers in [0...<die1>-1]
V=             #  Store as V and return it

WogU×o*VÌ
   U           #  The remaining numbers in U
    ×          #  Multiplied together
     o         #  For X in the range [0...N-1]:
      *        #   Multiply X by
       VÌ      #   The last (highest) number in V
  g            #  Index into the result (wrapping):
Wo             #   Numbers in the range [0...<die2>-1]

```
> 2 votes

# Answer
# C (gcc), 101 bytes

```
x;y;*p;f(a,b,n,r){p=r;for(x=n,y=a;r=y%=x;x=r)y=x;for(;a--;*p++=y--)y=y?:x;for(;b--;*p++=y-=x)y=y?:n;}

```

Try it online!

**Edit #1:** -1 byte thanks to ceilingcat
> 2 votes

# Answer
# Scala, ~~177~~ 172 bytes

saved bytes due to replacing `List` to `Seq`

---

Golfed version, try it online!

```
val f=(a:Int,b:Int,c:Int)=>(1 to a).filter(d=>a%d+b%d+c%(a/d)<1).flatMap(d=>Seq((d,1),(a/d,d))).zip(Seq(b,c)).map{case ((u,w),e)=>(0 until e).map(v=>v/(e/u)*w).toSeq}.toSeq

```

Ungolfed version

```
object Main {
  def main(args: Array[String]): Unit = {
    val f = (a: Int, b: Int, c: Int) =>
      (1 to a)
        .filter(d => a % d + b % d + c % (a / d) < 1)
        .flatMap(d => List((d, 1), (a / d, d)))
        .zip(List(b, c))
        .map { case ((u, w), e) => (0 until e).map(v => v / (e / u) * w).toList }
        .toList

    val d = f(4, 4, 4)
    println(f(9, 6, 6))
    println(f(9, 6, 3))
    println(f(18, 6, 6))
    println(f(18, 6, 3))
    println(f(20, 5, 12))
  }
}

```
> 2 votes

---
Tags: code-golf
---


title: Calculating areas.

text:
# Question
Title: Calculating areas.
The smallest code that gives the area between the curve p(x) = a0 \+ a1\*x + a2\*x2 \+ ..., the line y = 0, the line x = 0 and the line x = C

(i.e. something like this:

)

You can assume that p(x) \>= 0 for x \< C (bonus points if your code works for negative values of p(x)).

### Input

C, a0, a1, ...

### Output

a real number - the area

Example 1:

```
input: 2, 0, 1
output: 2.0

```

Examlpe 2:

```
input: 3.0, 0, 0.0, 2
output: 18

```

UPDATE:

* C \> 0 is also assumed
* the area is between the curve, y=0, x=C **and x = 0**
* the input can be a list of any form; not necessarily comma separated.
* the output can be a real of any form (thus, '18' is a valid output, as is '18.0')

# Answer
> 3 votes
## Mathematica: 48 Chars

.

```
Sum[#[[i+1]]#[[1]]^i/i,{i,Length@#-1}]&@Input[]

```

# Answer
> 10 votes
# APL (Dyalog Unicode), 9 bytes

```
⊃⊥∘⌽⊢÷⍳∘≢

```

Try it online!

A tacit function that takes `C, a0, a1, ...` as a single vector argument.

**12 bytes** if a full program is needed. Note that, while the default representation for a numeric vector is the numbers separated by spaces (no comma or anything), it accepts comma-separated ones since  evals the input and `,` is the "concatenate" function.

```
(⊃⊥∘⌽⊢÷⍳∘≢)⎕

```

Try it online!

Uses `⎕IO←0` and `⎕DIV←1`, so that the range generation is 0-based and division by zero gives 0.

Because the polynomial is nonnegative and the integral starts at 0, it suffices to evaluate the antiderivative of the given polynomial at C.

The antiderivative of \\$a\_0 + a\_1x + a\_2x^2 + \dots\\$ is \\$a\_0x + \frac{a\_1}{2} x^2 + \frac{a\_2}{3} x^3 + \dots\\$. Because we have C attached to the start of the vector, we simply divide the entire array by their 0-based indexes:

```
       C  a0   a1   a2
input: 3  0    0    2
div  : 0  1    2    3
res  : 0  0    0    2/3
       0  a0/1 a1/2 a2/3

```

Then we simply evaluate the resulting polynomial at C.

### How it works: the code

```
⊃⊥∘⌽⊢÷⍳∘≢  ⍝ Input: single array of C, a0, a1, a2, ...
      ⍳∘≢  ⍝ 0-based range 0, 1, 2, 3, ...
    ⊢÷     ⍝ Divide self by above
  ∘⌽       ⍝ Reverse
⊃⊥         ⍝ Convert from base C to real number
           ⍝ i.e. evaluate the polynomial, lowest term given last

```

# Answer
> 5 votes
**Python - 71 63 chars:**

```
a=input()
print sum(1.*a[i]*a[0]**i/i for i in range(1,len(a)))

```

It's a simple integration of a polynomial function between `0` and `C`. And I haven't tested it, but I'm quite sure it works for negative values.

# Answer
> 4 votes
## J, 26 characters

```
f=:3 :'((1}.y)&p.d._1)0{y'

```

e.g.

```
   f 2 0 1
2
   f 3 0 0 2
18

```

# Answer
> 3 votes
## Haskell, 85 characters

```
f(c:l)=sum.map(\(i,x)->x*c**i/i)$zip[1..]l
main=getLine>>=print.f.read.('[':).(++"]")

```

# Answer
> 3 votes
# APL(NARS), 8 chars, 16 bytes

```
∘{⍵⊥⌽⍺}∫

```

The new NARS2000 function integrate, ∫.

it seems f∫b is integrate(f, 0..b)=∫\_0^b f Here i don't know if can be ok, the right argument is the max of interval of integration \[0, max\] and the left argument is the list of numbers represent polinomy...

```
  f←∘{⍵⊥⌽⍺}∫
  0 1 f 2
2
  0 0 2 f 3
18
  1 2 3 4 5 6 f 7
137256

```

# Answer
> 2 votes
## Ruby, 65 chars

```
i=s=0
c=gets(q=",").to_f
$<.each(q){|a|s+=a.to_f*c**(i+=1)/i}
p s

```

The code reads until the end of input, not the end of the line. So you need to hit `Ctrl`+`D` to terminate input. (Pipe the input in using `echo` or from a file.)

# Answer
> 2 votes
## C GCC ~~186~~ 182 bytes

```
f(){i=0,l=1;float *d,s=0.0;d=malloc(sizeof(float)*50);scanf("%f",&d[0]);while(getchar()!='\n'){scanf("%f",&d[l]);l++;}for(i=0;i<l;i++)s+=d[i+1]*pow(d[0],(i+1))/(i+1);printf("%f",s);}

```

This program gives an output (area) for any curve between the curve, y=0, x=C and x=0. It can take coefficients (`float` as well) from a0 to a48. The first accepted input is `C` followed by coefficients. Press `Ènter` after the last coefficient.

```
void f()
{
  int i=0,l=1;
  float *d,s=0.0;
  const int sz=100;
  d=malloc(sizeof(float)*sz);

  scanf("%f",&d[0]);
  while(getchar()!='\n')
  {
    scanf("%f",&d[l]);
    l++;
  }

  for(i=0;i<l;i++)
    s+=d[i+1]*pow(d[0],(i+1))/(i+1);

   printf("%f",s);
}

```

# Answer
> 1 votes
# Mathematica, 48 bytes

Try it online!

```
f[a_]:=Sum[a[[i+1]]*a[[1]]^i/i,{i,1,Length@a-1}]

```

---
Tags: code-golf
---


title: How Super is this Prime?

text:
# Question
Title: How Super is this Prime?
A super prime is a prime whose index in the list of primes is also a prime:

```
3, 5, 11, 17, 31, 41, 59, 67, 83, 109, 127, 157, 179, 191, 211, 241, 277, 283, 331, 353, 367, 401, 431, 461, 509, 547, 563, 587, 599, 617, 709, 739, 773, 797, 859, 877, 919, 967, 991, ...

```

For this challenge, an "order 2" super prime is defined as a super prime whose index in the list of super primes is a super prime:

```
11, 31, 127, 277, 709, 1063, 1787, 2221, 3001, 4397, ...

```

An "order 3" super prime is an order 2 super prime whose index in the list of order 2 super primes is an order 2 super prime:

```
5381, 52711, 648391, ...

```

And so on.

## Task

Your task is to write a program or function, which, when given a prime, outputs/returns the highest order of super primes that the prime is a part of.

In other words, how "super" is the prime?

## Rules

* This is so the solution with the lowest byte count wins
* Standard loopholes are forbidden
* The index of each prime in the list of primes, super primes, and so on, is assumed to be 1-indexed
* You must output:
    + 0 for primes which are not super primes
    + 1 for super primes which are not order 2 super primes
    + 2 for order 2 super primes which are not order 3 super primes
    + And so on
* You can assume inputs will always be prime numbers

## Test Cases

```
2 -> 0
3 -> 1
11 -> 2
211 -> 1
277 -> 2
823 -> 0
4397 -> 2
5381 -> 3
171697 -> 2
499403 -> 2
648391 -> 3

```

Your program must in theory be able to handle any order of super prime from 0 to infinity, even if it can only do the first few in a reasonable time.

# Answer
# Jelly,  ~~12 11~~  10 bytes

```
ÆRJfịƊƬḊẎċ

```

A monadic Link that accepts a prime integer and yields the level.

**Try it online!**

### How?

```
ÆRJfịƊƬḊẎċ - Link: prime number, P   e.g
ÆR         - get all primes in [2..P] in ascending order
      Ƭ    - start with L=that and collect up while distinct applying:
     Ɗ     -   last three links as a monad - f(L):
  J        -     indices of L -> [1..length(L]
   f       -     filter keep if in (L)
    ị      -     index into (L) -> next level, less than or equal to P -> new L
       Ḋ   - dequeue - remove the initial list of primes
        Ẏ  - tighten - to a flat list of all of the numbers found at all levels
         ċ - count occurrences of (P)

```
> 5 votes

# Answer
# Wolfram Language (Mathematica), 43 bytes

```
If[PrimeQ@#,1+#0@PrimePi@#,0]&/*Log2/*Floor

```

Try it online!

Primes of order \\$n\\$ are those that are a result of applying `Prime` (with `Prime[x]` the `x`th prime) on an integer \\$2^n\\$ times.
> 4 votes

# Answer
# Vyxal, 21 bytes

```
Þp¥(¨₂›æ;)ḟ›&›)⁽æ$ŀL‹

```

Try it Online!

## Explained

```
Þp¥(¨₂›æ;)ḟ›&›)⁽æ$ŀL‹
              )⁽  $ŀ   # While applying function ⁽ on the result of function ) is true, collect results.
               ⁽æ      # Function ⁽: Is argument prime?
Þp¥(¨₂›æ;)ḟ›&›)        # Function ):
Þp                     #   The list of all primes
  ¥(     )             #   #register times (starts at 0):
    ¨₂  ;              #     Filter the top of the stack by:
      ›                #       item index + 1
       æ               #       is prime
                       #   This gets the (register)th order super primes
          ḟ›           #   Find the index of the function argument in that list
            &›         #   Increment the register for the next iteration
                    L‹ # Length of that - 1

```
> 3 votes

# Answer
# JavaScript (ES6), 84 bytes

```
n=>~~Math.log2((g=n=>{for(i=k=0;k<n;i+=!d)for(d=k++;k%d--;);return!d*n&&1+g(i)})(n))

```

Try it online!
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~106~~ ~~98~~ 66 bytes

```
   (a=Prime@Range@PrimePi@#;0)//.c_/;!FreeQ[a=0&@@a[[#]]&/@a,#]:>c+1&

```

Try it online!

Thanks to @att!

Old less golfed version for such noobs as I am:

```
(a=Table[Prime@k,{k,PrimePi@#}];
  c=0;
  While[
    MemberQ[a=If[#<=Length@a,a[[#]],Nothing]
     /@a,#],
  c++];
c)&

```
> 2 votes

# Answer
# 05AB1E, 12 bytes

```
ÅP.ΓDāåÏ}˜I¢

```

Very slow for larger inputs due to the `āåÏ`. The test suite below uses the legacy version with a slightly modified (1 byte longer) version to speed it up significally - although it'll still time out for the largest two test cases.

Try it online or verify all test cases.

**Explanation:**

```
ÅP        # Push a list of all primes <= the (implicit) input-prime
  .Γ      # Loop until the result no longer changes, retaining any intermediate results:
    D     #  Duplicate the current list
     ā    #  Push a list in the range [1,length] (without popping)
      å   #  Check for each index whether it's in the list
       Ï  #  Only keep the values at the truthy indices
   }˜     # After the changes-loop: flatten the list of lists
     I¢   # Count the input in this flattened list
          # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 354 bytes

Try it online!

```
NMax=648391;OrderMax=4;PrimePiPowerNest=Composition@@Table[PrimePi,{2^#}]&;x=Prime[Range@*PrimePi@NMax];res={x};n=1;While[n<=OrderMax,x=Table[x[[i]],{i,x[[;;PrimePiPowerNest[n][NMax]]]}];res=Append[res,x];n++];f[num_]:=Module[{i,output},output=-1;For[i=1,i<Length[res],i++,If[MemberQ[res[[i]],num]&&!MemberQ[res[[i+1]],num],output=i-1;Break[];];];output]

```

---

How does it work? Or Ungolfed version:

```
ClearAll["Global`*"];

NMax = 648391;
OrderMax = 4;

PrimePiPowerNest[n_] := Composition @@ Table[PrimePi, {2^n}];
PrimePowerNest[n_] := Composition @@ Table[Prime, {2^n}];
x = Prime[Range[1, PrimePi[NMax], 1]];
res = {x};
n = 1;
While[n <= OrderMax,
 x = Table[x[[i]], {i, x[[;; PrimePiPowerNest[n][NMax]]]}];
 Print[x[[;; 5]]];
 res = Append[res, x];
 n++]

f[num_] := Module[{i, output}, output = -1;
 For[i = 1, i < Length[res], i++,
  If[MemberQ[res[[i]], num] && ! MemberQ[res[[i + 1]], num],
    output = i - 1;
    Break[];];];
 output]    (*input 648391 output 3, 648391 is 3 order super prime*)

f[2]//Print
f[3]//Print
f[11]//Print
f[211]//Print
f[277]//Print
f[823]//Print
f[4397]//Print
f[5381]//Print
f[171697]//Print
f[499403]//Print
f[648391]//Print

```

the \\$k\\$-th element of \\$n\\$-order super prime is just `PrimePowerNest[n][k]`
> 0 votes

---
Tags: code-golf, number, primes
---


# Question
Title: CGAC2022 Day 24: North Pole Railroads, Part 2
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

Santa and the Elves are secretly preparing for a new tourist train service, called "North Pole Railroads". The train will travel through various sightseeing spots near the North Pole.

As a part of this project, they want to know how many seats they will need. They already have the list of travels for each passenger (given as "from station X to station Y"), which is thanks to the same magic that lets Santa know which children are nice. Each station is numbered from 1, starting from the North Pole.

The Elves are arguing over how to determine the number of seats. Another option is to have just enough seats to allow all passengers to choose their seats. Note that they will have to consider all possible order of reservations. Two passengers with strictly overlapping travel cannot share a seat (e.g. one is `(1, 3)` and the other is `(2, 4)`), but a travel that ends at X is not overlapping with another that starts at X.

## Task

Given the list of `X, Y` pairs that represent the travel of each passenger, output how many seats will be needed for North Pole Railroads.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
(1, 2), (2, 3), (1, 3), (3, 4) -> 3
1---2---3---4
 AAA     DDD
     BBB
 CCCCCCC
Explanation: if A takes seat 1 and B takes seat 2, C needs the third seat

(1, 2), (1, 3), (2, 3), (3, 4) -> 3
Explanation: the order in the input does not matter

(1, 3), (1, 3), (3, 6), (3, 6) -> 2

(1, 5), (2, 8), (6, 9), (5, 7), (4, 6) -> 5
Explanation: B's travel overlaps with the other 4, so if ACDE gets to book first,
B will need the 5th seat

```

# Answer
> 5 votes
# Jelly, 10 bytes

```
<>ƭ"Ạ¥þUSṀ

```

Try it online!

The goal is to find the passenger that whose journey overlaps with the most other passengers. The result is that number +1.

```
<>ƭ"Ạ¥þUSṀ
      þU    - outer product with itself with reversed elements
<>ƭ"Ạ¥      -   takes [a, b], [c, d] and returns a<c && b>d
        S   - sum rows
         Ṁ  - maximum

```

# Answer
> 1 votes
# , 44 bytes

```
\(a,b)max(rowSums((d=sapply(a,`<`,b))&t(d)))

```

Attempt This Online!

Same approach as AndrovT (upvote that!), combined with the observation that we can just calculate a single matrix of start-greater-than-stops, and AND it with itself after transposing to get the matrix of all passenger overlaps.
Calculating the matrix is easy in R by taking input as two lists, one of starts and one of stops, and using a vectorized greater-than comparison.

# Answer
> 0 votes
# JavaScript (Node.js), 60 bytes

```
x=>Math.max(...x.map(v=>x.map(w=>n+=w.r>v.l&v.r>w.l,n=0)|n))

```

Try it online!

Same approach as AndrovT

# Answer
> 0 votes
# Charcoal, 20 bytes

```
ＵＭθ…⌊ι⌈ιＩ⌈ＥθＬΦθ⁻ι⁻ιλ

```

Try it online! Link is to verbose version of code. Explanation: Assumes that @AndrovT's interpretation of the problem is correct.

```
ＵＭθ…⌊ι⌈ι

```

Turn each starting and ending pair into a range.

```
Ｉ⌈ＥθＬΦθ⁻ι⁻ιλ

```

For each passenger, do double set difference to see whether how many ranges intersect with other passengers and output the maximum.

# Answer
> 0 votes
# Scala, 72 bytes

Modified from @AndrovT's answer

---

Golfed version, try it online!

```
def f(t:List[Interval]):Int={t.map{v=>t.count{w=>w.r>v.l&&v.r>w.l}}.max}

```

Ungolfed version

```
object Main {
  def main(args: Array[String]): Unit = {
    val intervals = List(Interval(1, 5), Interval(2, 8), Interval(6, 9), Interval(5, 7), Interval(4, 6))
    println(maxOverlap(intervals))
  }

  case class Interval(l: Int, r: Int)

  def maxOverlap(intervals: List[Interval]): Int = {
    intervals.map { v =>
      intervals.count { w =>
        w.r > v.l && v.r > w.l
      }
    }.max
  }
}

```

---
Tags: code-golf
---


# Question
Title: A Fine sequence with fine interpretations
The ubiquitous Catalan numbers \\$C\_n\\$ count the number of *Dyck paths*, sequences of up-steps and down-steps of length \\$2n\\$ that start and end on a horizontal line and never go below said line. Many other interesting sequences can be defined as the number of Dyck paths satisfying given conditions, of which the *Fine sequence* \\$F\_n\\$ (not the Fibonacci numbers and not related to any common definition of "fine") is one.

Let a *hill* be a sequence of an up-step followed by a down-step that starts – and therefore also ends – on the horizontal line. \\$F\_n\\$ is then the number of Dyck paths of length \\$2n\\$ with **no** hills. The picture below illustrates this: there are \\$C\_5=42\\$ Dyck paths of length \\$10\\$, of which \\$F\_5=18\\$ (marked in black) have no hills.

This sequence is OEIS A000957 and begins $$\begin{array}{c|ccccccccccc} n&0&1&2&3&4&5&6&7&8&9&10\\ \hline F\_n&1&0&1&2&6&18&57&186&622&2120&7338 \end{array}$$ $$\begin{array}{c|ccccccccccc} n&11&12&13&14&15\\ \hline F\_n&25724&91144&325878&1174281&4260282 \end{array}$$

Other things counted by the Fine numbers include

* the number of Dyck paths of length \\$2n\\$ beginning with an even number of up-steps
* the number of ordered trees with \\$n+1\\$ vertices where the root has no leaf children
* the number of ordered trees with \\$n+1\\$ vertices where the root has *an even number of* children
* and so on. For more interpretations see Deutsch and Shapiro's "A survey of the Fine numbers".

## Formulas

You may use any correct formula to generate the sequence. Here are some:

* The generating function is $$\sum\_{n=0}^\infty F\_nz^n=\frac1z\cdot\frac{1-\sqrt{1-4z}}{3-\sqrt{1-4z}}$$
* For \\$n\ge1\\$, \\$C\_n=2F\_n+F\_{n-1}\\$.
* An explicit formula: $$F\_n=\frac1{n+1}\sum\_{k=0}^n(-1)^k(k+1)\binom{2n-k}{n-k}$$

## Task

Standard rules apply to this challenge, where permissible behaviours are

* outputting the \\$n\\$th term in 0- or 1-based indexing given \\$n\\$
* outputting the first \\$n\\$ terms given \\$n\\$
* outputting the infinite sequence with no input, either by printing or returning a lazy list/generator

This is ; fewest bytes wins.

# Answer
> 6 votes
# Python 2, 58 bytes

```
i=a=1;b=0
while 1:print a;i+=1;a,b=2*b+7*a/2-(2*a+b)*3/i,a

```

Try it online!

Prints the sequence endlessly. The method substitutes \\$C\_n = 2F\_n + F\_{n-1} \\$ into the Catalan recurrence $$ C\_n = 4C\_{n-1} - \left\lfloor \frac{6C\_{n-1}}{n+1} \right\rfloor $$

# Answer
> 6 votes
# Vyxal, 22 10 7 bytes

-12 bytes by emanresu A (double welp)
-3 bytes by alephalpha using a clever approach

```
ꜝ$ʀƈ¦ṁȧ

```

Try it Online!

**How it works**

```
ꜝ$ʀƈ¦ṁȧ
ꜝ$               Bitwise not n and swap with input
  ʀƈ             Take the binomial coefficient
    ¦ṁȧ          Cumultative sum, take the mean and push the absolute value

```

# Answer
> 5 votes
# HOPS, 19 bytes

```
C=1+x*C^2;C/(1+x*C)

```

Attempt This Online!

The generating function of the Catalan numbers satisfies \\$C(x)=1+x\ C(x)^2\\$. The generating function of this sequence is \\$F(x)=C(x)/(1+x\ C(x))\\$.

---

# HOPS, 21 bytes

```
2/(1+2*x+sqrt(1-4*x))

```

Attempt This Online!

A simplified version of the generating function.

It seems that HOPS on ATO is currently not working.

# Answer
> 5 votes
# Python 3, 61 bytes

```
f=lambda n,v=1:sum(f(i,0)*f(n+~i,v)for i in range(v,n))or 1-n

```

Try it online!

# JavaScript (Node.js), 50 bytes

```
f=(n,v=1,i=v)=>i<n?f(i,0)*f(n+~i,v)+f(n,v,i+1):+!n

```

Try it online!

Another 47 bytes JavaScript answer but output `true` and `false` for `f(0)`, `f(1)`.

First, we write down following recursive formula:

$$F\_n=\sum\_{i=1}^{n-1}C\_i\cdot F\_{n-i-1}$$ $$F\_1=0, F\_0=1$$ $$C\_n=\sum\_{i=0}^{n-1}C\_i\cdot C\_{n-i-1}$$ $$C\_0=1$$

Then, we try to merge two functions into one

$$f(x,1):=F\_x$$ $$f(x,0):=C\_x$$ $$f(x,v)=\begin{cases}\sum\_{i=v}^{x-1}f(i,0)\cdot f(x-i-1,v) & x\>v\\ 0 & x=v=1 \\ 1 & x=0 \end{cases}$$

# Answer
> 4 votes
# JavaScript (ES6), 48 bytes

Returns the \\$n\\$-th term (0-indexed).

Inspired by the Catalan recurrence pointed out by Sisyphus.

```
f=n=>n?(g=n=>n?g(n-1)*(4+6/~n):1)(n)-f(n-1)>>1:1

```

Try it online!

---

# JavaScript (ES6), 60 bytes

Returns the \\$n\\$-th term (0-indexed).

This is based on the explicit formula provided in the challenge.

```
f=(n,k=n)=>~k&&(g=v=>v--?(v-n-k)*g(v)/~v:--k-n)(k)/~n-f(n,k)

```

Try it online!

# Answer
> 4 votes
# Desmos, ~~46~~ 41 bytes

```
f(n)=-∑_{k=1}^n(-1)^kknCr(2n-k-1,n-k)/n

```

A port of the explicit formula but with one-indexing instead of zero-indexing.

Try It On Desmos!

Try It On Desmos! - Prettified

### Proof for the formula:

We start with the explicit formula given in the question: $$F(n)=\frac1{n+1}\sum\_{k=0}^n(-1)^k(k+1)\binom{2n-k}{n-k}$$ Then convert it to one-indexing (making a new function \\$f\\$) by doing the following: $$f(n)=F(n-1)=\frac1n\sum\_{k=0}^{n-1}(-1)^k(k+1)\binom{2n-k-2}{n-k-1}$$ From there, shift the bounds of the summation up by one, making sure to correct the shift within the summation: $$\frac1n\sum\_{k=0}^{n-1}(-1)^k(k+1)\binom{2n-k-2}{n-k-1}=\frac1n\sum\_{k=1}^n(-1)^{k-1}k\binom{2n-k-1}{n-k}$$ Factoring out a \\$-1\\$ gives the formula used in my answer: $$f(n)=-\frac1n\sum\_{k=1}^n(-1)^kk\binom{2n-k-1}{n-k}$$

# Answer
> 4 votes
# 05AB1E, ~~22~~ ~~21~~ 14 bytes

```
xŸIc2Å€(}ηOÅAÄ

```

Port of *@mathcat*'s Vyxal answer, so make sure to upvote him as well!

Uses the formula: $$G\_{n,k} = (-1)^{(k+1)}\binom{k}{n} + G\_{n-1,k}\\ F\_n=\left|\frac{1}{n+1}\sum\_{k=n}^{2n}G\_{n,k}\right|$$
Given \\$n\\$, it'll output \\$F\_n\\$.

Try it online or verify all test cases.

**Explanation:**

```
x              # Push double the (implicit) input (without popping)
 Ÿ             # Pop both, and push a list in the range [input,2*input]
  Ic           # Calculate the bionomical coefficient of each value with the input
    2Å€(}      # Negate every second item, starting with the first:
    2          #  Push a 2
     Å€ }      #  Map over each item where the 0-based index is divisible by 2:
       (       #   Negate that item
         ηO    # Calculate its cumulative sum:
         η     #  Get all prefixed of this list
          O    #  Sum each inner prefix-list together
           ÅA  # Get the arithmetic mean of that
             Ä # Convert it to its absolute value
               # (after which it is output implicitly as result)

```

---

**Original ~~22~~ 21 bytes answer:**

```
ÝεÈ·<y>Ixs‚y-`cI>zP}O

```

-1 byte thanks to *@emanresuA*

Uses the given explicit formula: $$F\_n=\sum\_{k=0}^n(-1)^k(k+1)\binom{2n-k}{n-k}\frac1{n+1}$$
Given \\$n\\$, it'll output \\$F\_n\\$.

Try it online or verify all test cases.

**Explanation:**

```
Ý              # Push a list in the range [0, (implicit) input]
 ε             # Map each integer to:
  È            #  Check whether it's even
   ·           #  Double that check (2 if even; 0 if odd)
    <          #  Decrease it by 1 (1 if event; -1 if odd)
  y>           #  Push the current integer, and decrease it by 1
  I            #  Push the input
   x           #  Double it (without popping)
    s‚         #  Swap, and pair them together: [2n,n]
      y-       #  Subtract the current integer from each: [2n-k,n-k]
        `      #  Pop and push the values back to the stack
         c     #  Calculate their binomial coefficient
  I>z          #  Push 1/(input+1)
  P            #  Take the product of the four values on the stack
 }O            # After the map: sum them together
               # (after which the result is output implicitly)

```

# Answer
> 4 votes
# Jelly, ~~12~~ 11 bytes

```
ḤrcµJNÐeḋ:L

```

Try it online!

Port of emanresu A's golf to mathcat's Vyxal solution.

```
Ḥrc            Each of [2n .. n] choose n.
   µ    ḋ      Take the dot product of that with
    J          [1 .. n+1]
     NÐe       with every other element negated,
         :     and (floor) divide that by
   µ      L    n+1.

```

# Jelly, 18 bytes

```
o2µḤœcµṬ-*ÄAƑ×ṂḂ)S

```

Try it online!

Haven't actually tried any closed form or recursive formulae, but ignoring the special case fix for \\$n=0\\$ this brute-force enumeration feels elegant enough to post, ~~especially considering how the current golflang closed form solutions are~~. Leverages the "even number of leading up-steps" interpretation--or rather, "first down-step at an odd 1-index", hence the special case.

```
o2µ                   If n is 0, from here on out, pretend it's 2.
    œc                Get every combination of n elements from
   Ḥ                  [1 .. 2n],
      µ         )     then for each combination:
       Ṭ-*            Produce a list of -1 at those indices and 1 elsewhere,
          Ä           take its cumulative sums,
           AƑ         and check that none of those is negative.
             ×        Multiply that result by
              Ṃ       the smallest element of the combination.
               Ḃ S    How many are odd?

```

# Answer
> 4 votes
# Python 2, 49 bytes

Prints the sequence indefinitely.

```
x=c=n=1
while 1:print x;n+=1;c=c*4-c*6/n;x=c-x>>1

```

Try it online!

Based on the Sage program at the end of the OEIS page.

# Answer
> 3 votes
# PARI/GP, 36 bytes

```
n->Vec(2/(1+2*x+sqrt(1-4*x+O(x^n))))

```

Attempt This Online!

Using the generating function.

---

# PARI/GP, 39 bytes

```
n->(matrix(n+1,,i,j,i>abs(j-2))^n)[1,1]

```

Attempt This Online!

Using this interesting formula on OEIS:

```
a(n) = the upper left term in M^n, n>0; where M = the infinite square production matrix:
0, 1, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, 1, ...
...
- Gary W. Adamson, Jul 14 2011

```

# Answer
> 3 votes
# Jelly, 7 bytes

```
~cŻÄÆmA

```

This calculates `abs(mean(cumsum(choose(-n-1, [0..n]))))`.

Try it online!

The "negative binomial coefficients" are defined as $$\binom{-a}{b} = (-1)^b \binom{a+b-1}{b}.$$ And they are supported by Jelly's `c`. So we can rewrite the closed form as:

\begin{align} F\_n&=\frac{1}{n+1}\sum\_{k=0}^n(-1)^k(k+1)\binom{2n-k}{n-k} \\ & \color{gray}{\text{(introduce negative binomials:)}} \\ &=\frac{1}{n+1}\sum\_{k=0}^n(-1)^k(k+1) \color{#0bf}{(-1)^{n-k} \binom{-n-1}{n-k}} \\ & \color{gray}{\text{(factor out powers of $-1$:)}} \\ &=(-1)^n \frac{1}{n+1} \sum\_{k=0}^n (k+1) \binom{-n-1}{n-k} \\ & \color{gray}{\text{(substitute $j=n-k$:)}} \\ &=(-1)^n \frac{1}{n+1} \sum\_{j=0}^n (n+1-j) \binom{-n-1}{j} \end{align}

The `~cŻ` generates the negative binomials \\$\binom{-n-1}{0}\\$ through \\$\binom{-n-1}{n}\\$.

Then we use an obscure trick: we can calculate \\$\sum\_{j=0}^n (n+1-j) \cdot z\_j\\$ as `sum(cumsum(z))`, or `ÄS` in Jelly parlance. But then because we want to divide by \\$n+1\\$ immediately after, and our list has \\$n+1\\$ elements, we can write `Æm` (mean) instead of `S` (sum).

Here's an example of why this works: \begin{align} & \textrm{sum}(\textrm{cumsum}(\[a,b,c,d\])) \\ =~& (a) + (a+b) + (a+b+c) + (a+b+c+d) \\ =~& 4a+3b+2c+d \end{align}

Finally we still have to multiply by \\$(-1)^n\\$ to fix the sign. But because we know the Fine numbers are never negative, we can just take the absolute value with `A`.

# Answer
> 2 votes
# Factor \+ `koszul math.combinatorics`, 69 bytes

```
[ 4 dupn + [a,b] [ -1^ -rot nCk * ] with map-index cum-sum mean abs ]

```

Try it online!

"Mathy" answers cause far too much whitespace in Factor so this is a port of mathcat's Vyxal answer.

# Answer
> 1 votes
# Charcoal, 25 bytes

```
⊞υ¹≔¹θＦＮ≔⊘⁻↨⊞ＯυΣ×⮌υυ⁰θθＩθ

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
⊞υ¹

```

Start with `C(0)` = 1.

```
≔¹θ

```

Start with `F(0)` = 1.

```
ＦＮ

```

Loop `n` times.

```
≔⊘⁻↨⊞ＯυΣ×⮌υυ⁰θθ

```

Calculate the next Catalan number from the dot product of the list of numbers with its reverse and use that to calculate the next Fine number.

```
Ｉθ

```

Output `F(n)`.

# Answer
> 1 votes
# Pyt, 32 bytes

```
Đ⁺Đř⁻ĐĐ05Ș↔+2ř*⇹ɐ-Á⇹ć⇹⁺*⇹1~⇹^·⇹/

```

Try it online!

Naive implementation of the formula in the question.

The following walkthrough of the code is worked on an input of n=3

| Code | Stack | Action |
| --- | --- | --- |
| Đ | 3 3 | implicit input; **Đ**uplicate |
|  | 3 4 | increment |
| Đ | 3 4 4 | **Đ**uplicate |
| ř | 3 4 \[1,2,3,4\] | **ř**angify |
|  | 3 4 \[0,1,2,3\] | decrement |
| ĐĐ | 3 4 \[0,1,2,3\] \[0,1,2,3\] \[0,1,2,3\] | **Đ**uplicate twice |
| 05Ș | 3 0 \[0,1,2,3\] \[0,1,2,3\] \[0,1,2,3\] 4 | Push **0**, then **Șwap** the top **5** items on the stack |
|  | 4 \[0,1,2,3\] \[0,1,2,3\] \[0,1,2,3\] 0 3 | Flip the entire stack |
| + | 4 \[0,1,2,3\] \[0,1,2,3\] \[0,1,2,3\] 3 | Remove that pesky 0 by adding |
|  | 4 \[0,1,2,3\] \[0,1,2,3\] \[0,1,2,3\] 3 \[1,2\] | Push **2** and **ř**angify |
| * | 4 \[0,1,2,3\] \[0,1,2,3\] \[0,1,2,3\] \[3,6\] | Multiply |
|  | 4 \[0,1,2,3\] \[0,1,2,3\] \[3,6\] \[0,1,2,3\] | Swap the top two items on the stack |
| ɐ- | 4 \[0,1,2,3\] \[0,1,2,3\] \[\[3,2,1,0\],\[6,5,4,3\]\] | For **ɐ**ll pairs of values, subtract |
| Á | 4 \[0,1,2,3\] \[0,1,2,3\] \[3,2,1,0\] \[6,5,4,3\] | Push contents of **Árray** to stack |
|  | 4 \[0,1,2,3\] \[0,1,2,3\] \[6,5,4,3\] \[3,2,1,0\] | Swap the top two items on the stack |
| ć | 4 \[0,1,2,3\] \[0,1,2,3\] \[20,10,4,1\] | nCr |
|  | 4 \[0,1,2,3\] \[20,10,4,1\] \[0,1,2,3\] | Swap top two items on stack |
|  | 4 \[0,1,2,3\] \[20,10,4,1\] \[1,2,3,4\] | Increment |
| * | 4 \[0,1,2,3\] \[20,20,12,4\] | multiply element-wise |
|  | 4 \[20,20,12,4\] \[0,1,2,3\] | Swap top two items |
| 1~ | 4 \[20,20,12,4\] \[0,1,2,3\] -1 | Push **1**, then negate |
| ⇹^ | 4 \[20,20,12,4\] \[1,-1,1,-1\] | Swap top two, then exponentiate |
| · | 4 8 | Dot product |
| ⇹/ | 2 | Swap top two items, then divide; implicit print |

# Answer
> 1 votes
# Mathematica, 51 bytes

It's A000957

Use the generating function

$$\sum\_{n=0}^\infty F\_nz^n=\frac1z\cdot\frac{1-\sqrt{1-4z}}{3-\sqrt{1-4z}}$$

Try it online!

```
f=SeriesCoefficient[2/(1+Sqrt[1-4*z]+2*z),{z,0,#}]&

```

---
Tags: code-golf, sequence, integer, combinatorics
---