Number of Straight-Chain Alk*nes of given length

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.

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 1

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

Answer 2

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)

Answer 3

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)

Answer 4

Jelly, 10 bytes

745DBæ*µḢḢ

Try it online!

Uses Luis Mendo's algorithm.

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

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

Answer 6

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 {}.

Answer 7

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!

Answer 8

Pyth - 16 bytes

Uses brute force.

lf.AgL4+VTtT^S3t

Test Suite.

Answer 9

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 10

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 11

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 12

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
}

Answer 13

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.

Answer 14

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 15

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 16

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 17

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]

Answer 18

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 19

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 20

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 21

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