2e:null 2f:["$","title",null,{"children":"Generating Functions with BigInt | Yao Liu | Observable"}] 34:T560,class QQ { constructor(p, q=1n, sign=1n) { if (q==0) return undefined if (q==Infinity && p==Infinity) return undefined if (q==Infinity) {p=0n; q=1n} let sign1=ZZ.sign(p), sign2=ZZ.sign(q) this.p=sign1*BigInt(p) this.q=sign2*BigInt(q) this.sign=sign*sign1*sign2 this.reduce() this.value=Number(this.sign*this.p)/Number(this.q) this.tex=(this.sign==1n)?"":"-" this.tex+=(this.q==1n)?this.p:"\\dfrac{"+this.p+"}{"+this.q+"}" } copy() {return new QQ(this.p, this.q, this.sign)} TeX(s="") {return tex`${this.tex}${s}`} num_sign() {return this.sign*this.p} reduce() { let gcd=ZZ.gcd(this.p, this.q) if (gcd>1) {this.p/=gcd; this.q/=gcd} } mult(x) { x = (x instanceof QQ) ? x : new QQ(x) return new QQ(this.p*x.p, this.q*x.q, this.sign*x.sign) } inverse() { return new QQ(this.q, this.p, this.sign) } div(x) { x = (x instanceof QQ) ? x : new QQ(x) return new QQ(this.p*x.q, this.q*x.p, this.sign*x.sign) } add(x) { x = (x instanceof QQ) ? x : new QQ(x) return new QQ(this.num_sign()*x.q+this.q*x.num_sign(), this.q*x.q) } subtract(x) { x = (x instanceof QQ) ? x : new QQ(x) return new QQ(this.num_sign()*x.q-this.q*x.num_sign(), this.q*x.q) } pow(n) { n = BigInt(n) return new QQ(this.p**n, this.q**n, this.sign**n) } }35:Te0f,class QQt { // implements the ring QQ((t)) of formal Laurent series with // coefficients in QQ (=blackboard bold Q) in one variable/indeterminate constructor(r, N=0n, M=Infinity) { this.a=undefined this.r=undefined this.arr=[] N=BigInt(N) if (M<=N) M=Infinity if (M!=Infinity) M=BigInt(M) this.N=N this.M=M if (r instanceof Function) { this.r=r this.a=(n)=>{ if (n=M) return new QQ(0) else { n=BigInt(n)-this.N while (this.arr.length<=n) this.arr.push(r(this.arr)) return this.arr[n] } } // this.strip() } else if (r instanceof Array) { this.M=this.N+BigInt(r.length) for (let i=0; i{ n=BigInt(n)-N return (n>=0 && n{ n=BigInt(n)-N return (n>=0 && nthis.N+1n) this.M-=1n } } TeX(m=5n, t="t") { t="\\color{blue}" + t +"\\color{black}" m=(m>this.N)?BigInt(m):this.N+5n for (let n=this.arr.length; n0)?"+":"" s+=an.tex s+=(i==0)?"":t s+=(i==0||i==1)?"":"^{"+i+"}" } if (m{ n=BigInt(n) this.a(n).add(f.a(n)) } return sum } mult(f) { if (f.constructor!=QQt) return undefined let M=(this.M==Infinity || f.M==Infinity)?Infinity:this.M+f.M-1n let prod=new QQt(undefined, this.N+f.N, M) prod.a=(n)=>{ n=BigInt(n) if (nn-f.M)?this.N:(n-f.M+1n) for (let i=init; i=f.N; i++) x=x.add(this.a(i).mult(f.a(n-i))) return x } return prod } inverse() { // inverse = inverse wrt multiplication // not to be confused with inversion (inverse wrt substitution) return (new QQt([1])).div(this) } div(f) { return new QQt((arr)=>{ let n=BigInt(arr.length) let x=this.a(this.N+n) for (let i=1n; i<=n && f.N+i{ n=BigInt(n) return (n%k==0) ? this.a(n/k) : new QQ(0) } return foo } inversion() { return this } }36:[] 32:{"id":"769a15c38e04c9e5","slug":"generating-functions-with-bigint","title":"Generating Functions with BigInt","thumbnail":"d2dcbb4c771bd2155e116a63e648e07f4f05dd43918e8473c09d52ca363e4371","access_level":"public","create_time":"$D2019-06-20T16:49:07.119Z","update_time":"$D2021-05-27T14:39:40.491Z","view_time":null,"first_public_time":"$D2019-07-09T21:44:35.152Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"490427fcc4ec2c1d","login":"liuyao12","name":"Yao Liu","avatar_url":"https://avatars-next.observableusercontent.com/895964f8b86922c183ea757cd86944e8e9d463ef5ba08171fab539d4dc087c54","tier":"starter_2024"},"version":2210,"publish_version":2210,"role":null,"authored":false,"authors":[{"type":"individual","id":"ae908de8dd38723a","login":"liuyao12","name":"Yao Liu","avatar_url":"https://avatars-next.observableusercontent.com/895964f8b86922c183ea757cd86944e8e9d463ef5ba08171fab539d4dc087c54","tier":null}],"members":[{"type":"individual","id":"ae908de8dd38723a","login":"liuyao12","name":"Yao Liu","avatar_url":"https://avatars-next.observableusercontent.com/895964f8b86922c183ea757cd86944e8e9d463ef5ba08171fab539d4dc087c54","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Generating Functions with BigInt","cells":[{"id":0,"value":"md`# Generating Functions with \\`\\`BigInt\\`\\`\n\nIn JavaScript, \\`\\`number\\`\\`s are actually \\`\\`float\\`\\`s, and as such it only keeps about 16 significant digits. We all know not to trust the last digit, but this is just embarrassing:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":72,"value":"0.1*0.2","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":530,"value":"md`Now that JavaScript supports \\`\\`BigInt\\`\\` (not available on mobile, sorry), can we do mathematical computation *with perfect precision* by only using rational numbers as pairs of \\`\\`BigInt\\`\\`s? Specifically, a (computable) real number would be treated as a \\`\\`function\\`\\` that takes the allowable error as input and returns a *rational* approximation to the number within the error; see [here](/@liuyao12/computable-numbers). (This sounds similar to [arbitrary-precision arithmetic](https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic), but is perhaps closer to [interval arithmetic](https://en.wikipedia.org/wiki/Interval_arithmetic).)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":505,"value":"// QQ is the class for rational numbers\nx=(new QQ(1,10)).mult(new QQ(2,10)) ","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":499,"value":"tex`${x.tex}=${x.value}`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":882,"value":"md`All the operations on rational numbers are exactly as one learns in grade school (commonly called fractions); in particular, the long division algorithm computes the *exact* decimal expression (or in any base) which eventually repeats itself. To convert a repeating decimal expression to a rational number is also easy if one knows about geometric series. To reduce a fraction, we use Euclid's algorithim for finding the greatest common divisor of two integers.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":284,"value":"md`Let us turn to **generating functions**, also known as **formal power series** ${tex`\\mathbb Q[[t]]`}—or more generally **formal Laurent series** ${tex`\\mathbb Q((t))`}—with coefficients in ${tex`\\mathbb Q`}, which is a way to encode an infinite sequence of rational numbers (i.e., a function ${tex`\\mathbb N\\to\\mathbb Q`}), but all the magic happens with the operations and manipulations that we can perform on them.\n\n> *\"A generating function is a clothesline on which we hang up a sequence of numbers for display.\"* — Herbert Wilf, *Generatingfunctionology* (1994)\n\n>*\"We now come to the most important idea in this whole book: the notion of a *generating function*.\"* — Donald Knuth, *Concrete Mathematics* (1989), aka the (expanded) mathematical preliminaries to *The Art of Computer Programming*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1072,"value":"md`## Generating functions\n\nWithout further ado, a generating function is by definition any infinite expression\n${tex.block`f(t)=\\sum_{n\\geq N} a_n t^n \\qquad a_n\\in\\mathbb Q`}\nfor some (possibly negative) index ${tex`N`}. So, naturally we shall construct one by specifying the coefficients ${tex`a_n`} as a \\`\\`function\\`\\` ${tex`\\mathbb Z\\to\\mathbb Q`} which returns 0 for all ${tex`nnew QQ(1, ZZ.factorial(n))\n return exp\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":348,"value":"exp.TeX(8) // print the first few terms","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1003,"value":"md`\\`\\`ZZ\\`\\` contains various operations on integers, and \\`\\`QQt\\`\\` is our class for generating functions as formal Laurent series ${tex`\\mathbb Q((t))`}, which includes as special cases the polynomials ${tex`\\mathbb Q[t]`}, rational functions ${tex`\\mathbb Q(t)`}, and formal power series ${tex`\\mathbb Q[[t]]`}. Apart from the restriction on the coefficients and extreme cases where ${tex`a_n`} grows too fast as ${tex`n\\to\\infty`}, we are secretly working with meromorphic functions of a single complex variable ${tex`t`}. [A somewhat archaic term is the *germ* of meromorphic functions.]`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":442,"value":"md`The principal advantage for writing the numbers ${tex`a_n`} as a generating function is that it makes clear how to multiply two such objects: by *pretending* they were functions of ${tex`t`}. One has to get used to the fact that it is easier to multiply than to \"evaluate\" at a specific value of ${tex`t`}, or to decide if two generating functions are equal.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":486,"value":"exp.mult(exp).TeX(8)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1332,"value":"md`It is also easy to make a substitution such as ${tex`t=2q`}, or even substituting ${tex`t`} for a power series ${tex`\\varphi(q)`} that does *not* have a constant term, to keep the computation of each coefficient *finite* (thus it remains *rational*). In other words, we are keeping things *algebraic* as much as possible. The inverse to this operation is to *invert* a generating function, i.e., find ${tex`\\varphi`} such that ${tex`f(\\varphi(t))=1`}.` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":328,"value":"md`Now, to divide one generating function by another is very similar to the long division algorithm; in particular, to compute ${tex`a_n`} of the quotient requires knowing all the previous coefficients. It then makes computational sense to compute and store the coefficients in strict order. In fact, it is often more convenient to use recursion as the basic building block for constructing an object of \\`\\`QQt\\`\\`, i.e., by providing the \\`\\`function\\`\\` that yields ${tex`a_n`} from the \\`\\`array\\`\\` ${tex`[a_0, a_1, \\ldots, a_{n-1}]`}. The utility of generating functions largely stems from the fact that recursion is natually built-in in ${tex`\\mathbb Q((t))`}.\n\nFor example, the exponential function can be defined by ${tex`a_0=1`} and ${tex`a_n=\\dfrac{a_{n-1}}{n}`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1886,"value":"{\n let exp=new QQt((arr)=>{\n let n=arr.length\n return (n==0) ? new QQ(1n) : arr[n-1].div(n)})\n return exp.TeX(8)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1884,"value":"md`The Fibonacci sequence is given by ${tex`a_0=a_1=1`} and the recursion ${tex`a_n=a_{n-2}+a_{n-1}`}. The miracle is that there is a simple expression for the generating function:\n${tex.block`f(t)=\\frac{1}{1-t-t^2}`}\nfrom which one could readily deduce, among other things, the closed form of ${tex`a_n`} in terms of the Golden Ratio ${tex`\\phi=\\frac{1+\\sqrt 5}{2}`}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1163,"value":"{\n let Fib=(new QQt([1,-1,-1])).inverse()\n return Fib.TeX(15)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":680,"value":"md`### Bernoulli numbers\n\nPerhaps one of the earliest examples of generating functions (attributed to Euler) that are used to \"generate\" interesting numbers is that of the Bernoulli numbers ${tex`B_n`}:\n\n${tex.block`\\frac{t}{e^t-1}=\\sum_{n\\geq 0}\\frac{B_n}{n!}t^n`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":796,"value":"Bernoulli={\n const foo=new QQt(undefined, 0)\n foo.a=(n)=>new QQ(1n, ZZ.factorial(n+1n))\n return foo.inverse()\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1467,"value":"Bernoulli.TeX(13)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1477,"value":"md`If we just want to see the Bernoulli numbers, we can make this generating function (though it may not be a \"natural\" function):`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1243,"value":"Bernoulli_numbers = {\n let foo=new QQt()\n foo.a=(n)=>Bernoulli.a(n).mult(ZZ.factorial(n))\n return foo\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1963,"value":"Bernoulli_numbers.TeX(36)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1680,"value":"md`### Counting numbers\n\nLet's get down to some basics, and what could be more basic than counting things?\n\n1) Counting the number of ways to choose *n* numbers out of ${tex`\\{1,2,\\ldots, ${k}\\}`}, better known as **binomial coefficients**:\n${tex.block`(1+t)^{${k}}=\\sum_{n=0}^{${k}} {{${k}} \\choose n} t^n`}\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1844,"value":"k = {\n let i=1\n while (true) {\n await Promises.delay(2000)\n yield i\n if (i==12) i=1;\n else i++\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1683,"value":"(new QQt([1,1])).pow(k).TeX(k+1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1737,"value":"md`2) Counting the number of partitions of *n*:\n${tex.block`\\sum_{n\\geq 0}p(n) t^n = \\prod_{k\\geq 1}\\frac{1}{1-t^k}`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1691,"value":"md`3) Counting the number of divisors of *n*. More generally, one may define the **${tex`k`}-th divisor function**\n${tex.block`\\sigma_k(n)=\\sum_{d|n} d^k`}\nthen,\n${tex.block`\n\\begin{aligned}\n\\sum_{n\\geq 1}\\sigma_k(n) q^n &= \\sum_{n\\geq 1} \\frac{n^k q^n}{1-q^n} \\\\\n\\end{aligned}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1698,"value":"md`4) Counting the number of ways that *n* can be written as a sum of 4 squares.\n\n${tex.block`\\theta(q)^4=\\biggl(1+2\\sum_{n\\geq 1}q^{n^2}\\biggr)^4`}\nThe coefficient 2 means that we count ${tex`n^2`} and ${tex`(-n)^2`} as two ways of writing the same number as a square.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1802,"value":"md`### Calculus\n\nThere are two other natural operations on generating functions: differentiation and integration.\n\nTo illustrate, let's define the function ${tex`\\sin(t)`} as the inverse to\n${tex.block`\\int_0^t \\frac{ds}{\\sqrt{1-s^2}}`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":608,"value":"md`### Modular forms and modular functions\nModular forms and modular functions, whatever they are, have the so-called *q*-expansion that often have integer coefficients, which is why they are so important in number theory.\n${tex.block`\\Delta(q) = q\\prod_{n\\geq 1}(1-q^n)^{24} = \\sum_{n\\geq 1} \\tau(n)q^n`}\nRamanujan (1916) made a set of conjectures about the coefficients, which he denoted ${tex`\\tau(n)`}, and the last one turns out to be very deep, and was settled by Deligne with the proof of the Weil conjecture (1974).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1896,"value":"bin24 = {\n // let's save binomial coefficients\n let bin=[1,1]\n for (let i=1; i<24; i++) {\n for (let j=i; j>0; j--)\n bin[j]+=bin[j-1]\n bin.push(1)\n }\n for (let i=1; i<24; i+=2) bin[i]*=-1\n return new QQt(bin)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":621,"value":"Delta = {\n let foo=new QQt(undefined, 1)\n foo.a=(n)=>{\n n=BigInt(n)\n let bar=new QQt([0,1])\n for (let i=1; i{\n if (Ek.arr[n] != undefined) return Ek.arr[n]\n let foo=new QQt([Bernoulli.a(k).div(-2n*k)])\n let num=[0,1], den=[1,-1]\n for (let i=1n; i<=n; i++) {\n foo=foo.add((new QQt(num)).div(new QQt(den)))\n num[i]=0; num.push((i+1n)**(k-1n));\n den[i]=0; den.push(-1);\n }\n Ek.arr[n]=foo.a(n)\n return foo.a(n)\n }\n return Ek\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1966,"value":"Eisenstein(4).TeX(3, 'q')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":490,"value":"md`## Code`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":184,"value":"ZZ = {\n // class for operations on BigInts\n const abs=(n)=>(n>=0)?n:-n\n const sign=(n)=>(n>=0)?1n:-1n\n const min=(a,b)=>(a(a>b)?a:b\n \n const ht=(list)=>{\n let m=list[0], M=list[0], n=0\n for (let i=1; iabs(M)) M=list[i]\n }\n return [m, M]\n }\n \n const gcd=(a, b)=>{\n if (abs(a){\n n=BigInt(n)\n if (n<0n) return Infinity\n if (n==0n) return 1n\n return factorial(n-1n)*n\n }\n \n return {abs, sign, gcd, min, max, ht, factorial}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 33:"$32:body"