# Number of Straight-Chain Alk*nes of given length

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

# 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!

• just to clarify, a chain is valid if all consecutive pairs are summed to <=4, right? Dec 13 '16 at 23:03
• Fixed. @Maltysen: yes. Dec 13 '16 at 23:19
• Why is there an OEIS sequence for everything? :P Dec 14 '16 at 3:28
• @ZacharyT, there is precisely one hydrocarbon with zero carbon atoms, and it's the one which also has zero hydrogen atoms. It's the exact same argument as for Pascal's triangle having a 1 at the top rather than a 0, or for literally hundreds of other combinatoric sequences. Dec 14 '16 at 12:15
• @Emigna, that's because the wrong sequence was linked. I'll correct it. Dec 14 '16 at 14:28

# MATL, 10 bytes

7K5vBiY^1)


Try it online!

### Explanation

This uses the characterization found in OEIS

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


# Oasis, 9 7 bytes

xcd-+3V


Try it online!

### Explanation

This uses the recurrence relationship in OEIS:

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)

• Nice use of initial values! You win this time ;) Dec 14 '16 at 12:08
• Yeah, there's probably no way to beat this. Dec 14 '16 at 19:51
• @ZacharyT Only if somebody can figure out a way to make the program have xkcd in it. Dec 15 '16 at 1:01
• @hBy2Py Well, xkcd-+311 works, because k is currently a no-op... Dec 15 '16 at 2:04

# Oasis, 9 8 bytes

Saved a byte thanks to Adnan

xc+d-63T


Try it online!

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)

• Nice! Also, x is short for 2* :). Dec 14 '16 at 11:16
• Beat ya :-P (I hadn't seen there already was an OASIS answer) Dec 14 '16 at 12:06
• @Adnan Is there a way to tell Oasis that you want to shift the output sequence index by 1? I mean, subtract 1 to the input argument (instead of using an initial 0 here) Dec 14 '16 at 12:14
• @LuisMendo Ah, that isn't implemented yet. But it's a good idea for the next release :). Dec 14 '16 at 18:21
• For future reference, this is now implemented Mar 26 '17 at 17:30

# Jelly, 10 bytes

745DBæ*µḢḢ


Try it online!

### 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!

Uses brute force.

### Explanation

3Rṗ’µ+2\<5PµÐfL    Main link. Argument: n
’               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


# MATL, 14 bytes

q3:Z^TTZ+!5<As


Try it online!

### 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


## Mathematica, 48 bytes

MatrixPower[{{1,1,1},{1,0,0},{1,0,1}},#][[1,1]]&


As Luis Mendo pointed out, this is 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 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 {}.

• Would this work? (Kind of ripped right from OEIS with adjustments) LinearRecurrence[{2,1,-1},{1,3,6},#][[#]]&? Dec 14 '16 at 1:28
• Part of why I love this site is learning all of the features Mathematica has to offer :) Dec 14 '16 at 1:34
• By this site, do you mean OEIS or PPCG? Dec 14 '16 at 1:35
• PPCG. I've picked up alot of Mathematica from people's suggestions. Dec 14 '16 at 1:37

# 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!

• (n*n+n)/2 is shorter than [1,3,6][n-1]. And if you're using Python 3 and don't like ending up with floating-point output, (n*n+n)//2 is still shorter. Dec 14 '16 at 12:50

# Pyth - 16 bytes

Uses brute force.

lf.AgL4+VTtT^S3t

• It would be nice to provide a description for those of us who don't "grok" Pyth. Dec 14 '16 at 1:08

# 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]


# 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]


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

## CJam (19 bytes)

{2,{__-2=+1b+}@*W=}


Online test suite. 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:

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
}


# Brain-Flak, 56 bytes

Uses the algorithm detailed in the first comment on the OEIS page.

Try it online!

({}[()]<(((())))>){({}[()]<{({}<>({}))<>}<>>)}{}({}<>{})


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

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

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


# Dyalog APL, 29 bytes

{⍵<4:⍵⌷1 3 6⋄+/2 1 ¯1×∇¨⍵-⍳3}


Works by using the recursive definition of the integer sequence OEIS A006356.

# Python with Numpy, 62 bytes

I had to try it, but it seems pure Python and recursion 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]


# R, 61585551 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))


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

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

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


# 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
`