Paraffins: Difference between revisions

Enumerate, without repetitions and in order of increasing size, all possible paraffin molecules (also known as [[wp:alkane|alkane]]s).

Paraffins are built up using only carbon atoms, which has four bonds, and hydrogen, which has one bond.   All bonds for each atom must be used, so it is easiest to think of an alkane as linked carbon atoms forming the "backbone" structure, with adding hydrogen atoms linking the remaining unused bonds.

In a paraffin, one is allowed neither double bonds (two bonds between the same pair of atoms), nor cycles of linked carbons. &nbsp; So all paraffins with &nbsp; '''n''' &nbsp; carbon atoms share the empirical formula &nbsp; &nbsp; <big>C_nH_2n+2</big>

In counting isomers it should be borne in mind that the four bond positions on a given carbon atom can be freely interchanged and bonds rotated (including 3-D "out of the paper" rotations when it's being observed on a flat diagram), &nbsp; so rotations or re-orientations of parts of the molecule (without breaking bonds) do not give different isomers. &nbsp; So what seem at first to be different molecules may in fact turn out to be different orientations of the same molecule.

::: &nbsp; [[oeis:A00602|A00602: number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers]].

<langsyntaxhighlight haskelllang="text">*Main> all_paraffins 1

[CCP H H H H]

[BCP (C H H H) (C H H H)]

[CCP H H (C H H H) (C H H H)]

[BCP (C H H (C H H H)) [BCP (C H H (C H H H)),CCP H (C H H H) (C H H H)),

[CCP H H (C H H (C H H H)) (C H H (C H H H)),CCP H (C H H H)

(C H H H) (C H CCP H (C H H H)),CCP (C H H H) (C H H H) (C H H H)),

[BCP (C H H (C H H (C H H H))) (C H H (C H H (C H H H))),BCP

BCP (C H H (C H H (C H H H))) (C H (C H H H) (C H H H)),BCP (C H

BCP (C H (C H H H) (C H H H)) (C H (C H H H) (C H H H)),CCP H (C H H H)

(C H CCP H (C H H H)) (C H H (C H H H)),CCP (C H H H) (C H H H)),

CCP (C H H H) (C H H H) (C H H H) (C H H (C H H H))]</langsyntaxhighlight>

<presyntaxhighlight lang="text"> Methane methane ethane Ethane propane Propane Isobutaneisobutane

H H H H H H H H H

| │ | | │ │ | | | │ │ │ | | | │ │ │

H -─ C -─ H H -─ C -─ C -─ H H -─ C -─ C -─ C -─ H H -─ C -─ C -─ C -─ H

| │ | | │ │ | | | │ │ │ | | | │ │ │

H H H H H H H |│ H

| │

H -─ C -─ H

| │

H</presyntaxhighlight>

* &nbsp; A paper that explains the problem and its solution in a functional language:

* &nbsp; A Haskell implementation:

* &nbsp; A Scheme implementation:

* &nbsp; A Fortress implementation: &nbsp; &nbsp; &nbsp; &nbsp; (this site has been closed)

<langsyntaxhighlight lang="c">#include <stdio.h>

}</langsyntaxhighlight>Same idea, with GMP, and done somewhat differently:<langsyntaxhighlight lang="c">#include <gmp.h>

}</langsyntaxhighlight>

<langsyntaxhighlight lang="d">import std.stdio, std.bigint;

}</langsyntaxhighlight>

<langsyntaxhighlight lang="freebasic">' version 31-12-2016

End</langsyntaxhighlight>

<langsyntaxhighlight lang="go">package main

}</langsyntaxhighlight>

<langsyntaxhighlight lang="haskell">-- polynomial utils

main = mapM_ print $ take 200 $ zip [0 ..] a602</langsyntaxhighlight>

<langsyntaxhighlight lang="haskell">import Data.Array

main = mapM_ print $ map (\x->(x, unrooted x)) [1..max_nodes]</langsyntaxhighlight>

