Paraffins: Difference between revisions

 

The sequence of those results is visible in the OEIS entry:  

 

The sequence is (the index starts from zero, and represents the number of carbon atoms):

A flat 1D representation, with arrays or lists is enough, for instance:

 

[CCP H H H H]

*Main> all_paraffins 2

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 H (C H H H)) (C H H (C H H H)),

Showing a basic 2D ASCII-art representation of the paraffins is better; for instance (molecule names aren't necessary):

H H H H H H H H H

H ─ C ─ H

│

 

;Links:

{{trans|Nim}}

 

V nBranches = 4

V rooted = [BigInt(0)] * (nMax + 1)

tree(0, n, n, 1, BigInt(1))

bicenter(n)

 

{{out}}

=={{header|C}}==

Can't show the tree shapes; count only.

 

#define MAX_N 33 /* max number of tree nodes */

 

return 0;

#include <stdio.h>

#include <stdlib.h>

 

return 0;

 

=={{header|D}}==

{{trans|Go}}

 

enum uint nMax = 250;

writeln(n, ": ", unrooted[n]);

}

{{out}}

<pre>1: 1

{{trans|Pascal}}

{{libheader|GMP}}

' compile with: fbc -s console

' uses gmp, translation from pascal

Print : Print "hit any key to end program"

Sleep

<pre style="height:35ex;overflow:scroll"> 1: 1

2: 1

=={{header|Go}}==

{{trans|C}}

 

import (

fmt.Printf("%d: %d\n", n, &unrooted[n])

}

Output: (trimmed)

<pre>

=={{header|Haskell}}==

Using formula from OEIS page, similar to the Mathematica entry below:

a `nmul` n = map (*n) a

a `ndiv` n = map (`div` n) a

a602 = a678 - a599 + x2

 

 

Counting trees with some fairly primitive caching:

 

choose :: Integer -> Int -> Integer

| otherwise = x * (x + 1) `div` 2 where x = build_block (n `div` 2)

 

{{out}}

<pre>

The following code is an interpretation of the Haskell program listed in the links above.

 

 

part4=: 3 :0

)

 

Output:

1 1 1 1 2 3

5 9 18 35 75 159

60523 148284 366319 910726 2278658 5731580

14490245 36797588 93839412 240215803 617105614 1590507121

 

=={{header|Java}}==

Translation of [[Paraffins#C|C]] via [[Paraffins#Go|Go]] and [[Paraffins#D|D]]

import java.util.Arrays;

 

}

}

<pre>1: 1

2: 1

Currently jq uses IEEE 754 64-bit numbers. Large integers are approximated by floats and therefore the results generated by the program presented here are only precise for n up to and including 45.

 

def BRANCH: 4;

 

;

 

'''Output''' (trimmed):

<pre style="height:35ex;overflow:scroll">$ jq -M -n -c -f paraffins.jq

{{works with|jq|>1.4}}

The following is a more elegant alternative to paraffins/0 as defined above but requires "foreach":

foreach range(1; MAX_N) as $n

( [unrooted, ra];

[$n, .[0][$n]]

)

 

=={{header|Julia}}==

{{trans|Go}}

Output is the same as the Go version.

const nmax = 500

 

 

paraffins()

 

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.math.BigInteger

println("$n: ${unrooted[n]}")

}

 

{{out}}

{{works with|Mathematica|9.0}}

Using the formula on OEIS.

CycleIndexPolynomial[SymmetricGroup[m],

Table[ComposeSeries[p, x^i + O[x]^(n + 1)], {i, m}]];

A000602[n_] := SeriesCoefficient[G000602[n], n];

A000602List[n_] := CoefficientList[G000602[n], x];

{{Out}}

<pre>0 1

{{trans|C}}

{{libheader|bigints}}

 

const

tree 0, n, n, 1, 1.initBigInt

n.bicenter

 

{{out}}

 

This function is for recent PARI/GP:

{

local (P = p+1, R, U = R = Vec([1,1], P));

if (n % 2,, U[n+1] += R[n/2+1] * (R[n/2+1]+1)/2);

print([n, U[n+1]]))

 

 

Code for older version of PARI/GP < 2.9:

{

my (b,c,i,s);

if (n % 2,, U[n+1] += R[n/2+1] * (R[n/2+1]+1)/2);

print([n, U[n+1]]))

 

Output:<pre>paraffin(32)

{{libheader|GMP}}

Conversion of the C example:

 

uses

mp_printf('%d: %Zd'+chr(13)+chr(10), n, @unrooted[n]);

