[Question]
  [
A straight-chain alk\*ne is defined as a sequence of carbon atoms connected by single (alkane), double (alkene), or triple bonds (alkyne), (implicit hydrogens are used.) Carbon atoms can only form 4 bonds, so no carbon atom may be forced to have more than four bonds. A straight-chain alk\*ne can be represented as a list of its carbon-carbon bonds.
These are some examples of valid straight-chain alk\*nes:
```
[]       CH4              Methane
[1]      CH3-CH3          Ethane
[2]      CH2=CH2          Ethene
[3]      CH≡CH            Ethyne
[1,1]    CH3-CH2-CH3      Propane
[1,2]    CH3-CH=CH2       Propene
[1,3]    CH3-C≡CH         Propyne
[2,1]    CH2=CH-CH3       Propene
[2,2]    CH2=C=CH2        Allene (Propadiene)
[3,1]    CH≡C-CH3         Propyne 
[1,1,1]  CH3-CH2-CH2-CH3  Butane
...
```
While these are not, as at least one carbon atom would have more than 4 bonds:
```
[2,3]
[3,2]
[3,3]
...
```
Your task is to create a program/function that, given a positive integer `n`, outputs/returns the **number** of valid straight-chain alk\*nes of exactly `n` carbon atoms in length. This is [OEIS A077998](//oeis.org/A077998).
# Specifications/Clarifications
* You must handle `1` correctly by returning `1`.
* Alk\*nes like `[1,2]` and `[2,1]` are considered distinct.
* Output is the *length* of a list of all the possible alk\*nes of a given length.
* You do *not* have to handle 0 correctly.
# Test Cases:
```
1 => 1
2 => 3
3 => 6
4 => 14
```
This is code golf, so lowest *byte* count wins!
  
[Answer]
# [MATL](http://github.com/lmendo/MATL), 10 bytes
```
7K5vBiY^1)
```
[Try it online!](http://matl.tryitonline.net/#code=N0s1dkJpWV4xKQ&input=NA)
### Explanation
This uses the characterization found in [OEIS](http://oeis.org/A006356)
> 
> a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 1, 1; 1, 0, 0; 1, 0, 1]
> 
> 
> 
```
7    % Push 7
K    % Push 4
5    % Push 5
v    % Concatenate all numbers into a column vector: [7; 4; 5]
B    % Convert to binary: gives 3×3 matrix [1, 1, 1; 1, 0, 0; 1, 0, 1]
i    % Input n
Y^   % Matrix power
1)   % Take the first element of the resulting matrix, i.e. its upper-left corner.
     % Implicitly display
```
[Answer]
# [Oasis](http://github.com/Adriandmen/Oasis), ~~9~~ 7 bytes
```
xcd-+3V
```
[Try it online!](http://oasis.tryitonline.net/#code=eGNkLSszVg&input=&args=NA)
### Explanation
This uses the recurrence relationship in [OEIS](http://oeis.org/A006356):
> 
> a(n) = 2\*a(n-1) + a(n-2) - a(n-3)
> 
> 
> 
```
x    Multiply a(n-1) by 2: gives 2*a(n-1)
c    Push a(n-2)
d    Push a(n-3)
-    Subtract: gives a(n-2) - a(n-3)
+    Add: gives 2*a(n-1) + a(n-2) - a(n-3)
3    Push 3: initial value for a(n-1)
V    Push 1, 1: initial values for a(n-2), a(n-3)
```
[Answer]
# [Oasis](http://github.com/Adriandmen/Oasis), ~~9~~ 8 bytes
Saved a byte thanks to *Adnan*
```
xc+d-63T
```
[Try it online!](http://oasis.tryitonline.net/#code=eGMrZC02M1Q&input=&args=NA)
**Explanation**
```
a(0) = 0
a(1) = 1
a(2) = 3
a(3) = 6
a(n) = xc+d-
x         # calculate 2*a(n-1)
 c        # calculate a(n-2)
  +       # add: 2*a(n-1) + a(n-2)
   d      # calculate a(n-3)
    -     # subtract: 2*a(n-1) + a(n-2) - a(n-3)
```
[Answer]
# Jelly, 10 bytes
```
745DBæ*µḢḢ
```
[Try it online!](https://tio.run/nexus/jelly#@29uYuridHiZ1qGtD3csAqL///@bAAA)
Uses [Luis Mendo's algorithm](https://codegolf.stackexchange.com/a/103112/30164).
### Explanation
```
745DBæ*µḢḢ    Main link. Argument: n
745D          Get the digits of 745
    B         Convert each to binary
     æ*       Matrix power
        ḢḢ    First element of first row
```
## Jelly, 15 bytes
```
3Rṗ’µ+2\<5PµÐfL
```
[Try it online!](https://tio.run/nexus/jelly#ARsA5P//M1LhuZfigJnCtSsyXDw1UMK1w5BmTP///zQ)
Uses brute force.
### Explanation
```
3Rṗ’µ+2\<5PµÐfL    Main link. Argument: n
3R                 Start with [1, 2, 3]
   ’               Take the (n-1)'th
  ṗ                Cartesian power
            Ðf     Filter on:
     +2\             Sums of overlapping pairs
        <5           1 for sums < 5, 0 otherwise
          P          Product: 1 if all pairs < 5
              L    Length
```
[Answer]
# [MATL](http://github.com/lmendo/MATL), 14 bytes
```
q3:Z^TTZ+!5<As
```
[Try it online!](http://matl.tryitonline.net/#code=cTM6Wl5UVForNTwhQXM&input=NA)
### Explanation
This generates the Cartesian power of `[1 2 3]` "raised" to the number of atoms minus 1, and then uses convolution to check that no two contiguous numbers in each Cartesian tuple sum more than `4`.
```
q    % Take number of atoms n implicitly
3:   % Push [1 2 3]
Z^   % Cartesian power. Gives a matrix with each (n-1)-tuple on a row
TT   % Push [1 1]
Z+   % 2D convolution. For each tuple this gives the sum of contiguous numbers
5<   % For each entry, gives true if less than 5
!    % Transpose
A    % True if all elements of each column are true. Gives a row vector
s    % Sum of true results. Implicitly display
```
[Answer]
## Mathematica, 48 bytes
```
MatrixPower[{{1,1,1},{1,0,0},{1,0,1}},#][[1,1]]&
```
As [Luis Mendo pointed out](https://codegolf.stackexchange.com/a/103112/61980), this is [A006356](http://oeis.org/A006356) in the OEIS. Here are my original attempts:
```
Count[Length@Split[#,+##<5&]&/@Tuples[{1,2,3},#-1],0|1]&
```
For an input `n`, `Tuples[{1,2,3},n-1]` is the list of all `(n-1)`-tuples of elements in `{1,2,3}` representing all possible sequences of single, double, or triple bonds for `n` carbon atoms. `+##<5&` is a pure function which returns whether the sum of its arguments is less than `5`, so `Split[#,+##<5&]&` splits a list into sublists consisting of consecutive elements whose pairwise sums are less than `5`. Describing a valid alk\*ne is equivalent to this list having length `0` (in the case where `n=1`) or `1`, so I just `Count` the number of `(n-1)`-tuples where the length of that list matches `0|1`.
```
Count[Fold[If[+##>4,4,#2]&]/@Tuples[{1,2,3},#-1],Except@4]&
```
`If[+##>4,4,#2]&` returns `4` if the sum of its arguments is greater than `4` and returns the second argument otherwise. `Fold[If[+##>4,4,#2]&]` does a left [`Fold`](http://reference.wolfram.com/language/ref/Fold.html) of its input with this function. So here I `Count` the number of `(n-1)`-tuples to which applying this operator doesn't give `4`. The case where `n=1` is covered since `Fold` remains unevaluated when its second argument is the empty list `{}`.
[Answer]
# Python, 51 bytes
```
f=lambda n:n<4and(n*n+n)/2or 2*f(n-1)+f(n-2)-f(n-3)
```
This is a straightforward implementation of the recurrence relation. Thanks to Tim Pederick for 3 bytes. The output is a float in Python 3 and an integer in Python 2.
[Try it online!](https://tio.run/nexus/python3#FYtLDoMwDET3PYXFyuZTRFo2UXsYVxAUCaYooivE2VNn9UYzb3J4r7p9JiV4vJ6KiVGjgfTum8jVgdEN0hQ46QoekoNNkSIoKZaZh9bywRH772AR8TeiPZWqOi9P51Xd7bGpKS0Fjqbk8Q8 "Python 3 – TIO Nexus")
[Answer]
# Pyth - 16 bytes
Uses brute force.
```
lf.AgL4+VTtT^S3t
```
[Test Suite](http://pyth.herokuapp.com/?code=lf.AgL4%2BVTtT%5ES3t&test_suite=1&test_suite_input=1%0A2%0A3%0A4&debug=0).
[Answer]
# Ruby, 62 bytes
```
->n{c=0
(10**n/10).times{|i|"#{i}#{i*11}"=~/[3-9]/||c+=1}
c}
```
Horribly inefficient base 10 brute force approach. Could be improved to base 5 for additional bytes.
Numbers are generated where each digit represents a bond (n-1 digits.) `0` represents a bond order of 1, `2` represents a bond order of 3. Digits over 2 are invalid.
We multiply this by 11 to sum adjacent pair of digits. Again digits over 3 are invalid.
We combine the two numbers in a string and perform a regex to search for invalid digits. If none are found, we increment the counter.
**in test program**
```
f=->n{c=0
(10**n/10).times{|i|"#{i}#{i*11}"=~/[3-9]/||c+=1}
c}
p f[gets.to_i]
```
[Answer]
# Ruby, 51 bytes
```
->n{a=[1,1,3]
n.times{a<<2*a[-1]+a[-2]-a[-3]}
a[n]}
```
Based on the recurrence relation per OEIS A006356.
Starts with an array for elements 0,1 and 2 of the sequence which are 1 (as calculated by me, to make it work), 1 and 3 respectively.
Iteratively adds `n` more elements to the sequence, then returns element `n`. It always calculates 2 elements more than it actually needs to, but it's still linear time, which is way more efficient than my previous answer.
**in test program**
```
f=->n{a=[1,1,3]
n.times{a<<2*a[-1]+a[-2]-a[-3]}
a[n]}
p f[gets.to_i]
```
[Answer]
## Mathematica, ~~42~~ 40 bytes
Byte count assumes a compatible single-byte encoding like CP-1252 (the default on Windows installations).
```
±0=±1=1;±2=3;±n_:=±(n-1)2+±(n-2)-±(n-3);
```
This simply implements the recurrence given on OEIS as a unary operator.
[Answer]
## CJam (19 bytes)
```
{2,{__-2=+1b+}@*W=}
```
[Online test suite](http://cjam.aditsu.net/#code=10%2C%0A%0A%7B2%2C%7B__-2%3D%2B1b%2B%7D%40*W%3D%7D%0A%0A%25p). This is an anonymous block (function) which takes one item on the stack and leaves one on the stack. Note that the test suite includes `a(0) = 1`.
The recurrence used is based on the observation for the related OEIS sequence [A006356](//oeis.org/A006356):
> 
> Equals the INVERT transform of (1, 2, 1, 1, 1,...) equivalent to a(n) = a(n-1) + 2\*a(n-2) + a(n-3) + a(n-4) + ... + 1. a(6) = 70 = (31 + 2\*14 + 6 + 3 + 1 + 1). - Gary W. Adamson, Apr 27 2009
> 
> 
> 
but with the appropriate offset, which removes the need for the final `+ 1` as now covered by `a(0)`.
### Dissection
```
{         e# Define a block
  2,      e#   Take starting sequence [0 1] (beginning at index -1 for golfiness)
  {       e#   Loop...
    _     e#     Copy sequence so far
    _-2=+ e#     Append an extra copy of a(n-2)
    1b    e#     Sum
    +     e#     Append
  }@*     e#   ...n times
  W=      e#   Take the final value from the sequence
}
```
[Answer]
# Brain-Flak, 56 bytes
Uses the algorithm detailed in the first comment on the OEIS page.
[Try it online!](http://brain-flak.tryitonline.net/#code=KHt9WygpXTwoKCgoKSkpKT4peyh7fVsoKV08eyh7fTw-KHt9KSk8Pn08Pj4pfXt9KHt9PD57fSk&input=NQ)
```
({}[()]<(((())))>){({}[()]<{({}<>({}))<>}<>>)}{}({}<>{})
```
## Explanation
The sequence can be defined as such:
```
For u(k), v(k), and w(k) such that
u(1) = v(1) = w(1) = 1
u(k+1) = u(k) + v(k) + w(k)
v(k+1) = u(k) + v(k)
w(k+1) = u(k)
u(k) is the number of straight-chain alk*nes with length k
```
The program starts at `1` and repeatedly applies this recurrence to calculate `u(k)`
### Annotated Code (actual annotation to come)
```
# Setup: decrement the input by one and push three 1's to the stack under it
({}[()]<(((())))>)
# Calculation:
{                          }           # While the input is not zero (main loop)
 ({}[()]                  )            # Pop the counter decrement it by one and push it
        <                >             # Before the counter gets pushed back to the stack...
         {            }                # Loop while the top of the stack is not zero (subloop)
          (        )                   # Push...
           {}                          # The top of the stack (popped)...
             <>                        # to the other stack...
               ({})                    # plus the top of the other stack (peeked)
                    <>                 # Switch back to the first stack.
                       <>              # Switch to the other stack
                            {}         # Pop the input (now zero)
                              (      ) # Push...
                               {}      # The top of the stack (u(k))...
                                 <>    # to the other stack...
                                   {}  # plus the top of the other stack (zero).
```
### Visualization of the stacks
In one iteration of the main loop this is what happens (note that the zeros may or may not be present but it does not matter either way):
```
Start of main loop iteration/subloop first iteration:
A    B
u
v
w
0    0
^
After first subloop iteration:
A    B
v
w    u
0    0
^
After second subloop iteration:
A    B
    u+v
w    u
0    0
^
After third subloop iteration (top of stack is zero so subloop terminates):
A    B
   u+v+w
    u+v
     u
0    0
^
End of main loop iteration:
A    B
   u+v+w
    u+v
     u
0    0
     ^
```
The state of the stacks is now the same as it was at the start of the loop except that the current stack now has the next values for `u`, `v`, and `w` on it.
[Answer]
## Perl 6, 48
```
{my @a=1,0,0;@a=reverse [\+] @a for 1..$_;@a[0]}
```
Originally
```
sub f {$_>2??2*f($_-1)+f($_-2)-f($_-3)!!(1,1,3)[$_]}
```
but I forgot I needed the `sub f` so the iterative solution wins out.
[Answer]
# Dyalog APL, 30 bytes
```
{⍵<3:⍵⌷1 3⋄+/∧/¨4≥2+/¨,⍳1↓⍵/3}
```
Uses brute force.
Explanation (my best attempt at one, at least):
```
⍵<3:⍵⌷1 3 - if ⍵ (function arg) is 1 (case 1) or 2 (case 2), return 1 (case 1) or 3 (case 2)
⋄ - separate statements
⍵/3 - otherwise, 3 repeated ⍵ times
1↓ - without the first element
⍳ - the matrix of possible indices of a matrix of that size
,  - ravel, return a list of all the elements of the matrix
2+/¨ - sum of each contiguous pair on each element
4≥ - tests whether each element is less than or equal to 4
∧/¨ - all elements are true, applied to each item.
+/ - Sum.
```
[Answer]
# Dyalog APL, 29 bytes
```
{⍵<4:⍵⌷1 3 6⋄+/2 1 ¯1×∇¨⍵-⍳3}
```
Works by using the recursive definition of the integer sequence OEIS A006356.
[Answer]
# Python with Numpy, 62 bytes
I had to try it, but it seems [pure Python and recursion](https://codegolf.stackexchange.com/a/103149/13959) is shorter than numpy and the explicit, matrix-based calculation on the OEIS page.
```
from numpy import*
lambda n:(mat('1 1 1;1 0 0;1 0 1')**n)[0,0]
```
[Answer]
# R, ~~61~~ ~~58~~ ~~55~~ ~~51~~ 50 bytes
Takes input from stdin, uses matrix exponentiation to determine exact result.
```
el(expm::`%^%`(matrix(!-3:5%in%2^(0:2),3),scan()))
```
If you prefer a recursive solution, here's a straightforward implementation of the recurrence relation listed in OEIS, for **55 bytes**.
```
f=function(n)`if`(n<4,(n*n+n)/2,2*f(n-1)+f(n-2)-f(n-3))
```
[Answer]
# Excel, 123 bytes
Implements the formula from OEIS:
```
=4*(SIN(4*PI()/7)^2*(1+2*COS(2*PI()/7))^A1+SIN(8*PI()/7)^2*(1+2*COS(4*PI()/7))^A1+SIN(2*PI()/7)^2*(1+2*COS(8*PI()/7))^A1)/7
```
As always, input in `A1`, formula in any other cell.
Dug up old Trig identities to see if could be helpful. Now my head hurts.
[Answer]
## [Lithp](https://github.com/andrakis/node-lithp), 79 bytes
```
#N:(((if(< N 4)((/(+ N(* N N))2))((-(+(* 2(f(- N 1)))(f(- N 2)))(f(- N 3)))))))
```
Implements recursive integer sequence listed in OEIS.
Readable implementation and test suite.
```
% alkaline.lithp
% run with: ./run.js alkaline.lithp
(
    (def f #N : ((
        (if (< N 4) (
            (/ (+ N (* N N)) 2)
        ) (else (
            (- (+ (* 2 (f (- N 1))) (f (- N 2))) (f (- N 3)))
        )))
    )))
    % Test cases 1 to 4
    (import lists)
    (each (seq 1 4) #I :: ((print (f I))))
)
```
[Answer]
# MMIX, 44 bytes (11 instrs)
If passed 0, returns \$A077998(2^{64})\$ (if the computer doesn't break down).
Works mod \$2^{64}\$.
(jxd)
```
00000000: e3010001 e3020001 e3030003 27000001  ẉ¢¡¢ẉ£¡¢ẉ¤¡¤'¡¡¢
00000010: 28ff0302 26ffff01 c1010200 c1020300  (”¤£&””¢Ḋ¢£¡Ḋ£¤¡
00000020: c103ff00 5b00ffb5 f8020000           Ḋ¤”¡[¡”Ọẏ£¡¡
```
Disassembly and explanation:
```
alkns   SET   $1,1          // a(0)
        SET   $2,1          // a(1)
        SET   $3,3          // a(2)
0H      SUBU  $0,$0,1       // loop: n--
        2ADDU $255,$3,$2    // a' = 2a + a`
        SUBU  $255,$255,$1  // - a``
        SET   $1,$2         // a`` = a`
        SET   $2,$3         // a` = a
        SET   $3,$255       // a = a'
        PBNZ  $0,0B         // if(n) goto loop
        POP   2,0           // return a
```
]