GitHub 源文件 Markdown 中文

Grox's Sequence V B: an exponential generating function

Codex (GPT-6): apply the exponential generating function of binomial moments and formal-series log/exp. Generating functions, Newton iteration and NTT are established methods, not inventions of this problem. The program uses a substantially different derivation from the Stirling-convolution reference. The latter uses fewer operations and can truncate to needed terms, so it remains preferred.

Extract the moment directly

For \(k>0\) , the formal exponential gives

\[ \sum_{i=0}^n\binom ni e^{iz}=(1+e^z)^n \]

Thus the answer is

\[ S=k!\,[z^k](1+e^z)^n \]

Here \([z^k]\) extracts the coefficient of degree \(k\) . The zero-index term contributes zero to a positive power, matching the statement. For \(k=0\) , return \(2^n-1\) separately rather than using the generating function's constant term.

Normalize the constant term to one:

\[ H(z)=\frac{1+e^z}{2},\qquad H(0)=1,\qquad (1+e^z)^n=2^n\exp\big(n\log H(z)\big) \]

Construct the first \(k+1\) coefficients of \(e^z\) from inverse factorials, calculate \(F=n\log H\) , then \(G=\exp F\) . The answer is \(2^n k!G_k\) . Keep only terms of degree at most \(k\) throughout.

Formal-series implementation

Inverse precision doubles: if \(AU=1\pmod{z^m}\) , use

\[ U_{\mathrm{next}}=U(2-AU)\pmod{z^{2m}} \]

The new error is the square of the old one. For a series with constant term one, use

\[ \log A=\int\frac{A'}A\,dz \]

with integration constant zero. If \(G=\exp F\pmod{z^m}\) , use

\[ G_{\mathrm{next}}=G(1+F-\log G)\pmod{z^{2m}} \]

The error \(F-\log G\) starts at degree \(m\) . The linear correction cancels it, while quadratic terms start at degree \(2m\) , proving the new precision. Products use NTT or naive multiplication at fixed small sizes.

Correctness and applicability

The binomial theorem establishes the generating function; its degree-\(k\) exponential coefficient is the positive-power moment divided by \(k!\) . Normalization and the log/exp identity preserve the formal series. Precision-doubling iterations recover the required coefficient exactly, and multiplication by \(2^n k!\) gives the answer.

For the fixed prime \(P=1005060097\) , \(k<P\) , so inverse factorials, integer integration denominators and the inverse of \(2\) exist. Series inversion has a nonzero constant term; log input has constant term one and exp input has constant term zero. The largest NTT length is \(2^{18}\) , dividing \(P-1\) . This division-based implementation cannot be transferred directly to V A's arbitrary composite modulus.

Complexity and tradeoffs

The precision-doubling costs sum over geometrically increasing polynomial multiplications. Total time is \(O(k\log(k+1)+\log(n+1))\) and space is \(O(k+1)\) . These match the untruncated Stirling convolution asymptotically, but repeated inversion, log and exp have larger constants. The preferred method can reduce work further when \(m=\min(n,k)\) is small. This option supplies a different complete derivation and program; measurements determine whether it meets the current limit, since matching asymptotic bounds alone do not establish that.

Same-input measurements

Both programs agree on all 10 formal inputs. Five alternating timing runs and input, source and binary hashes are in the full record; see the reference environment. Largest per-input median times are 0.124843 seconds for the reference and 0.637622 seconds for this option. Peak working sets are 9.89 and 14.93 MiB respectively, including process/runtime overhead. This implementation exceeds the 0.5-second indicative limit on cases 04, 05, 06, 07, 08, 09. It is therefore a backup option that does not pass the measured full data under the current limit. Algorithmic correctness and timing applicability are separate; this implementation cannot serve as the current reference.