end;

Output (trimmed):

<pre>1: 1

{{works with|Free_Pascal}}

This method of counting alkanes is based on a paper by Shinsaku Fujita (see program for reference). Multi-precision is not used, so alkanes are counted only up to order 49. The results are identical to those from the REXX program.

program CountAlkanes;

 

WriteLn( SysUtils.Format( '%2d %d', [k, nrAlkanes[k]]));

end.

{{out}}

<pre>

{{trans|C}}

This is using Math::GMPz for best performance. Math::GMP works almost as well. Math::BigInt is in core and only 9 times slower for this task.

 

my $nmax = 250;

bicenter($n);

print "$n: $unrooted[$n]\n";

 

Output identical to C GMP example (truncated to 250).

{{trans|Ruby}}

{{trans|FreeBASIC}}

{{out}}

<pre>

9: 35

32: 27711253769

</pre>

 

=={{header|Pike}}==

{{trans|Python}}

int BRANCH = 4;

write("%d: %d\n", n, unrooted[n]);

}

 

=={{header|Python}}==

This version only counts different paraffins. The multi-precision integers of Python avoid overflows.

{{trans|C}}

import psyco

psyco.full()

print "%d: %d" % (n, unrooted[n])

 

Output (newlines added):

<pre>1: 1

=== Using generating function ===

This is almost the same as the one in [[Formal power series]]. Compare to the Mathematica and Haskell solutions.

from fractions import Fraction

from sys import setrecursionlimit

a602 = a678 - a599 + x2

 

 

=== Using generating function without OO ===

This uses a different generating function, but also demonstrates a lower level approach and the use of <code>functools.lru_cache</code> to memoise a recursive function which would otherwise make an exponential number of recursive calls.

 

 

from functools import lru_cache

def A000602(k): return A000642(k) + (A000642((k-1) // 2) if k % 2 == 1 else 0) - A000631(k-1)

 

 

=={{header|Racket}}==

 

Or, a direct translation of the C entry:

#lang racket

 

(bicenter n)

(printf "~a: ~a\n" n (vector-ref unrooted n)))

 

=={{header|Raku}}==

Note how lexical scoping &mdash; rather than global variables or repeated arguments &mdash; is used to pass down information to subroutines.

 

my @rooted = flat 1,1,0 xx $max-weight - 1;

my @unrooted = flat 1,1,0 xx $max-weight - 1;

my constant N = 100;

my @paraffins = count-unrooted-trees(4, N);

 

{{out}}

 

Programming note: &nbsp; the biggest concern was calculating the number of decimal digits &nbsp; (so as to avoid integer overflow).

parse arg nodes . /*obtain optional argument from the CL.*/

if nodes=='' | nodes=="," then nodes= 100 /*Not specified? Then use the default.*/

end /*m*/

end /*b*/ /* ↑↑↑↑↑↑↑↑↑ recursive. */

{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 600 </tt>}}

 

=={{header|Ruby}}==

{{trans|Python}}

BRANCH = 4

 

bicenter(n)

puts "%d: %d" % [n, $unrooted[n]]

{{out}}

<pre>

 

=={{header|Scala}}==

val (nMax, nBranches) = (250, 4)

val rooted, unrooted = Array.tabulate(nMax + 1)(i => if (i < 2) BigInt(1) else BigInt(0))

println(f"$n%3d: ${unrooted(n)}%s")

}

{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/JjR1R6k/2 ScalaFiddle (JavaScript)] or by [https://scastie.scala-lang.org/QycB9fBTTYG890zKOqREVw Scastie (JVM)].

 

=={{header|Seed7}}==

include "bigint.s7i";

 

writeln(n <& ": " <& unrooted[n]);

end for;

 

Output (trimmed):

{{trans|C}}

Handles arbitrarily large values.

 

set maxN 200

bicenter $n

puts "${n}: [lindex $unrooted $n]"

 

=={{header|Wren}}==

{{libheader|Wren-big}}

{{libheader|Wren-fmt}}

 

var branches = 4

bicenter.call(n)

Fmt.print("$3d: $i", n, unrooted[n])

 

{{out}}

250: 16206624309085062837751018464745815688226709117091506494175397665527493805947344857313038875654104100026504

</pre>

 

=={{header|zkl}}==

{{trans|Go}}

Uses GMP for big ints, mostly modified in place. Rather slow.

 

const nMax=100, nBranches=4;

bicenter(n);

println(n, ": ", unrooted[n]);

{{out}}

<pre>