Paraffins

From Rosetta Code
Task
Paraffins
You are encouraged to solve this task according to the task description, using any language you may know.
Paraffins.isopentane.png

This organic chemistry task is essentially to implement a tree enumeration algorithm.


Task

Enumerate, without repetitions and in order of increasing size, all possible paraffin molecules (also known as alkanes).


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. So all paraffins with   n   carbon atoms share the empirical formula   CnH2n+2

But for all   n ≥ 4   there are several distinct molecules ("isomers") with the same formula but different structures.

The number of isomers rises rather rapidly when   n   increases.

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), so rotations or re-orientations of parts of the molecule (without breaking bonds) do not give different isomers. So what seem at first to be different molecules may in fact turn out to be different orientations of the same molecule.


Example

With   n = 3   there is only one way of linking the carbons despite the different orientations the molecule can be drawn;   and with   n = 4   there are two configurations:

  • a   straight chain:     (CH3)(CH2)(CH2)(CH3)
  • a branched chain:     (CH3)(CH(CH3))(CH3)


Due to bond rotations, it doesn't matter which direction the branch points in.

The phenomenon of "stereo-isomerism" (a molecule being different from its mirror image due to the actual 3-D arrangement of bonds) is ignored for the purpose of this task.

The input is the number   n   of carbon atoms of a molecule (for instance 17).

The output is how many different different paraffins there are with   n   carbon atoms (for instance   24,894   if   n = 17).

The sequence of those results is visible in the Sloane encyclopedia. The sequence is (the index starts from zero, and represents the number of carbon atoms):

1, 1, 1, 1, 2, 3, 5, 9, 18, 35, 75, 159, 355, 802, 1858, 4347, 10359,
24894, 60523, 148284, 366319, 910726, 2278658, 5731580, 14490245,
36797588, 93839412, 240215803, 617105614, 1590507121, 4111846763,
10660307791, 27711253769, ...


Extra credit

Show the paraffins in some way.

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

