[Question]
  [
Polystrips are a subset of polyominoes conforming to the following rules:
* each piece consist of 1 or more cells
* no cell can have more than two neighbours
* the cells should not enclose a hole
Free polyominoes are distinct when none is a rigid transformation (translation, rotation, reflection or glide reflection) of another (pieces that can be picked up and flipped over). Translating, rotating, reflecting, or glide reflecting a free polyomino does not change its shape ([Wikipedia](https://en.wikipedia.org/wiki/Polyomino#Free,_one-sided,_and_fixed_polyominoes))
For example, there are 30 free heptastrips (polystrips with length 7). Here are all of them, packed into a 14x15 grid. 
[![Heptastrips](https://i.stack.imgur.com/Dtwzt.gif)](https://i.stack.imgur.com/Dtwzt.gif)
[Image credit: Miroslav Vicher](http://www.vicher.cz/puzzle/polyform/minio/polystrip.htm)
## Goal
Write a program / function that takes a positive integer `n` as input and enumerates the distinct free `n`-polystrips.
* n=1 --> 1 (A single square)
* n=2 --> 1 (There is only one possible 2-polystrip made of 2 squares)
* n=3 --> 2 (One is composed of 3 squares joined in a line and the
other one is L-shaped)
* n=4 --> 3 (One straight, one L-shaped and one Z-shaped)
* . . .
## Test cases:
```
n   polystrips
1   1
2   1
3   2
4   3
5   7
6   13
7   30
8   64
9   150
10  338
11  794
12  1836
13  4313
14  10067
15  23621
```
## Scoring
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shorter code is better. I would highly appreciate detailed explanations of the algorithm and the code.
## Partial reference implementation in [J](http://www.jsoftware.com/)
I decided to describe each piece in "vector" format and I only need n-2 blocks to describe an n-polystrip piece (there is only 1 2-polystrip and it's returned explicitly). The blocks describe the relative direction: 0 - no change; 1 - turn left; 2 - turn right. It doesn't matter which direction one will start but only to indicate where the next cell is to be put. There can be any number of consecutive 0s, but 1s and 2s are always single.
This implementation is partial, because it doesn't account for the holes - solutions for n>6 count the pieces with holes too.
[Try it online!](https://tio.run/##nZTdjtowEIXv8xQjLRIgQRTS7k1Y9qIP0EdoZcJAXAU7Gju7G7Xqq9OxnUACBK3qi/zI48/nzIz963SCPWwy@AoZJBG4Qe7/A0bG928xEJq6tCFa7mOYPTVzeIHf2eQDdjq@ipZ7sAVCiepgC9DhL6@JUFkopbEgDc8awxNCgQKIzuuJ1TWLZERHLsqSA94lcxMQVYVqh7vh6h8ZzFbwN2N1LLKBBazurF6dV5/lCifM4tGpU9rC6pabDrjp/3HTwMXSYDxwzlUgxjb3nAdqALoMWu2/Q2FaCgfEXUUfjVBRW5PqMSKYR1Gwo5WxVOfWgAibeWfOZKWNkdsSQRAJdcAjV5SjWBjhUb@h8UDTHNGS5LR43yaCA2xi@OI6Di5NlMJrxmZd/yStnth7OHeRgpcNhy1fQauy4QezdVlbqVXACMedJS5py3Q@Se4YNVZQ6wCPlW06TynkyI5MockiBdzW4QSXMpmMdeABFZKw6NMxyELXxbmDUCCNQIIQJ8PAXlO/ki6XteHu4ST6LKJpW4QDf8qYNQ4PXA/rUCjyoq/r0l8@58tYAnddPoS06ZZ2GjpUqq6OrYSQsmi4JQWjC5AjzSqv29SZu4L4bOWfgvTkjEH@xHIEYljDG5LBW9q4IqrKnC@TdQprSNer@WekdbcAz6dg3l3obmyHGeud3@zid2jPeie6vUTFlg9ZH9UjX05///PxTfDgKvBH6wDP4@t20lSlaPxCzofle45kxcWJMC80iPCaTsP7SZxO/wA "J – Try It Online")
  
[Answer]
# [Python 3](https://docs.python.org/3/), 480 433 406 364 309 299 295 bytes
Looked like a good point to start my PPCG career (or not?).
```
def C(s):
 S,*a={''},0,1;n=d=r=1
 for c in s:d=c*d*1jor d;n+=d;a+=n,;r*=not{n}&S;x,*a=a;S|={x+t+u*1jfor t in A for u in A}
 return r
from itertools import*;A=-1,0,1;n,y=int(input())-2,0;x={*filter(C,product(*[A]*n))}
while x:s=x.pop();S=*(-u for u in s),;x-={s[::-1],S,S[::-1]}-{s};y+=1
print(y)
```
[Try it online!](https://tio.run/##RVHBbqswEDyXr7Ai5WGbpcI4ISnW6imqeuiZY5RDFIxKlRpkjB4Rj29PTajUk0fendHMbHtzH42R91JXpDZt72jw9I5HASlI2MAWMtjBHl5AJCAEiBSEBLEBsT1B8PQ2by67u3kgE8jmWQJS7mH34vFeZrCRMylJsh2kMkvFKWB5DRo7Z@n7c9u0NGEM3n6Qam1tHF1VdJ12LCfrbUn@IlnzbrWmngbb@KoNncna01YrBtqU6F9lteutIXWgB32hYRg@cr1SLxOQAvgZxzCcwEdRBku0KAJSNZZcfHbS5SVeeMnFp/8plYmwVOcIDSjL0TRuNNOfQg2zylkV/3EcIhf1fn1WcLPC4SHWP@AUkB83Nqhs80Vqp61rmmtH6q@2sY6rA8Zi8QI3nCMvB2AsTiFRA468qq@eRV@htU3ZXxzlx8OJG8am4N9HfdVkyDscHr0xVSCncf9roWOghhjH7pjnsThBAcWCpnjsJnWLfPql6hu7@6642LD7Nw "Python 3 – Try It Online")
**Edits:**
* Inlined `D` and `X`, and tweaked a little bit on some golfable spots.
* Applied more tricks, mainly set-related ones.
* Changed into program form, and changed to using complex numbers instead of arbitrary number `m`. (Complex numbers are really a strong but often ignored golfy feature; adapted from [xnor's solution for another challenge](https://codegolf.stackexchange.com/a/156598/78410))
* Changed the `LFR` string representation to `-1,0,1` tuples and sacrificed execution time for crazy amount of byte reduction(!). Now the solution is theoretically correct but timeouts before outputting the result for 15.
* One-lined the loop thanks to Jonathan Frech, then I found the much better alternative for calculating `r`. FINALLY UNDER 300 BYTES!!!
* Surprisingly `1j` can stick to anything else without confusing the parser (-2B), and `not` has insanely low precedence (-2B).
Obsolete version (480 bytes):
```
def C(s):
 m=999;a=[0,1];n=d=1
 D={'F':{},'L':{1:m,m:-1,-1:-m,-m:1},'R':{1:-m,-m:-1,-1:m,m:1}}
 X=lambda x:{x+~m,x-m,x-m+1,x-1,x,x+1,x+m-1,x+m,x-~m}
 for c in s:
  d=D[c].get(d,d);n+=d;a+=n,
  if n in set().union(*map(X,a[:-3])):return 0
 return 1
def f(n):
 if n<3:return 1
 x={*'LF'}
 for _ in range(3,n):x={s+c for s in x for c in({*'LRF'}-{s[-1]})|{'F'}}
 y={*x}
 for s in x:
  if s in y:S=s.translate(str.maketrans('LR','RL'));y-={s[::-1],S,S[::-1]}-{s}
 return sum(map(C,y))
```
[Try it online!](https://tio.run/##RVDBioMwEL37FbmZrBNpEBYaN6eWnnpqLwWRJVu1K9ukxVhQXPvr3YmWbiDJJG/mzbx37dvvi00ej6KsyIo6JgNi1HK5TLXKFiDy1KpCiYCs1RBuQjmMEG7xEtKAkVwAF5Ib4EYKRHYTMr9nzGeJcQzIQZ21@So06eTQRXcDHZ92JPDEDZ2PIsOnE//uBquqS0OOpLbE4VykUOvsmMensqUFFCy1kSpSHSkLCNYVsVMmoiy@2fpi6ZvRV3oAnUme5IzJpmxvjSWLgDwjEXjdFbVet2f4SOQLIp0a3sLtJnwO8unpG21PJU0AKxB20XGCnIe617jU1@2wkA8u4yIf2a93z/vQI2f3JJyr5Dz89OjlXrm4xSburNuSuraJjf4ppx@KnCGavA0ZS3uO3TOJNuewh/0c@X7jS5y7GeoNWEHP2MM3rP8VCBDvXjSua1PbltaAPtSY@Ac "Python 3 – Try It Online")
Ungolfed solution with comments:
```
t = str.maketrans('LR','RL')
# hole checking function
def check(s):
    m = 999   # (imaginary) board size enough to fit all generated polyominoes
    a = [0,1] # previous path
    n = 1     # current cell
    d = 1     # current direction
    # dict for direction change
    D = {'F':{}, 'L':{1:m, m:-1, -1:-m, -m:1}, 'R':{1:-m, -m:-1, -1:m, m:1}}
    # used to 'blur' all cells in path into 3x3
    X = lambda x: {x-m-1,x-m,x-m+1,x-1,x,x+1,x+m-1,x+m,x+m+1}
    for c in s:
        d = D[c].get(d,d) # change direction
        n += d            # move current cell
        # the polyomino has a hole if the current cell touches previous cells (including diagonally; thus the blurring function)
        if n in set().union(*map(X,a[:-2])): return False
        a.append(n)       # add current cell to the path
    return True
# main function
def f(n):
    if n < 3: return 1
    x = {*'LF'}
    # generate all polystrips using the notation similar to the reference
    for _ in range(3, n): x = {s+c for s in x for c in ({*'LRF'}-{s[-1]})|{'F'}}
    y = {*x}
    # remove duplicates (mirror, head-to-tail, mirror of head-to-tail) but retain self
    for s in x:
        if s in y:
            S = s.translate(t)
            y -= {s[::-1], S, S[::-1]} - {s}
    # finally filter out holey ones
    return sum(map(check,y))
```
[Try it online!](https://tio.run/##bVRNb9swDL3nVxDowXZjB/MCDKi33oqeckp3KBAEg2rJsVB9GJJcxMvy2ztSdj7azYgthU8iH8kndUNorVm@vwe4Bx/cQrNXERwzPk1W6yRP1qskm81uoLVKQN2K@lWaHTS9qYO0ZsZFM1pTn1UzwEejo7vb2zuAG0ilZjtpmBsyeLHMcfDytwBhbL9rIVhoZACmFOyEEY4FwaGzarBaGit8dMfQ3eZLXm7RXefEm7S9h46FNqIG0ZImiNa9c8IEqIVSEeT/Abl0YmQ@2rmsAzTWXQBMh5mdiPgDejgkj0l1OOaQrHAsK52Drooyh6KsCvxT6KokdB3RyTLhcW15PE7Beo8JYtbJi@pdEhMnsh6kiSnhiOhyv4zrnzG4YvqFM9hXcNgXGr3il945zfDN9zSbR2Su6Z2XYzTKqSbHfmzLqSAPm3q72ImQ8pxnVJiY7ae6jKWd3@OOq@cGtH0T/9Z5xEIrLs2DlnlsXRSNbCJ2vQ2L0KNq/KWjYx1SaWrVc1IYl2xnDZZo@I7bcQX5oLq5a/1lZwIYxcR0MbVs0RsE01vNuvQ5Z5uq@LrNsgqcCL0z8MiUF@edbMG6ThiemuycDOP8M@ExwZPwJk8/XS/odGiGoT8cigbdjZWPzH7A8hy@jOY9aes2WT0mJ3mcDkEUBpUSz6PsPMqGUqbwxgYWNeqlloq5Ey0nGoFca3Fu/S@qhaPWpssckMoYz8/rCEfJ7S8iSYnJGqkUB78pyu0x@0O6n5Q7RKr7E08nog543ylZI1/sm5bOWZdDKxgvgi0Ckwq1H61gmw92vAr6QLVgsV2qOZMeWVXXPY2m4WKi54muqkW8pBSGT0P2AR6goEw3FZ7CbQ5P@BvnRyjQfsqikVFdOKogkCRyIrkOYM109Uzt8r1OSUjxmsuHLHsnrvJS4DIvv0297lCdIZU5tl/iwr8 "Python 3 – Try It Online")
`m = 999` is chosen because it takes exponential time to count everything, and it's already taking ~8s to calculate `n = 1..15`. Maybe it's fine to save 1 byte by using 99 instead. We don't need this anymore, and now it's guaranteed to be correct for arbitrary input size, thanks to complex number built-in.
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), ~~70~~ 65 bytes
```
+/{∧/∊2≤|(⊢-¯3↓¨,\)+\0 1,×\0j1*⍵}¨∪{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}¨2-,⍳2↓⎕⍴3
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT///qKO94L@2fvWjjuX6jzq6jB51LqnReNS1SPfQeuNHbZMPrdCJ0dSOMVAw1Dk8PcYgy1DrUe/W2kMrHnWsqgYqa37UMeNRbzeI0bVIE6RP51HP3kMrNIGqNHSBhCZQrZGuzqPezUZA0x71TX3Uu8UYZOl/BTAo4DLkgrGM4CxjOMsEzjKFs8zgLHM4ywLOsoSzDA0QTEMA "APL (Dyalog Unicode) – Try It Online")
Full program version of the code below, thanks to Adám.
---
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 70 bytes
```
{+/{∧/∊2≤|(⊢-¯3↓¨,\)+\0 1,×\0j1*⍵}¨∪{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}¨2-,⍳3⍴⍨0⌈⍵-2}
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT/@fnpr3qG1CtZGuzqPezY96tz7q3WJcy5WcmJefl5mcmJNZlQqS1njU1fyoY8aj3m4Qo2uRJlBgkc6jnr2HVmgCNWnoAgnNWq6S1OISiPKO5fpAFdUg2uhR55KaR727dA@tN37UNhmosvbQCp0YTe0YAwVDncPTYwyyDLVAov@rtfXBOh51dIE1gSyB6sKu49CKRx2riHTcoRUQPxoDffiod4XBo54OoLiuUe3/NKCTH/X2Peqb6ukPNAFs4UQgLzjIGUiGeHgG/68AKkkD2ta72dCQq4Kr4lHnQkMFQwUjBWMFcwVDYwVjAwUzEwVDUwMFY2MLBXNLEwA "APL (Dyalog Unicode) – Try It Online")
### How it works
The code above is equivalent to the following definition:
```
gen←{2-,⍳3⍴⍨0⌈⍵-2}
canonicalize←{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}
test←{(∧/⊢{∧/2≤|⍺-¯3↓⍵}¨,\)+\0 1,×\0j1*⍵}
{+/test¨∪canonicalize¨gen⍵}
```
This works like the Python solution, but in a different order. It `gen`erates `LFR`-strips of length `n-2`, `canonicalize`s each strip, takes `∪`nique strips, `test`s each strip if it touches itself (1 if not touching, 0 otherwise), and sums `+/` the boolean result.
### `gen`
```
{2-,⍳3⍴⍨0⌈⍵-2}
{            }  ⍝ ⍵←input number n
        0⌈⍵-2   ⍝ x←max(0, n-2)
     3⍴⍨        ⍝ x copies of 3
   ,⍳           ⍝ multi-dimensional indexes; x-th cartesian power of [1,2,3]
                ⍝ (`⍳` gives x-dimensional hypercube; `,` flattens it)
 2-             ⍝ compute 2-k for each k in the array
⍝ in each strip, ¯1, 0, 1 corresponds to R, F, L respectively
```
### `canonicalize`
```
{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}
{                  }  ⍝ ⍵←single strip
              ⍵(-⍵)   ⍝ nested array of ⍵ and its LR-flip
        (⊢,⌽¨)        ⍝ concatenate their head-to-tail flips to the above
 (⊃∘⍋  )              ⍝ find the index of the lexicographically smallest item
     ⊃⊢               ⍝ take that item
```
### `test`
```
{(∧/⊢{∧/2≤|⍺-¯3↓⍵}¨,\)+\0 1,×\0j1*⍵}
{                                  }  ⍝ ⍵←single strip
                              0j1*⍵   ⍝ power of i; direction changes
                            ×\        ⍝ cumulative product; directions
                        0 1,    ⍝ initial position(0) and direction(1)
                      +\        ⍝ cumulative sum; tile locations
 (  ⊢{           }¨,\)   ⍝ test with current tile(⍺) and all tiles up to ⍺(⍵):
             ¯3↓⍵        ⍝ x←⍵ with last 3 tiles removed
           ⍺-            ⍝ relative position of each tile of x from ⍺
        2≤|              ⍝ test if each tile of x is at least 2 units away
      ∧/                 ⍝ all(...for each tile in x)
  ∧/        ⍝ all(...for each position in the strip)
```
[Answer]
# [Scala](https://www.scala-lang.org/), ~~2277~~ 1710 bytes\*:
Modified from [@Bubbler's answer](https://codegolf.stackexchange.com/a/156335/110802).
### Golfed version
[Try it online!](https://tio.run/##fVRba9swFH73rzikhUr4srjdHhbWwgotDDoGTfdUSlFtOVFny6mkdAnBvz07kuVLIF0eYvuc7/vOVdIZK9l@L6pVrQxo@5VkdVnyzIhaJtXasJeSJ3NugqB@eUUz/GRCwi4AyHkB2ZJnf@b8jegZzI0SckFncF3XJWcSLh0M4J2VULENfl@LxQ9pyFearOq/@PBuBQydVsYDpjTqsCkdUHKQSAdrfsRaQi6URsdPtiLOBnB2ewbxlbU8tvAuxhOhUYe56zCkl7QGTD9yNeC7d8TpkGTcomIHiw9xWECvfn9c/SjviP6RLLr2DIWz/BXrJpuZh1C4vMLeGoK0lgxpBP6jf4Gws9qHffOGcMwJO07YcWjgAuukqBVn2RJ2kGFAX7AdjR0EyWiy4OaXuik1J3kEOfUICSFC/IdN/z1FjiiAsKTkcmGWcAXnFFiiS5FxMo2gd8ToSCpsJpZMgaO02yE6UtOd2nuaCH1TrcyW2mY89pNveehWPF9jgGcIQ3juNCxVp3gkpMG110RSCoqbtZJQMCR6mF1fBrMQpDM07t@otfU3gT8rBZEzsANx//3psCEkfIOLXjkN@t3euHNhyORuEsHkdtLmRS5gLY0oQdJR35@HvlvaJilKZnDX0KX52@BsO5MtmTsgVh23PrLLGdkzgptm8UnJtMEJo6XnOY7ruJ2xUw0h63rV@Nr75Lcui6ysJfdD2YzSPcjJNmE7tBl92OjdQcJGzS3D5ab4qmQ4rLYtJxM6WO6t5W5sObGW@wk9UHOLYWtv5d650jxqY/hHZx14W4hjjJ8muSgK4sn0aPm2FhwR6e5HOl6ECmskTC3wzvyuFNs@tjfnEy7GbynMwb1pXJ5bbXiVSCbrB1F1zSQpmBrSL@MdEENLHfv8Q3YLUNzuQEHE2Ggu/sNaYaqmlERPTgWcWv7pDgkxxmqk9l1uhvw/f6g1KD3UxkLRNUM1ghyUwyvvE6RT90umTdVqN0ET7Pf/AA)
```
import scala.collection.mutable.Set
object Main {
  def checkSeq(s: String): Boolean = {
    val max = BigInt(9).pow(9)
    var a = Seq(BigInt(0), BigInt(1))
    var n = BigInt(1)
    var d = BigInt(1)
    val dirs = Map(
      'F' -> Map[BigInt, BigInt](),
      'L' -> Map(BigInt(1) -> max, max -> BigInt(-1), BigInt(-1) -> -max, -max -> BigInt(1)),
      'R' -> Map(BigInt(1) -> -max, -max -> BigInt(-1), BigInt(-1) -> max, max -> BigInt(1))
    )
    val adj = (x: BigInt) => Set(x - max - 1, x - max, x - max + 1, x - 1, x, x + 1, x + max - 1, x + max, x + max + 1)
    s.foreach { c =>
      d = dirs(c).getOrElse(d, d)
      n += d
      val v1 = if (a.length > 2) a.slice(0, a.length - 2).map(adj) else Seq()
      val s1 = if (v1.isEmpty) Set[BigInt]() else v1.reduce(_ ++ _)
      if (s1.contains(n)) return false
      a = a :+ n
    }
    true
  }
  def f(n: Int): Int = {
    if (n < 3) return 1
    var x = Set("L", "F")
    (3 until n).foreach { _ =>
      x = x.flatMap { seq =>
        val chars = Set('L', 'R', 'F') - seq.last + 'F'
        chars.map(c => seq + c)
      }
    }
    var y = x.clone()
    x.foreach { seq =>
      if (y.contains(seq)) {
        val trSeq = seq.replace("L", "#").replace("R", "L").replace("#", "R")
        val s1 = Set(seq.reverse, trSeq, trSeq.reverse)
        y --= s1.diff(Set(seq))
      }
    }
    y.count(checkSeq)
  }
  def main(args: Array[String]): Unit = {
    val t1 = System.nanoTime()
    (1 to 15).foreach { i =>
      val t2 = System.nanoTime()
      val res = f(i)
      val t3 = System.nanoTime()
      println(s"$i $res ${t3 - t2}ns")
    }
    val t4 = System.nanoTime()
    println(s"Total time: ${(t4 - t1) / 1000000.0}ms")
  }
}
```
### Ungolfed version
[Try it online!](https://tio.run/##jVXbbtw2EH3frxhsHkJCF1t2@9BFbCBBEqCAjQJ22hcjCBiJu1ZCUVuSSnZR7Le7MxIpSvY6iQ1Y1vDMmeuhbCmUeHiom21rHFh6y8tWKVm6utV50znxWcn8VrrFov38Bc1wLWoN/y0AKrmG8l6WX2/lv53UpWR2BbfO1HrDV/CmbZUUGi56LMA3oaARu3@E6iQa39SbP7Vjf/B8237Hh8cYEHiIhMwDTnkasAWPKB0pimitjlgVVLUZyrF4fC22rD8BePn@JWSXZLkbnEKkj4ynAXP1LGYMRIBQWRprRKuHZEUsIhvwWXTIjnhgqWMGN7@WwU8Yj@Tww5xDs2MbcTfKTgknX1dfRCm1w26y3co7cLi4xLk5toNswgdFClPL/A2ScE4P@s8bkicUyYwimVFwzPDkBIx0ndG4QJa2ldJetwZYCa8ysNyvIfRLEleClTzfSPeXeaesZFUKFfc4DQkC/Qs1ADesQN96DUzkSuqNu4dLOOMgcqtqXP/TFMaDDA/yBpftSds4SAzV7zifsGPSgZ0C5bV912zdnlNT78a9HHx7gJFVh0E/QZLAp8BE7sSEItYOhWqZ5rF0CD1aC6TxxoN/kvAErBLQi2h2piPcYeH1vmZ6BTTu/u8obgqr4RWcx1g@UuHJRo3uen07trxaprB8v@RxUjVN6hw67WoFOlJRe7T8jl6D791wyXwc@9d7W38LEcluWjNFLe@FEaWTxvrwKOyUtJXSNYBygOCeK2Hd6Dvxw21A6Hgy7FY4pqARO40OIXX0H1NMIngEHh7Ngxo1uD5u4R5PdnmpWi3ZpH3PNIBms4/7EFB83iKFoxba0qJW4T6HmDFu21bh@vqxvVjyaLkhy9XU8oIsN0uOqpQ7rFRvZH@TCl319xl@QALxLAWvAZrPJPA37Ciq/ml@x2wBzx8Tnz0ifgJ4W6/X0ox1o4YqtJCaziJ2D1l2MUfPxuanRP3GNWazzyOfCqnBYTBhNvjJfG2M2IedRmH9rWs3@2wOTdlbJ5tcC91@qJvZ4HvdFOBaKH6fq2ao@qjnADDSdoqirVk9tbvzHzhuMVOnNMZNYIm/SaAJrwzdMwzOyaKt1/ghFvTbs@x0LJXYWlldk1YZYpEK7/gTKE77n/x0Mc1i@aF1xIkcqz56dMfozRD9sDgsHh7@Bw)
```
import scala.collection.mutable.Set
object Main {
  def checkSequence(s: String): Boolean = {
    val maxValue = BigInt(9).pow(9)
    var a = Seq(BigInt(0), BigInt(1))
    var n = BigInt(1)
    var d = BigInt(1)
    val directions = Map(
      'F' -> Map[BigInt, BigInt](),
      'L' -> Map[BigInt, BigInt](BigInt(1) -> maxValue, maxValue -> BigInt(-1), BigInt(-1) -> -maxValue, -maxValue -> BigInt(1)),
      'R' -> Map[BigInt, BigInt](BigInt(1) -> -maxValue, -maxValue -> BigInt(-1), BigInt(-1) -> maxValue, maxValue -> BigInt(1))
    )
    val calculateAdjacent = (x: BigInt) => Set(x - maxValue - 1, x - maxValue, x - maxValue + 1, x - 1, x, x + 1, x + maxValue - 1, x + maxValue, x + maxValue + 1)   // return a set
    for (c <- s) {
      d = directions(c).getOrElse(d, d)
      n += d
      val var1 = if (a.length > 2) a.slice(0, a.length - 2).map(calculateAdjacent) else Seq()
      val set1 = if (var1.isEmpty) Set[BigInt]() else var1.reduce(_ ++ _)
      if (set1.contains(n)) {
        return false
      }
      a = a :+ n
    }
    true
  }
  def f(n: Int): Int = {
    if (n < 3) {
      return 1
    }
    var x = Set("L", "F")
    for (i <- 3 until n) {
      val newSet = Set[String]()
      for (sequence <- x) {
        var characters = Set('L', 'R', 'F') - sequence.last
        characters += 'F'
        for (character <- characters) {
          newSet += sequence + character
        }
      }
      x = newSet
    }
    var y = x.clone()
    for (sequence <- x) {
      if (y.contains(sequence)) {
        val translatedSequence = sequence.replace("L", "#").replace("R", "L").replace("#", "R") //exchange 'L' and 'R' in sequence
        val set1 = Set(sequence.reverse, translatedSequence, translatedSequence.reverse)
        val set2 = Set(sequence)
        val setDifference = set1.diff(set2)
        y --= setDifference
      }
    }
    y.count(checkSequence)
  }
  def main(args: Array[String]): Unit = {
    val t1 = System.nanoTime()
    for (i <- 1 to 15) {
      val t2 = System.nanoTime()
      val result = f(i)
      val t3 = System.nanoTime()
      println(i + " " + result + " " + (t3 - t2) + "ns")
    }
    val t4 = System.nanoTime()
    val elapsedMs = (t4 - t1) / 1000000.0
    println("Total time: " + elapsedMs + "ms")
  }
}
```
\* Rather long in bytes, but computes solutions up to and including \$n=15\$
around 15 seconds on TIO.
]