Paraffins: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (aligned formulas, used colored window, increased whitespace.) |
m (→{{header|Wren}}: Minor tidy) |
||
(13 intermediate revisions by 9 users not shown) | |||
Line 35:
The sequence of those results is visible in the OEIS entry:
::: [[oeis:A00602|A00602: number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers]].
The sequence is (the index starts from zero, and represents the number of carbon atoms):
Line 50:
A flat 1D representation, with arrays or lists is enough, for instance:
<syntaxhighlight lang="text">*Main> all_paraffins 1
[CCP H H H H]
*Main> all_paraffins 2
Line 68:
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)),
CCP (C H H H) (C H 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):
<syntaxhighlight lang="text"> methane ethane propane isobutane
H H H H H H H H H
Line 80:
H ─ C ─ H
│
H</
;Links:
Line 95:
http://java.net/projects/projectfortress/sources/sources/content/ProjectFortress/demos/turnersParaffins0.fss?rev=3005
<br><br>
=={{header|11l}}==
{{trans|Nim}}
<syntaxhighlight lang="11l">V nMax = 250
V nBranches = 4
V rooted = [BigInt(0)] * (nMax + 1)
V unrooted = [BigInt(0)] * (nMax + 1)
rooted[0] = BigInt(1)
rooted[1] = BigInt(1)
unrooted[0] = BigInt(1)
unrooted[1] = BigInt(1)
F choose(m, k)
I k == 1
R m
V result = m
L(i) 1 .< k
result = result * (m + i) I/ (i + 1)
R result
F tree(br, n, l, sum, cnt)
V s = 0
L(b) br + 1 .. :nBranches
s = sum + (b - br) * n
I s > :nMax {R}
V c = choose(:rooted[n], b - br) * cnt
I l * 2 < s {:unrooted[s] += c}
I b == :nBranches {R}
:rooted[s] += c
L(m) (n - 1 .< 0).step(-1)
tree(b, m, l, s, c)
F bicenter(s)
I (s [&] 1) == 0
:unrooted[s] += :rooted[s I/ 2] * (:rooted[s I/ 2] + 1) I/ 2
L(n) 1 .. nMax
tree(0, n, n, 1, BigInt(1))
bicenter(n)
print(n‘: ’unrooted[n])</syntaxhighlight>
{{out}}
<pre>
1: 1
2: 1
3: 1
4: 2
5: 3
6: 5
7: 9
8: 18
9: 35
10: 75
...
244: 34576004768296889785887066794910718730985852896707505707076422305798138880427343561380451664648670542260
245: 96356944442415066997623733664230869603611716312377642117711752082444867783045964116385053282421589905891
246: 268540209617944059776303921971316267806082307732727328919911735252505071315985779867844056236080213000010
247: 748434113260252449609376828666343341456610378512725586135955779939163320693444008584504390382026391947130
248: 2086006351917005252913566124773054331962205157167696706926185063169623907656246841866717933958839366769700
249: 5814271898167303040368103945830220447130073898083466852225709084407144308593691069932064987528870826155297
250: 16206624309085062837751018464745815688226709117091506494175397665527493805947344857313038875654104100026504
</pre>
=={{header|C}}==
Can't show the tree shapes; count only.
<
#define MAX_N 33 /* max number of tree nodes */
Line 212 ⟶ 277:
return 0;
}</
#include <stdio.h>
#include <stdlib.h>
Line 317 ⟶ 382:
return 0;
}</
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iostream>
#include <vector>
const int32_t MAX_TREE_NODES = 52;
const int32_t MAX_BRANCHES = 4;
std::vector<uint64_t> rooted(MAX_TREE_NODES + 1, 0);
std::vector<uint64_t> unrooted(MAX_TREE_NODES + 1,0);
std::vector<uint64_t> count(MAX_BRANCHES, 0);
void tree(const int32_t& branches, const int32_t& radius, const int32_t& combinations,
const int32_t& previous_nodes, const uint64_t& branches_count) {
int32_t nodes = previous_nodes;
for ( int32_t branch = branches + 1; branch <= MAX_BRANCHES; ++branch ) {
nodes += radius;
if ( nodes > MAX_TREE_NODES || ( combinations * 2 >= nodes && branch >= MAX_BRANCHES ) ) {
return;
}
if ( branch == branches + 1 ) {
count[branches] = rooted[radius] * branches_count;
} else {
count[branches] *= ( rooted[radius] + branch - branches - 1 );
count[branches] /= ( branch - branches );
}
if ( combinations * 2 < nodes ) {
unrooted[nodes] += count[branches];
}
if ( branch < MAX_BRANCHES ) {
rooted[nodes] += count[branches];
}
for ( int32_t next_radius = radius - 1; next_radius > 0; --next_radius ) {
tree(branch, next_radius, combinations, nodes, count[branches]);
}
}
}
void bicenter(const int32_t& node) {
if ( ( node & 1 ) == 0 ) {
const uint64_t temp = ( rooted[node / 2] + 1 ) * rooted[node / 2];
unrooted[node] += temp / 2;
}
}
int main() {
rooted[0] = rooted[1] = 1;
unrooted[0] = unrooted[1] = 1;
for ( int32_t node = 1; node <= MAX_TREE_NODES; ++node ) {
tree(0, node, node, 1, 1);
bicenter(node);
std::cout << node << ": " << unrooted[node] << std::endl;
}
}
</syntaxhighlight>
{{ out }}
<pre>
1: 1
2: 1
3: 1
4: 2
5: 3
// elided
48: 156192366474590639
49: 417612400765382272
50: 1117743651746953270
51: 2994664179967370611
52: 8031081780535296591
</pre>
=={{header|D}}==
{{trans|Go}}
<
enum uint nMax = 250;
Line 364 ⟶ 508:
writeln(n, ": ", unrooted[n]);
}
}</
{{out}}
<pre>1: 1
Line 397 ⟶ 541:
{{trans|Pascal}}
{{libheader|GMP}}
<
' compile with: fbc -s console
' uses gmp, translation from pascal
Line 496 ⟶ 640:
Print : Print "hit any key to end program"
Sleep
End</
<pre style="height:35ex;overflow:scroll"> 1: 1
2: 1
Line 1,000 ⟶ 1,144:
=={{header|Go}}==
{{trans|C}}
<
import (
Line 1,060 ⟶ 1,204:
fmt.Printf("%d: %d\n", n, &unrooted[n])
}
}</
Output: (trimmed)
<pre>
Line 1,111 ⟶ 1,255:
=={{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
Line 1,154 ⟶ 1,298:
a602 = a678 - a599 + x2
main = mapM_ print $ take 200 $ zip [0 ..] a602</
Counting trees with some fairly primitive caching:
<
choose :: Integer -> Int -> Integer
Line 1,188 ⟶ 1,332:
| otherwise = x * (x + 1) `div` 2 where x = build_block (n `div` 2)
main = mapM_ print $ map (\x->(x, unrooted x)) [1..max_nodes]</
{{out}}
<pre>
Line 1,213 ⟶ 1,357:
The following code is an interpretation of the Haskell program listed in the links above.
<
part4=: 3 :0
Line 1,244 ⟶ 1,388:
)
NofParaff=: {. radGenN ((ccpGenN +:) + bcpGenN ) 2&|+<.@-:</
Output:
<
1 1 1 1 2 3
5 9 18 35 75 159
Line 1,252 ⟶ 1,396:
60523 148284 366319 910726 2278658 5731580
14490245 36797588 93839412 240215803 617105614 1590507121
4111846763 10660307791 27711253769 72214088660 188626236139 493782952902</
=={{header|Java}}==
Translation of [[Paraffins#C|C]] via [[Paraffins#Go|Go]] and [[Paraffins#D|D]]
<
import java.util.Arrays;
Line 1,314 ⟶ 1,458:
}
}
}</
<pre>1: 1
2: 1
Line 1,336 ⟶ 1,480:
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;
Line 1,400 ⟶ 1,544:
;
paraffins</
'''Output''' (trimmed):
<pre style="height:35ex;overflow:scroll">$ jq -M -n -c -f paraffins.jq
Line 1,458 ⟶ 1,602:
{{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];
Line 1,464 ⟶ 1,608:
[$n, .[0][$n]]
)
;</
=={{header|Julia}}==
{{trans|Go}}
Output is the same as the Go version.
<
const nmax = 500
Line 1,511 ⟶ 1,655:
paraffins()
</syntaxhighlight>
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.math.BigInteger
Line 1,562 ⟶ 1,706:
println("$n: ${unrooted[n]}")
}
}</
{{out}}
Line 1,569 ⟶ 1,713:
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
{{works with|Mathematica|9.0}}
Using the formula on OEIS.
<
CycleIndexPolynomial[SymmetricGroup[m],
Table[ComposeSeries[p, x^i + O[x]^(n + 1)], {i, m}]];
Line 1,581 ⟶ 1,725:
A000602[n_] := SeriesCoefficient[G000602[n], n];
A000602List[n_] := CoefficientList[G000602[n], x];
Grid@Transpose@{Range[0, 200], A000602List@200}</
{{Out}}
<pre>0 1
Line 1,603 ⟶ 1,747:
=={{header|Nim}}==
{{trans|C}}
<syntaxhighlight lang="nim">import bigints
const
Line 1,616 ⟶ 1,761:
unrooted[i] = 0.initBigInt
proc choose(m
result = m
if k == 1: return
for i in 1 ..
result = result * (m + i) div (i + 1)
proc tree(br, n, l, sum: int32
var s: int32 = 0
for b in br + 1 .. nBranches:
Line 1,636 ⟶ 1,781:
tree b, m, l, s, c
proc bicenter(s: int32) =
if (s and 1) == 0:
unrooted[s] += rooted[s div 2] * (rooted[s div 2] + 1) div 2
Line 1,643 ⟶ 1,788:
tree 0, n, n, 1, 1.initBigInt
n.bicenter
echo n, ": ", unrooted[n]</
{{out}}
<pre>1: 1
2: 1
Line 1,673 ⟶ 1,819:
This function is for recent PARI/GP:
<
{
local (P = p+1, R, U = R = Vec([1,1], P));
Line 1,687 ⟶ 1,833:
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);
Line 1,709 ⟶ 1,855:
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)
Line 1,751 ⟶ 1,897:
{{libheader|GMP}}
Conversion of the C example:
<
uses
Line 1,838 ⟶ 1,984:
mp_printf('%d: %Zd'+chr(13)+chr(10), n, @unrooted[n]);
end;
end.</
Output (trimmed):
<pre>1: 1
Line 1,885 ⟶ 2,031:
{{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;
Line 1,996 ⟶ 2,142:
WriteLn( SysUtils.Format( '%2d %d', [k, nrAlkanes[k]]));
end.
</syntaxhighlight>
{{out}}
<pre>
Line 2,014 ⟶ 2,160:
{{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;
Line 2,053 ⟶ 2,199:
bicenter($n);
print "$n: $unrooted[$n]\n";
}</
Output identical to C GMP example (truncated to 250).
Line 2,060 ⟶ 2,206:
{{trans|Ruby}}
{{trans|FreeBASIC}}
Using IEEE754 floats, hence imprecise above n=45 on 32 bit, n=52 on 64bit, tested to n=
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">MAX_N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">BRANCH</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rooted</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">MAX_N</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">unrooted</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">MAX_N</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">br</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tot</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">cnt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">br</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">BRANCH</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tot</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tot</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">MAX_N</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">tot</span> <span style="color: #008080;">and</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">BRANCH</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tot</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">==</span><span style="color: #000000;">br</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n1</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">cnt</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">*=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n1</span><span style="color: #0000FF;">]+(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">-</span><span style="color: #000000;">br</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))/(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">-</span><span style="color: #000000;">br</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;"><</span><span style="color: #000000;">tot</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">b</span><span style="color: #0000FF;"><</span><span style="color: #000000;">BRANCH</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tot</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">bicenter</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">aux</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">aux</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">aux</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">MAX_N</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">bicenter</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">10</span> <span style="color: #008080;">or</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">MAX_N</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,119 ⟶ 2,272:
9: 35
32: 27711253769
</pre>
And the same thing using gmp, obviously without any such accuracy limits
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">max_n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">200</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">branch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ivals</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">max_n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">rooted</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">max_n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ivals</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">unrooted</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">max_n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ivals</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">branch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">br</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">mpz</span> <span style="color: #000000;">cnt</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">cbr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">br</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">br</span> <span style="color: #008080;">to</span> <span style="color: #000000;">branch</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">></span><span style="color: #000000;">max_n</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">s</span> <span style="color: #008080;">and</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">branch</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">br</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cbr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">cnt</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">-</span><span style="color: #000000;">br</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cbr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cbr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_divexact_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cbr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cbr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">-</span><span style="color: #000000;">br</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;"><</span><span style="color: #000000;">s</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cbr</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">b</span><span style="color: #0000FF;"><</span><span style="color: #000000;">branch</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cbr</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cbr</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">bicenter</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">aux</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">aux</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">aux</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_tdiv_q_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">cnt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">max_n</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cnt</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">bicenter</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">25</span> <span style="color: #008080;">or</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">mpz_get_short_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
Unusually this is significantly faster (6*) under pwa/p2js than desktop/Phix, the following output/time is from the former.<br>
The limit of 200 in the code above finishes on desktop/Phix in 6s, p2js 1s, 500 takes about 40s in the browser but a whopping three and a half minutes on desktop/Phix, compared to the Go entry above completing that task in 15.6s, all on the same box of course. I have earmarked this task for further investigation into performance improvements, should Phix 2.0 ever actually get started on, that is.
{{out}}
<pre>
1: 1
2: 1
3: 1
4: 2
5: 3
6: 5
7: 9
8: 18
9: 35
10: 75
11: 159
12: 355
13: 802
14: 1858
15: 4347
16: 10359
17: 24894
18: 60523
19: 148284
20: 366319
21: 910726
22: 2278658
23: 5731580
24: 14490245
25: 36797588
100: 5921072038125809849884993369103538010139
200: 94304332879903850516...51576307818857723954 (84 digits)
300: 30845274893235665913...77084032710062170279 (129 digits)
400: 13544322063698139999...74867143490557738328 (174 digits)
500: 69888806977968318652...40565376686372508743 (218 digits)
600: 39937810748209753430...83373172999304809224 (263 digits)
"1 minute and 23s"
</pre>
=={{header|Pike}}==
{{trans|Python}}
<
int BRANCH = 4;
Line 2,185 ⟶ 2,440:
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()
Line 2,242 ⟶ 2,497:
print "%d: %d" % (n, unrooted[n])
main()</
Output (newlines added):
<pre>1: 1
Line 2,292 ⟶ 2,547:
=== 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
Line 2,404 ⟶ 2,659:
a602 = a678 - a599 + x2
for n,x in zip(count(0), islice(a602, 500)): print(n,x)</
=== Using generating function without OO ===
Line 2,410 ⟶ 2,665:
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
Line 2,441 ⟶ 2,696:
def A000602(k): return A000642(k) + (A000642((k-1) // 2) if k % 2 == 1 else 0) - A000631(k-1)
for k in range(500): print(k, A000602(k))</
=={{header|Racket}}==
Line 2,447 ⟶ 2,702:
Or, a direct translation of the C entry:
<
#lang racket
Line 2,484 ⟶ 2,739:
(bicenter n)
(printf "~a: ~a\n" n (vector-ref unrooted n)))
</syntaxhighlight>
=={{header|Raku}}==
Line 2,494 ⟶ 2,749:
Note how lexical scoping — rather than global variables or repeated arguments — is used to pass down information to subroutines.
<syntaxhighlight lang="raku"
my @rooted = flat 1,1,0 xx $max-weight - 1;
my @unrooted = flat 1,1,0 xx $max-weight - 1;
Line 2,538 ⟶ 2,793:
my constant N = 100;
my @paraffins = count-unrooted-trees(4, N);
say .fmt('%3d'), ': ', @paraffins[$_] for flat 1 .. 30, N;</
{{out}}
Line 2,577 ⟶ 2,832:
Programming note: the biggest concern was calculating the number of decimal digits (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.*/
Line 2,603 ⟶ 2,858:
if LL<sum then unrooted.sum= unrooted.sum + #.br
if b==4 then leave
rooted.sum
do m=nm by -1 for nm; call tree b, m, L, sum, #.br
end /*m*/
end /*b*/ /* ↑↑↑↑↑↑↑↑↑ recursive. */
return</
{{out|output|text= when using the input of: <tt> 600 </tt>}}
Line 3,217 ⟶ 3,472:
=={{header|Ruby}}==
{{trans|Python}}
<
BRANCH = 4
Line 3,252 ⟶ 3,507:
bicenter(n)
puts "%d: %d" % [n, $unrooted[n]]
end</
{{out}}
<pre>
Line 3,297 ⟶ 3,552:
=={{header|Scala}}==
<
val (nMax, nBranches) = (250, 4)
val rooted, unrooted = Array.tabulate(nMax + 1)(i => if (i < 2) BigInt(1) else BigInt(0))
Line 3,330 ⟶ 3,585:
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";
Line 3,395 ⟶ 3,650:
writeln(n <& ": " <& unrooted[n]);
end for;
end func;</
Output (trimmed):
Line 3,432 ⟶ 3,687:
{{trans|C}}
Handles arbitrarily large values.
<
set maxN 200
Line 3,477 ⟶ 3,732:
bicenter $n
puts "${n}: [lindex $unrooted $n]"
}</
=={{header|Wren}}==
Line 3,483 ⟶ 3,738:
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var branches = 4
Line 3,533 ⟶ 3,788:
bicenter.call(n)
Fmt.print("$3d: $i", n, unrooted[n])
}</
{{out}}
Line 3,577 ⟶ 3,832:
250: 16206624309085062837751018464745815688226709117091506494175397665527493805947344857313038875654104100026504
</pre>
=={{header|zkl}}==
Line 3,583 ⟶ 3,837:
{{trans|Go}}
Uses GMP for big ints, mostly modified in place. Rather slow.
<
const nMax=100, nBranches=4;
Line 3,617 ⟶ 3,871:
bicenter(n);
println(n, ": ", unrooted[n]);
}</
{{out}}
<pre>
|