*Main> all_paraffins 1
[CCP H H H H]
*Main> all_paraffins 2
[BCP (C H H H) (C H H H)]
*Main> all_paraffins 3
[CCP H H (C H H H) (C H H H)]
*Main> all_paraffins 4
[BCP (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 H H)]
*Main> all_paraffins 5
[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 H (C H H H)),CCP (C H H H) (C H H H) (C H H H)
(C H H H)]
*Main> all_paraffins 6
[BCP (C H H (C H H (C H H H))) (C H H (C H H (C H H H))),BCP
(C H H (C H H (C H H H))) (C H (C H H H) (C H H 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 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):

 Methane         Ethane              Propane              Isobutane
                 
    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


Links
  • A paper that explains the problem and its solution in a functional language:

http://www.cs.wright.edu/~tkprasad/courses/cs776/paraffins-turner.pdf

  • A Haskell implementation:

https://github.com/ghc/nofib/blob/master/imaginary/paraffins/Main.hs

  • A Scheme implementation:

http://www.ccs.neu.edu/home/will/Twobit/src/paraffins.scm

  • A Fortress implementation:

http://java.net/projects/projectfortress/sources/sources/content/ProjectFortress/demos/turnersParaffins0.fss?rev=3005

C[edit]

Can't show the tree shapes; count only.

#include <stdio.h>
 
#define MAX_N 33 /* max number of tree nodes */
#define BRANCH 4 /* max number of edges a single node can have */
 
/* The basic idea: a paraffin molecule can be thought as a simple tree
with each node being a carbon atom. Counting molecules is thus the
problem of counting free (unrooted) trees of given number of nodes.
 
An unrooted tree needs to be uniquely represented, so we need a way
to cannonicalize equivalent free trees. For that, we need to first
define the cannonical form of rooted trees. Since rooted trees can
be constructed by a root node and up to BRANCH rooted subtrees that
are arranged in some definite order, we can define it thusly:
* Given the root of a tree, the weight of each of its branches is
the number of nodes contained in that branch;
* A cannonical rooted tree would have its direct subtrees ordered
in descending order by weight;
* In case multiple subtrees are the same weight, they are ordered
by some unstated, but definite, order (this code doesn't really
care what the ordering is; it only counts the number of choices
in such a case, not enumerating individual trees.)
 
A rooted tree of N nodes can then be constructed by adding smaller,
cannonical rooted trees to a root node, such that:
* Each subtree has fewer than BRANCH branches (since it must have
an empty slot for an edge to connect to the new root);
* Weight of those subtrees added later are no higher than earlier
ones;
* Their weight total N-1.
A rooted tree so constructed would be itself cannonical.
 
For an unrooted tree, we can define the radius of any of its nodes:
it's the maximum weight of any of the subtrees if this node is used
as the root. A node is the center of a tree if it has the smallest
radius among all the nodes. A tree can have either one or two such
centers; if two, they must be adjacent (cf. Knuth, tAoCP 2.3.4.4).
 
An important fact is that, a node in a tree is its sole center, IFF
its radius times 2 is no greater than the sum of the weights of all
branches (ibid). While we are making rooted trees, we can add such
trees encountered to the count of cannonical unrooted trees.
 
A bi-centered unrooted tree with N nodes can be made by joining two
trees, each with N/2 nodes and fewer than BRANCH subtrees, at root.
The pair must be ordered in aforementioned implicit way so that the
product is cannonical. */

 
typedef unsigned long long xint;
#define FMT "llu"
 
xint rooted[MAX_N] = {1, 1, 0};
xint unrooted[MAX_N] = {1, 1, 0};
 
/* choose k out of m possible values; chosen values may repeat, but the
ordering of them does not matter. It's binomial(m + k - 1, k) */

xint choose(xint m, xint k)
{
xint i, r;
 
if (k == 1) return m;
for (r = m, i = 1; i < k; i++)
r = r * (m + i) / (i + 1);
return r;
}
 
/* constructing rooted trees of BR branches at root, with at most
N radius, and SUM nodes in the partial tree already built. It's
recursive, and CNT and L carry down the number of combinations
and the tree radius already encountered. */

void tree(xint br, xint n, xint cnt, xint sum, xint l)
{
xint b, c, m, s;
 
for (b = br + 1; b <= BRANCH; b++) {
s = sum + (b - br) * n;
if (s >= MAX_N) return;
 
/* First B of BR branches are all of weight n; the
rest are at most of weight N-1 */

c = choose(rooted[n], b - br) * cnt;
 
/* This partial tree is singly centered as is */
if (l * 2 < s) unrooted[s] += c;
 
/* Trees saturate at root can't be used as building
blocks for larger trees, so forget them */

if (b == BRANCH) return;
rooted[s] += c;
 
/* Build the rest of the branches */
for (m = n; --m; ) tree(b, m, c, s, l);
}
}
 
void bicenter(int s)
{
if (s & 1) return;
 
/* Pick two of the half-size building blocks, allowing
repetition. */

unrooted[s] += rooted[s/2] * (rooted[s/2] + 1) / 2;
}
 
int main()
{
xint n;
for (n = 1; n < MAX_N; n++) {
tree(0, n, 1, 1, n);
bicenter(n);
printf("%"FMT": %"FMT"\n", n, unrooted[n]);
}
 
return 0;
}
Same idea, with GMP, and done somewhat differently:
#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_BRANCH 4
#define MAX_N 500
 
mpz_t bcache[MAX_N + 1];
mpz_t ucache[MAX_N + 1];
mpz_t *rcache[MAX_N + 1][MAX_BRANCH + 1];
 
mpz_t tmp1, tmp2;
void choose(mpz_t r, mpz_t m, int k)
{
int i;
mpz_set(r, m);
 
mpz_add_ui(tmp1, m, 1);
for (i = 1; i < k; ) {
mpz_mul(r, r, tmp1);
mpz_divexact_ui(r, r, ++i);
 
if (i >= k) break;
mpz_add_ui(tmp1, tmp1, 1);
}
}
 
mpz_t rtmp1, rtmp2;
void calc_rooted(mpz_t res, int n, int b, int r)
{
mpz_set_ui(res, 0);
 
if (n == 1 && b == 0 && r == 0) {
mpz_set_ui(res, 1);
return;
} else if (n <= b || n <= r || n == 1 || b == 0 || r == 0)
return;
 
int b1, r1;
for (b1 = 1; b1 <= b && r * b1 < n; b1++) {
choose(rtmp1, bcache[r], b1);
mpz_set_ui(rtmp2, 0);
for (r1 = 0; r1 < r && r1 + r * b1 < n; r1++)
mpz_add(rtmp2, rtmp2, rcache[n - r * b1][b - b1][r1]);
 
mpz_addmul(res, rtmp1, rtmp2);
}
}
 
void calc_first_branch(int n)
{
int b, r;
mpz_init_set_ui(bcache[n], 0);
 
for (b = 0; b < MAX_BRANCH; b++)
for (r = 0; r < n; r++)
mpz_add(bcache[n], bcache[n], rcache[n][b][r]);
}
 
void calc_unrooted(int n)
{
int b, r;
 
for (b = 0; b <= MAX_BRANCH; b++) {
mpz_t *p = malloc(sizeof(mpz_t) * n);
rcache[n][b] = p;
for (r = 0; r < n; r++) {
mpz_init(p[r]);
calc_rooted(p[r], n, b, r);
}
}
 
calc_first_branch(n);
 
mpz_init_set_ui(ucache[n], 0);
for (r = 0; r * 2 < n; r++)
for (b = 0; b <= MAX_BRANCH; b++)
mpz_add(ucache[n], ucache[n], rcache[n][b][r]);
 
if (!(n & 1)) {
mpz_add_ui(rtmp1, bcache[n/2], 1);
mpz_mul(rtmp1, rtmp1, bcache[n/2]);
mpz_divexact_ui(rtmp1, rtmp1, 2);
mpz_add(ucache[n], ucache[n], rtmp1);
}
}
 
void init(void)
{
mpz_init(tmp1), mpz_init(tmp2);
mpz_init(rtmp1), mpz_init(rtmp2);
}
 
int main(void)
{
int i;
 
init();
 
for (i = 0; i <= MAX_N; i++) {
calc_unrooted(i);
gmp_printf("%d: %Zd\n", i, ucache[i]);
}
 
return 0;
}

D[edit]

Translation of: Go
import std.stdio, std.bigint;
 
enum uint nMax = 250;
enum uint nBranches = 4;
 
__gshared BigInt[nMax + 1] rooted = [1.BigInt, 1.BigInt /*...*/],
unrooted = [1.BigInt, 1.BigInt /*...*/];
 
void tree(in uint br, in uint n, in uint l, in uint inSum,
in BigInt cnt) nothrow {
__gshared static BigInt[nBranches] c;
 
uint sum = inSum;
foreach (immutable b; br + 1 .. nBranches + 1) {
sum += n;
if (sum > nMax || (l * 2 >= sum && b >= nBranches))
return;
if (b == br + 1) {
c[br] = rooted[n] * cnt;
} else {
c[br] *= rooted[n] + b - br - 1;
c[br] /= b - br;
}
if (l * 2 < sum)
unrooted[sum] += c[br];
if (b < nBranches)
rooted[sum] += c[br];
foreach_reverse (immutable m; 1 .. n)
tree(b, m, l, sum, c[br]);
}
}
 
void bicenter(in uint s) nothrow {
if ((s & 1) == 0)
unrooted[s] += rooted[s / 2] * (rooted[s / 2] + 1) / 2;
}
 
void main() {
foreach (immutable n; 1 .. nMax + 1) {
tree(0, n, n, 1, 1.BigInt);
n.bicenter;
writeln(n, ": ", unrooted[n]);
}
}
Output:
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
...
247: 748434113260252449609376828666343341456610378512725586135955779939163320693444008584504390382026391947130
248: 2086006351917005252913566124773054331962205157167696706926185063169623907656246841866717933958839366769700
249: 5814271898167303040368103945830220447130073898083466852225709084407144308593691069932064987528870826155297
250: 16206624309085062837751018464745815688226709117091506494175397665527493805947344857313038875654104100026504

Run-time with nMax = 250 is about 3.6 seconds (about twice the Go entry using go1.2).

FreeBASIC[edit]

Translation of: Pascal
Library: GMP
' version 31-12-2016
' compile with: fbc -s console
' uses gmp, translation from pascal
 
#Include Once "gmp.bi"
 
Const As Integer max_n = 500, branch = 4
 
Dim Shared As mpz_ptr rooted(), unrooted(), c()
Dim Shared As mpz_ptr cnt, tmp
 
Sub tree(br As UInteger, n As UInteger, l As UInteger, sum As UInteger, cnt As mpz_ptr)
 
Dim As UInteger b, m
 
For b = br +1 To branch
sum = sum + n
If sum > max_n Then Return
 
' prevent unneeded long math
If (l * 2 >= sum) And (b >= branch) Then Return
 
If b = (br +1) Then
mpz_mul(c(br), rooted(n), cnt)
Else
mpz_add_ui(tmp, rooted(n), b - br -1)
mpz_mul(c(br), c(br), tmp)
mpz_divexact_ui(c(br), c(br), b - br)
End If
 
If l * 2 < sum Then
mpz_add(unrooted(sum), unrooted(sum), c(br))
End If
If b < branch Then
mpz_add(rooted(sum), rooted(sum), c(br))
For m = n -1 To 1 Step -1
tree(b, m, l, sum, c(br))
Next
End If
Next
 
End Sub
 
Sub bicenter(s As UInteger)
If (s And 1) = 1 Then Return
mpz_add_ui(tmp, rooted(s \ 2), 1)
mpz_mul(tmp, rooted(s \ 2), tmp)
mpz_tdiv_q_2exp(tmp, tmp, 1)
mpz_add(unrooted(s), unrooted(s), tmp)
End Sub
 
' ------=< MAIN >=------
 
Dim As UInteger n, sum
Dim As ZString Ptr ans
 
ReDim rooted(max_n), unrooted(max_n)
For n = 0 To max_n
rooted(n) = Allocate(Len(__mpz_struct)) : Mpz_init( rooted(n))
unrooted(n) = Allocate(Len(__mpz_struct)) : Mpz_init(unrooted(n))
Next
For n = 0 To 1
mpz_set_ui( rooted(n), 1)
mpz_set_ui(unrooted(n), 1)
Next
 
ReDim c(branch -1)
For n = 0 To branch -1
c(n) = Allocate(Len(__mpz_struct)) : Mpz_init(c(n))
Next
 
cnt = Allocate(Len(__mpz_struct)) : Mpz_init_set_ui(cnt, 1)
tmp = Allocate(Len(__mpz_struct)) : Mpz_init(tmp)
 
sum = 1
For n = 1 To max_n
tree(0, n, n, sum, cnt)
bicenter(n)
'gmp_printf("%d: %Zd"+Chr(13)+Chr(10), n, unrooted(n))
ans = Mpz_get_str (0, 10, unrooted(n))
Print Using "###: "; n; : Print *ans
Next
 
For n = 0 To max_n
mpz_Clear( rooted(n))
mpz_Clear(unrooted(n))
Next
 
For n = 0 To branch -1
mpz_clear(c(n))
Next
 
mpz_clear(cnt)
mpz_clear(tmp)
 
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
  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
 26: 93839412
 27: 240215803
 28: 617105614
 29: 1590507121
 30: 4111846763
 31: 10660307791
 32: 27711253769
 33: 72214088660
 34: 188626236139
 35: 493782952902
 36: 1295297588128
 37: 3404490780161
 38: 8964747474595
 39: 23647478933969
 40: 62481801147341
 41: 165351455535782
 42: 438242894769226
 43: 1163169707886427
 44: 3091461011836856
 45: 8227162372221203
 46: 21921834086683418
 47: 58481806621987010
 48: 156192366474590639
 49: 417612400765382272
 50: 1117743651746953270
 51: 2994664179967370611
 52: 8031081780535296591
 53: 21557771913572630901
 54: 57919180873148437753
 55: 155745431857549699124
 56: 419149571193411829372
 57: 1128939578361332867936
 58: 3043043571906827182530
 59: 8208615366863753915949
 60: 22158734535770411074184
 61: 59858097847706865855186
 62: 161805725349297357221898
 63: 437671691526158936922623
 64: 1184616185385310843585573
 65: 3208285066181475821271463
 66: 8694130712024868414002815
 67: 23573796134448175745408811
 68: 63955159527348138708694312
 69: 173603007393950249896865875
 70: 471484798515330363034639871
 71: 1281151315764638215613845510
 72: 3482965749140691245110434511
 73: 9473447386804490449091871124
 74: 25779306238954404972323916397
 75: 70183211512214096492433058105
 76: 191156381393249393027319384769
 77: 520874195248906781713044332539
 78: 1419908915343952137338409797325
 79: 3872282575137005474139119076135
 80: 10564476906946675106953415600016
 81: 28833609436277333169440806135431
 82: 78725585464391037293036629979444
 83: 215027809474796675607407513633870
 84: 587531723826577193455385789266377
 85: 1605913778494711520354663202536756
 86: 4391002908093323425994602631972445
 87: 12010257907756938974208750945664835
 88: 32861295558120887536942123568548502
 89: 89940959024891576997396491928932689
 90: 246245150242821439632304475956113295
 91: 674391606297983432514229725117306224
 92: 1847515048012613337782670842346319120
 93: 5062818112121161180862827915688625902
 94: 13877857529584521384324419956411729295
 95: 38051836070803837001309074456088423358
 96: 104363664561059273927704242814298678658
 97: 286312976836850192359345859166390622180
 98: 785684759853087702778573182234297830503
 99: 2156596319845084996862701478402986311496
100: 5921072038125809849884993369103538010139
101: 16260750014333666174953055376699249561110
102: 44667063168726812052821334495766769690630
103: 122726610195426301690448676841677827340780
104: 337281538963751874669853952178948219200633
105: 927143441542280244466720172757699607129825
106: 2549176520305910764377448963173035784835631
107: 7010510656300876673813654064741809461787182
108: 19283877336110239907079044091958051661009951
109: 53055727810105880736027950213934519705620559
110: 146002972524313232817393491844985704938385801
111: 401865724190508834753025926637435418813476039
112: 1106339625432222709435767174129826811545391101
113: 3046369875968510015403046201590835240153395100
114: 8389999420170754836800638580300552381250693062
115: 23111326593011774543116815302964652139347135182
116: 63675155467360117136901070528242608498818046250
117: 175467195960062612437322237574246321515725845634
118: 483616671898832299071277369263305813784565460114
119: 1333167312321418940566764416056977442040495550342
120: 3675740183950426011078357941139728051663026172228
121: 10136322901774027447848977748665383292736169662267
122: 27956983197937526275999613945221497078279509595407
123: 77121096978813982358935411851692069578533009193138
124: 212778592638033483022781655638827961970402357080215
125: 587155794584829621068447884048323985962957796104395
126: 1620497362318232091081355117667505915417499978679013
127: 4473132502312622821884079561929897829404710575328024
128: 12349306792492607803837161096610238756912653878568775
129: 34098849774876383478036291434385545792965491914980650
130: 94167748474814466028838037996326649316233175269577493
131: 260093170948828891650104553710684162327855828421145690
132: 718487205759724277833835055443909476145495116155508155
133: 1985050220521088907210323840127550973214943015739291120
134: 5485110653386099899275645856977233423965042141295771502
135: 15158624968755754576600389921905653584106659889930620820
136: 41898053824932615440265041900412507427220728337249680527
137: 115820822448502452349822520317304132018285539473087897141
138: 320211802888589798701825810680319271475504997973219083170
139: 885411355238188116465394365370757710295372148438998022826
140: 2448550585524918609600214967948504177437555812600018440773
141: 6772180336728084537425567078328320492989943976904644119200
142: 18732796033402227075307540055538834651333956120072379687678
143: 51823958523558404531622255138725304201359354985976024954747
144: 143387634030485523461662580179416231260007790242619239696168
145: 396775836020295064920040342935953476579230225268967120945252
146: 1098070975453594757891511609218085888434254839495604326720679
147: 3039251105982158526063018965393900608357891201531016545453671
148: 8413041613874240075848233530979949485087059914285837491890647
149: 23291051500594069758631194545655502320903778728677961917787017
150: 64487285324785805685734825467573942213924157583096655274158296
151: 178569541961158786360447600422369518262867694211679827307797522
152: 494525085028771691070376002671999818542495469214503552543494392
153: 1369671107847363840368349527801907625890550280754690871159384167
154: 3793941909035282970536126899217159922244816989321008990552343933
155: 10510197366726219419291185594221700080820692107164072063617583537
156: 29118988780427095392911694296588496006042150251385271606702314123
157: 80683801316548713731547508195369620842564695928190934573122040053
158: 223583881196691039626561929582827819978293196688915654006262185620
159: 619638153674192054430980737083649826660231642062541457264064352590
160: 1717428978037773119953669826811378686605009454833429087085211111817
161: 4760601845949152288761851253868434642647478893273231351009713026471
162: 13197353449186709568929592710369551730672357721629256541119049584662
163: 36589226826424289787166608629764201634396432211204018812233928108927
164: 101451975263926040804307438557581821336425438886780992752450611791029
165: 281324901033788598583154170205263556814795889090791609969956549076553
166: 780181677818281299965193432627955631078491817302716837810578348379410
167: 2163828038323756757063639945018570904120396578192324738853110253083851
168: 6001899167570139611127915072874671685163847392112466633395193150607161
169: 16649191065671323727576273232609293462550308875754570697371028619095529
170: 46188686972056579073145176280276791118176099297131728121378351698216964
171: 128149137125681447665302588425507023489080631426025859378879991574150361
172: 355576383032176188837060897590191000068058505378256432541548821711409736
173: 986703913063443346422020725722084251185909113284392827422830038792419867
174: 2738275183964917202164682060710234556685852044781624370789938274187242387
175: 7599818348156354735525837090092498330135165342551619766604085368593605623
176: 21094284799140605474267783653778252494175708547669907184929527663028371844
177: 58554660677719531288883019197284429180673377561888244491058170393359945984
178: 162552183133868639189244204285356619593212307470997836346642760606493409411
179: 451292826786530619879633220482642976940485477290114448603416892241141577694
180: 1253019870825476025726441067676567248038950763298814178748038046446512128926
181: 3479293084378459187212303139960535018989517537846033787292960498791544468857
182: 9661781855977284524013799278118239872342899149756408496918889491272019198160
183: 26832197158239597797570968340612728947891256166650480273266227097169558934791
184: 74522545727244539603451333395337695567614066525612042720018110555143893455632
185: 206990881176753531116559188573370889805581604324744059300494333307748123498957
186: 574971719221297425559348824161112797452658996937464320320048053830834065076638
187: 1597250942564001477500533605167309927398304330031144648098072721512668593957703
188: 4437423571982333312534972159110678450135834859468229274326790786916695731276497
189: 12328758711422329105019389982539560951228986597668702145097956175468519348920309
190: 34256124585721478074980980873512523523896822875906637442595527046990665266761523
191: 95189094589104790904556217884090558824685828617516319665565748564984723369457220
192: 264524521940855272106937702820301986845470010150944446148610489622177560655580196
193: 735146927788110318878638054407335543366855876665936464594690408421993895145574507
194: 2043202995476015462049187462882169976289343296164934404442378707876446055277665852
195: 5679076882963913929265887525377096781591407289261632655627568444557125995319535956
196: 15786016263625679649343179544010857226174369384245579060916786714528288038933116607
197: 43882930188633901470015828734437451959746697520345645823789728504039719238235284266
198: 121996306076853365751053531202168307620916572983606780123661900035869303555630148063
199: 339176261988518728096836182493660862745709169352281541101577697702699073887422989905
200: 943043328799038505167332910595466006794464252841664581909549826351576307818857723954
201: 2622195090600379263364346956264279702121691087227848066895838284611152725976467138514
202: 7291640328972323818932818268921088199080628040707037288217930491456875016135548131376
203: 20277391980621940663950418790370236703345679504035237316723532280155012704421841134349
204: 56393014827755686247101145333945229562531368138401437274854961321951321148392478837326
205: 156842815530515935964014240194651333844507609987619166694876840912879248319077130581042
206: 436244327522179535577207667646065280269833187002466982658692809627210486721781255271000
207: 1213446271931548955557154166653292946893343739485414159573064525913091105471901382363618
208: 3375488708820014134062868343953409434477577207616345786043331438445002602958236463369496
209: 9390265533842684145381903993662706957889355090166833985181893569515242461156430420087174
210: 26124257322713604151166532772505893583948958402141893219135619374261694917895951421995216
211: 72683304203243676344755903584747211387194000236278332965871882088118015556154063840306823
212: 202231949421481999766866699910650758032171534187352358158377153614156835833334273717131223
213: 562715711666310319461011612553561742990998466225938804278692337156743603187662151365368333
214: 1565857565336512188705390960430387447731996020954944548096469264981742312029607101653583428
215: 4357517959671123300838959993742696621943017700847213254885626681813005595459240045099075216
216: 12126894898610872886310565416845280412742023065548437498642351657251934710541687754081654026
217: 33750741717021238734330907104325257824118779361033241504478398185637818043649623474315265399
218: 93937737312335248803818931862078208076074752854934195324106075781489944419493627198038389700
219: 261468709433838684317888993242737209511093586216774554328802510011968600660643442350819036063
220: 727816668798656458204462998706538701005731200304158665308881919140152438032334192310185418095
221: 2026033924729657796058178057776349080819410108838068133330231127278657184350600523917658261950
222: 5640189120704586237460028096950040726608416653216674308167097595939322372553028535058020450921
223: 15702277858615709125768061794209929881772942003228681661684701314937614138722747596565403037124
224: 43717315979005745749656846671283395378656317609179742248155824749456112069949537586095666617258
225: 121721128292306933059993974247348540921262802966704236768446493370986884003643919966941048534839
226: 338922110694788427241777802405838150613492773013920995745534133385509651242705886920398223181010
227: 943745948264384101974654246655344635790924945832998571660171925129987029630345274360528181753602
228: 2628036396188665255122485857407491640837938331141774537726852980481211265329884171692375404118006
229: 7318608979755404166520379853847121693286549981969246032578382667986026415973227568070229589183702
230: 20381982477815712032070175127992226329196107434900428011148438268022423947798435659837662375820784
231: 56765548015352873669830186155391542225154245344836703122834457861735047936794014876150374629860524
232: 158104270172530515145265641139760077405201789758339337585177180751307186891559972317181979411965521
233: 440374885613967273764570923053527071581411261510943039612254074378568326443950283692532685610902647
234: 1226652343389215664746827690619448544313348534138985205724729790807207201280976341202710717893074853
235: 3416963010634291402556279395279280039897379691659516509445008289967225395946292319651344904483142876
236: 9518723877111155596143748502002445531218893550853129590490604506008598318134823819368242604272122748
237: 26517750521770746045881213675376639453619783582926617680386483834380296365299612479395492961088242736
238: 73877802385952947032921713908581985111328188063663582097893741466810319537930797134111900695946616163
239: 205830832103408707745581845015281353687041390648973776794197115951467164317467871635600767010770430175
240: 573490073391076513109930570190363749116344599275683632274375821562743183409191580097184195332209714304
241: 1597939145083038119284545851972427651672212885904578621056479058274066462851925440771984480190480136917
242: 4452595736241139504848505768149348728327738257189209919868237125085182422374731188865584214640572836004
243: 12407515928191678703401447333122259693080851830690277274671393962029357182157422967017478923028296493797
244: 34576004768296889785887066794910718730985852896707505707076422305798138880427343561380451664648670542260
245: 96356944442415066997623733664230869603611716312377642117711752082444867783045964116385053282421589905891
246: 268540209617944059776303921971316267806082307732727328919911735252505071315985779867844056236080213000010
247: 748434113260252449609376828666343341456610378512725586135955779939163320693444008584504390382026391947130
248: 2086006351917005252913566124773054331962205157167696706926185063169623907656246841866717933958839366769700
249: 5814271898167303040368103945830220447130073898083466852225709084407144308593691069932064987528870826155297
250: 16206624309085062837751018464745815688226709117091506494175397665527493805947344857313038875654104100026504
251: 45175937003790110836570547902793926244224423679908111750183970641450850884015931131155869896510573436377669
252: 125932844251389164587464842843820559638763899540510199408003184309130630867218196313865482109056537730398481
253: 351065342330255763232857455169736646100231492324922604469018864206124242515874849723301032460307149363100441
254: 978709648454897177175122229161387383812277957992041737463093257271644176592407853706597679764899372036161233
255: 2728579524947965774924389584178729664141559400119961753692868837602435434199845226128003794876379357316697077
256: 7607396703016294839448365361938795245280010901284162245456747052211826446860068129026466203061153094215518724
257: 21210557506627112926709102814428055407062200441680249553023821619098519349155457094641057751120559709171040766
258: 59140439362561173332419239067243021493683835575971725019164864794611034386190038342974191464909448990949160433
259: 164904810640488270400543694428054069489544003984942619936396942506713662286505814885161827364845226768614358614
260: 459831050079703806398893682379638814715447009656839612265184371710342022860900424760438175669232045681912458051
261: 1282269545669451251495903825012981075351208474904611796782387631860379995597556946571575503111416187201880410644
262: 3575825396849372674227875243103667862184010172899663062411840184180866163260563950451991491936318403482879258621
263: 9972156891686411557328508654295124624639913506842521363764257263308033015597557061627102698432983819442412394838
264: 27811063827636093132667356617123953605179549615375068595807588613293746133844403466327129871126313264974628662807
265: 77564265332280746617483643899828940094749105640853192164718696895612990060307255121145982345803398310187898079392
266: 216332231349983182677166502499939151645373218726526211012542076898269883946723118249478997581133729453560312506066
267: 603387244708899225237309237330610582381466132219204206651989196705483816075205241122264636682375218975924652825723
268: 1683008287833477538339860215212515239936353956160360612774483581234476591477397755553006707152662976687651986820471
269: 4694523362293720915770110468625254606334394674668223296355229413555998319740629081646850706213675263754699054633081
270: 13095188764074847449997295761581235990086284447120964420084615733616254354939466149397793993685871755799835949802912
271: 36529768402903517606384673511136047656882432642972469371446625066352669529799727046128853301739369357159703149780745
272: 101905321192540151862638359736728614554608647415740089819403904415838588146647274739611127649149596882860882722587389
273: 284289935231308453374750088765973199540899741283799909358363233742287775789400140615985324231011233577018262261573605
274: 793123245325306332656455155240700037979451600908118795329947235860752298477617419042698562753980516235445433182899253
275: 2212760132831467572448479267369564903248109841785416455962789880485683556412683401911627301645620036274083564670518082
276: 6173655026597144030316412809287663876433674099262130586459961369609545873586739771264653817548847051334819819267673785
277: 17225214341482211996032609302647305657523857862682844736606106535050865551873299016458209128943795787480117352433192085
278: 48061914342670201573422935228854332433440964678249011765471625586477627885410949735846954120344190850911152111629213202
279: 134107030939622800029603293300903916561747683391063747072730704147537374895733111331174560543849820565430622535700765087
280: 374210510638629940690846658146299050872996272327226981131494408641813084321751382508507907480321412498705157378605184512
281: 1044225435503012203708531726182660970486727267736874255761377919782453611846615819319682114158692224800786189315971278877
282: 2913978259975249383405724359543135914479847534340004256170151623725094458935882014206856559644179292630105188852484942654
283: 8131899511255901661123024274302643005342358280792291668909947468080778066409261184072068071349503993858694564467915250947
284: 22694010896831082150833881059471315166090154920352083471916559708043752042060890804464910281660301317591577341450643643408
285: 63335029821662407792368658364099477321708085419464650722906960844887633330655722051429941743869159345683126460066342502022
286: 176762473380773688334564893776355424385292545126164061340618485071148722461544771780431630578615064360263323717976541381234
287: 493343530262595826525964374079648726397444990904885237605455236919429909498402035512893215123730306166937343830199098906264
288: 1376962107154173493629678201172367360428665626252713512103398076898209747598726288264583330503085546722567594976794377910916
289: 3843329627580641896092936292497953013493677730608250853017184751560504997627908821176789676128330028340434788417374548321665
290: 10727691632324916343855749374736278911611036078629853835188027850311800148076269026969505419892040571311019353938342366479921
291: 29944553492856643003705267171203053740637479757153174554386011341347968315240452765007183277660357717971836148800091968332374
292: 83587671350621452088852077606615169147100357534595837577486058324929087065974679646254472788204214648005248614193318414377024
293: 233334710228304175640537431761015155226516041956764172024879820060328914791790564269514952923849421296827499293644779973947944
294: 651372050316781966807515452385884535330825922949828062262435782904101091097575267639485669941314856354615008764966125315567827
295: 1818408509063580466007837286680677983183200164466347108731791763610863204309478600683111564194332619888539094594355873251409769
296: 5076521961686346652128084504011167440512053731910308671725721188988125758183538040191772757449820238766222803630357752112485124
297: 14172728853081183487692819360642616465697855744649707292748353245040159044544320770757891836594915830996846840829976619821699618
298: 39568810871971230524136981094496991848828417446424705179645229759385730879357244432238970058197255613334159244290428131124452830
299: 110475187771839384048492533823159918390262532886305090937767272270110025203334389240257568860480586164979548476232996728116729683
300: 308452748932356659134640254457496633283824248738866911531511793646459565034445179334045501201901754682633289077084032710062170279
301: 861240824463152722071836109344427337431877614848901867514576156478082914538339062870758774046333091097667962110703879907047902312
302: 2404764529074988740593535159997552717572283601360445481122700282665430064398873396193716880348601148493581071074166478693990790856
303: 6714789670469454153386611562013961023242903621637710232282341992915250322865847054817163511814626619935187437204372380050492741416
304: 18750122030724673491128292527199763297679319101861503773445345726522308044322152662576165962119970647127449975852633174621969880739
305: 52358540776822171397938610797428972138604966642799660183619135856732885313895214904783970369869810500221836523091218317395627621618
306: 146211874171546304848114890907617543441612329368468136490630136290133091812328020942022322642930758562497993998813033035404037543378
307: 408309374766218968874889934904388454292250204332400357496458432386295109182205213667370847008916451504534109623708005838430560375834
308: 1140269692101119225290015431235563792069793485705983470470867840010583946573338083342919032742493114840430853835483727638466969240655
309: 3184470707522086900997866971280896496954514816942511201817116808120545961910541675928058343909676364966063888004625727819620056540601
310: 8893614673793550426203177888486104267711942366176132474668917683523216912995539226525055322211719832653261036678928338242794559299112
311: 24838802846610505668649291989193851484488311070565125269868527227254250892146180700796996471641995241264610499129510168778379797378423
312: 69373601175140878518878407416354675734791611152355756178787188936758881149210187484048705485225593356694870840499748283514606905423246
313: 193762163046096898541813934971517737075188015959344864028603775487737030285826209135941854672715712590577000793283534406527423821603576
314: 541196268484366087460262358027194004033064530954199287174876761416952913147671036693586440799261630163373615316567720548527381195438918
315: 1511651318369444868069381097588803592058478348477392184356035123988931642510796085735141212763489336934853150751083260832206937172777771
316: 4222400314117802395206774109473525042605695338264852324330490813196732243068423992961417072802043842042530256505735344967053794408556908
317: 11794459906262866121871266626258612511077816494044508649944585283517043771401831174632355215381132675014638552720472693257723281462233129
318: 32946365969776950669210980118015393793307352206055398592039144337621666690536830616548580432186809783833682326945726304026143435880100838
319: 92033876907305433205854719644923336617100767023736541909688403892639957967832412603103787416503526220933894910089369504797536063937671030
320: 257097934297469931507121119430597202704570898364889238133318471104541259886397767255481550138719826045933630544145524425190555924302974158
321: 718224246661073548051565677535142499609012941753481223097942887830348917070217610983727147940761519744793793610330362338688442615673197462
322: 2006467255534766659252829163933203490934832421279044800912337935400118444158392493858857751565420235179779642111003320596793004219471322947
323: 5605502679518523143080247371236214990417155138717305546851545955873633006386080207929423558432674748825829901712741304990371774362283193320
324: 15660566253432279506286172779655932839156833825354675435289251721808777572046022488948890326675140567766761094326162530759197028738047873342
325: 43753288739599158009572690177719694499517002167269307889473331175822392011133070749493619973508391450631282964371854365131850614423969032045
326: 122243063487953630168779441726858835845029369553685692636128110535135358236544861593075531121566156537338799874811313621048205453846948646594
327: 341545026553716654296677021076699009557085350341854224151424291838064554557651097172377365249127972138551966103843383352678909134633899780049
328: 954293272184484715061223205140067155456619561299656508883393887930115103078655393909392079957547038845854807951838617028341170549971437113756
329: 2666403386739315827868066185122722123280808213775194857874678398607400719066832564196623913793636277667368621779542858235837144754558689362770
330: 7450404892053082221574739602061345433226079835970620657414429662265437596906083041228826067447081207920786076025248511641195093761018228486117
331: 20818233236540500078078726545737487276469129757876541102703166024191510234936838646279399885038539925967058597219811390519182332350074088483801
332: 58172506428290564368141089289481919244396569391637155592567737523706232298107560669789028286499114696254965115086663396724793700039535105809825
333: 162555450043434528743216203388499100784722341392396045140172843700097191508823985571422968024333740892364547560879635001525731982520443668407207
334: 454250157235286994930516589657219180338096942589294611421361473820956593031171048775282611503529678045566128639300306815980549814735817293632328
335: 1269399644216896674419509697729463047322902302717880576621386334890813629251048864345125927692087232669828899817484051825954105426712749458105719
336: 3547409580555749581428375893211291993132883055153877931717905621147151289844110360051310758575795791014297933394182694793731277677223886505210604
337: 9913657616876180996272994213830886174557219586954823670177585140374478051025004200168094107564237013138944074674000581394701452285244389597956715
338: 27705504250793641201136147317977373743683200591499163219665638173564039350984177869778739763213987393664627300779909086252047370214399911131005215
339: 77429723308686422060745817247773603245179312769655054126749234498755173568276490783876715746154890754203846791494405123875247961686499129038297227
340: 216400771687500406123258313919627031449853827152325829464263282001824129364025389238788652830899867301042402568490706765506227298942393806928108235
341: 604810464516125477241566412882349204137572849071402383810346407708410011599408641489401825943216390533769925718210249763369632034958372608290844206
342: 1690398611265385833597216662397255544989165037053280798937154717423932000388167869168930853825927977852841640076328038923189020256557719193791256028
343: 4724634772968354441296131448066702565819242471972930246064518060636141614755603261379142845848576742911828869261061820791686009759021485237698477831
344: 13205552829661483110364753142284962949107602363850885398784926506038176551941835670483442213970733618691835956778974797080500820139190122943284582135
345: 36910855280499292111957523443882193440612445434176479707767186915266152482973875689799871251737846372737188112909754993522207982690542240926130029049
346: 103171739679545034385009574491036788498270729350913451333950358713843618189620777988883995604632555973833362206978350103925117854467640580483436552018
347: 288387524830070207712762522892988184663566029872195934853726561639393938557865016202521468003680404859295709114570707309431763967645212689873531414264
348: 806122798918603963804489903399570959132892552474576252746348067356487862540352928356904945671326172417576672782142508442928521818059159444295065569351
349: 2253382439271040388149474850917992870398476906210930447444262444269257785111968397614677064122886740776607477106889945148953791648085596979576315110482
350: 6299085778376549624821429179458510900194958604210429834866285306534323334146994999589505103105601742105346495367945462306323190533152968350936328833093
351: 17608769315860492326012526752722740196012949442575558856980140609187722195861145221351750035945476764574248561005920231231717297371258189428413075334925
352: 49225405206515153087568948490481900524317536823931935604937570379534876242330540513362387565765326989735254840166835073173949257982193474194915953803083
353: 137612650518574117451330956726549297191660051390691147866537032385615815835760333658095155505973979232131231656924338282838926211524292823285634711474633
354: 384712355414294702563904729491023243627956319486020537228732734017954863719619385122127616879959104196458802246444742876626069471608782252965968612497198
355: 1075530112808179390071712452176822139103273689672504194433511328424197482887796207661106800366074422776307279191236098858340632644479271310162484217917592
356: 3006890624730903809203348452903910972516333634451058962761600995261350724210387631287122470914299872520878957623017199446857400919899829039177221306594762
357: 8406616889129974244397003491764309398845023627456637599897772061394635091675951085559195087235345860699090644025580860759237281995429915998000191117024816
358: 23503546635376640553461907666151910955199316486853220612258843913181768436558650960045561863244812806343068989021774935699707646736474569067094595172637657
359: 65713412324197507817554740047743479221985390537015377014989484413218559711974382297521939019242021211490372847064568851951672832785537922807500683400249532
360: 183731264265605405843365379086835345824768411971600936222075279683603801778731406834023568040750755069976677442393364831096485389709475423423923842324234989
361: 513712917445044879755632157033905467853325637578640428524826452382229282708618525455937273019555303667710885659176534752548868969162928871024925640927161271
362: 1436369721757738892958929630900072633478136236302452472776025832973978953360582366193284186527643210738556081221865437790061121840459854628616810254345970340
363: 4016245794540314317921944312723698293128035701349480130082040705613877555134606721253578868773247173814885875141129338065351555559857572125255328673559903040
364: 11230072676900921539509513093811870438221223811407353714408100824976815504864394851215848887535311992988055261583243142720576553693459388593499340501967396681
365: 31401691722083002417916521112590305246634105177634870336292298563102470515942642976648214528157455982603109225664757020091550414449178440472115353901460446268
366: 87807512761131019669123968936239187378772472970044116529030740009892838597955402589441089059731825346348183259877624129805446563680453288496566314058216307906
367: 245537829077557462081805831685248187855901611678405068758323753424431585375668081543454789249905741266414098458353610411274351872164493867031138938128923811548
368: 686614878793290692365946544967060402435535533439703386546543223974161565447591982500008138197759562141079983471234903850797409958408513821168604305660233455976
369: 1920065425464977040324811492258229712997831388944954536187026895473557682246017688375844072781501718600065677696568681677877698513717956212078409365696123045631
370: 5369413119739521311056720267346543730592359961974707919525707549927075193415306869557412051089850170504998931658579633249836081815067808652981724838365477410138
371: 15015698655075199976272693540591951974686627178052097189140504117200293380788618682016180014774425725189940423758616707837564049839054439038244580983396016421457
372: 41992541273525656280816728152861921327282968075742417388570730872160514840242297724716590418591898627935767029025045814765426888230438006343622529004355375447430
373: 117437451617808130046188436954085072439890141075163700595649694726378129352031098060028554827004529062795043051505437759166127676602137044028420695202260238129785
374: 328434585854209340800737235202631048479389646967661462661636385280689838843051278282037131977798234542111589298178308943123728279398372661517711552909591088784233
375: 918541776532521351454724481253885522834135226674595847968788334998829497077329738397794713874792704493917411483057346313840275225405419095759541352537427198471361
376: 2568955991329503485226380237480690026457620304891552709544079697736557060175045666781524391372284817097487693711568229673638942005261714904270596319620459445473073
377: 7184922639842464802885587606384993105812537555100932976724521004335615481127788471733279920114210245392313310696302660580629852175413665384841282424990274512998952
378: 20095331213097242826563162272499766152631926335640382078466171436906227170028969073653693324764624153071420218919694803612847629293085720506187191280898163161455459
379: 56205115000964715479430619822300149295636199494967750046285804235705714672057128797682804682319483130603018470221174104272691669435190474297594016851022802881775642
380: 157204173871080042791005946717771678337361252434570214919197069033737233975532054514134984100074728607605448843429503324009721173077600035149528834377866256366868698
381: 439703400811858555207639749643726653558421712817679422805771543513429103622860604933643940150767355269757140263417467587920793699669593550165394733491349240341674306
382: 1229880900617123738697150100582819767140664530048573343103926649877593886795685942716888518384280768195953829891157101302209774951380318232971790780725003756440384976
383: 3440121102632042079574613394421649270740520637604825615393031704257937458096065224440923093918018322351606881630669114742178776088172570978745260713419443230092125550
384: 9622586153410285880728601242215813228736953178547030205700671938265580922941045790964674136785441869346080134382440299672770112153048801535047402111613597150233137802
385: 26916417073868835612084046395717066429589754342172599151445996645973182853695742811985385571104615280559324692412532184104060944969040374899401596525144276063496606951
386: 75292205017596473959671194546459881939425223139193528761923230931282225448658395453816549305362589894258565077274255739531780576422930761591566614827365864785744388371
387: 210615374773386578684517006047492496179433849760360062115309171505982400240424567645729377980367191880450044703844070448199457434424447733296596271409138799278813628792
388: 589165593539042565026821664726253771125102392942799570084371611237980668383862899518543972291941987174860430622620845291051584358900044292209062952024279357217152693785
389: 1648131634367803359707937524405442419859146581867717423163925363504695800177924017679629258999831406080436972262726185670821749962455879487957060784659258524546455581229
390: 4610559064987066414427050590937762145598052261340165536440498484715451027309887206327522221902752378407014621350941505017043523362673050032523032661992076158518536005778
391: 12898001529190616022484918680061560268661536583969359034337027007145503209652354449213917560064014207287702364662015373426938255345873775474502731101617752214575992285418
392: 36082644620996153148038727193256245008320497097861657913961729581140014845827188376920642954902439230587657766314154785765478870307888754802107259886317826893553106804930
393: 100944198599027248783600823572294966728098367736287563685025750028398559174509674211748882662296187357779753297978614667703646499577995198827952979877028011286861153332753
394: 282404360855276282716306438076203561991927984814874123615833082419342075073300818298143667783619353700203041664950921219404793198597337805332599891804349037634418093688990
395: 790075196968580287113310427568508296534767777989983578958455239841484146867900273312870931943399650187650384519148343602398017385028135462146727009392677651724149009203100
396: 2210407864644557643077943428130036115120005355005863034693962386953303913777130833664505916356588804136917108572166425275703362600247757560627546883653191701356713724881730
397: 6184197213841155963141186936830050316876429270782960114608113611454443113269768822881621431873473199159722369366346768263832565030241083004062489507422442039877756049941418
398: 17302192284358750361786474763512039709932246415093507793264284194707998216570204017598123722561533418066238564079099555280757068590210544190267158733975378120143529011121869
399: 48408964478720606842334516835456503133891009741876761610509930173984048922536882285498454923654304602541207830033885488966200458238451441698474624088789395574264007093221536
400: 135443220636981399994430263118955670404849053743512266219798964274651348636218951062787429358223371361277791236256039812270730583793196129114199348221358274867143490557738328
401: 378961890510224587569566655998411842677134297089260038876458238638229055545809515163409480094842115984755225020882928808762277385061107246292620066217371335189839256602213303
402: 1060328799527796787222598339931167000208396813370163594230643943947688583463969446349509310574226512421543474171708182414556560544006657534805443950509050237412103119784241027
403: 2966827500438017966196272821500751701435193621918452681834143840775808934808121748954280576329936166909795819651139559023393628300372149591807874889041382961414276711325083127
404: 8301388147622077303436735958992004021517158912757903546117814861761961286642212993601204978952566450658646412745606842787680318691545681444075901779595216670171932018840156290
405: 23228212920137197019820942610285680773369010452318432585529759033889251185186142910113032696833229809848463162415175535690697164862784647828492646710089206718128497417272167609
406: 64996129638352050440843829288503357383792368058408672417856862732213424091459654085381278596306204367057157588435899771537285442289030753397438750907636378942119087740428995934
407: 181871974514312058787407127315167850202573331626084538673515841562617666603022499256980441524696015460880522623759189784104442385498077959208069046099122778846279941296315607302
408: 508921293889379994459075220441095072936705411037429540662998519808455715649194294354896777470062777665283379251730640643916798271769311972019715142166777508673057182083075439429
409: 1424104919704551370931120477105438945719198975965445860802160045382994308137848033344213193904080353659290651799550995830635165912211281014281176050241988912974508156576930123512
410: 3985105674119379719613473023083433865228342356444696693071449237116824150440441252010348086703299231235101479003372267346695772139029905436276139550454159690445853915134601601269
411: 11151779080187371481231992741401770017872829181149322195705476953287512469455988910839841754572894650021155474376091541134246064933106710984356510400939913969212295793471876146513
412: 31207206938926983067147727221154068167887772255436498988153083289901842635719116116280127591607768984050467628939465309028297107637008697100529834548888032231317887477485172806549
413: 87331725585020938619559624374688440661539803993897909449937112117444074793842275272099711088488653448295819463702914281156863262753493080365544876458417287285003055222824879720780
414: 244396818627923436543044509131904409206923721658156467500754855205934102852186813605522163506104956675950752865215720967269303856285927832484052980180273374327953434476871534413540
415: 683951632694543479102158116853589042884967771893064113437642546713263835724926513576081730012152709764140453678491826677943135992928873094071770203921417873849946088253924179804024
416: 1914086401803157252525483121260321559895559007042220486892482735818107970890133725779443699914357933292788488572628644415573014078298882567354892604501998174591627421637960341350958
417: 5356781843212895081358358702304209294802606675851666570503291583110817229110401297205001248101478494597923305522097774360666328503358045010812965713936587323544536405180531722405525
418: 14991760191098191810138884758572381033980177285519522538002929720069303179039888962564813158684732183212164813120008802003727947967332417301966653502367744259640522679982074240052935
419: 41957297583977073983702363775537276063667525934586084972566377077897379234326941152252308316248314022743475105166365682125455479385328973837826717926371342135100033396024998999711450
420: 117427164649003110142152852039309150271542231005840042633270394358905870024111027811834168760888092684365398533085841898319052996537137409148600044897766758306959422263805041815035065
421: 328651634923820753593213641391615586245769269329135515410723721158590485927853206438291653675705669829844447752566275324876757760795171712027718243095981609198053940152414671545372503
422: 919833338235055417852315527855320952122258706367356027362166805853019201858886407226970738663262056708085068659591296530831817876141948320695715907387734534780390267081213097851623926
423: 2574474487646626632539287026800786404743596827905521895518376238428706085102089551200246220070600149447218837788218132341157680996167476365296697212327216000519534723950623014052562902
424: 7205665667592596185493148013569520321002783567886505195373190949113985058687961485034757755359307774339390881649408647759537333207108232331072998897954029570557671512417161804939366569
425: 20168131434027562204440255506283465875389862304407698539108424209996440684182389196069743314657438655440573946315154127658616978643901056314906869018127846612726971718400035968749166018
426: 56449906899724942047505771637510301180460568010641046003667211377067455974036122730947794173621469883426661320310970747156632955969753852875150630047276376711346998907743979302070281313
427: 158003526673335268129040271181964695519126921278889669906317219204139766887778977957695566072127968587031601234293405692668000075925616270225572854068950838825908224968159082404106015134
428: 442258599979431848391406555229855427518506100942056562122348962514620862303367256139977453548852488681085930719342224041746947531262397172450943200613952242630186401056685133695906260262
429: 1237917552017093850402076044531591942827017686420656648424109421790021634509829111059302648772027906040585297174304126581227216116155207043835665782778612934737290712605195133819856519062
430: 3465078315972343860372538551750530713497922627051904533821996681217921800615373684000895297305178899415702486014119749497882204026757269809006284940463844540137465373894929009654720484680
431: 9699297080453775101320815109284416331144463935663258526967517831954608850816900683813652316638254077050209765141440151807366826086817206175181202087389875138340309965367763865501728571109
432: 27150217551505555618139537163164507176039939439429688302804853725238852409340703442794977612087713364134687732101666077061039800269026733239438258751217609444333185068116914514760083583780
433: 75999753676480301561140909251306512576996597581717224239482078114539914122206191832267711131022981716019615815229050502247271178827064651941512819446443447663567423910119154532928248808854
434: 212743768078542227974107793959413118191783320144200906112511129901557100484433846711030090775414576479874753603565609429366122326437075693794662936485348777801553548537159522792800204843077
435: 595534978287274129557815478890999237342639631710933231600443338243697446238420359116221055705407530695255255797186958373488510376088399011097968679804635823714838510606176210103312556282938
436: 1667106866993012009738048724203648847789357812909740555893815853100209249219093911697525171181338358328434883594238370290309396230294400217639471162139187473094991023670935960149228884691264
437: 4666865864249353281320078704012934753401737086940708686290046970355274011817607310211442075126178184544907153856841831290286920471585179851032823312901592316896275923306636633382050404951318
438: 13064502691465503331496979509263442199242430738722467485716986907489389337535512987298869418780872092794140927836899073572169176570423540838225780325840405386914224765197775158869935886132308
439: 36573464941519815016993284926389744686128467599198825108604334301587908700991438757799778776379591537809204577303961211834736897473197458725391425399805708258283780845803472483724829308499158
440: 102387034801847643405549008400637176298875981552734149229523842867835664065407550598592377192075769357488060245677070395752593729565915415641269251338499244754054356422434373991804100339787288
441: 286635141072427375498100476108163220382497481938821125132296034922046116539400243866662134416523721753392885500770428866803135350327729311308050639964324664322524296915872303049333243233063371
442: 802452776642802578771773060767748719046097561968169463921460704294540054428227580569740903358514433024200099533415098775392933614644896726285044148154823247614097647187673554735715744773826614
443: 2246544849619415890258046612371209088300865211635814214012511886660980184034972215928128019202338157078347229971946501155993356014249699956150589573685977100473895831208624097115475682140515410
444: 6289501649225784392780503335689658729084771488077509996429501874287761786523941153941168420274740516150624301548765385965904919326602368831112994391151449282648235334602397423236251123942812603
445: 17608521245602370453309358197667918453324808965805288184007046857140536249633776335160636757151758073188473361111351872831488595346484114648956040900886318197179158362694883652268082653203960816
446: 49298649182829931269442452247690970866951223239512451041034523083646912273059667920120855544709087163739440794611655242580540001201556277145529735532921198512078831709982004835590545821624721675
447: 138023365283501643172120627032301339872263876888267855443343545360854901718497319204396943648334875257424762335797402282634187852240627591890657376377438728045938810213212753434013616337639224457
448: 386434274916820923522164046982004407665830730281302875549681979670777226707924140937512220519082444542354857967666896287766781877598555642605938623019886223086785663905707716066803911411286281397
449: 1081942241041412843342801306377314128938595941226709615758725246447576837849605915025482480987589675194623011793741932438474589622478261973242320151519896247629605039690847316507789418134456637827
450: 3029269417768609765160337407124200015486163814552893282843251090687250165489257362547243817113569645233746058477828167223523132762950235399572506835312237226277164203152272356102034536019296391294
451: 8481586318311385288734521192920868467270039534541723644192388612007264998860540345100785093887970292666153225114424664452217056046138876059684378649482048761623829799322843406423777308533920219070
452: 23747703106104423014325258140304375732684986550090578217405234480462667752274794237666234812462575613551700288282266872421292080146767531632383820729064228671469763885872280565208337751080593344999
453: 66492314454280637134764294178457217478862139513263475578987547070484513744890443746487888749907918088417362565230487121854504280334021532192009371637336497822869058055985634663088967547878217120969
454: 186177237041880167250082703615615906711469226006628683330015454509577099494801180033125853930416036475328346558339575481998626950999321652099880573706898734989028639251899999393194339425694454345799
455: 521299105693071721134346815801917273478090598105738978325617213178721952761963650686896186419028455325103010511113187858174012474240131297963986633948841343459701163951657791742336745183846908202693
456: 1459663082035342934887882781425257110248409976092170592292687001118353543510903639012142254926129620397281644788427969861856196397265614060708111086420781518554356664201230646799774368796497847289560
457: 4087177417055441441926038522636669779632975383455435861702787829487050730647644274243796689359039880995184808595150267791772426267267595216466519189659062251522097218459884984685292035892709537318312
458: 11444571992533113663092437880990068860482429953863778311744000646149153383578777138577579451370599464607353224136647353149403241554028448524921382528775644679190951320692142995225920894358581518868864
459: 32046514239119535874557007189938336657555337609334578424470303607436424413038337983768254880878690416363200099465227596231806443533600106180349076033054441534432099244612976407280044552076098821403252
460: 89736100519002389851198827841205289488930608401833288837431558806157207068707865857431660194968325536326825922036661750485787248488069036537183719134777585007115406330216099105020965250968921230637531
461: 251280461467296852385574630546574386900308754696924319255811421905696343777953369172240361971576177698693495120548775396582903158268833375865317152528104410678373354372825259596648414461025206277196061
462: 703647838584625032634850730660409028130392079000514964449801824100171552697792694225173476450892173048712804817684375485123450329584457100326311770211425495950916098573065500347826314334095474713560259
463: 1970412174922793351898662531323302254183616229126007272286170131156249546380113862126766843599077305606654555049456355906721272812241518709542011017045667578674276027112987044616906273148370712324325362
464: 5517773536559450183232340514258026490011471945680485508559372110766683981404048596720627842140536666240121637533493171755062890606815893185673601104533408355167110373867915820214842211744851723397569593
465: 15451679990201568411215578122073370356403742496527885209833637937700223637979907251807600646374760670954350341779571360161674730998882159817422440392907738425891277795466982145716585006689968425505380119
466: 43270564429340265025283937524300878478501493530381291220397194282241171515447134894215109317300783342867417360199432997982875302235206383259387444427698315762380570352312116615363155703009920832689352871
467: 121175387073295736524569718822097639420463861716971063492109528962492569785076732921975740253331081548338333727361459218154437136082325290987001985839144830920858486257553315470385995502530184051873497066
468: 339344840189475536421125940700761759628752222992160549381027643941745741914656836040232730595608192347759637830477587902350052606592456881569785539786928879480686510907084881467566111373965693128772815168
469: 950326942647405347844160146627862711768881566137164131522937150987646591788240557198082994780294550892371568822419949180800659521354470469743632592095655784774066429590870707610663947413928541377601304331
470: 2661397660073852552129723028095885797019532580891659413666656327685520361494990644244780459416494337505306325842984790687846760034636266016838667025621454787635756967010007792781115241634931034023342955909
471: 7453348271319000807792642584688862626586099412065267712592599510401797049893846344817387925831913586906215688069450852737050111320975144949815225427831362617279252934288022295734101068785815612716970311808
472: 20873628693465442369994091580260968702372775440196031927070687104083645990021388958800099647202094094135845379561614782887105082175039614621895682762293655052254837096492726532427207985365110705700858185105
473: 58458728731766254613260704634770549014535819580818340519042652762258547931670198980355298780573863556078114808742211556195563024034089763095349562343593909106562326371091563375170455486291957378525618197831
474: 163721469153385637408150476563293561192630360744595190990592087993468898713335977248677815933276982928116057236035906891546690927202148725585574081941714037659737484743937984394080547704511778110792121687207
475: 458528920077354685502169678831532604357019434399108847894808896709351443638466718242161166503349046639203448149470195902534259098807880444564985003619318026651644088082419427990684019605853227416774184858732
476: 1284199937356117010353036111976291463604172133918493472823892597653505936748633559438891259654067719601811837856803850228207178704881159679844950373205860758636370584332260625151603176391842907361800288702852
477: 3596692826870076496488870100810883119867190535450061805109321868771960959615817567820544952252639528684637338431882866065151676205653648613261366208363844491931760159185397360397157081159998934076146625574324
478: 10073463693660743814830768135279278537079909784776055480865370746882390281411517464342747341359496246287190961417525136257220264919874937072794203921533179745349010643055354298890387265997799866799848104338235
479: 28213635719632829111553766945298618684025617913525005700531345253000364443673781640156844004227127409788826310407619909467100939134351426418260762969996556114029193750675871742395710571704344996337919334627311
480: 79021272029812529198306048278738451404456552316178623835088343424900929896529145986849511125817498577910188475147844537607285370369164399968397118901967107253074866629088624713978766067247085915460907203507916
481: 221326640007559663668965755167218010334237161338270139368837726672890339102089097625270467903768037212482685022578414146878493502591843464527824997936161209273201301931996307060804297022524160462260698613537211
482: 619909167426938833226794412160056195934133884103637737354763534557844211624630276625508115154691754605800841672755247108234248396654245317254494351293449688401442053466436766136865155607831934082917347856426393
483: 1736309336940064055314375159645968597229131182622025720281597392750374289881332068277426029158100061555043458510124867482152338705144101468366800180174515094346512495259376551669075968372524272389756751432854853
484: 4863297048468267534636166312939910470952766062828082277824505171156300282060030581670231761463878726184462085106767555905935986480934403918197493275089839501765798644464700331235805831873720464298566133914310111
485: 13621945190301700706138963992367401939405566877527256386624696446539344800813487799938840805754463459615136581585117531096761299146137690070987761802590544736755857013785633546389925702052333218769869982790548052
486: 38155054329515229613775470033224877184200699251781861664268079502676128352861614648198071275587050390975562955844380056803299861976593575165303651531182196565505294625797093250325990896145553936059099182468469941
487: 106873398849478133039914184580874875231786272245238762673187219575665471269978868235613615591616484938408255629005435265191765938106429802557895876693594503003511545832633156383000727183561568902367863186683667386
488: 299358603826075402277899963139952216438074968330347955827805421649062237131327956205363209204249356420478800321507971357294900909553107391222810893361186943113207800413096895718566298784120554090436875783734064658
489: 838529657705833034226462835006399865426986819335499347214210855084885678859732280609017110745548560768471886696342486720814635172359590192655917206826346091436208169907230087809358382454265923070116812677298151128
490: 2348819542369503943745770103735793608241357602923831591641116837956213501074463807697474203912578951142821017553783252607800118192578200768970029556421579893140989343065980349644833804994551495825731452145526250765
491: 6579386479996359380652505811548331172430892668901276541544233471990370985480393191871721148991766536717220264862961217017435585211918629713359048858315079558167250616463096722818683439439764375707901662500150442223
492: 18430013297106462705563823748850922689996624541574571380773518214465413984005545896077127791090690118569929503235833070046114981151702312880527866333379163449235952921156068688050620988293428148558907616760764230182
493: 51626226783162901884788448815927116139784145435568714116360575592327600891647514042914267976366137939193067990947983679977241677448127920019074746593823496272420143919124413908756022387549336194531782497745210053318
494: 144617080122147701980280207133464988259100003413798968327225643978306456666956314890639498978440890457630421021855428539194342433864427806316257734937387813993364347367110868522308183407058843998076264751693102167102
495: 405110259662180001404402330891745929672485944541334128902338780325351363683988833428262927776387719886899607701108769883875334759722976317523430427909747225193367590120906316894975981073694814441448542441371959370139
496: 1134831355904717012865001274054429116248775025280754969468716824949667862347555347996290225366000942364709536217262581087333644261895222727600153755613494310524232705702001879535164138079533205048872360533370572443014
497: 3179024139613983878848518783709510209263571759925674510120249336292840845927230735400333746765269611853557998210338782704187073085423815480824362906609395745543530469335794431219957388926521344251394881172155468218720
498: 8905549466780876642396073343654258905917693028466999354614122414334803973053490695667380301725459866905052509157458138657523790806693604983304945043446074074823147488033014740909049433466213254508146498309733349188106
499: 24947785035695184159749164581713850084342937257706468262391560672422449715753806019752051214121544475469837920461991186908900888093113539339801359611535867899901287200789925164011521414091897974716359811774035382416687
500: 69888806977968318652007568872323509883145559195919337637376568556764896550639165374194198834566064897188044072953504164443147167221896769574954040005634802439024034052447587053721967608928388404735140565376686372508743

Go[edit]

Translation of: C
package main
 
import (
"fmt"
"math/big"
)
 
const branches = 4
const nMax = 500
 
var rooted, unrooted [nMax + 1]big.Int
var c [branches]big.Int
var tmp = new(big.Int)
var one = big.NewInt(1)
 
func tree(br, n, l, sum int, cnt *big.Int) {
for b := br + 1; b <= branches; b++ {
sum += n
if sum > nMax {
return
}
if l*2 >= sum && b >= branches {
return
}
if b == br+1 {
c[br].Mul(&rooted[n], cnt)
} else {
tmp.Add(&rooted[n], tmp.SetInt64(int64(b-br-1)))
c[br].Mul(&c[br], tmp)
c[br].Div(&c[br], tmp.SetInt64(int64(b-br)))
}
if l*2 < sum {
unrooted[sum].Add(&unrooted[sum], &c[br])
}
if b < branches {
rooted[sum].Add(&rooted[sum], &c[br])
}
for m := n - 1; m > 0; m-- {
tree(b, m, l, sum, &c[br])
}
}
}
 
func bicenter(s int) {
if s&1 == 0 {
tmp.Rsh(tmp.Mul(&rooted[s/2], tmp.Add(&rooted[s/2], one)), 1)
unrooted[s].Add(&unrooted[s], tmp)
}
}
 
func main() {
rooted[0].SetInt64(1)
rooted[1].SetInt64(1)
unrooted[0].SetInt64(1)
unrooted[1].SetInt64(1)
for n := 1; n <= nMax; n++ {
tree(0, n, n, 1, big.NewInt(1))
bicenter(n)
fmt.Printf("%d: %d\n", n, &unrooted[n])
}
}

Output: (trimmed)

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
26: 93839412
27: 240215803
28: 617105614
29: 1590507121
30: 4111846763
31: 10660307791
32: 27711253769
33: 72214088660
34: 188626236139
35: 493782952902
...
499: 2494778503569518415974916458171385008434293725770646826239156067
242244971575380601975205121412154447546983792046199118690890088809311
353933980135961153586789990128720078992516401152141409189797471635981
1774035382416687
500: 6988880697796831865200756887232350988314555919591933763737656855
676489655063916537419419883456606489718804407295350416444314716722189
676957495404000563480243902403405244758705372196760892838840473514056
5376686372508743

Haskell[edit]

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

-- polynomial utils
a `nmul` n = map (*n) a
a `ndiv` n = map (`div` n) a
 
instance (Integral a) => Num [a] where
(+) = zipWith (+)
negate = map negate
a * b = foldr f undefined b where
f x z = (a `nmul` x) + (0 : z)
abs _ = undefined
signum _ = undefined
fromInteger n = fromInteger n : repeat 0
 
-- replace x in polynomial with x^n
repl a n = concatMap (: replicate (n-1) 0) a
 
-- S2: (a^2 + b)/2
cycleIndexS2 a b = (a*a + b)`ndiv` 2
 
-- S4: (a^4 + 6 a^2 b + 8 a c + 3 b^2 + 6 d) / 24
cycleIndexS4 a b c d = ((a ^ 4) +
(a ^ 2 * b) `nmul` 6 +
(a * c) `nmul` 8 +
(b ^ 2) `nmul` 3 +
d `nmul` 6) `ndiv` 24
 
 
a598 = x1
-- A000598: A(x) = 1 + (1/6)*x*(A(x)^3 + 3*A(x)*A(x^2) + 2*A(x^3))
x1 = 1 : ((x1^3) + ((x2*x1)`nmul` 3) + (x3`nmul`2)) `ndiv` 6
x2 = x1`repl`2
x3 = x1`repl`3
x4 = x1`repl`4
 
-- A000678 = x CycleIndex(S4, A000598(x))
a678 = 0 : cycleIndexS4 x1 x2 x3 x4
 
-- A000599 = CycleIndex(S2, A000598(x) - 1)
a599 = cycleIndexS2 (0 : tail x1) (0 : tail x2)
 
-- A000602 = A000678(x) - A000599(x) + A000599(x^2)
a602 = a678 - a599 + x2
 
main = mapM_ print $ take 200 $ zip [0 ..] a602

Counting trees with some fairly primitive caching:

import Data.Array
 
choose :: Integer -> Int -> Integer
choose m k = let kk = toInteger k in (product [m..m+kk-1]) `div` (product [1..kk])
 
max_branches = 4
max_nodes = 200
 
bcache = listArray (0, max_nodes)
[sum[rcache!n!b!r | r <- [0..n], b <- [0..max_branches-1]] | n <- [0..max_nodes]]
build_block = (bcache !)
 
rcache = listArray (0,max_nodes) [arr_b i | i <- [0..max_nodes]] where
arr_b n = listArray(0,max_branches) [arr_r b n | b <- [0..max_branches]]
arr_r b n = listArray(0,n) [rooted n b r | r <- [0..n]]
 
rooted 1 0 0 = 1
rooted 1 _ _ = 0
rooted _ 0 _ = 0
rooted _ _ 0 = 0
rooted n b r
| (n <= b) || (n <= r) = 0
| otherwise = sum [(firsts b1) * (rests b1) | b1 <- [1..b], r * b1 < n] where
firsts = choose (build_block r)
rests bb = sum [rcache!(n-r*bb)!(b - bb)!r1 | r1 <- [0..r-1], r1 < (n-r*bb)]
 
unrooted n = unicenter + bycenter where
unicenter = sum [ rcache!n!b!r | b <- [0..max_branches], r <-[0..n], r * 2 < n]
bycenter| odd n = 0
| otherwise = x * (x + 1) `div` 2 where x = build_block (n `div` 2)
 
main = mapM_ print $ map (\x->(x, unrooted x)) [1..max_nodes]
Output:
(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)
...
(199,339176261988518728096836182493660862745709169352281541101577697702699073887422989905)
(200,943043328799038505167332910595466006794464252841664581909549826351576307818857723954)

J[edit]

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

part3=: ;@((<@([(],.(-+/"1))],.][email protected](]-~1+<[email protected]:@-))"0 [email protected]>:@<[email protected]%&3))
 
part4=: 3 :0
ij=.; (,.][email protected]:(]-~1+[:<.3%~y-]))&.> i.1+<.y%4
(,.y - +/"1) ; (<@(],"1 0 <[email protected]:@(y-[) (] + [email protected]>:@-) {:@] >. (>.-:y)-[)~+/)"1 ij
)
 
c0=: */@:{
c1=: 13 :'(*-:@(*>:))/y{~}:x'
c2=: 13 :'(*-:@(*>:))~/y{~}.x'
c3=: 13 :'3!2+y{~{.x'
 
radGenN=: [:;[:(],[:+/c0`c1`c2`[email protected](#[email protected](}.=}:)@[)"1)&.>/(<1x),~part3&.>@ [email protected]
 
bcpGenN=: [: , 0 ,.~ -:@(*>:)@({~i.)
 
c11=: 13 :'*/(y{~0 1{x), -:(*>:)y{~{:x'
c12=: 13 :'*/(y{~0 3{x), -:(*>:)y{~2{x'
c13=: 13 :'*/(y{~{.x) , 3!2+ y{~{: x'
c14=: 13 :'*/(y{~_2{.x), -:(*>:)y{~{.x'
c15=: 13 :'*/ -:(*>:) y{~0 3{x'
c16=: 13 :'*/(y{~{:x) , 3!2+ y{~{. x'
c17=: 13 :'4!3+y{~{.x'
 
cassl=: c0`c11`c12`c13`c14`c15`c16`c17
 
ccpGenN=: 4 :0
if. 0=y do. i.0 return. end.
y{.2({.,0,}.) 0,+/@:(x [email protected](#[email protected](}.=}:)@[)"1~[)@:part4"0 [1-.~i.y-1
)
 
NofParaff=: {. radGenN ((ccpGenN +:) + bcpGenN ) 2&|+<[email protected]:

Output:

   6 6 $ NofParaff 36
1 1 1 1 2 3
5 9 18 35 75 159
355 802 1858 4347 10359 24894
60523 148284 366319 910726 2278658 5731580
14490245 36797588 93839412 240215803 617105614 1590507121
4111846763 10660307791 27711253769 72214088660 188626236139 493782952902

Java[edit]

Translation of C via Go and D

import java.math.BigInteger;
import java.util.Arrays;
 
class Test {
final static int nMax = 250;
final static int nBranches = 4;
 
static BigInteger[] rooted = new BigInteger[nMax + 1];
static BigInteger[] unrooted = new BigInteger[nMax + 1];
static BigInteger[] c = new BigInteger[nBranches];
 
static void tree(int br, int n, int l, int inSum, BigInteger cnt) {
int sum = inSum;
for (int b = br + 1; b <= nBranches; b++) {
sum += n;
 
if (sum > nMax || (l * 2 >= sum && b >= nBranches))
return;
 
BigInteger tmp = rooted[n];
if (b == br + 1) {
c[br] = tmp.multiply(cnt);
} else {
c[br] = c[br].multiply(tmp.add(BigInteger.valueOf(b - br - 1)));
c[br] = c[br].divide(BigInteger.valueOf(b - br));
}
 
if (l * 2 < sum)
unrooted[sum] = unrooted[sum].add(c[br]);
 
if (b < nBranches)
rooted[sum] = rooted[sum].add(c[br]);
 
for (int m = n - 1; m > 0; m--)
tree(b, m, l, sum, c[br]);
}
}
 
static void bicenter(int s) {
if ((s & 1) == 0) {
BigInteger tmp = rooted[s / 2];
tmp = tmp.add(BigInteger.ONE).multiply(rooted[s / 2]);
unrooted[s] = unrooted[s].add(tmp.shiftRight(1));
}
}
 
public static void main(String[] args) {
Arrays.fill(rooted, BigInteger.ZERO);
Arrays.fill(unrooted, BigInteger.ZERO);
rooted[0] = rooted[1] = BigInteger.ONE;
unrooted[0] = unrooted[1] = BigInteger.ONE;
 
for (int n = 1; n <= nMax; n++) {
tree(0, n, n, 1, BigInteger.ONE);
bicenter(n);
System.out.printf("%d: %s%n", n, unrooted[n]);
}
}
}
1: 1
2: 1
3: 1
4: 2
5: 3
6: 5
7: 9
8: 18
9: 35
10: 75
(...)
248: 2086006351917005252913566124773054331962205157167696706926185063169623907656246841866717933958839366769700
249: 5814271898167303040368103945830220447130073898083466852225709084407144308593691069932064987528870826155297
250: 16206624309085062837751018464745815688226709117091506494175397665527493805947344857313038875654104100026504

jq[edit]

Works with: jq version 1.4

The following version is based on the C/python/ruby implementations.

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 MAX_N: 500;  # imprecision begins at 46
def BRANCH: 4;
 
# state: [unrooted, ra]
# tree(br; n; l; sum; cnt) where initially: l=n, sum=1 and cnt=1
def tree(br; n; l; sum; cnt):
 
# The inner function is used to implement the range(b+1; BRANCH) loop
# as there are early exits.
# On completion, _tree returns [unrooted, ra]
def _tree: # state [ (b, c, sum), (unrooted, ra)]
if length != 5 then error("_tree input has length \(length)") else . end
| .[0] as $b | .[1] as $c | .[2] as $sum | .[3] as $unrooted | .[4] as $ra
| if $b > BRANCH then [$unrooted, $ra]
else
($sum + n) as $sum
| if $sum >= MAX_N or
# prevent unneeded long math
( l * 2 >= $sum and $b >= BRANCH) then [$unrooted, $ra] # return
else (if $b == br + 1 then $ra[n] * cnt
else ($c * ($ra[n] + (($b - br - 1)))) / ($b - br) | floor
end) as $c
| (if l * 2 < $sum then ($unrooted | .[$sum] += $c)
else $unrooted end) as $unrooted
| if $b >= BRANCH then [$b+1, $c, $sum, $unrooted, $ra] | _tree # next
else [$unrooted, ($ra | .[$sum] += $c) ]
| reduce range(1; n) as $m (.; tree($b; $m; l; $sum; $c))
| ([$b + 1, $c, $sum] + .) | _tree
end
end
end
 ;
 
# start by incrementing b, and prepending values for (b,c,sum)
([br+1, cnt, sum] + .) | _tree
;
 
# input and output: [unrooted, ra]
def bicenter(s):
if s % 2 == 1 then .
else
.[1][s / 2] as $aux
| .[0][s] += ($aux * ($aux + 1)) / 2 # 2 divides odd*even
end
;
 
def array(n;init): [][n-1] = init | map(init);
 
def ra: array( MAX_N; 0) | .[0] = 1 | .[1] = 1;
 
def unrooted: ra;
 
# See below for a simpler implementation using "foreach"
def paraffins:
# range(1; MAX_N)
def _paraffins(n):
if n >= MAX_N then empty
else tree(0; n; n; 1; 1) | bicenter(n)
| [n, .[0][n]], # output
_paraffins(n+1)
end;
[unrooted, ra] | _paraffins(1)
;
 
paraffins

Output (trimmed):

$ jq -M -n -c -f paraffins.jq
[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]
[26,93839412]
[27,240215803]
[28,617105614]
[29,1590507121]
[30,4111846763]
[31,10660307791]
[32,27711253769]
[33,72214088660]
[34,188626236139]
[35,493782952902]
[36,1295297588128]
[37,3404490780161]
[38,8964747474595]
[39,23647478933969]
[40,62481801147341]
[41,165351455535782]
[42,438242894769226]
[43,1163169707886427]
[44,3091461011836856]
[45,8227162372221203]
# The above answer for 45 is the last precisely correct answer -- floating point approximations hereon:
...
[100,5.921072038125814e+39]
...
[499,2.4947785035695037e+217]

Using foreach[edit]

Works with: jq version >1.4

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

def paraffins:
foreach range(1; MAX_N) as $n
( [unrooted, ra];
tree(0; $n; $n; 1; 1) | bicenter($n);
[$n, .[0][$n]]
)
;

Kotlin[edit]

Translation of: Java
// version 1.1.4-3
 
import java.math.BigInteger
 
const val MAX_N = 250
const val BRANCHES = 4
 
val rooted = Array(MAX_N + 1) { if (it < 2) BigInteger.ONE else BigInteger.ZERO }
val unrooted = Array(MAX_N + 1) { if (it < 2) BigInteger.ONE else BigInteger.ZERO }
val c = Array(BRANCHES) { BigInteger.ZERO }
 
fun tree(br: Int, n: Int, l: Int, s: Int, cnt: BigInteger) {
var sum = s
for (b in (br + 1)..BRANCHES) {
sum += n
if (sum > MAX_N || (l * 2 >= sum && b >= BRANCHES)) return
 
var tmp = rooted[n]
if (b == br + 1) {
c[br] = tmp * cnt
}
else {
val diff = (b - br).toLong()
c[br] *= tmp + BigInteger.valueOf(diff - 1L)
c[br] /= BigInteger.valueOf(diff)
}
 
if (l * 2 < sum) unrooted[sum] += c[br]
if (b < BRANCHES) rooted[sum] += c[br]
for (m in n - 1 downTo 1) tree(b, m, l, sum, c[br])
}
}
 
fun bicenter(s: Int) {
if ((s and 1) == 0) {
var tmp = rooted[s / 2]
tmp *= tmp + BigInteger.ONE
unrooted[s] += tmp.shiftRight(1)
}
}
 
fun main(args: Array<String>) {
for (n in 1..MAX_N) {
tree(0, n, n, 1, BigInteger.ONE)
bicenter(n)
println("$n: ${unrooted[n]}")
}
}
Output:
Same as Java entry

Mathematica[edit]

Works with: Mathematica version 9.0

Using the formula on OEIS.

G000602[n_] := 
Block[{x},
x*CycleIndexPolynomial[SymmetricGroup[4],
Table[ComposeSeries[#, x^i + O[x]^(n + 1)], {i, 4}]] -
CycleIndexPolynomial[SymmetricGroup[2],
Table[ComposeSeries[# - 1, x^i + O[x]^(n + 1)], {i, 2}]] +
ComposeSeries[#, x^2 + O[x]^(n + 1)] &@
Fold[Series[
1 + x/6 (#1^3 + 3 #1 ComposeSeries[#1, x^2 + O[x]^#2] +
2 ComposeSeries[#1, x^3 + O[x]^#2]), {x, 0, #2}] &,
1 + O[x], Range[n + 1]]];
A000602[n_] := SeriesCoefficient[G000602[n], n];
A000602List[n_] := CoefficientList[G000602[n], x];
[email protected]@{Range[0, 200], [email protected]}
Output:
0	1
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
...
199	339176261988518728096836182493660862745709169352281541101577697702699073887422989905
200	943043328799038505167332910595466006794464252841664581909549826351576307818857723954

Nim[edit]

Translation of: C
import bigints
 
const
nMax: int32 = 250
nBranches = 4
 
var rooted, unrooted: array[nMax + 1, BigInt]
rooted[0..1] = [1.initBigInt, 1.initBigInt]
unrooted[0..1] = [1.initBigInt, 1.initBigInt]
for i in 2 .. nMax:
rooted[i] = 0.initBigInt
unrooted[i] = 0.initBigInt
 
proc choose(m, k): BigInt =
result = m
if k == 1: return
for i in 1 .. < k:
result = result * (m + i) div (i + 1)
 
proc tree(br, n, l, sum: int32, cnt: BigInt) =
var s: int32 = 0
for b in br + 1 .. nBranches:
s = sum + (b - br) * n
if s > nMax: return
 
let c = choose(rooted[n], b - br) * cnt
 
if l * 2 < s: unrooted[s] += c
if b == nBranches: return
rooted[s] += c
for m in countdown(n-1, 1):
tree b, m, l, s, c
 
proc bicenter(s) =
if (s and 1) == 0:
unrooted[s] += rooted[s div 2] * (rooted[s div 2] + 1) div 2
 
for n in 1 .. nMax:
tree 0, n, n, 1, 1.initBigInt
n.bicenter
echo n, ": ", unrooted[n]

Output:

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
...
249: 5814271898167303040368103945830220447130073898083466852225709084407144308593691069932064987528870826155297
250: 16206624309085062837751018464745815688226709117091506494175397665527493805947344857313038875654104100026504

PARI/GP[edit]

This function is for recent PARI/GP:

paraffin(p) =
{
local (P = p+1, R, U = R = Vec([1,1], P));
 
for (n = 1, p,
((B,n,C,S,l=n) -> my(b,c,i,s);
for (b = 1, 4-B,
if ((s = S + b * n) < P,
c = R[n+1] * C * prod(i = 1, b-1, (R[n+1]+i)/(i+1));
if (l+l < s, U[s+1] += c);
if (B+b < 4, R[s+1] += c; i = n; while (i--, self()(B+b, i, c, s, l)))))
)(0,n,1,1);
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:

iso(B,n,C,S,l=n) =
{
my (b,c,i,s);
 
for (b = 1, 4-B,
if ((s = S + b * n) < P,
c = R[n+1] * C * prod(i = 1, b-1, (R[n+1]+i)/(i+1));
if (l+l < s, U[s+1] += c);
if (B+b < 4, R[s+1] += c; i = n; while (i--, iso(B+b, i, c, s, l)))))
}
 
paraffin(p) =
{
local (P = p+1, R, U = R = Vec([1,1], P));
 
for (n = 1, p, iso(0, n, 1, 1);
if (n % 2,, U[n+1] += R[n/2+1] * (R[n/2+1]+1)/2);
print([n, U[n+1]]))
}
Output:
paraffin(32)

[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]
[26, 93839412]
[27, 240215803]
[28, 617105614]
[29, 1590507121]
[30, 4111846763]
[31, 10660307791]
[32, 27711253769]

Pascal[edit]

Works with: Free_Pascal
Library: GMP

Conversion of the C example:

Program Paraffins;
 
uses
gmp;
 
const
max_n = 500;
branch = 4;
 
var
rooted, unrooted: array [0 .. max_n-1] of mpz_t;
c: array [0 .. branch-1] of mpz_t;
cnt, tmp: mpz_t;
n: integer;
fmt: pchar;
sum: integer;
 
procedure tree(br, n, l: integer; sum: integer; cnt: mpz_t);
var
b, m: integer;
begin
for b := br + 1 to branch do
begin
sum := sum + n;
if sum >= max_n then
exit;
 
(* prevent unneeded long math *)
if (l * 2 >= sum) and (b >= branch) then
exit;
 
if b = (br + 1) then
mpz_mul(c[br], rooted[n], cnt)
else
begin
mpz_add_ui(tmp, rooted[n], b - br - 1);
mpz_mul(c[br], c[br], tmp);
mpz_divexact_ui(c[br], c[br], b - br);
end;
 
if l * 2 < sum then
mpz_add(unrooted[sum], unrooted[sum], c[br]);
 
if b < branch then
begin
mpz_add(rooted[sum], rooted[sum], c[br]);
for m := n-1 downto 1 do
tree(b, m, l, sum, c[br]);
end;
end;
end;
 
procedure bicenter(s: integer);
begin
if odd(s) then
exit;
mpz_add_ui(tmp, rooted[s div 2], 1);
mpz_mul(tmp, rooted[s div 2], tmp);
mpz_tdiv_q_2exp(tmp, tmp, 1);
 
mpz_add(unrooted[s], unrooted[s], tmp);
end;
 
begin
for n := 0 to 1 do
begin
mpz_init_set_ui(rooted[n], 1);
mpz_init_set_ui(unrooted[n], 1);
end;
for n := 2 to max_n-1 do
begin
mpz_init_set_ui(rooted[n], 0);
mpz_init_set_ui(unrooted[n], 0);
end;
for n := 0 to BRANCH-1 do
mpz_init(c[n]);
 
mpz_init(tmp);
 
mpz_init_set_ui(cnt, 1);
sum := 1;
for n := 1 to MAX_N do
begin
tree(0, n, n, sum, cnt);
bicenter(n);
mp_printf('%d: %Zd'+chr(13)+chr(10), n, @unrooted[n]);
end;
end.

Output (trimmed):

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
26: 93839412
27: 240215803
28: 617105614
29: 1590507121
30: 4111846763
31: 10660307791
32: 27711253769
33: 72214088660
34: 188626236139
35: 493782952902
..
499: 2494778503569518415974916458171385008434293725770646826239156067242244971575380601975205121412154447546983792
     0461991186908900888093113539339801359611535867899901287200789925164011521414091897974716359811774035382416687
500: 35027241765694350953134643689731689510165490186734465975716452976264824623941928748229034890456068034873862265
     02245470029705798383457667757879016306516643706616463708365586217812176623950823312143595975577679489832553344

Perl[edit]

Translation of: 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.

use Math::GMPz;
 
my $nmax = 250;
my $nbranches = 4;
 
my @rooted = map { Math::GMPz->new($_) } 1,1,(0) x $nmax;
my @unrooted = map { Math::GMPz->new($_) } 1,1,(0) x $nmax;
my @c = map { Math::GMPz->new(0) } 0 .. $nbranches-1;
 
sub tree {
my($br, $n, $l, $sum, $cnt) = @_;
for my $b ($br+1 .. $nbranches) {
$sum += $n;
return if $sum > $nmax || ($l*2 >= $sum && $b >= $nbranches);
if ($b == $br+1) {
$c[$br] = $rooted[$n] * $cnt;
} else {
$c[$br] *= $rooted[$n] + $b - $br - 1;
$c[$br] /= $b - $br;
}
$unrooted[$sum] += $c[$br] if $l*2 < $sum;
return if $b >= $nbranches;
$rooted[$sum] += $c[$br];
for my $m (reverse 1 .. $n-1) {
next if $sum+$m > $nmax;
tree($b, $m, $l, $sum, $c[$br]);
}
}
}
 
sub bicenter {
my $s = shift;
$unrooted[$s] += $rooted[$s/2] * ($rooted[$s/2]+1) / 2 unless $s & 1;
}
 
for my $n (1 .. $nmax) {
tree(0, $n, $n, 1, Math::GMPz->new(1));
bicenter($n);
print "$n: $unrooted[$n]\n";
}

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

Perl 6[edit]

Works with: rakudo version 2016.04

Counting only, same algorithm as the C solution with some refactorings.

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

sub count-unrooted-trees(Int $max-branches, Int $max-weight) {
my @rooted = flat 1,1,0 xx $max-weight - 1;
my @unrooted = flat 1,1,0 xx $max-weight - 1;
 
sub count-trees-with-centroid(Int $radius) {
sub add-branches(
Int $branches, # number of branches to add
Int $w, # weight of heaviest branch to add
Int $weight is copy, # accumulated weight of tree
Int $choices is copy, # number of choices so far
) {
$choices *= @rooted[$w];
for 1 .. $branches -> $b {
($weight += $w) <= $max-weight or last;
@unrooted[$weight] += $choices if $weight > 2*$radius;
if $b < $branches {
@rooted[$weight] += $choices;
add-branches($branches - $b, $_, $weight, $choices) for 1 ..^ $w;
$choices = $choices * (@rooted[$w] + $b) div ($b + 1);
}
}
}
add-branches($max-branches, $radius, 1, 1);
}
 
sub count-trees-with-bicentroid(Int $weight) {
if $weight %% 2 {
my \halfs = @rooted[$weight div 2];
@unrooted[$weight] += (halfs * (halfs + 1)) div 2;
}
}
 
gather {
take 1;
for 1 .. $max-weight {
count-trees-with-centroid($_);
count-trees-with-bicentroid($_);
take @unrooted[$_];
}
}
}
 
my constant N = 100;
my @paraffins = count-unrooted-trees(4, N);
say .fmt('%3d'), ': ', @paraffins[$_] for flat 1 .. 30, N;
Output:
  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
 26: 93839412
 27: 240215803
 28: 617105614
 29: 1590507121
 30: 4111846763
100: 5921072038125809849884993369103538010139

Pike[edit]

Translation of: Python
int MAX_N = 300;
int BRANCH = 4;
 
array ra = allocate(MAX_N);
array unrooted = allocate(MAX_N);
 
void tree(int br, int n, int l, int sum, int cnt)
{
int c;
for (int b = br + 1; b < BRANCH + 1; b++)
{
sum += n;
if (sum >= MAX_N)
return;
 
// prevent unneeded long math
if (l * 2 >= sum && b >= BRANCH)
return;
 
if (b == br + 1)
{
c = ra[n] * cnt;
}
else
{
c = c * (ra[n] + (b - br - 1)) / (b - br);
}
 
if (l * 2 < sum)
unrooted[sum] += c;
 
if (b < BRANCH)
{
ra[sum] += c;
for (int m=1; m < n; m++)
{
tree(b, m, l, sum, c);
}
}
}
}
 
void bicenter(int s)
{
if (!(s & 1))
{
int aux = ra[s / 2];
unrooted[s] += aux * (aux + 1) / 2;
}
}
 
 
void main()
{
ra[0] = ra[1] = unrooted[0] = unrooted[1] = 1;
 
for (int n = 1; n < MAX_N; n++)
{
tree(0, n, n, 1, 1);
bicenter(n);
write("%d: %d\n", n, unrooted[n]);
}
}

Python[edit]

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

Translation of: C
try:
import psyco
psyco.full()
except ImportError:
pass
 
MAX_N = 300
BRANCH = 4
 
ra = [0] * MAX_N
unrooted = [0] * MAX_N
 
def tree(br, n, l, sum = 1, cnt = 1):
global ra, unrooted, MAX_N, BRANCH
for b in xrange(br + 1, BRANCH + 1):
sum += n
if sum >= MAX_N:
return
 
# prevent unneeded long math
if l * 2 >= sum and b >= BRANCH:
return
 
if b == br + 1:
c = ra[n] * cnt
else:
c = c * (ra[n] + (b - br - 1)) / (b - br)
 
if l * 2 < sum:
unrooted[sum] += c
 
if b < BRANCH:
ra[sum] += c;
for m in range(1, n):
tree(b, m, l, sum, c)
 
def bicenter(s):
global ra, unrooted
if not (s & 1):
aux = ra[s / 2]
unrooted[s] += aux * (aux + 1) / 2
 
 
def main():
global ra, unrooted, MAX_N
ra[0] = ra[1] = unrooted[0] = unrooted[1] = 1
 
for n in xrange(1, MAX_N):
tree(0, n, n)
bicenter(n)
print "%d: %d" % (n, unrooted[n])
 
main()

Output (newlines added):

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
26: 93839412
27: 240215803
28: 617105614
29: 1590507121
30: 4111846763
31: 10660307791
32: 27711253769
33: 72214088660
34: 188626236139
35: 493782952902
36: 1295297588128
...
498: 8905549466780876642396073343654258905917693028466999354614122414
334803973053490695667380301725459866905052509157458138657523790806693
604983304945043446074074823147488033014740909049433466213254508146498
309733349188106
499: 2494778503569518415974916458171385008434293725770646826239156067
242244971575380601975205121412154447546983792046199118690890088809311
353933980135961153586789990128720078992516401152141409189797471635981
1774035382416687

Using generating function[edit]

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

from itertools import count, chain, tee, islice, cycle
from fractions import Fraction
from sys import setrecursionlimit
setrecursionlimit(5000)
 
def frac(a,b): return a//b if a%b == 0 else Fraction(a,b)
 
# infinite polynomial class
class Poly:
def __init__(self, gen = None):
self.gen, self.source = (None, gen) if type(gen) is Poly \
else (gen, None)
 
def __iter__(self):
# We're essentially tee'ing it everytime the iterator
# is, well, iterated. This may be excessive.
return Poly(self)
 
def getsource(self):
if self.gen == None:
s = self.source
s.getsource()
s.gen, self.gen = tee(s.gen, 2)
 
def next(self):
self.getsource()
return next(self.gen)
 
__next__ = next
 
# Overload "<<" as stream input operator. Hey, C++ does it.
def __lshift__(self, a): self.gen = a
 
# The other operators are pretty much what one would expect
def __neg__(self): return Poly(-x for x in self)
 
def __sub__(a, b): return a + (-b)
 
def __rsub__(a, n):
a = Poly(a)
def gen():
yield(n - next(a))
for x in a: yield(-x)
return Poly(gen())
 
def __add__(a, b):
if type(b) is Poly:
return Poly(x + y for (x,y) in zip(a,b))
 
a = Poly(a)
def gen():
yield(next(a) + b)
for x in a: yield(x)
 
return Poly(gen())
 
def __radd__(a,b):
return a + b
 
def __mul__(a,b):
if not type(b) is Poly:
return Poly(x*b for x in a)
 
def gen():
s = Poly(cycle([0]))
for y in b:
s += y*a
yield(next(s))
 
return Poly(gen())
 
def __rmul__(a,b): return a*b
 
def __truediv__(a,b):
if not type(b) is Poly:
return Poly(frac(x, b) for x in a)
 
a, b = Poly(a), Poly(b)
def gen():
r, bb = a,next(b)
while True:
aa = next(r)
q = frac(aa, bb)
yield(q)
r -= q*b
 
return Poly(gen())
 
def repl(self, n):
def gen():
for x in self:
yield(x)
for i in range(n-1): yield(0)
return Poly(gen())
 
def __pow__(self, n):
return Poly(self) if n == 1 else self * self**(n-1)
 
def S2(a,b): return (a*a + b)/2
def S4(a,b,c,d): return a**4/24 + a**2*b/4 + a*c/3 + b**2/8 + d/4
 
x1 = Poly()
x2 = x1.repl(2)
x3 = x1.repl(3)
x4 = x1.repl(4)
x1 << chain([1], (x1**3 + 3*x1*x2 + 2*x3)/6)
 
a598 = x1
a678 = Poly(chain([0], S4(x1, x2, x3, x4)))
a599 = S2(x1 - 1, x2 - 1)
a602 = a678 - a599 + x2
 
for n,x in zip(count(0), islice(a602, 500)): print(n,x)

Racket[edit]

This Scheme solution runs in Racket too:

Or, a direct translation of the C entry:

 
#lang racket
 
(define MAX_N 33)
(define BRANCH 4)
 
(define rooted (make-vector MAX_N 0))
(define unrooted (make-vector MAX_N 0))
(for ([i 2]) (vector-set! rooted i 1) (vector-set! unrooted i 1))
 
(define (vector-inc! v i d) (vector-set! v i (+ d (vector-ref v i))))
 
(define (choose m k)
(if (= k 1) m
(for/fold ([r m]) ([i (in-range 1 k)]) (/ (* r (+ m i)) (add1 i)))))
 
(define (tree br n cnt sum l)
(let/ec return
(for ([b (in-range (add1 br) (add1 BRANCH))])
(define s (+ sum (* (- b br) n)))
(when (>= s MAX_N) (return))
(define c (* (choose (vector-ref rooted n) (- b br)) cnt))
(when (< (* l 2) s) (vector-inc! unrooted s c))
(when (= b BRANCH) (return))
(vector-inc! rooted s c)
(for ([m (in-range (sub1 n) 0 -1)]) (tree b m c s l)))))
 
(define (bicenter s)
(when (even? s)
(vector-inc! unrooted s (* (vector-ref rooted (/ s 2))
(add1 (vector-ref rooted (/ s 2)))
1/2))))
 
(for ([n (in-range 1 MAX_N)])
(tree 0 n 1 1 n)
(bicenter n)
(printf "~a: ~a\n" n (vector-ref unrooted n)))
 

REXX[edit]

(Based, in large part, on the Pascal version.)

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

/*REXX program enumerates (without repetition) the # of paraffins with N atoms of carbon*/
parse arg nodes . /*obtain optional argument from the CL.*/
if nodes=='' | nodes=="," then nodes=100 /*Not specified? Then use the default.*/
rooted. = 0; rooted.0=1; rooted.1=1 /*define the base rooted numbers.*/
unrooted. = 0; unrooted.0=1; unrooted.1=1 /* " " " unrooted " */
numeric digits max(9,nodes%2) /*this program may use gihugeic numbers*/
w=length(nodes) /*W: used for aligning formatted nodes.*/
say right(0,w) unrooted.0 /*show enumerations of 0 carbon atoms*/
/* [↓] process all nodes (up to NODES)*/
do C=1 for nodes; h=C%2 /*C: is the number of carbon atoms. */
call tree 0, C, C, 1, 1 /* [↓] if # of carbon atoms is even···*/
if C//2==0 then unrooted.C=unrooted.C + rooted.h * (rooted.h + 1) % 2
say right(C,w) unrooted.C /*display an aligned formatted number. */
end /*C*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
tree: procedure expose rooted. unrooted. nodes #. /*this function is recursive.*/
parse arg br,n,L,sum,cnt; nm=n-1; LL=L+L; brp=br+1
do b=brp to 4; sum=sum+n; if sum>nodes then leave
if b==4 then if LL>=sum then leave
if b==brp then #.br=rooted.n * cnt
else #.br=#.br * (rooted.n + b - brp) % (b - br)
if LL<sum then unrooted.sum=unrooted.sum + #.br
if b==4 then leave
rooted.sum = rooted.sum + #.br
do m=nm by -1 for nm; call tree b, m, L, sum, #.br; end /*m*/
end /*b*/ /* ↑↑↑↑↑↑↑↑↑ recursive invocation of TREE. */

{{out|output|text=  when using the input of:   600

(Shown at four-fifths size.)

  0 1
  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
 26 93839412
 27 240215803
 28 617105614
 29 1590507121
 30 4111846763
 31 10660307791
 32 27711253769
 33 72214088660
 34 188626236139
 35 493782952902
 36 1295297588128
 37 3404490780161
 38 8964747474595
 39 23647478933969
 40 62481801147341
 41 165351455535782
 42 438242894769226
 43 1163169707886427
 44 3091461011836856
 45 8227162372221203
 46 21921834086683418
 47 58481806621987010
 48 156192366474590639
 49 417612400765382272
 50 1117743651746953270
 51 2994664179967370611
 52 8031081780535296591
 53 21557771913572630901
 54 57919180873148437753
 55 155745431857549699124
 56 419149571193411829372
 57 1128939578361332867936
 58 3043043571906827182530
 59 8208615366863753915949
 60 22158734535770411074184
 61 59858097847706865855186
 62 161805725349297357221898
 63 437671691526158936922623
 64 1184616185385310843585573
 65 3208285066181475821271463
 66 8694130712024868414002815
 67 23573796134448175745408811
 68 63955159527348138708694312
 69 173603007393950249896865875
 70 471484798515330363034639871
 71 1281151315764638215613845510
 72 3482965749140691245110434511
 73 9473447386804490449091871124
 74 25779306238954404972323916397
 75 70183211512214096492433058105
 76 191156381393249393027319384769
 77 520874195248906781713044332539
 78 1419908915343952137338409797325
 79 3872282575137005474139119076135
 80 10564476906946675106953415600016
 81 28833609436277333169440806135431
 82 78725585464391037293036629979444
 83 215027809474796675607407513633870
 84 587531723826577193455385789266377
 85 1605913778494711520354663202536756
 86 4391002908093323425994602631972445
 87 12010257907756938974208750945664835
 88 32861295558120887536942123568548502
 89 89940959024891576997396491928932689
 90 246245150242821439632304475956113295
 91 674391606297983432514229725117306224
 92 1847515048012613337782670842346319120
 93 5062818112121161180862827915688625902
 94 13877857529584521384324419956411729295
 95 38051836070803837001309074456088423358
 96 104363664561059273927704242814298678658
 97 286312976836850192359345859166390622180
 98 785684759853087702778573182234297830503
 99 2156596319845084996862701478402986311496
100 5921072038125809849884993369103538010139
101 16260750014333666174953055376699249561110
102 44667063168726812052821334495766769690630
103 122726610195426301690448676841677827340780
104 337281538963751874669853952178948219200633
105 927143441542280244466720172757699607129825
106 2549176520305910764377448963173035784835631
107 7010510656300876673813654064741809461787182
108 19283877336110239907079044091958051661009951
109 53055727810105880736027950213934519705620559
110 146002972524313232817393491844985704938385801
111 401865724190508834753025926637435418813476039
112 1106339625432222709435767174129826811545391101
113 3046369875968510015403046201590835240153395100
114 8389999420170754836800638580300552381250693062
115 23111326593011774543116815302964652139347135182
116 63675155467360117136901070528242608498818046250
117 175467195960062612437322237574246321515725845634
118 483616671898832299071277369263305813784565460114
119 1333167312321418940566764416056977442040495550342
120 3675740183950426011078357941139728051663026172228
121 10136322901774027447848977748665383292736169662267
122 27956983197937526275999613945221497078279509595407
123 77121096978813982358935411851692069578533009193138
124 212778592638033483022781655638827961970402357080215
125 587155794584829621068447884048323985962957796104395
126 1620497362318232091081355117667505915417499978679013
127 4473132502312622821884079561929897829404710575328024
128 12349306792492607803837161096610238756912653878568775
129 34098849774876383478036291434385545792965491914980650
130 94167748474814466028838037996326649316233175269577493
131 260093170948828891650104553710684162327855828421145690
132 718487205759724277833835055443909476145495116155508155
133 1985050220521088907210323840127550973214943015739291120
134 5485110653386099899275645856977233423965042141295771502
135 15158624968755754576600389921905653584106659889930620820
136 41898053824932615440265041900412507427220728337249680527
137 115820822448502452349822520317304132018285539473087897141
138 320211802888589798701825810680319271475504997973219083170
139 885411355238188116465394365370757710295372148438998022826
140 2448550585524918609600214967948504177437555812600018440773
141 6772180336728084537425567078328320492989943976904644119200
142 18732796033402227075307540055538834651333956120072379687678
143 51823958523558404531622255138725304201359354985976024954747
144 143387634030485523461662580179416231260007790242619239696168
145 396775836020295064920040342935953476579230225268967120945252
146 1098070975453594757891511609218085888434254839495604326720679
147 3039251105982158526063018965393900608357891201531016545453671
148 8413041613874240075848233530979949485087059914285837491890647
149 23291051500594069758631194545655502320903778728677961917787017
150 64487285324785805685734825467573942213924157583096655274158296
151 178569541961158786360447600422369518262867694211679827307797522
152 494525085028771691070376002671999818542495469214503552543494392
153 1369671107847363840368349527801907625890550280754690871159384167
154 3793941909035282970536126899217159922244816989321008990552343933
155 10510197366726219419291185594221700080820692107164072063617583537
156 29118988780427095392911694296588496006042150251385271606702314123
157 80683801316548713731547508195369620842564695928190934573122040053
158 223583881196691039626561929582827819978293196688915654006262185620
159 619638153674192054430980737083649826660231642062541457264064352590
160 1717428978037773119953669826811378686605009454833429087085211111817
161 4760601845949152288761851253868434642647478893273231351009713026471
162 13197353449186709568929592710369551730672357721629256541119049584662
163 36589226826424289787166608629764201634396432211204018812233928108927
164 101451975263926040804307438557581821336425438886780992752450611791029
165 281324901033788598583154170205263556814795889090791609969956549076553
166 780181677818281299965193432627955631078491817302716837810578348379410
167 2163828038323756757063639945018570904120396578192324738853110253083851
168 6001899167570139611127915072874671685163847392112466633395193150607161
169 16649191065671323727576273232609293462550308875754570697371028619095529
170 46188686972056579073145176280276791118176099297131728121378351698216964
171 128149137125681447665302588425507023489080631426025859378879991574150361
172 355576383032176188837060897590191000068058505378256432541548821711409736
173 986703913063443346422020725722084251185909113284392827422830038792419867
174 2738275183964917202164682060710234556685852044781624370789938274187242387
175 7599818348156354735525837090092498330135165342551619766604085368593605623
176 21094284799140605474267783653778252494175708547669907184929527663028371844
177 58554660677719531288883019197284429180673377561888244491058170393359945984
178 162552183133868639189244204285356619593212307470997836346642760606493409411
179 451292826786530619879633220482642976940485477290114448603416892241141577694
180 1253019870825476025726441067676567248038950763298814178748038046446512128926
181 3479293084378459187212303139960535018989517537846033787292960498791544468857
182 9661781855977284524013799278118239872342899149756408496918889491272019198160
183 26832197158239597797570968340612728947891256166650480273266227097169558934791
184 74522545727244539603451333395337695567614066525612042720018110555143893455632
185 206990881176753531116559188573370889805581604324744059300494333307748123498957
186 574971719221297425559348824161112797452658996937464320320048053830834065076638
187 1597250942564001477500533605167309927398304330031144648098072721512668593957703
188 4437423571982333312534972159110678450135834859468229274326790786916695731276497
189 12328758711422329105019389982539560951228986597668702145097956175468519348920309
190 34256124585721478074980980873512523523896822875906637442595527046990665266761523
191 95189094589104790904556217884090558824685828617516319665565748564984723369457220
192 264524521940855272106937702820301986845470010150944446148610489622177560655580196
193 735146927788110318878638054407335543366855876665936464594690408421993895145574507
194 2043202995476015462049187462882169976289343296164934404442378707876446055277665852
195 5679076882963913929265887525377096781591407289261632655627568444557125995319535956
196 15786016263625679649343179544010857226174369384245579060916786714528288038933116607
197 43882930188633901470015828734437451959746697520345645823789728504039719238235284266
198 121996306076853365751053531202168307620916572983606780123661900035869303555630148063
199 339176261988518728096836182493660862745709169352281541101577697702699073887422989905
200 943043328799038505167332910595466006794464252841664581909549826351576307818857723954
201 2622195090600379263364346956264279702121691087227848066895838284611152725976467138514
202 7291640328972323818932818268921088199080628040707037288217930491456875016135548131376
203 20277391980621940663950418790370236703345679504035237316723532280155012704421841134349
204 56393014827755686247101145333945229562531368138401437274854961321951321148392478837326
205 156842815530515935964014240194651333844507609987619166694876840912879248319077130581042
206 436244327522179535577207667646065280269833187002466982658692809627210486721781255271000
207 1213446271931548955557154166653292946893343739485414159573064525913091105471901382363618
208 3375488708820014134062868343953409434477577207616345786043331438445002602958236463369496
209 9390265533842684145381903993662706957889355090166833985181893569515242461156430420087174
210 26124257322713604151166532772505893583948958402141893219135619374261694917895951421995216
211 72683304203243676344755903584747211387194000236278332965871882088118015556154063840306823
212 202231949421481999766866699910650758032171534187352358158377153614156835833334273717131223
213 562715711666310319461011612553561742990998466225938804278692337156743603187662151365368333
214 1565857565336512188705390960430387447731996020954944548096469264981742312029607101653583428
215 4357517959671123300838959993742696621943017700847213254885626681813005595459240045099075216
216 12126894898610872886310565416845280412742023065548437498642351657251934710541687754081654026
217 33750741717021238734330907104325257824118779361033241504478398185637818043649623474315265399
218 93937737312335248803818931862078208076074752854934195324106075781489944419493627198038389700
219 261468709433838684317888993242737209511093586216774554328802510011968600660643442350819036063
220 727816668798656458204462998706538701005731200304158665308881919140152438032334192310185418095
221 2026033924729657796058178057776349080819410108838068133330231127278657184350600523917658261950
222 5640189120704586237460028096950040726608416653216674308167097595939322372553028535058020450921
223 15702277858615709125768061794209929881772942003228681661684701314937614138722747596565403037124
224 43717315979005745749656846671283395378656317609179742248155824749456112069949537586095666617258
225 121721128292306933059993974247348540921262802966704236768446493370986884003643919966941048534839
226 338922110694788427241777802405838150613492773013920995745534133385509651242705886920398223181010
227 943745948264384101974654246655344635790924945832998571660171925129987029630345274360528181753602
228 2628036396188665255122485857407491640837938331141774537726852980481211265329884171692375404118006
229 7318608979755404166520379853847121693286549981969246032578382667986026415973227568070229589183702
230 20381982477815712032070175127992226329196107434900428011148438268022423947798435659837662375820784
231 56765548015352873669830186155391542225154245344836703122834457861735047936794014876150374629860524
232 158104270172530515145265641139760077405201789758339337585177180751307186891559972317181979411965521
233 440374885613967273764570923053527071581411261510943039612254074378568326443950283692532685610902647
234 1226652343389215664746827690619448544313348534138985205724729790807207201280976341202710717893074853
235 3416963010634291402556279395279280039897379691659516509445008289967225395946292319651344904483142876
236 9518723877111155596143748502002445531218893550853129590490604506008598318134823819368242604272122748
237 26517750521770746045881213675376639453619783582926617680386483834380296365299612479395492961088242736
238 73877802385952947032921713908581985111328188063663582097893741466810319537930797134111900695946616163
239 205830832103408707745581845015281353687041390648973776794197115951467164317467871635600767010770430175
240 573490073391076513109930570190363749116344599275683632274375821562743183409191580097184195332209714304
241 1597939145083038119284545851972427651672212885904578621056479058274066462851925440771984480190480136917
242 4452595736241139504848505768149348728327738257189209919868237125085182422374731188865584214640572836004
243 12407515928191678703401447333122259693080851830690277274671393962029357182157422967017478923028296493797
244 34576004768296889785887066794910718730985852896707505707076422305798138880427343561380451664648670542260
245 96356944442415066997623733664230869603611716312377642117711752082444867783045964116385053282421589905891
246 268540209617944059776303921971316267806082307732727328919911735252505071315985779867844056236080213000010
247 748434113260252449609376828666343341456610378512725586135955779939163320693444008584504390382026391947130
248 2086006351917005252913566124773054331962205157167696706926185063169623907656246841866717933958839366769700
249 5814271898167303040368103945830220447130073898083466852225709084407144308593691069932064987528870826155297
250 16206624309085062837751018464745815688226709117091506494175397665527493805947344857313038875654104100026504
251 45175937003790110836570547902793926244224423679908111750183970641450850884015931131155869896510573436377669
252 125932844251389164587464842843820559638763899540510199408003184309130630867218196313865482109056537730398481
253 351065342330255763232857455169736646100231492324922604469018864206124242515874849723301032460307149363100441
254 978709648454897177175122229161387383812277957992041737463093257271644176592407853706597679764899372036161233
255 2728579524947965774924389584178729664141559400119961753692868837602435434199845226128003794876379357316697077
256 7607396703016294839448365361938795245280010901284162245456747052211826446860068129026466203061153094215518724
257 21210557506627112926709102814428055407062200441680249553023821619098519349155457094641057751120559709171040766
258 59140439362561173332419239067243021493683835575971725019164864794611034386190038342974191464909448990949160433
259 164904810640488270400543694428054069489544003984942619936396942506713662286505814885161827364845226768614358614
260 459831050079703806398893682379638814715447009656839612265184371710342022860900424760438175669232045681912458051
261 1282269545669451251495903825012981075351208474904611796782387631860379995597556946571575503111416187201880410644
262 3575825396849372674227875243103667862184010172899663062411840184180866163260563950451991491936318403482879258621
263 9972156891686411557328508654295124624639913506842521363764257263308033015597557061627102698432983819442412394838
264 27811063827636093132667356617123953605179549615375068595807588613293746133844403466327129871126313264974628662807
265 77564265332280746617483643899828940094749105640853192164718696895612990060307255121145982345803398310187898079392
266 216332231349983182677166502499939151645373218726526211012542076898269883946723118249478997581133729453560312506066
267 603387244708899225237309237330610582381466132219204206651989196705483816075205241122264636682375218975924652825723
268 1683008287833477538339860215212515239936353956160360612774483581234476591477397755553006707152662976687651986820471
269 4694523362293720915770110468625254606334394674668223296355229413555998319740629081646850706213675263754699054633081
270 13095188764074847449997295761581235990086284447120964420084615733616254354939466149397793993685871755799835949802912
271 36529768402903517606384673511136047656882432642972469371446625066352669529799727046128853301739369357159703149780745
272 101905321192540151862638359736728614554608647415740089819403904415838588146647274739611127649149596882860882722587389
273 284289935231308453374750088765973199540899741283799909358363233742287775789400140615985324231011233577018262261573605
274 793123245325306332656455155240700037979451600908118795329947235860752298477617419042698562753980516235445433182899253
275 2212760132831467572448479267369564903248109841785416455962789880485683556412683401911627301645620036274083564670518082
276 6173655026597144030316412809287663876433674099262130586459961369609545873586739771264653817548847051334819819267673785
277 17225214341482211996032609302647305657523857862682844736606106535050865551873299016458209128943795787480117352433192085
278 48061914342670201573422935228854332433440964678249011765471625586477627885410949735846954120344190850911152111629213202
279 134107030939622800029603293300903916561747683391063747072730704147537374895733111331174560543849820565430622535700765087
280 374210510638629940690846658146299050872996272327226981131494408641813084321751382508507907480321412498705157378605184512
281 1044225435503012203708531726182660970486727267736874255761377919782453611846615819319682114158692224800786189315971278877
282 2913978259975249383405724359543135914479847534340004256170151623725094458935882014206856559644179292630105188852484942654
283 8131899511255901661123024274302643005342358280792291668909947468080778066409261184072068071349503993858694564467915250947
284 22694010896831082150833881059471315166090154920352083471916559708043752042060890804464910281660301317591577341450643643408
285 63335029821662407792368658364099477321708085419464650722906960844887633330655722051429941743869159345683126460066342502022
286 176762473380773688334564893776355424385292545126164061340618485071148722461544771780431630578615064360263323717976541381234
287 493343530262595826525964374079648726397444990904885237605455236919429909498402035512893215123730306166937343830199098906264
288 1376962107154173493629678201172367360428665626252713512103398076898209747598726288264583330503085546722567594976794377910916
289 3843329627580641896092936292497953013493677730608250853017184751560504997627908821176789676128330028340434788417374548321665
290 10727691632324916343855749374736278911611036078629853835188027850311800148076269026969505419892040571311019353938342366479921
291 29944553492856643003705267171203053740637479757153174554386011341347968315240452765007183277660357717971836148800091968332374
292 83587671350621452088852077606615169147100357534595837577486058324929087065974679646254472788204214648005248614193318414377024
293 233334710228304175640537431761015155226516041956764172024879820060328914791790564269514952923849421296827499293644779973947944
294 651372050316781966807515452385884535330825922949828062262435782904101091097575267639485669941314856354615008764966125315567827
295 1818408509063580466007837286680677983183200164466347108731791763610863204309478600683111564194332619888539094594355873251409769
296 5076521961686346652128084504011167440512053731910308671725721188988125758183538040191772757449820238766222803630357752112485124
297 14172728853081183487692819360642616465697855744649707292748353245040159044544320770757891836594915830996846840829976619821699618
298 39568810871971230524136981094496991848828417446424705179645229759385730879357244432238970058197255613334159244290428131124452830
299 110475187771839384048492533823159918390262532886305090937767272270110025203334389240257568860480586164979548476232996728116729683
300 308452748932356659134640254457496633283824248738866911531511793646459565034445179334045501201901754682633289077084032710062170279
301 861240824463152722071836109344427337431877614848901867514576156478082914538339062870758774046333091097667962110703879907047902312
302 2404764529074988740593535159997552717572283601360445481122700282665430064398873396193716880348601148493581071074166478693990790856
303 6714789670469454153386611562013961023242903621637710232282341992915250322865847054817163511814626619935187437204372380050492741416
304 18750122030724673491128292527199763297679319101861503773445345726522308044322152662576165962119970647127449975852633174621969880739
305 52358540776822171397938610797428972138604966642799660183619135856732885313895214904783970369869810500221836523091218317395627621618
306 146211874171546304848114890907617543441612329368468136490630136290133091812328020942022322642930758562497993998813033035404037543378
307 408309374766218968874889934904388454292250204332400357496458432386295109182205213667370847008916451504534109623708005838430560375834
308 1140269692101119225290015431235563792069793485705983470470867840010583946573338083342919032742493114840430853835483727638466969240655
309 3184470707522086900997866971280896496954514816942511201817116808120545961910541675928058343909676364966063888004625727819620056540601
310 8893614673793550426203177888486104267711942366176132474668917683523216912995539226525055322211719832653261036678928338242794559299112
311 24838802846610505668649291989193851484488311070565125269868527227254250892146180700796996471641995241264610499129510168778379797378423
312 69373601175140878518878407416354675734791611152355756178787188936758881149210187484048705485225593356694870840499748283514606905423246
313 193762163046096898541813934971517737075188015959344864028603775487737030285826209135941854672715712590577000793283534406527423821603576
314 541196268484366087460262358027194004033064530954199287174876761416952913147671036693586440799261630163373615316567720548527381195438918
315 1511651318369444868069381097588803592058478348477392184356035123988931642510796085735141212763489336934853150751083260832206937172777771
316 4222400314117802395206774109473525042605695338264852324330490813196732243068423992961417072802043842042530256505735344967053794408556908
317 11794459906262866121871266626258612511077816494044508649944585283517043771401831174632355215381132675014638552720472693257723281462233129
318 32946365969776950669210980118015393793307352206055398592039144337621666690536830616548580432186809783833682326945726304026143435880100838
319 92033876907305433205854719644923336617100767023736541909688403892639957967832412603103787416503526220933894910089369504797536063937671030
320 257097934297469931507121119430597202704570898364889238133318471104541259886397767255481550138719826045933630544145524425190555924302974158
321 718224246661073548051565677535142499609012941753481223097942887830348917070217610983727147940761519744793793610330362338688442615673197462
322 2006467255534766659252829163933203490934832421279044800912337935400118444158392493858857751565420235179779642111003320596793004219471322947
323 5605502679518523143080247371236214990417155138717305546851545955873633006386080207929423558432674748825829901712741304990371774362283193320
324 15660566253432279506286172779655932839156833825354675435289251721808777572046022488948890326675140567766761094326162530759197028738047873342
325 43753288739599158009572690177719694499517002167269307889473331175822392011133070749493619973508391450631282964371854365131850614423969032045
326 122243063487953630168779441726858835845029369553685692636128110535135358236544861593075531121566156537338799874811313621048205453846948646594
327 341545026553716654296677021076699009557085350341854224151424291838064554557651097172377365249127972138551966103843383352678909134633899780049
328 954293272184484715061223205140067155456619561299656508883393887930115103078655393909392079957547038845854807951838617028341170549971437113756
329 2666403386739315827868066185122722123280808213775194857874678398607400719066832564196623913793636277667368621779542858235837144754558689362770
330 7450404892053082221574739602061345433226079835970620657414429662265437596906083041228826067447081207920786076025248511641195093761018228486117
331 20818233236540500078078726545737487276469129757876541102703166024191510234936838646279399885038539925967058597219811390519182332350074088483801
332 58172506428290564368141089289481919244396569391637155592567737523706232298107560669789028286499114696254965115086663396724793700039535105809825
333 162555450043434528743216203388499100784722341392396045140172843700097191508823985571422968024333740892364547560879635001525731982520443668407207
334 454250157235286994930516589657219180338096942589294611421361473820956593031171048775282611503529678045566128639300306815980549814735817293632328
335 1269399644216896674419509697729463047322902302717880576621386334890813629251048864345125927692087232669828899817484051825954105426712749458105719
336 3547409580555749581428375893211291993132883055153877931717905621147151289844110360051310758575795791014297933394182694793731277677223886505210604
337 9913657616876180996272994213830886174557219586954823670177585140374478051025004200168094107564237013138944074674000581394701452285244389597956715
338 27705504250793641201136147317977373743683200591499163219665638173564039350984177869778739763213987393664627300779909086252047370214399911131005215
339 77429723308686422060745817247773603245179312769655054126749234498755173568276490783876715746154890754203846791494405123875247961686499129038297227
340 216400771687500406123258313919627031449853827152325829464263282001824129364025389238788652830899867301042402568490706765506227298942393806928108235
341 604810464516125477241566412882349204137572849071402383810346407708410011599408641489401825943216390533769925718210249763369632034958372608290844206
342 1690398611265385833597216662397255544989165037053280798937154717423932000388167869168930853825927977852841640076328038923189020256557719193791256028
343 4724634772968354441296131448066702565819242471972930246064518060636141614755603261379142845848576742911828869261061820791686009759021485237698477831
344 13205552829661483110364753142284962949107602363850885398784926506038176551941835670483442213970733618691835956778974797080500820139190122943284582135
345 36910855280499292111957523443882193440612445434176479707767186915266152482973875689799871251737846372737188112909754993522207982690542240926130029049
346 103171739679545034385009574491036788498270729350913451333950358713843618189620777988883995604632555973833362206978350103925117854467640580483436552018
347 288387524830070207712762522892988184663566029872195934853726561639393938557865016202521468003680404859295709114570707309431763967645212689873531414264
348 806122798918603963804489903399570959132892552474576252746348067356487862540352928356904945671326172417576672782142508442928521818059159444295065569351
349 2253382439271040388149474850917992870398476906210930447444262444269257785111968397614677064122886740776607477106889945148953791648085596979576315110482
350 6299085778376549624821429179458510900194958604210429834866285306534323334146994999589505103105601742105346495367945462306323190533152968350936328833093
351 17608769315860492326012526752722740196012949442575558856980140609187722195861145221351750035945476764574248561005920231231717297371258189428413075334925
352 49225405206515153087568948490481900524317536823931935604937570379534876242330540513362387565765326989735254840166835073173949257982193474194915953803083
353 137612650518574117451330956726549297191660051390691147866537032385615815835760333658095155505973979232131231656924338282838926211524292823285634711474633
354 384712355414294702563904729491023243627956319486020537228732734017954863719619385122127616879959104196458802246444742876626069471608782252965968612497198
355 1075530112808179390071712452176822139103273689672504194433511328424197482887796207661106800366074422776307279191236098858340632644479271310162484217917592
356 3006890624730903809203348452903910972516333634451058962761600995261350724210387631287122470914299872520878957623017199446857400919899829039177221306594762
357 8406616889129974244397003491764309398845023627456637599897772061394635091675951085559195087235345860699090644025580860759237281995429915998000191117024816
358 23503546635376640553461907666151910955199316486853220612258843913181768436558650960045561863244812806343068989021774935699707646736474569067094595172637657
359 65713412324197507817554740047743479221985390537015377014989484413218559711974382297521939019242021211490372847064568851951672832785537922807500683400249532
360 183731264265605405843365379086835345824768411971600936222075279683603801778731406834023568040750755069976677442393364831096485389709475423423923842324234989
361 513712917445044879755632157033905467853325637578640428524826452382229282708618525455937273019555303667710885659176534752548868969162928871024925640927161271
362 1436369721757738892958929630900072633478136236302452472776025832973978953360582366193284186527643210738556081221865437790061121840459854628616810254345970340
363 4016245794540314317921944312723698293128035701349480130082040705613877555134606721253578868773247173814885875141129338065351555559857572125255328673559903040
364 11230072676900921539509513093811870438221223811407353714408100824976815504864394851215848887535311992988055261583243142720576553693459388593499340501967396681
365 31401691722083002417916521112590305246634105177634870336292298563102470515942642976648214528157455982603109225664757020091550414449178440472115353901460446268
366 87807512761131019669123968936239187378772472970044116529030740009892838597955402589441089059731825346348183259877624129805446563680453288496566314058216307906
367 245537829077557462081805831685248187855901611678405068758323753424431585375668081543454789249905741266414098458353610411274351872164493867031138938128923811548
368 686614878793290692365946544967060402435535533439703386546543223974161565447591982500008138197759562141079983471234903850797409958408513821168604305660233455976
369 1920065425464977040324811492258229712997831388944954536187026895473557682246017688375844072781501718600065677696568681677877698513717956212078409365696123045631
370 5369413119739521311056720267346543730592359961974707919525707549927075193415306869557412051089850170504998931658579633249836081815067808652981724838365477410138
371 15015698655075199976272693540591951974686627178052097189140504117200293380788618682016180014774425725189940423758616707837564049839054439038244580983396016421457
372 41992541273525656280816728152861921327282968075742417388570730872160514840242297724716590418591898627935767029025045814765426888230438006343622529004355375447430
373 117437451617808130046188436954085072439890141075163700595649694726378129352031098060028554827004529062795043051505437759166127676602137044028420695202260238129785
374 328434585854209340800737235202631048479389646967661462661636385280689838843051278282037131977798234542111589298178308943123728279398372661517711552909591088784233
375 918541776532521351454724481253885522834135226674595847968788334998829497077329738397794713874792704493917411483057346313840275225405419095759541352537427198471361
376 2568955991329503485226380237480690026457620304891552709544079697736557060175045666781524391372284817097487693711568229673638942005261714904270596319620459445473073
377 7184922639842464802885587606384993105812537555100932976724521004335615481127788471733279920114210245392313310696302660580629852175413665384841282424990274512998952
378 20095331213097242826563162272499766152631926335640382078466171436906227170028969073653693324764624153071420218919694803612847629293085720506187191280898163161455459
379 56205115000964715479430619822300149295636199494967750046285804235705714672057128797682804682319483130603018470221174104272691669435190474297594016851022802881775642
380 157204173871080042791005946717771678337361252434570214919197069033737233975532054514134984100074728607605448843429503324009721173077600035149528834377866256366868698
381 439703400811858555207639749643726653558421712817679422805771543513429103622860604933643940150767355269757140263417467587920793699669593550165394733491349240341674306
382 1229880900617123738697150100582819767140664530048573343103926649877593886795685942716888518384280768195953829891157101302209774951380318232971790780725003756440384976
383 3440121102632042079574613394421649270740520637604825615393031704257937458096065224440923093918018322351606881630669114742178776088172570978745260713419443230092125550
384 9622586153410285880728601242215813228736953178547030205700671938265580922941045790964674136785441869346080134382440299672770112153048801535047402111613597150233137802
385 26916417073868835612084046395717066429589754342172599151445996645973182853695742811985385571104615280559324692412532184104060944969040374899401596525144276063496606951
386 75292205017596473959671194546459881939425223139193528761923230931282225448658395453816549305362589894258565077274255739531780576422930761591566614827365864785744388371
387 210615374773386578684517006047492496179433849760360062115309171505982400240424567645729377980367191880450044703844070448199457434424447733296596271409138799278813628792
388 589165593539042565026821664726253771125102392942799570084371611237980668383862899518543972291941987174860430622620845291051584358900044292209062952024279357217152693785
389 1648131634367803359707937524405442419859146581867717423163925363504695800177924017679629258999831406080436972262726185670821749962455879487957060784659258524546455581229
390 4610559064987066414427050590937762145598052261340165536440498484715451027309887206327522221902752378407014621350941505017043523362673050032523032661992076158518536005778
391 12898001529190616022484918680061560268661536583969359034337027007145503209652354449213917560064014207287702364662015373426938255345873775474502731101617752214575992285418
392 36082644620996153148038727193256245008320497097861657913961729581140014845827188376920642954902439230587657766314154785765478870307888754802107259886317826893553106804930
393 100944198599027248783600823572294966728098367736287563685025750028398559174509674211748882662296187357779753297978614667703646499577995198827952979877028011286861153332753
394 282404360855276282716306438076203561991927984814874123615833082419342075073300818298143667783619353700203041664950921219404793198597337805332599891804349037634418093688990
395 790075196968580287113310427568508296534767777989983578958455239841484146867900273312870931943399650187650384519148343602398017385028135462146727009392677651724149009203100
396 2210407864644557643077943428130036115120005355005863034693962386953303913777130833664505916356588804136917108572166425275703362600247757560627546883653191701356713724881730
397 6184197213841155963141186936830050316876429270782960114608113611454443113269768822881621431873473199159722369366346768263832565030241083004062489507422442039877756049941418
398 17302192284358750361786474763512039709932246415093507793264284194707998216570204017598123722561533418066238564079099555280757068590210544190267158733975378120143529011121869
399 48408964478720606842334516835456503133891009741876761610509930173984048922536882285498454923654304602541207830033885488966200458238451441698474624088789395574264007093221536
400 135443220636981399994430263118955670404849053743512266219798964274651348636218951062787429358223371361277791236256039812270730583793196129114199348221358274867143490557738328
401 378961890510224587569566655998411842677134297089260038876458238638229055545809515163409480094842115984755225020882928808762277385061107246292620066217371335189839256602213303
402 1060328799527796787222598339931167000208396813370163594230643943947688583463969446349509310574226512421543474171708182414556560544006657534805443950509050237412103119784241027
403 2966827500438017966196272821500751701435193621918452681834143840775808934808121748954280576329936166909795819651139559023393628300372149591807874889041382961414276711325083127
404 8301388147622077303436735958992004021517158912757903546117814861761961286642212993601204978952566450658646412745606842787680318691545681444075901779595216670171932018840156290
405 23228212920137197019820942610285680773369010452318432585529759033889251185186142910113032696833229809848463162415175535690697164862784647828492646710089206718128497417272167609
406 64996129638352050440843829288503357383792368058408672417856862732213424091459654085381278596306204367057157588435899771537285442289030753397438750907636378942119087740428995934
407 181871974514312058787407127315167850202573331626084538673515841562617666603022499256980441524696015460880522623759189784104442385498077959208069046099122778846279941296315607302
408 508921293889379994459075220441095072936705411037429540662998519808455715649194294354896777470062777665283379251730640643916798271769311972019715142166777508673057182083075439429
409 1424104919704551370931120477105438945719198975965445860802160045382994308137848033344213193904080353659290651799550995830635165912211281014281176050241988912974508156576930123512
410 3985105674119379719613473023083433865228342356444696693071449237116824150440441252010348086703299231235101479003372267346695772139029905436276139550454159690445853915134601601269
411 11151779080187371481231992741401770017872829181149322195705476953287512469455988910839841754572894650021155474376091541134246064933106710984356510400939913969212295793471876146513
412 31207206938926983067147727221154068167887772255436498988153083289901842635719116116280127591607768984050467628939465309028297107637008697100529834548888032231317887477485172806549
413 87331725585020938619559624374688440661539803993897909449937112117444074793842275272099711088488653448295819463702914281156863262753493080365544876458417287285003055222824879720780
414 244396818627923436543044509131904409206923721658156467500754855205934102852186813605522163506104956675950752865215720967269303856285927832484052980180273374327953434476871534413540
415 683951632694543479102158116853589042884967771893064113437642546713263835724926513576081730012152709764140453678491826677943135992928873094071770203921417873849946088253924179804024
416 1914086401803157252525483121260321559895559007042220486892482735818107970890133725779443699914357933292788488572628644415573014078298882567354892604501998174591627421637960341350958
417 5356781843212895081358358702304209294802606675851666570503291583110817229110401297205001248101478494597923305522097774360666328503358045010812965713936587323544536405180531722405525
418 14991760191098191810138884758572381033980177285519522538002929720069303179039888962564813158684732183212164813120008802003727947967332417301966653502367744259640522679982074240052935
419 41957297583977073983702363775537276063667525934586084972566377077897379234326941152252308316248314022743475105166365682125455479385328973837826717926371342135100033396024998999711450
420 117427164649003110142152852039309150271542231005840042633270394358905870024111027811834168760888092684365398533085841898319052996537137409148600044897766758306959422263805041815035065
421 328651634923820753593213641391615586245769269329135515410723721158590485927853206438291653675705669829844447752566275324876757760795171712027718243095981609198053940152414671545372503
422 919833338235055417852315527855320952122258706367356027362166805853019201858886407226970738663262056708085068659591296530831817876141948320695715907387734534780390267081213097851623926
423 2574474487646626632539287026800786404743596827905521895518376238428706085102089551200246220070600149447218837788218132341157680996167476365296697212327216000519534723950623014052562902
424 7205665667592596185493148013569520321002783567886505195373190949113985058687961485034757755359307774339390881649408647759537333207108232331072998897954029570557671512417161804939366569
425 20168131434027562204440255506283465875389862304407698539108424209996440684182389196069743314657438655440573946315154127658616978643901056314906869018127846612726971718400035968749166018
426 56449906899724942047505771637510301180460568010641046003667211377067455974036122730947794173621469883426661320310970747156632955969753852875150630047276376711346998907743979302070281313
427 158003526673335268129040271181964695519126921278889669906317219204139766887778977957695566072127968587031601234293405692668000075925616270225572854068950838825908224968159082404106015134
428 442258599979431848391406555229855427518506100942056562122348962514620862303367256139977453548852488681085930719342224041746947531262397172450943200613952242630186401056685133695906260262
429 1237917552017093850402076044531591942827017686420656648424109421790021634509829111059302648772027906040585297174304126581227216116155207043835665782778612934737290712605195133819856519062
430 3465078315972343860372538551750530713497922627051904533821996681217921800615373684000895297305178899415702486014119749497882204026757269809006284940463844540137465373894929009654720484680
431 9699297080453775101320815109284416331144463935663258526967517831954608850816900683813652316638254077050209765141440151807366826086817206175181202087389875138340309965367763865501728571109
432 27150217551505555618139537163164507176039939439429688302804853725238852409340703442794977612087713364134687732101666077061039800269026733239438258751217609444333185068116914514760083583780
433 75999753676480301561140909251306512576996597581717224239482078114539914122206191832267711131022981716019615815229050502247271178827064651941512819446443447663567423910119154532928248808854
434 212743768078542227974107793959413118191783320144200906112511129901557100484433846711030090775414576479874753603565609429366122326437075693794662936485348777801553548537159522792800204843077
435 595534978287274129557815478890999237342639631710933231600443338243697446238420359116221055705407530695255255797186958373488510376088399011097968679804635823714838510606176210103312556282938
436 1667106866993012009738048724203648847789357812909740555893815853100209249219093911697525171181338358328434883594238370290309396230294400217639471162139187473094991023670935960149228884691264
437 4666865864249353281320078704012934753401737086940708686290046970355274011817607310211442075126178184544907153856841831290286920471585179851032823312901592316896275923306636633382050404951318
438 13064502691465503331496979509263442199242430738722467485716986907489389337535512987298869418780872092794140927836899073572169176570423540838225780325840405386914224765197775158869935886132308
439 36573464941519815016993284926389744686128467599198825108604334301587908700991438757799778776379591537809204577303961211834736897473197458725391425399805708258283780845803472483724829308499158
440 102387034801847643405549008400637176298875981552734149229523842867835664065407550598592377192075769357488060245677070395752593729565915415641269251338499244754054356422434373991804100339787288
441 286635141072427375498100476108163220382497481938821125132296034922046116539400243866662134416523721753392885500770428866803135350327729311308050639964324664322524296915872303049333243233063371
442 802452776642802578771773060767748719046097561968169463921460704294540054428227580569740903358514433024200099533415098775392933614644896726285044148154823247614097647187673554735715744773826614
443 2246544849619415890258046612371209088300865211635814214012511886660980184034972215928128019202338157078347229971946501155993356014249699956150589573685977100473895831208624097115475682140515410
444 6289501649225784392780503335689658729084771488077509996429501874287761786523941153941168420274740516150624301548765385965904919326602368831112994391151449282648235334602397423236251123942812603
445 17608521245602370453309358197667918453324808965805288184007046857140536249633776335160636757151758073188473361111351872831488595346484114648956040900886318197179158362694883652268082653203960816
446 49298649182829931269442452247690970866951223239512451041034523083646912273059667920120855544709087163739440794611655242580540001201556277145529735532921198512078831709982004835590545821624721675
447 138023365283501643172120627032301339872263876888267855443343545360854901718497319204396943648334875257424762335797402282634187852240627591890657376377438728045938810213212753434013616337639224457
448 386434274916820923522164046982004407665830730281302875549681979670777226707924140937512220519082444542354857967666896287766781877598555642605938623019886223086785663905707716066803911411286281397
449 1081942241041412843342801306377314128938595941226709615758725246447576837849605915025482480987589675194623011793741932438474589622478261973242320151519896247629605039690847316507789418134456637827
450 3029269417768609765160337407124200015486163814552893282843251090687250165489257362547243817113569645233746058477828167223523132762950235399572506835312237226277164203152272356102034536019296391294
451 8481586318311385288734521192920868467270039534541723644192388612007264998860540345100785093887970292666153225114424664452217056046138876059684378649482048761623829799322843406423777308533920219070
452 23747703106104423014325258140304375732684986550090578217405234480462667752274794237666234812462575613551700288282266872421292080146767531632383820729064228671469763885872280565208337751080593344999
453 66492314454280637134764294178457217478862139513263475578987547070484513744890443746487888749907918088417362565230487121854504280334021532192009371637336497822869058055985634663088967547878217120969
454 186177237041880167250082703615615906711469226006628683330015454509577099494801180033125853930416036475328346558339575481998626950999321652099880573706898734989028639251899999393194339425694454345799
455 521299105693071721134346815801917273478090598105738978325617213178721952761963650686896186419028455325103010511113187858174012474240131297963986633948841343459701163951657791742336745183846908202693
456 1459663082035342934887882781425257110248409976092170592292687001118353543510903639012142254926129620397281644788427969861856196397265614060708111086420781518554356664201230646799774368796497847289560
457 4087177417055441441926038522636669779632975383455435861702787829487050730647644274243796689359039880995184808595150267791772426267267595216466519189659062251522097218459884984685292035892709537318312
458 11444571992533113663092437880990068860482429953863778311744000646149153383578777138577579451370599464607353224136647353149403241554028448524921382528775644679190951320692142995225920894358581518868864
459 32046514239119535874557007189938336657555337609334578424470303607436424413038337983768254880878690416363200099465227596231806443533600106180349076033054441534432099244612976407280044552076098821403252
460 89736100519002389851198827841205289488930608401833288837431558806157207068707865857431660194968325536326825922036661750485787248488069036537183719134777585007115406330216099105020965250968921230637531
461 251280461467296852385574630546574386900308754696924319255811421905696343777953369172240361971576177698693495120548775396582903158268833375865317152528104410678373354372825259596648414461025206277196061
462 703647838584625032634850730660409028130392079000514964449801824100171552697792694225173476450892173048712804817684375485123450329584457100326311770211425495950916098573065500347826314334095474713560259
463 1970412174922793351898662531323302254183616229126007272286170131156249546380113862126766843599077305606654555049456355906721272812241518709542011017045667578674276027112987044616906273148370712324325362
464 5517773536559450183232340514258026490011471945680485508559372110766683981404048596720627842140536666240121637533493171755062890606815893185673601104533408355167110373867915820214842211744851723397569593
465 15451679990201568411215578122073370356403742496527885209833637937700223637979907251807600646374760670954350341779571360161674730998882159817422440392907738425891277795466982145716585006689968425505380119
466 43270564429340265025283937524300878478501493530381291220397194282241171515447134894215109317300783342867417360199432997982875302235206383259387444427698315762380570352312116615363155703009920832689352871
467 121175387073295736524569718822097639420463861716971063492109528962492569785076732921975740253331081548338333727361459218154437136082325290987001985839144830920858486257553315470385995502530184051873497066
468 339344840189475536421125940700761759628752222992160549381027643941745741914656836040232730595608192347759637830477587902350052606592456881569785539786928879480686510907084881467566111373965693128772815168
469 950326942647405347844160146627862711768881566137164131522937150987646591788240557198082994780294550892371568822419949180800659521354470469743632592095655784774066429590870707610663947413928541377601304331
470 2661397660073852552129723028095885797019532580891659413666656327685520361494990644244780459416494337505306325842984790687846760034636266016838667025621454787635756967010007792781115241634931034023342955909
471 7453348271319000807792642584688862626586099412065267712592599510401797049893846344817387925831913586906215688069450852737050111320975144949815225427831362617279252934288022295734101068785815612716970311808
472 20873628693465442369994091580260968702372775440196031927070687104083645990021388958800099647202094094135845379561614782887105082175039614621895682762293655052254837096492726532427207985365110705700858185105
473 58458728731766254613260704634770549014535819580818340519042652762258547931670198980355298780573863556078114808742211556195563024034089763095349562343593909106562326371091563375170455486291957378525618197831
474 163721469153385637408150476563293561192630360744595190990592087993468898713335977248677815933276982928116057236035906891546690927202148725585574081941714037659737484743937984394080547704511778110792121687207
475 458528920077354685502169678831532604357019434399108847894808896709351443638466718242161166503349046639203448149470195902534259098807880444564985003619318026651644088082419427990684019605853227416774184858732
476 1284199937356117010353036111976291463604172133918493472823892597653505936748633559438891259654067719601811837856803850228207178704881159679844950373205860758636370584332260625151603176391842907361800288702852
477 3596692826870076496488870100810883119867190535450061805109321868771960959615817567820544952252639528684637338431882866065151676205653648613261366208363844491931760159185397360397157081159998934076146625574324
478 10073463693660743814830768135279278537079909784776055480865370746882390281411517464342747341359496246287190961417525136257220264919874937072794203921533179745349010643055354298890387265997799866799848104338235
479 28213635719632829111553766945298618684025617913525005700531345253000364443673781640156844004227127409788826310407619909467100939134351426418260762969996556114029193750675871742395710571704344996337919334627311
480 79021272029812529198306048278738451404456552316178623835088343424900929896529145986849511125817498577910188475147844537607285370369164399968397118901967107253074866629088624713978766067247085915460907203507916
481 221326640007559663668965755167218010334237161338270139368837726672890339102089097625270467903768037212482685022578414146878493502591843464527824997936161209273201301931996307060804297022524160462260698613537211
482 619909167426938833226794412160056195934133884103637737354763534557844211624630276625508115154691754605800841672755247108234248396654245317254494351293449688401442053466436766136865155607831934082917347856426393
483 1736309336940064055314375159645968597229131182622025720281597392750374289881332068277426029158100061555043458510124867482152338705144101468366800180174515094346512495259376551669075968372524272389756751432854853
484 4863297048468267534636166312939910470952766062828082277824505171156300282060030581670231761463878726184462085106767555905935986480934403918197493275089839501765798644464700331235805831873720464298566133914310111
485 13621945190301700706138963992367401939405566877527256386624696446539344800813487799938840805754463459615136581585117531096761299146137690070987761802590544736755857013785633546389925702052333218769869982790548052
486 38155054329515229613775470033224877184200699251781861664268079502676128352861614648198071275587050390975562955844380056803299861976593575165303651531182196565505294625797093250325990896145553936059099182468469941
487 106873398849478133039914184580874875231786272245238762673187219575665471269978868235613615591616484938408255629005435265191765938106429802557895876693594503003511545832633156383000727183561568902367863186683667386
488 299358603826075402277899963139952216438074968330347955827805421649062237131327956205363209204249356420478800321507971357294900909553107391222810893361186943113207800413096895718566298784120554090436875783734064658
489 838529657705833034226462835006399865426986819335499347214210855084885678859732280609017110745548560768471886696342486720814635172359590192655917206826346091436208169907230087809358382454265923070116812677298151128
490 2348819542369503943745770103735793608241357602923831591641116837956213501074463807697474203912578951142821017553783252607800118192578200768970029556421579893140989343065980349644833804994551495825731452145526250765
491 6579386479996359380652505811548331172430892668901276541544233471990370985480393191871721148991766536717220264862961217017435585211918629713359048858315079558167250616463096722818683439439764375707901662500150442223
492 18430013297106462705563823748850922689996624541574571380773518214465413984005545896077127791090690118569929503235833070046114981151702312880527866333379163449235952921156068688050620988293428148558907616760764230182
493 51626226783162901884788448815927116139784145435568714116360575592327600891647514042914267976366137939193067990947983679977241677448127920019074746593823496272420143919124413908756022387549336194531782497745210053318
494 144617080122147701980280207133464988259100003413798968327225643978306456666956314890639498978440890457630421021855428539194342433864427806316257734937387813993364347367110868522308183407058843998076264751693102167102
495 405110259662180001404402330891745929672485944541334128902338780325351363683988833428262927776387719886899607701108769883875334759722976317523430427909747225193367590120906316894975981073694814441448542441371959370139
496 1134831355904717012865001274054429116248775025280754969468716824949667862347555347996290225366000942364709536217262581087333644261895222727600153755613494310524232705702001879535164138079533205048872360533370572443014
497 3179024139613983878848518783709510209263571759925674510120249336292840845927230735400333746765269611853557998210338782704187073085423815480824362906609395745543530469335794431219957388926521344251394881172155468218720
498 8905549466780876642396073343654258905917693028466999354614122414334803973053490695667380301725459866905052509157458138657523790806693604983304945043446074074823147488033014740909049433466213254508146498309733349188106
499 24947785035695184159749164581713850084342937257706468262391560672422449715753806019752051214121544475469837920461991186908900888093113539339801359611535867899901287200789925164011521414091897974716359811774035382416687
500 69888806977968318652007568872323509883145559195919337637376568556764896550639165374194198834566064897188044072953504164443147167221896769574954040005634802439024034052447587053721967608928388404735140565376686372508743
501 195788691591167358983391697449037971940030264992640916356261226388550228184090102380273799313853791372688026208122257167117578777323459026117493349556753561788856363822885976681867205634092580493325710364904047588782531
502 548494032946436495469620611795432979620763461369106146549869347798577635070861996537588958985456038738490074623264997230333113526957977331005103506330698269434761435756409311208727307430024569502936206334553694283676634
503 1536598904504020022390182411725047622200819847186681809932497847822676986046575419040245980552330718581280600217997983244508065171419798533850912230390660880590427418403620514675655804742184351964865010834911870260532737
504 4304804399696237237507463761025719027368507839779837180796834025304374000283519921714975073048412322678796133355944724703959888901927384437117293324439590274617544550675650074944617797896522994225668856852390729039132854
505 12060091457367838356213610817207234492788918818485067716307605848734397401969983569015491356977123520274608350782427421607680673607611421693067241201544491744636061545720805042074071705277143768237509563975581521481971744
506 33787187151401359474138248785114344113312671816443199831447300383553450708584370216211336875384723399889706123181744528180234956967328946497287340103298696637196990369343041151384152213862740349556350988246854939570357460
507 94658085087600767191814295625767249595924998256072418807984205214517757901371372122612009197699848176311901481271194791454722663092510105871357747683604714671675892751969983638228197725633072216463700392042188326488394134
508 265196394876068538373882629260283401265291216082994401252529458513871580318500770697711905539654827042665184414463166697227923698966383149290066454899757132953798122218684163429442520747546194624074319341533809187955859850
509 742987872327542939782616463958400742805603198481051214041825574666488856920606250928581874241724462792461629424623763690623204714770029065303797191854683567405043220191095551009306245915236192966672841365430534911831131941
510 2081613160807052627852671106429699815346637106588558039549850943282344854796785381431301194195553809491424445009953316091702948592825818399878585803321563802098469325842437856189296223605845914855517526617036889123791916879
511 5832066935792974884467907134920571271897853778052470885492407657804476350992729502794437759057956535540384995556877321698401457926234137392312868296040813445628205937149453084385402716294640357428781165896966449684574454361
512 16339890167962447114698099986458863352206177083383900932997918005501783478563092435529831406801065305291687696314783303059532484613725570916382493884546624303413507269714944392090534814565582831222233859429586344081533623241
513 45780434299714465900528472125920725498064971363403795279045937481470113424325181182505262687930126114077659876437271891333711756627584325630066079172781399287862623328125519649485377842290310077120775093950497665089366130687
514 128266962310953974817496160900699691497973827713233238862518018518153845134405137336599725997863436033386936752436933102935100419014549625516239149651689776363494280982666232916940899586072745348967003932355195829652710565323
515 359379930993429264828841632427244309223147010714116927910718740188846797318879347570762566427252001469939998654930594986004094801299842961112093140981896788981026626501686993621027437750157900308470012337112622156560636947110
516 1006924542315488374500853560606537597587628897577216253321035732074520962650385695695957162041323200214214989456931729021525131967461613489483575393225063950698261368046789785512490836183019178363176483284998222852131260793329
517 2821266485261678190970175585995599013302402666565073477188760415313469345059253072487099276926742680217597162061717288831991636305900535562690589744681682822209861817463637168946441775672540557108754665007706181417194852743673
518 7904881349656251061473987277087113441221261735694942390935942379504114520513016461328765196760949216247834315180133902874405614838577638980548097603486286719488897631013013645540201605430865161968047603658933276895894118126577
519 22148822783476459665161239520326747892863972254121722623165980783450639660107999871629236134994978017405408286812397246138293987458554447735277276332009520637564097247635625196663974747191523216939685776154127668063344206727515
520 62059742901425904629338150724437488232533191831824171835399430762211865699881006074035063307010595844284819123816004126700235429376699704613442238250638578034471580678600448677946228171430160413252521269033173497010829305310070
521 173889481103654993885697912180230847109956571064408633157840864019960668444788394597848388174035112832058754118840959218604629363187380115374538541239969681456462399851049935709259430469140038092416800099936809837501548629419251
522 487237438353510461480322055175216685358453440965503679089110259244098601622481946525987154583247290474495825110790428232083837065845141230995208072661400874125847173599395779442881348010764780130289373675407844748825375982291576
523 1365249341977970463286629534436802597874909462165553276526036533935380410982365034267951544109405793394976898112548175325365716440901089833896913384181543565844061890207485518367244573267650254673044598876870761459673032426572791
524 3825491754932762419915561097537121564200743271411781620746512306663469742497358308861993572741066210926122399635337243791511129258811126187919571241817605904443010401346719713702760894877466325186307517614731894445947894796767114
525 10719302309878652380384516356382166639006440998188516638004132546072910806665312028794505327365735543508251609975945836859111394467645220818489365630282327075608186191418644287250242839490280434025629012415174874427233644792719126
526 30036526459402062339463395705693696485866208596205236429655914914106224348466112590375499803794725589039703740454167809009734970232956535563557834120671943961554465487325495175688210953272246053057252063214625992519724954037612961
527 84166025782723224095384188649790709148610075463432507426660325284564796705881224942036706561317071843116699201695872922866817921335289864428901472097479476719671087269605856347371997124934383552502396699362196988401346430646747006
528 235845635416842984456760777132945515856999196345706521389832909973935764210127671873134402454473246185921537102807505090269863242522141089414715962011039922723491733664638304673495569805055060565311063722326422751154200368631923503
529 660880231379418802777405081733926492570382106194676639514531412541032743121901858634475519373238487979339786507626766650356659413373515413279306429681912200932474828848682189973033135004565071892737745753906027827392728494556608253
530 1851917173296694678131177893097318031623351289196824232764870955345929906799243777446150541763007544665282692010482438584242343759620431067600724503315950171790180289180547484654739221490877726046711452233984632302850104520393724054
531 5189484539024974023060875229774459591175978879639211085596012701140080697953109311482167882706819672027235879767680334343132237433286607705575186891265480211543746643225881080885049561084461898859029632641541226282584718381268175284
532 14542220879050360468056495508039988477537129558157932975694199470190023232596163271638005095632655623681745060401562812445232701439964105915379192018753747780606081564529607769212580629016695103746761378973852075134397600207239056838
533 40751264346923384786996965333315471839035647346221284958868668144487725863041235362546027668216008491814785443004899010486870681224741576355160079456169818039399521103425839936168704536127581475054701011765204921022680006656506731092
534 114197148770541289129501657935967570120831361511197908446708083121615458350973234981741703062009747904717372645816351932083843518152909894099264366138522196870140181674523295392341523113827395326268784477436847600723381666850120301704
535 320017141527120548155297412500771871637046169922477155187755780091054695713444846561482870121158885207500121060459631775307006125397162661315301295022918385533306500201241016332699288226137659172385531665873544082877183260065443528563
536 896798795355927088583924740422419682680866663505270431857216104966363348283353096966112641466720640187665375866913775151778000064499549604147786887710103094823085924825063852439000077995374899965278521225209620423338100208823243577255
537 2513162496805305924994652929028227337900741303359422401258394445587620033563645371499586182646472574653524190122869992411537135046049723054704744895499809154948562458828371717215723933400837612554282072082923689324233263977702545335851
538 7042873528789804549023009429718508551240587395855454959447393625342687774113800208261550606915863764942627597293039530062620372289271654245519428805971979154263451098064110255730764962829489726948583677142406488354501935599650602704947
539 19737082687673556390721352264345841632628535899939477532501654872496250958883076796995396819937848508128319714087260948961412388238084295158556424245451789499629020892332182754145418430933844036596506680814926680881314886271496487397407
540 55312051809619551602032016880706543547044952891600243538996187044388577634128367035421891948845733143229655367153402733360285007971873542860702416019445927084453904646813876592387963001229881246292976508105361557214351135048699246219811
541 155010208742753427903084060324542228423870932489178221998163352879931170991350276156041821048277685181745196403821699135825031110010570548889285568859124774726102729888006672041845309890610453251798090166517895683828928695809150847161413
542 434414730403660666242480686151710405338291484348230483585265286431580631267787441681318931026972101375430655228073093667316312547851635688536686416789104596367223363266070786304645414433814791288332340665282553670531128654338935303062710
543 1217453777306053121974148130743827857250659905273978704087466955307958571108154566599556032709858439461424561321924541748674579082931332082048534393583969471373077566005250564194285092637693793477193025827897246702506377676667110888003051
544 3411961346304902166996546829236508375915661135096426152507382266780566115714464209731679505255350530297089589812760894910710662186652736515101681004796684951420075002848722945527385446694615063405612261948513249172344498476049032727368932
545 9562234557956215685447778971326839077971742508799397524726224980913770107542561233642537144755707764084441929855861338353411285576179719342733844867177863883572857211253257918657829949918268506597671210470859354038320983239803717948367057
546 26798984551944683896396972318203163300857663084556679915541460368274709450724851926215891854335257456859458212153626677811044926821774459229820661734053511910571785044003105044189638479606205266225446270840351353803273506169309471118208792
547 75107088400900935171428085766875460116078467071158059355550247373382656732937588776182338864603196235423355445938774847823000176252156320630305251715304955734307474521217572362374380356950458814490495201942851073681363411572726197723049322
548 210497597569301464288882416746271630627769460318548424487398185389081895427856735644325921548229743917952363214141905170334974750650776035004471387484354387432276219557447934141967586167564145736084901456735019380066463037900443368463750529
549 589952405670431312846732401541380055186678119288039300689019939966342269594068798076436018655794387803242115875612696777183707618498034665222357698402861839948544106654631760783965089206855637695677614562512652270011965573212912699150222306
550 1653447507782337854669859432138926115896644560678375475585702833879062465044870860669782613832197058452033490028732429312890629478909704586710851380721604876336726548704184794379564420818809125170496149758753891339593223873980466873657808675
551 4634121720374734876640015591275431220573719131896909689366804603883699372776723472237794656441957894804197374766817918202390675874135373912188537366950018228164738740572376864189332528537357341103370670904643559897426782873780924694404549952
552 12988172209958629354976479409887444232123870744472352461328494204014704070828026244185289280873080980631066297726926833848567305280970726703561881224727325697331320379610683962327265822755320616434222212741773936363823808982553652267656168868
553 36402583213297983893923717735314224806825009894247086975969745049876671625637320995335223140254138376863007565713896028681823975541880556241201015294981361924817665491211717706449102517872363313475464948800527281736167326461314836475762602132
554 102028128150871389624662995225471385626166470585516654271684749249146725344283355732835385231420923622121533361738287147345626269665983990682230430616181913975846190453144484442659897716807859861528370360657442232122713556070577420285383208688
555 285963874416020847109389094930639635310978070371917574848163514539256031622688475895043236807308840234385196458361427522717331753297967827774160725107466211955626920606425411335024033340578146198527828288903709377216287155450097973101513931048
556 801504474479813271309133372006480815774341489295873255358450479482345656539199652283517903763335961661569446982675025397282292830860672634283562452027344063269331309337781792056883435784253528457756731627198813595711933244967467670299374114046
557 2246488720207418329511276558277129470312106841874831124509410961099392817867249483985459588851395061897990263510836956434220351808930512362946163237936078660073482552772671903962215951191588803644208347288874453393266565443383162511657234118345
558 6296598959643092242021079585551078329850847268482171525470064761779801868460108402966668577295804134857293593759745117030878010004545736079682629323904363192618015053884473822270672571028721277391455244118991807746061002383902058418497875855719
559 17648642730266631868292372424977116267164237749404494221290915860131181882432797360164844699371892654424711605839763522329377096378132334711304905157957787701392734323958015971951220582183536590796265168463226513526448874376764310281387844265925
560 49467511648677843282150463393198182539660072909980483113248490098998257026549030443046473466516779500401900622056138457089583290673236119906693645839379735180063169334780902343519825146748491893711455668538850413590648271587545146478226087608088
561 138653960839720237780903529828886134179691393692197687961957505041394830362519491941711098742262499248612126723601317413164269527377101918721014795215731365573180931616856051047575192199455062578706819385718912289901845562979643787482220868470590
562 388640401404166726403604040849981573098393513226469303628837869996521785319521706543446407178328777717743373901923259217158612116651021164106312346635520946085334891999324129923894777900567248375001666785358736438720284544587738704414468904032120
563 1089349026371463401009368158207284707868138777281928593430252016526434574315276722928699429463879419586873781858260522963182861510174218509296474856977004106229622607819672469874387850085077891347597685755137100980144662073737174021186942689660110
564 3053441323563156856176173676476587746805206297444249491946613780577979509794372049192873666862100947279183913627112592173557057246256829321823438895271839470217698266648777542868826756796039640240841766865966822413852054415954144377331869096796079
565 8558852096820271775136720162461746547157423302243504173777592432887397654600479455464910907614603059047717971820020739888406164363436245821091289687550736029180777147833311398272790695986854037745909972157173521678102836203247861876126446623455941
566 23990807481507543363161119705635169223195483872753731231795993562626030819714639155074197774210088117109884822565992585843961866250403970561002968150135283942837164666422735496871886046653853601296395351635669654473996145870242254148487475307989363
567 67247725400514283441979337039015640682550676266572122233325347901774356639149525513033798919434539216083589575130443122562669309331966602929415277653012096623561084489778553727715607758071393441474715374180374812815472372801693951122572645561927972
568 188501022505615684981643115677699164754597350474195256056838146595177282144702175679897760845349918183759144278975953042018370336077526782303586476388543669978744010364213538970656378558771393693604806870918230917582142037940393284658036787796190095
569 528388293255699102768267980469032149927750544755411892116416888489381846695801228731476090820280927877733786235582677407755142595222187354458545616895456886946057362906637510923192846746478586898401249334809798543795790968101490955357548944689404419
570 1481139681819815984865596066119662646334970924597483028336367581391121951340303627468759478204423857870249313301338629009644743574956065854431325886381588648142897681667774313394610536579961171470177735442934858952609128677482450696112615071586842452
571 4151855116506668476194441700073079663723633462987242470405343562546713587958888648184810808699594843360967240724207789273501519226400493619246392208411552889455839912060087804590680797912338644051634046222148307123301178624036564900761321836191710011
572 11638357480345263990394090085259461185314769988960064237934836804925487110850655787138211592716050979856552696090052257943220978936791160054789403330241696199508450474010366551507612864466925270239152767446146366039050216218430677383776526207907402180
573 32624548811039863401037904007503284685293162205756830237882621136394392231068271280838341272733134688746658301784930533226029385976859586943837246137886034267907725333280479851554161785852662216907267193846654411745493408712732912484322747332569753453
574 91453565674803323768650830787276391811790063277550546004088694302628003182356333714047246018460967121395604723905367694772767795719531666793458510125166054851374267422730070214170914744385870914586163951159279595527449335944182886312691586553233544577
575 256365787336200929662034995821832390782901686928666874914069870370899411988421716154978333918736608690998878032992026547373667897661458006356779012690154706230243595830670415795736781249829251604726586760616697397361843738537308599671636128579766216782
576 718658845458758948702506099414021740112482114046088825658217733686793969462599685179137088238180952190394501163540929663698693688626584661285609749190141699964291053616343446908078388333027956836799572017270515282536504689083312961976194101462009359273
577 2014599660718172239358116605568856643151694289592073184425378273339989273348446339530727067696215854925213852206846102453349076412870365759644605659609783655714495452989015512852782223342828697700975206316701023605719615208342689777480895652276918504978
578 5647522879136413357043724962594194504509633277832144949066669490968478169978265556931566259002219427236007284245775753982950164107453385405960196151336248322201999888483166770542105522061775658707061620122677414898163155742057815886196812402259969187179
579 15831807173985862230107233053740741225612150185883101942540738540805830142634489058353779736162060565012145038054537756897243621466457330455955360553588041663278393105683723270458467556857755350606334738147209666024283469508953705750032998696854798882645
580 44381934001809692854756234269339315268470812596184703350405777120385183746883266152363516633876130125715212048430353040990333864666668831092958058599902474661246719890649315933844962255722663618054299097621520743489665201792451468614468913805975939827161
581 124418563451516717608159100241815057283891676377719678049022523196841786480992596032937228075126531995845396570532231756642367365743421776575398563615306941652795043493879881555454901683170515996805680559072186753736120076299373616446780086382772114931490
582 348792677349397309921528003866345863078288267128493115672623941522598776048251693732220755695431025178954502003908300766946990653422522409924817907661106508452087513434457878479779367729504982041734325073482182713922396135716196574656655917397176197508130
583 977806095585530428632890396349706483802108823441728751679077318093791239811258523588997322066823172053681534768862290564941339740251318834996032403685878595490338721229316118276427225932610752806672464800979531064027120225560291194836902693859291591304222
584 2741203745663437197736966440075137280851590485930314314587430580429575299512638713863969043150561831257032907715877401346996895296371290810703263836968320712939488378652866926641411909003873930822786738931046101321221325518315503962888376469401885265994060
585 7684808975913748652658967209307550026523625275725094128438468943922610561207598683967435518752918768168507923564618394072959860767215524485283100021926457609544261438530080673308562813716434922652310343666831692314313814970864451784428183836630928761650925
586 21544082791572906374946543781698049780372017958131916803345812602051605063383357232769995526919572102263994075038577092961024866879890540209628195098351235216405806648226367194569995759364031549796794238451414851144853052277666188839248681656548840911976649
587 60398493203123814085741196048964149458512214037197668589929833317931339018583950108268519326289514738313787604417699619567516222039243832183111178975585132940535614925187936726455836925903379425771368882224750816934541830962269930208271296475299926097625829
588 169327443006257573936646668349993867371898008622610164830955246279443424780534844823501342873267243826339934580783994073161973066663427908757748662682726366130882813806141273920032882868503108969241638154455553267567334572303893084865937522389951076285562747
589 474713668677088177094489482816227829504214352031323328270852779360795018627789537625498386079963131140368014696147596583604174811662296316215059880117728254587970371706740754712461820279546896203566157197971197495596350292834179333673528205132035438250223164
590 1330881086420173306472948842759034690388910835295708974701333347660281670372459868081546212221113168910799422984731503469641850319057297334418465703665451344306647829255276929453191448457762628094479367340404299426294764351292073296725138478070792305441994538
591 3731211685853046312563549804130192897894482665030016266213087718612969311730880556578228029440815256686371193612574126989800542685829595776767537625213336082451094407407753556113939616300924932057250588551086212328579069506182741208817570498197312000742027368
592 10460769517069739123687359810990316933489754837697607563060284873467767539631923775688564129175741466685148807938844948747499540214329998412416929773775341634383236367254529863598273698602704596025443271552973353883471455235251012798519258800836394435256519692
593 29327866858198207273574697780347354356736116274690885262860503347335873300288784621640105014427556311411239219193699064303605837210661734415346483263614357407858009798534956262057005804505509515500210664404703260756759631826962240762669956817971864561833592337
594 82224341953171929187993905974962398928689723174426292533299121654485229400096226495378345033289635192763405369603254224997947459074546576024079725573161809794749764393919071879732548335769111790225907188986528941931947672807840538706068520494757531062918651280
595 230527857674048343225923287378916402012939247063362423388045806625032470956505298314548628283027281141067660946488844016949754327695750825324231532143975797755830364765752272082152457678171775390388816889440647194887750291226936134708385231454852335253374241748
596 646322818871330819020026678859151232061945333744713991936981932978546339303692997493447216968561755944917675383810074482696023111390775261108373960890978770059536587716142486753445394021006709484586337320355689424155373151867240261358068356432336536173701295311
597 1812085231834964215986906286863558635801490208069682768154934692134797667605615863726859184203234040625899662283570285824836621732282277052641805198110266692539388281482866732375570715791640627557951307341871938752994799577907793806283669790186478849153786642552
598 5080550811840925643349676975073865244948497511823204612517164274084436176208486664180393520748149776872590054598605859910426770644290299687261305357381604813070954512351764834513332811381108395464045201934843255479950655358013934072061752933652412745207762928593
599 14244460781002294316293074748972676839717294390438741914842858681346369082771919307761594749385763933292062997927147254167820081532109568783310795522655235761093743035795930250205460385764201602882347095383486593446651566858974756939480439429601195323970185730231
600 39937810748209753430512819297411285489490181966942130366946252177280246828533288052682458081457090995010644569965651629864310293039821827595701938168213375114735446642304994845573628605370612685047772112154447318646467342856791534542089457868883373172999304809224

Ruby[edit]

Translation of: Python
MAX_N = 500
BRANCH = 4
 
def tree(br, n, l=n, sum=1, cnt=1)
for b in br+1 .. BRANCH
sum += n
return if sum >= MAX_N
# prevent unneeded long math
return if l * 2 >= sum and b >= BRANCH
if b == br + 1
c = $ra[n] * cnt
else
c = c * ($ra[n] + (b - br - 1)) / (b - br)
end
$unrooted[sum] += c if l * 2 < sum
next if b >= BRANCH
$ra[sum] += c
(1...n).each {|m| tree(b, m, l, sum, c)}
end
end
 
def bicenter(s)
return if s.odd?
aux = $ra[s / 2]
$unrooted[s] += aux * (aux + 1) / 2
end
 
$ra = [0] * MAX_N
$unrooted = [0] * MAX_N
 
$ra[0] = $ra[1] = $unrooted[0] = $unrooted[1] = 1
for n in 1...MAX_N
tree(0, n)
bicenter(n)
puts "%d: %d" % [n, $unrooted[n]]
end
Output:
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
26: 93839412
27: 240215803
28: 617105614
29: 1590507121
30: 4111846763
31: 10660307791
32: 27711253769
33: 72214088660
34: 188626236139
35: 493782952902
36: 1295297588128
...
498: 8905549466780876642396073343654258905917693028466999354614122414334803973053490695667380301725459866905052509157458138657523790806693604983304945043446074074823147488033014740909049433466213254508146498309733349188106
499: 24947785035695184159749164581713850084342937257706468262391560672422449715753806019752051214121544475469837920461991186908900888093113539339801359611535867899901287200789925164011521414091897974716359811774035382416687

Seed7[edit]

$ include "seed7_05.s7i";
include "bigint.s7i";
 
const integer: max_n is 500;
const integer: branch is 4;
 
var array bigInteger: rooted is max_n times 0_;
var array bigInteger: unrooted is max_n times 0_;
 
const proc: tree (in integer: br, in integer: n, in integer: l, in var integer: sum, in bigInteger: cnt) is func
local
var integer: b is 0;
var integer: m is 0;
var bigInteger: c is 0_;
var bigInteger: diff is 0_;
begin
for b range br + 1 to branch do
sum +:= n;
if sum > max_n or l * 2 >= sum and b >= branch then
# Prevent unneeded long math.
b := branch;
else
if b = (br + 1) then
c := rooted[n] * cnt;
else
diff := bigInteger conv (b - br);
c := c * (rooted[n] + pred(diff)) div diff;
end if;
if l * 2 < sum then
unrooted[sum] +:= c;
end if;
if b < branch then
rooted[sum] +:= c;
for m range n-1 downto 1 do
tree(b, m, l, sum, c);
end for;
end if;
end if;
end for;
end func;
 
const proc: bicenter (in integer: s) is func
begin
if not odd(s) then
unrooted[s] +:= (rooted[s div 2] * succ(rooted[s div 2])) >> 1;
end if;
end func;
 
const proc: main is func
local
var bigInteger: cnt is 1_;
var integer: n is 0;
var integer: sum is 1;
begin
rooted[1] := 1_;
unrooted[1] := 1_;
for n range 1 to max_n do
tree(0, n, n, sum, cnt);
bicenter(n);
writeln(n <& ": " <& unrooted[n]);
end for;
end func;

Output (trimmed):

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
...
499: 24947785035695184159749164581713850084342937257706468262391560672422449715753806019752051214121544475469837920461991186908900888093113539339801359611535867899901287200789925164011521414091897974716359811774035382416687
500: 69888806977968318652007568872323509883145559195919337637376568556764896550639165374194198834566064897188044072953504164443147167221896769574954040005634802439024034052447587053721967608928388404735140565376686372508743

Tcl[edit]

Translation of: C

Handles arbitrarily large values.

package require Tcl 8.5
 
set maxN 200
set rooted [lrepeat $maxN 0]
lset rooted 0 1; lset rooted 1 1
set unrooted $rooted
 
proc choose {m k} {
if {$k == 1} {
return $m
}
for {set r $m; set i 1} {$i < $k} {incr i} {
set r [expr {$r * ($m+$i) / ($i+1)}]
}
return $r
}
 
proc tree {br n cnt sum l} {
global maxN rooted unrooted
for {set b [expr {$br+1}]} {$b <= 4} {incr b} {
set s [expr {$sum + ($b-$br) * $n}]
if {$s >= $maxN} return
set c [expr {[choose [lindex $rooted $n] [expr {$b-$br}]] * $cnt}]
if {$l*2 < $s} {
lset unrooted $s [expr {[lindex $unrooted $s] + $c}]
}
if {$b == 4} return
lset rooted $s [expr {[lindex $rooted $s] + $c}]
for {set m $n} {[incr m -1]} {} {
tree $b $m $c $s $l
}
}
}
 
proc bicenter {s} {
if {$s & 1} return
global unrooted rooted
set r [lindex $rooted [expr {$s/2}]]
lset unrooted $s [expr {[lindex $unrooted $s] + $r*($r+1)/2}]
}
 
for {set n 1} {$n < $maxN} {incr n} {
tree 0 $n 1 1 $n
bicenter $n
puts "${n}: [lindex $unrooted $n]"
}

zkl[edit]

Translation of: D
Translation of: Go

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

var BN=Import("zklBigNum");
 
const nMax=100, nBranches=4;
 
var rooted =(nMax+1).pump(List.createLong(nMax+1).write,BN.fp(0)),
unrooted=(nMax+1).pump(List.createLong(nMax+1).write,BN.fp(0));
rooted[0]=BN(1); rooted[1]=BN(1); unrooted[0]=BN(1); unrooted[1]=BN(1);
 
fcn tree(br,n,l,inSum,cnt){
var c=(nBranches).pump(List().write,0); // happens only once
 
sum := inSum;
foreach b in ([br + 1 .. nBranches]){
sum += n;
if (sum > nMax or (l * 2 >= sum and b >= nBranches)) return();
if (b == br + 1) c[br] = rooted[n] * cnt; // -->BigInt
else{
c[br].mul(rooted[n] + b - br - 1);
c[br].div(b - br);
}
if (l * 2 < sum) unrooted[sum].add(c[br]);
if (b < nBranches) rooted[sum].add(c[br]);
foreach m in ([n-1 .. 1,-1]) { tree(b, m, l, sum, c[br]); }
}
}
 
fcn bicenter(s){
if (s.isEven) unrooted[s].add(rooted[s / 2] * (rooted[s / 2] + 1) / 2);
}
 
foreach n in ([1 .. nMax]){
tree(0, n, n, 1, BN(1));
bicenter(n);
println(n, ": ", unrooted[n]);
}
Output:
1: 1
2: 1
3: 1
4: 2
5: 3
6: 5
7: 9
8: 18
9: 35
10: 75
...
97: 286312976836850192359345859166390622180
98: 785684759853087702778573182234297830503
99: 2156596319845084996862701478402986311496
100: 5921072038125809849884993369103538010139