Paraffins
You are encouraged to solve this task according to the task description, using any language you may know.
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 OEIS entry:
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: (this site has been closed)
11l
V nMax = 250
V nBranches = 4
V rooted = [BigInt(0)] * (nMax + 1)
V unrooted = [BigInt(0)] * (nMax + 1)
rooted[0] = BigInt(1)
rooted[1] = BigInt(1)
unrooted[0] = BigInt(1)
unrooted[1] = BigInt(1)
F choose(m, k)
I k == 1
R m
V result = m
L(i) 1 .< k
result = result * (m + i) I/ (i + 1)
R result
F tree(br, n, l, sum, cnt)
V s = 0
L(b) br + 1 .. :nBranches
s = sum + (b - br) * n
I s > :nMax {R}
V c = choose(:rooted[n], b - br) * cnt
I l * 2 < s {:unrooted[s] += c}
I b == :nBranches {R}
:rooted[s] += c
L(m) (n - 1 .< 0).step(-1)
tree(b, m, l, s, c)
F bicenter(s)
I (s [&] 1) == 0
:unrooted[s] += :rooted[s I/ 2] * (:rooted[s I/ 2] + 1) I/ 2
L(n) 1 .. nMax
tree(0, n, n, 1, BigInt(1))
bicenter(n)
print(n‘: ’unrooted[n])
- Output:
1: 1 2: 1 3: 1 4: 2 5: 3 6: 5 7: 9 8: 18 9: 35 10: 75 ... 244: 34576004768296889785887066794910718730985852896707505707076422305798138880427343561380451664648670542260 245: 96356944442415066997623733664230869603611716312377642117711752082444867783045964116385053282421589905891 246: 268540209617944059776303921971316267806082307732727328919911735252505071315985779867844056236080213000010 247: 748434113260252449609376828666343341456610378512725586135955779939163320693444008584504390382026391947130 248: 2086006351917005252913566124773054331962205157167696706926185063169623907656246841866717933958839366769700 249: 5814271898167303040368103945830220447130073898083466852225709084407144308593691069932064987528870826155297 250: 16206624309085062837751018464745815688226709117091506494175397665527493805947344857313038875654104100026504
C
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;
}
C++
#include <cstdint>
#include <iostream>
#include <vector>
const int32_t MAX_TREE_NODES = 52;
const int32_t MAX_BRANCHES = 4;
std::vector<uint64_t> rooted(MAX_TREE_NODES + 1, 0);
std::vector<uint64_t> unrooted(MAX_TREE_NODES + 1,0);
std::vector<uint64_t> count(MAX_BRANCHES, 0);
void tree(const int32_t& branches, const int32_t& radius, const int32_t& combinations,
const int32_t& previous_nodes, const uint64_t& branches_count) {
int32_t nodes = previous_nodes;
for ( int32_t branch = branches + 1; branch <= MAX_BRANCHES; ++branch ) {
nodes += radius;
if ( nodes > MAX_TREE_NODES || ( combinations * 2 >= nodes && branch >= MAX_BRANCHES ) ) {
return;
}
if ( branch == branches + 1 ) {
count[branches] = rooted[radius] * branches_count;
} else {
count[branches] *= ( rooted[radius] + branch - branches - 1 );
count[branches] /= ( branch - branches );
}
if ( combinations * 2 < nodes ) {
unrooted[nodes] += count[branches];
}
if ( branch < MAX_BRANCHES ) {
rooted[nodes] += count[branches];
}
for ( int32_t next_radius = radius - 1; next_radius > 0; --next_radius ) {
tree(branch, next_radius, combinations, nodes, count[branches]);
}
}
}
void bicenter(const int32_t& node) {
if ( ( node & 1 ) == 0 ) {
const uint64_t temp = ( rooted[node / 2] + 1 ) * rooted[node / 2];
unrooted[node] += temp / 2;
}
}
int main() {
rooted[0] = rooted[1] = 1;
unrooted[0] = unrooted[1] = 1;
for ( int32_t node = 1; node <= MAX_TREE_NODES; ++node ) {
tree(0, node, node, 1, 1);
bicenter(node);
std::cout << node << ": " << unrooted[node] << std::endl;
}
}
- Output:
1: 1 2: 1 3: 1 4: 2 5: 3 // elided 48: 156192366474590639 49: 417612400765382272 50: 1117743651746953270 51: 2994664179967370611 52: 8031081780535296591
D
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
' 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
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
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
The following code is an interpretation of the Haskell program listed in the links above.
part3=: ;@((<@([(],.(-+/"1))],.]+i.@(]-~1+<.@-:@-))"0 i.@>:@<.@%&3))
part4=: 3 :0
ij=.; (,.]+i.@:(]-~1+[:<.3%~y-]))&.> i.1+<.y%4
(,.y - +/"1) ; (<@(],"1 0 <.@-:@(y-[) (] + i.@>:@-) {:@] >. (>.-:y)-[)~+/)"1 ij
)
c0=: */@:{
c1=: 13 :'(*-:@(*>:))/y{~}:x'
c2=: 13 :'(*-:@(*>:))~/y{~}.x'
c3=: 13 :'3!2+y{~{.x'
radGenN=: [:;[:(],[:+/c0`c1`c2`c3@.(#.@(}.=}:)@[)"1)&.>/(<1x),~part3&.>@ i.@-
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 cassl@.(#.@(}.=}:)@[)"1~[)@:part4"0 [1-.~i.y-1
)
NofParaff=: {. radGenN ((ccpGenN +:) + bcpGenN ) 2&|+<.@-:
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
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
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
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]]
)
;
Julia
Output is the same as the Go version.
const branches = 4
const nmax = 500
const rooted = zeros(BigInt, nmax + 1)
const unrooted = zeros(BigInt, nmax + 1)
rooted[1] = rooted[2] = unrooted[1] = unrooted[2] = 1
const c = zeros(BigInt, branches)
function tree(br, n, l, sum, cnt)
for b in br+1:branches
sum += n
if (sum > nmax) || (l * 2 >= sum && b >= branches)
return
elseif b == br + 1
c[br + 1] = rooted[n + 1] * cnt
else
c[br + 1] *= rooted[n + 1] + b - br - 1
c[br + 1] = div(c[br + 1], b - br)
end
if l*2 < sum
unrooted[sum + 1] += c[br + 1]
end
if b < branches
rooted[sum + 1] += c[br + 1]
end
for m in n-1:-1:1
tree(b, m, l, sum, c[br + 1])
end
end
end
bicenter(n) = if iseven(n) unrooted[n + 1] += div(rooted[div(n, 2) + 1] * (rooted[div(n, 2) + 1] + 1), 2) end
function paraffins()
for n in 1:nmax
tree(0, n, n, 1, one(BigInt))
bicenter(n)
println("$n: $(unrooted[n + 1])")
end
end
paraffins()
Kotlin
// 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 /Wolfram Language
Using the formula on OEIS.
s[m_, p_, n_] :=
CycleIndexPolynomial[SymmetricGroup[m],
Table[ComposeSeries[p, x^i + O[x]^(n + 1)], {i, m}]];
G000598[n_] := Nest[1 + x s[3, #, n] &, 1 + O[x], n];
G000602[n_] :=
x s[4, #, n] - s[2, # - 1, n] +
ComposeSeries[#, x^2 + O[x]^(n + 1)] &[G000598[n]];
A000602[n_] := SeriesCoefficient[G000602[n], n];
A000602List[n_] := CoefficientList[G000602[n], x];
Grid@Transpose@{Range[0, 200], A000602List@200}
- 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
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: BigInt; k: int32): 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: int32) =
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
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
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
Alternative method
This method of counting alkanes is based on a paper by Shinsaku Fujita (see program for reference). Multi-precision is not used, so alkanes are counted only up to order 49. The results are identical to those from the REXX program.
program CountAlkanes;
{$mode objfpc}{$H+}
uses SysUtils; // only for output
type TArrayUint64 = array of uint64;
{
Function to count alkanes, based on: Shinsaku Fujita,
"Numbers of Alkanes and Monosubstituted Alkanes.
A Long-Standing Interdisciplinary Problem over 130 Years",
Bull. Chem. Soc. Jpn. Vol. 83, No. 1, 1–18 (2010)
}
function CountAlkanes() : TArrayUint64;
const
MAX_RESULT_INDEX = 49; // as far as this code can get without multi-precision
MAX_R_INDEX = MAX_RESULT_INDEX div 2;
var
R : array [0..MAX_R_INDEX] of uint64;
nrCentUnb : uint64; // number of centroidal unbalanced alkanes
temp : uint64;
m, n, h, i, j, k : integer;
begin
SetLength( result, MAX_RESULT_INDEX + 1); // zero-based
{
Calculate enough of the coefficients R[], where the generating function
r(x) = R[0] + R[1]x + R[2]x^2 + R[3]x^3 + ... satifies
r(x) = 1 + (x/6)[r(x)^3 + 2r(x^3) + 3r(x)r(x^2)] (Fujita, equation 4)
}
R[0] := 1;
n := 0;
repeat
if (n mod 3 = 0) then temp := 2*R[n div 3]
else temp := 0;
for j := 0 to (n div 2) do begin
inc( temp, 3 * R[j] * R[n - 2*j]);
end;
for j := 0 to n do begin
for k := 0 to (n - j) do begin
inc(temp, R[j] * R[k] * R[n - j - k]);
end;
end;
Assert( temp mod 6 = 0); // keep an eye on it
inc(n);
R[n] := temp div 6;
until (n = MAX_R_INDEX);
{
Now use the generating function
(x/24)[r(x)^4 + 3r(x^2)^2 + *r(x)r(x^3) + 6r(x)^2r(x^2) + 6r(x^4)]
where inserting r(x) up to the term in x^m will give the number of alkanes
of orders 2m+1 and 2m+2, as the coefficients of x^(2m+1) and x^(2m+2).
Note: In Fujita's paper, equation 23, the factor is 1/24 not x/24,
but x/24 seems to be needed to give correct results.
}
result[0] := 1; // conventional
for n := 1 to MAX_RESULT_INDEX do begin
m := (n - 1) div 2; // so n = 2*m + 1 or 2*m + 2
temp := 0;
// These loops are written for clarity not efficiency
for k := 0 to m do begin
for j := 0 to m do begin
for i := 0 to m do begin
h := n - 1 - i - j - k;
if (h >= 0) and (h <= m) then inc( temp, R[h]*R[i]*R[j]*R[k]);
end;
end;
end;
if Odd(n) then begin
for k := 0 to m do begin
inc( temp, 3*R[k]*R[m - k]);
end;
end;
for k := 0 to (n - 1) div 3 do begin
j := n - 1 - 3*k;
if (j <= m) then inc( temp, 8*R[j]*R[k]);
end;
for k := 0 to m do begin
for j := 0 to m do begin
i := n - 1 - 2*k - j;
if (i >= 0) and (i <= m) then inc( temp, 6*R[i]*R[j]*R[k]);
end;
end;
if (n mod 4 = 1) then inc( temp, 6*R[(n - 1) div 4]);
Assert( temp mod 24 = 0); // keep an eye on it
nrCentUnb := temp div 24;
if Odd(n) then
result[n] := nrCentUnb
else begin
temp := R[n div 2];
result[n] := nrCentUnb + (temp*(temp + 1) div 2);
end;
end;
end;
// Call function and display the results
var
nrAlkanes : TArrayUint64;
k : integer;
begin
nrAlkanes := CountAlkanes();
for k := 0 to Length( nrAlkanes) - 1 do
WriteLn( SysUtils.Format( '%2d %d', [k, nrAlkanes[k]]));
end.
- Output:
0 1 1 1 2 1 3 1 4 2 5 3 6 5 [...] 48 156192366474590639 49 417612400765382272
Perl
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).
Phix
Using IEEE754 floats, hence imprecise above n=45 on 32 bit, n=52 on 64bit, tested to n=600, giving 3.99378e+262 using %g format, ie accurate to better than 1e-10%.
with javascript_semantics constant MAX_N = 32, BRANCH = 4 sequence rooted = repeat(0,MAX_N+2), unrooted = repeat(0,MAX_N+2) procedure tree(integer br, n, l=n, tot=1, atom cnt=1) atom c for b=br+1 to BRANCH do tot += n if tot>=MAX_N+1 or (l*2>=tot and b>=BRANCH) then return end if integer n1 = n+1, t1 = tot+1 if b==br+1 then c = rooted[n1]*cnt else c *= (rooted[n1]+(b-br-1))/(b-br) end if if l*2<tot then unrooted[t1] += c end if if b<BRANCH then rooted[t1] += c for m=1 to n-1 do tree(b,m,l,tot,c) end for end if end for end procedure procedure bicenter(integer s) if even(s) then atom aux = rooted[s/2+1] s += 1 unrooted[s] += aux*(aux+1)/2 end if end procedure rooted[1..2] = 1 unrooted[1..2] = 1 for n=1 to MAX_N do tree(0, n) bicenter(n) if n<10 or n=MAX_N then printf(1,"%d: %d\n",{n, unrooted[n+1]}) end if end for
- Output:
1: 1 2: 1 3: 1 4: 2 5: 3 6: 5 7: 9 8: 18 9: 35 32: 27711253769
And the same thing using gmp, obviously without any such accuracy limits
with javascript_semantics constant max_n = 200, branch = 4 atom t0 = time() include mpfr.e sequence ivals = repeat(1,2)&repeat(0,max_n-1), rooted = mpz_inits(max_n+1,ivals), unrooted = mpz_inits(max_n+1,ivals), c = mpz_inits(branch,0) mpz tmp = mpz_init() procedure tree(integer br, n, l, s, mpz cnt) mpz cbr = c[br] for b=br to branch do s += n if s>max_n or (l*2>=s and b>=branch) then return end if if b=br then mpz_mul(cbr, rooted[n+1], cnt) else mpz_add_ui(tmp, rooted[n+1], b-br) mpz_mul(cbr, cbr, tmp) mpz_divexact_ui(cbr, cbr, b-br+1) end if if l*2<s then mpz u = unrooted[s+1] mpz_add(u, u, cbr) end if if b<branch then mpz r = rooted[s+1] mpz_add(r, r, cbr) for m=n-1 to 1 by -1 do tree(b+1, m, l, s, cbr) end for end if end for end procedure procedure bicenter(integer s) if even(s) then mpz aux = rooted[s/2+1], u = unrooted[s+1] mpz_add_ui(tmp, aux, 1) mpz_mul(tmp, aux, tmp) mpz_tdiv_q_2exp(tmp, tmp, 1) mpz_add(u, u, tmp) end if end procedure mpz cnt = mpz_init(1) integer s = 1 for n=1 to max_n do tree(1, n, n, s, cnt) bicenter(n) if n<=25 or remainder(n,100)=0 then printf(1,"%d: %s\n",{n, mpz_get_short_str(unrooted[n+1])}) end if end for ?elapsed(time()-t0)
Unusually this is significantly faster (6*) under pwa/p2js than desktop/Phix, the following output/time is from the former.
The limit of 200 in the code above finishes on desktop/Phix in 6s, p2js 1s, 500 takes about 40s in the browser but a whopping three and a half minutes on desktop/Phix, compared to the Go entry above completing that task in 15.6s, all on the same box of course. I have earmarked this task for further investigation into performance improvements, should Phix 2.0 ever actually get started on, that is.
- 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 100: 5921072038125809849884993369103538010139 200: 94304332879903850516...51576307818857723954 (84 digits) 300: 30845274893235665913...77084032710062170279 (129 digits) 400: 13544322063698139999...74867143490557738328 (174 digits) 500: 69888806977968318652...40565376686372508743 (218 digits) 600: 39937810748209753430...83373172999304809224 (263 digits) "1 minute and 23s"
Pike
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
This version only counts different paraffins. The multi-precision integers of Python avoid overflows.
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
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)
Using generating function without OO
This uses a different generating function, but also demonstrates a lower level approach and the use of functools.lru_cache
to memoise a recursive function which would otherwise make an exponential number of recursive calls.
#!/usr/bin/python3
from functools import lru_cache
def Z_S(n, f, k):
"""
The cycle index of the symmetric group has recurrence
Z(S_n, f(x)) = 1/n \sum_{i=1}^n f(x^i) Z(S_{n-i}, f(x)).
This function finds the coefficient of x^k in Z(S_n, f(x))
"""
# Special case to avoid division by zero
if n == 0:
return 1 if k == 0 else 0
# Special case as a speed optimisation
if n == 1:
return f(k)
return sum(
sum(f(ij // i) * Z_S(n-i, f, k - ij) for ij in range(0, k+1, i))
for i in range(1, n+1)
) // n
@lru_cache(maxsize=None)
def A000598(k): return 1 if k == 0 else Z_S(3, A000598, k-1)
@lru_cache(maxsize=None)
def A000642(k): return Z_S(2, A000598, k)
def A000631(k): return Z_S(2, A000642, k)
def A000602(k): return A000642(k) + (A000642((k-1) // 2) if k % 2 == 1 else 0) - A000631(k-1)
for k in range(500): print(k, A000602(k))
Racket
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)))
Raku
(formerly Perl 6)
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
REXX
(Based, in large part, on the Pascal version.)
Programming note: the biggest concern was calculating the number of decimal digits (so as to avoid integer overflow).
/*REXX pgm enumerates (without repetition) the number of paraffins with N carbon atoms. */
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) 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. */
return
- output when using the input of: 600
(Shown at three-quarter 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
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
Scala
object Paraffins extends App {
val (nMax, nBranches) = (250, 4)
val rooted, unrooted = Array.tabulate(nMax + 1)(i => if (i < 2) BigInt(1) else BigInt(0))
val (unrooted, c) = (rooted.clone(), new Array[BigInt](nBranches))
for (n <- 1 to nMax) {
def tree(br: Int, n: Int, l: Int, inSum: Int, cnt: BigInt): Unit = {
var sum = inSum
for (b <- br + 1 to nBranches) {
sum += n
if (sum > nMax || (l * 2 >= sum && b >= nBranches)) return
if (b == br + 1) c(br) = rooted(n) * cnt
else {
c(br) = c(br) * (rooted(n) + BigInt(b - br - 1))
c(br) = c(br) / BigInt(b - br)
}
if (l * 2 < sum) unrooted(sum) = unrooted(sum) + c(br)
if (b < nBranches) rooted(sum) = rooted(sum) + c(br)
for (m <- n - 1 to 1 by -1) tree(b, m, l, sum, c(br))
}
}
def bicenter(s: Int): Unit = if ((s & 1) == 0) {
val halves = rooted(s / 2)
unrooted(s) = unrooted(s) + ((halves + BigInt(1)) * halves >> 1)
}
tree(0, n, n, 1, BigInt(1))
bicenter(n)
println(f"$n%3d: ${unrooted(n)}%s")
}
}
- Output:
See it in running in your browser by ScalaFiddle (JavaScript) or by Scastie (JVM).
Seed7
$ 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
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]"
}
Wren
import "./big" for BigInt
import "./fmt" for Fmt
var branches = 4
var nMax = 250
var rooted = List.filled(nMax + 1, BigInt.zero)
var unrooted = List.filled(nMax + 1, BigInt.zero)
var c = List.filled(branches, BigInt.zero)
var tree
tree = Fn.new { |br, n, l, sum, cnt|
var b = br + 1
while (b <= branches) {
sum = sum + n
if (sum > nMax) return
if (l*2 >= sum && b >= branches) return
if (b == br + 1) {
c[br] = rooted[n] * cnt
} else {
var tmp = rooted[n] + BigInt.new(b - br - 1)
c[br] = c[br] * tmp
c[br] = c[br] / BigInt.new(b - br)
}
if (l*2 < sum) unrooted[sum] = unrooted[sum] + c[br]
if (b < branches) rooted[sum] = rooted[sum] + c[br]
var m = n - 1
while (m > 0) {
tree.call(b, m, l, sum, c[br])
m = m - 1
}
b = b + 1
}
}
var bicenter = Fn.new { |s|
if (s%2 == 0) {
var tmp = (rooted[(s/2).floor] + BigInt.one) * rooted[(s/2).floor]
tmp = tmp >> 1
unrooted[s] = unrooted[s] + tmp
}
}
rooted[0] = BigInt.one
rooted[1] = BigInt.one
unrooted[0] = BigInt.one
unrooted[1] = BigInt.one
for (n in 1..nMax) {
tree.call(0, n, n, 1, BigInt.one)
bicenter.call(n)
Fmt.print("$3d: $i", n, unrooted[n])
}
- Output:
Abbreviated.
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 ... 249: 5814271898167303040368103945830220447130073898083466852225709084407144308593691069932064987528870826155297 250: 16206624309085062837751018464745815688226709117091506494175397665527493805947344857313038875654104100026504
zkl
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