28
2
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 returning1
. - 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? – Maltysen – 2016-12-13T23:03:52.503Fixed. @Maltysen: yes. – Zacharý – 2016-12-13T23:19:26.310
4Why is there an OEIS sequence for everything? :P – HyperNeutrino – 2016-12-14T03:28:46.520
Is 0-indexing (like the OEIS sequence does) okay? – Emigna – 2016-12-14T10:24:28.620
@Emigna, to fix things just insert
a(0) = 1
. To be honest, I think that should be a required test case in this question. – Peter Taylor – 2016-12-14T11:38:26.2370 doesn't matter, but if I included it, it would be 0: because nothing isn't even a molecule. – Zacharý – 2016-12-14T12:04:02.263
2@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. – Peter Taylor – 2016-12-14T12:15:58.533
@PeterTaylor: I did an initial value for a(0) (at no extra cost in bytes). I just wondered if it was necessary as the OEIS sequence linked is 0-indexed. – Emigna – 2016-12-14T12:29:45.847
1@Emigna, that's because the wrong sequence was linked. I'll correct it. – Peter Taylor – 2016-12-14T14:28:12.643