Дмитрий Рыбас on Thu, 18 Jul 2019 16:31:32 +0200
[
Date Prev
] [
Date Next
] [
Thread Prev
] [
Thread Next
] [
Date Index
] [
Thread Index
]
Re: Help understanding generating functions, (partitioning n into k parts)
To
: Mike Day <
mike_liz.day@tiscali.co.uk
>,
pari-users@pari.math.u-bordeaux.fr
Subject
: Re: Help understanding generating functions, (partitioning n into k parts)
From
: Дмитрий Рыбас <
drybas@gmail.com
>
Date
: Thu, 18 Jul 2019 17:31:20 +0300
Delivery-date
: Thu, 18 Jul 2019 16:31:32 +0200
Dkim-signature
: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=l8bTjZLGXxzIeBNNfRIPIkw4jaAPAuzIQEJg/f55L6o=; b=DuQlPcE5IrstywPDlf9duSPCEk4cLM+6Pw+cjUmkDjnYA2ze3x/Bxh8MiRNByEEp8c EzyoPCphuMPVUVEl5Mx4lPlMiqa84wK5toHNpbop5obAePJr95sBlTgTUBxJJ/8ACv9I QEoGsRDAlPgfkVrScQ6Oj+R3mMaT/cwMboJCmP7gIQ0t8TDwLnxwIrs5x6RfMNZ979RG x0aFOxN09Dde09sNpUL2PGtuSUPK2aLCWpJIvef1zZMuzgMmFu6n7X9QGgAfvt303SJH Zzi1zQIAjYabIypmCKK72sIDk3arIwdzpJf63h/rmDG5DoBMKgDWccZWs/b56c0DI1P0 r3aw==
Mike,
Thanks to user
mihaild
on russian scientific forum
dxdy.ru
, here is the best (so far), iterative (non-recursive), low-memory (one vector of lenght n) algorithm for partitions function p(n,k) calculation:
pnk(n,k)=
{
my(M=vector(n),res=0);
M[1]=1;
for(i=1,k,
for(j=1,n-2*i+1,
M[i+j]+=M[j]);
res+=M[n-i+1]);
return(res);
}
Try it!
Regards,
Dmitry.
Follow-Ups
:
Re: Help understanding generating functions, (partitioning n into k parts)
From:
Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
Re: Help understanding generating functions, (partitioning n into k parts)
From:
Jacques Gélinas <jacquesg00@hotmail.com>
Prev by Date:
Re: Using local variable for memoizing in recursion
Next by Date:
Re: Help understanding generating functions, (partitioning n into k parts)
Previous by thread:
Re: components of t_PADIC
Next by thread:
Re: Help understanding generating functions, (partitioning n into k parts)
Index(es):
Date
Thread