<langsyntaxhighlight lang="j">part3=: ;@((<@([(],.(-+/"1))],.]+i.@(]-~1+<.@-:@-))"0 i.@>:@<.@%&3))

NofParaff=: {. radGenN ((ccpGenN +:) + bcpGenN ) 2&|+<.@-:</langsyntaxhighlight>

<langsyntaxhighlight lang="j"> 6 6 $ NofParaff 36

4111846763 10660307791 27711253769 72214088660 188626236139 493782952902</langsyntaxhighlight>

<langsyntaxhighlight lang="java">import java.math.BigInteger;

}</langsyntaxhighlight>

<langsyntaxhighlight lang="jq">def MAX_N: 500; # imprecision begins at 46

paraffins</langsyntaxhighlight>

<langsyntaxhighlight lang="jq">def paraffins:

;</langsyntaxhighlight>

<langsyntaxhighlight lang="julia">const branches = 4

<langsyntaxhighlight lang="scala">// version 1.1.4-3

}</langsyntaxhighlight>

=={{header|Mathematica}}/{{header|Wolfram Language}}==

<langsyntaxhighlight lang="mathematica">s[m_, p_, n_] :=

Grid@Transpose@{Range[0, 200], A000602List@200}</langsyntaxhighlight>

<lang nim>import {{libheader|bigints}}

proc choose(m,: BigInt; k: int32): BigInt =

for i in 1 .. < k:

proc tree(br, n, l, sum: int32,; cnt: BigInt) =

proc bicenter(s: int32) =

echo n, ": ", unrooted[n]</langsyntaxhighlight>

<langsyntaxhighlight lang="parigp">paraffin(p) =

}</langsyntaxhighlight>

<langsyntaxhighlight lang="parigp">iso(B,n,C,S,l=n) =

}</langsyntaxhighlight>

<langsyntaxhighlight lang="pascal">Program Paraffins;

end.</langsyntaxhighlight>

<langsyntaxhighlight lang="pascal">

<langsyntaxhighlight lang="perl">use Math::GMPz;

}</langsyntaxhighlight>

Using IEEE754 floats, hence imprecise above n=45 on 32 bit, n=52 on 64bit, tested to n=500600, giving 63.988e21799378e+262 using %g format, ie accurate to better than 1e-10%.

c <span style="color: rooted[n+1]*cnt#008080;">return</span>

<langsyntaxhighlight Pikelang="pike">int MAX_N = 300;

}</langsyntaxhighlight>

<langsyntaxhighlight lang="python">try:

main()</langsyntaxhighlight>

<langsyntaxhighlight lang="python">from itertools import count, chain, tee, islice, cycle

for n,x in zip(count(0), islice(a602, 500)): print(n,x)</langsyntaxhighlight>

<langsyntaxhighlight lang="python">#!/usr/bin/python3

for k in range(500): print(k, A000602(k))</langsyntaxhighlight>

<langsyntaxhighlight lang="racket">

<syntaxhighlight lang="raku" perl6line>sub count-unrooted-trees(Int $max-branches, Int $max-weight) {

say .fmt('%3d'), ': ', @paraffins[$_] for flat 1 .. 30, N;</langsyntaxhighlight>

<langsyntaxhighlight lang="rexx">/*REXX pgm enumerates (without repetition) the number of paraffins with N carbon atoms. */

rooted.sum = rooted.sum + #.br

return</langsyntaxhighlight>

<langsyntaxhighlight lang="ruby">MAX_N = 500

end</langsyntaxhighlight>

<langsyntaxhighlight Scalalang="scala">object Paraffins extends App {

}</langsyntaxhighlight>

<langsyntaxhighlight lang="seed7">$ include "seed7_05.s7i";

end func;</langsyntaxhighlight>

<langsyntaxhighlight lang="tcl">package require Tcl 8.5

}</langsyntaxhighlight>

<langsyntaxhighlight ecmascriptlang="wren">import "./big" for BigInt

import "./fmt" for Fmt

}</langsyntaxhighlight>

<langsyntaxhighlight lang="zkl">var BN=Import("zklBigNum");

}</langsyntaxhighlight>