/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Coefficients of $\prod_{k>0} (1 - x^k/k!)$

The sequence $a(n)$ has exponential generating function $$E(x) = \prod_{k=1}^\infty \left(1 - \frac{x^k}{k!}\right),$$ so that $a(n) = n! [x^n] \prod_{k=1}^n \left(1 - \frac{x^k}{k!}\right)$.

Since $a(n)$ is a sum of multinomial coefficients with $\pm$ signs, it is always an integer.

References:

@[expose] public sectionopen Polynomialnamespace OeisA185895

The finite polynomial approximation $\prod_{k=1}^n (1 - X^k / k!)$.

noncomputable def p (n : ℕ) : Polynomial ℚ := ∏ k ∈ Finset.Icc 1 n, (1 - C (1 / (k.factorial : ℚ)) * X ^ k)a:ℚb:ℚn:ℕm:ℕ⊢ C a * X ^ n * (C b * X ^ m) = C a * C b * (X ^ n * X ^ m) All goals completed! 🐙

The sequence $a(n) = n! [x^n] \prod_{k=1}^n (1 - x^k / k!)$.

noncomputable def a (n : ℕ) : ℤ := if n = 0 then 1 else (coeff (p n) n * (n.factorial : ℚ)).floor@[category test, AMS 11] theorem a_0 : a 0 = 1 := ⊢ a 0 = 1 All goals completed! 🐙@[category test, AMS 11] theorem a_1 : a 1 = -1 := ⊢ a 1 = -1 ⊢ ((∏ k ∈ Finset.Icc 1 1, (1 - C (1 / ↑k.factorial) * X ^ k)).coeff 1 * 1).floor = -1 ⊢ (-1).floor = -1 All goals completed! 🐙hI:Finset.Icc 1 2 = {1, 2}⊢ (((1 - C (1 / ↑(Nat.factorial 1)) * X ^ 1) * (1 - C (1 / ↑(Nat.factorial 2)) * X ^ 2)).coeff 2 * 2).floor = -1 hI:Finset.Icc 1 2 = {1, 2}⊢ ((if 2 = 0 then 1 else 0) * 2 - (if 2 = 1 then 1 / ↑(Nat.factorial 1) else 0) * 2 - ((if True then 1 / ↑(Nat.factorial 2) else 0) * 2 - (if 2 = 1 + 2 then 1 / ↑(Nat.factorial 1) * (1 / ↑(Nat.factorial 2)) else 0) * 2)).floor = -1 All goals completed! 🐙hI:Finset.Icc 1 3 = {1, 2, 3}⊢ (((1 - C (1 / ↑(Nat.factorial 1)) * X ^ 1) * ((1 - C (1 / ↑(Nat.factorial 2)) * X ^ 2) * (1 - C (1 / ↑(Nat.factorial 3)) * X ^ 3))).coeff 3 * ↑(Nat.factorial 3)).floor = 2 hI:Finset.Icc 1 3 = {1, 2, 3}⊢ ((if 3 = 0 then 1 else 0) * ↑(Nat.factorial 3) - (if 3 = 1 then 1 / ↑(Nat.factorial 1) else 0) * ↑(Nat.factorial 3) - ((if 3 = 2 then 1 / ↑(Nat.factorial 2) else 0) * ↑(Nat.factorial 3) - (if True then 1 / ↑(Nat.factorial 1) * (1 / ↑(Nat.factorial 2)) else 0) * ↑(Nat.factorial 3)) - ((if True then 1 / ↑(Nat.factorial 3) else 0) * ↑(Nat.factorial 3) - (if 3 = 1 + 3 then 1 / ↑(Nat.factorial 1) * (1 / ↑(Nat.factorial 3)) else 0) * ↑(Nat.factorial 3) - ((if 3 = 2 + 3 then 1 / ↑(Nat.factorial 2) * (1 / ↑(Nat.factorial 3)) else 0) * ↑(Nat.factorial 3) - (if 3 = 1 + (2 + 3) then 1 / ↑(Nat.factorial 1) * (1 / ↑(Nat.factorial 2) * (1 / ↑(Nat.factorial 3))) else 0) * ↑(Nat.factorial 3)))).floor = 2 All goals completed! 🐙hI:Finset.Icc 1 4 = {1, 2, 3, 4}⊢ (((1 - C (1 / ↑(Nat.factorial 1)) * X ^ 1) * ((1 - C (1 / ↑(Nat.factorial 2)) * X ^ 2) * ((1 - C (1 / ↑(Nat.factorial 3)) * X ^ 3) * (1 - C (1 / ↑(Nat.factorial 4)) * X ^ 4)))).coeff 4 * ↑(Nat.factorial 4)).floor = 3 hI:Finset.Icc 1 4 = {1, 2, 3, 4}⊢ ((if 4 = 0 then 1 else 0) * ↑(Nat.factorial 4) - (if 4 = 1 then 1 / ↑(Nat.factorial 1) else 0) * ↑(Nat.factorial 4) - ((if 4 = 2 then 1 / ↑(Nat.factorial 2) else 0) * ↑(Nat.factorial 4) - (if 4 = 1 + 2 then 1 / ↑(Nat.factorial 1) * (1 / ↑(Nat.factorial 2)) else 0) * ↑(Nat.factorial 4)) - ((if 4 = 3 then 1 / ↑(Nat.factorial 3) else 0) * ↑(Nat.factorial 4) - (if True then 1 / ↑(Nat.factorial 1) * (1 / ↑(Nat.factorial 3)) else 0) * ↑(Nat.factorial 4) - ((if 4 = 2 + 3 then 1 / ↑(Nat.factorial 2) * (1 / ↑(Nat.factorial 3)) else 0) * ↑(Nat.factorial 4) - (if 4 = 1 + (2 + 3) then 1 / ↑(Nat.factorial 1) * (1 / ↑(Nat.factorial 2) * (1 / ↑(Nat.factorial 3))) else 0) * ↑(Nat.factorial 4))) - ((if True then 1 / ↑(Nat.factorial 4) else 0) * ↑(Nat.factorial 4) - (if 4 = 1 + 4 then 1 / ↑(Nat.factorial 1) * (1 / ↑(Nat.factorial 4)) else 0) * ↑(Nat.factorial 4) - ((if 4 = 2 + 4 then 1 / ↑(Nat.factorial 2) * (1 / ↑(Nat.factorial 4)) else 0) * ↑(Nat.factorial 4) - (if 4 = 1 + (2 + 4) then 1 / ↑(Nat.factorial 1) * (1 / ↑(Nat.factorial 2) * (1 / ↑(Nat.factorial 4))) else 0) * ↑(Nat.factorial 4)) - ((if 4 = 3 + 4 then 1 / ↑(Nat.factorial 3) * (1 / ↑(Nat.factorial 4)) else 0) * ↑(Nat.factorial 4) - (if 4 = 1 + (3 + 4) then 1 / ↑(Nat.factorial 1) * (1 / ↑(Nat.factorial 3) * (1 / ↑(Nat.factorial 4))) else 0) * ↑(Nat.factorial 4) - ((if 4 = 2 + (3 + 4) then 1 / ↑(Nat.factorial 2) * (1 / ↑(Nat.factorial 3) * (1 / ↑(Nat.factorial 4))) else 0) * ↑(Nat.factorial 4) - (if 4 = 1 + (2 + (3 + 4)) then 1 / ↑(Nat.factorial 1) * (1 / ↑(Nat.factorial 2) * (1 / ↑(Nat.factorial 3) * (1 / ↑(Nat.factorial 4)))) else 0) * ↑(Nat.factorial 4))))).floor = 3 All goals completed! 🐙

The $n$-th coefficient of the square of the ordinary generating function $A(x)^2$.

noncomputable def c (n : ℕ) : ℤ := ∑ k ∈ Finset.range (n + 1), a k * a (n - k)set_option linter.style.formal_proof_palomar false in

$a(n)$ differs in sign from $a(n-1)$ if and only if $n$ is a triangular number (checked up to $n = 1225 = (50 \cdot 51)/2$).

    Peter Bala, Mar 17 2022

@[category research solved, AMS 11, formal_proof using lean4 at "https://github.com/epoch-research/LeanOpenProblems-results/blob/f02efd9a8c5fc6a735d2a90c33e24f7278ce0ffc/runs/oeis-lite-200usd-sol-nk5wh4g0vh3546nm/oeis_185895_conjecture_1/Submission/Spec.lean#L4835"] theorem conjecture_1 (n : ℕ) (hn : 0 < n) : a n * a (n - 1) < 0 ↔ n.IsTriangular := n:ℕhn:0 < n⊢ a n * a (n - 1) < 0 ↔ n.IsTriangular All goals completed! 🐙set_option linter.style.formal_proof_palomar false in

The coefficients $c(n)$ of $A(x)^2 = (\sum_{n \ge 0} a(n) x^n)^2$ differ in sign from $c(n-1)$ if and only if $n$ is a triangular number.

    Peter Bala, Mar 17 2022

Proof sketch (the kernel-checked development lives at the formal_proof permalink below). Write $a(n)/n! = \sum_j (-1)^j L_j(n)$, where $L_j(n)$ is the sum of $\prod_{s \in S} 1/s!$ over all sets $S$ of $j$ distinct positive integers with sum $n$. A "down map" (lowering by one the least element of $S$ above its first gap) gives $L_{k-1}(n) \le \frac{91}{100} L_k(n)$ for all $k \ge 1$ and $n \ge k(k+1)/2$. Hence the top nonzero layer $L_m(n)$ dominates, where $m(m+1)/2 \le n < (m+1)(m+2)/2$; this reproves conjecture_1 and gives $|a(n)| \ge \frac{9}{100} n! L_m(n)$. Since $c(n) = 2a(n) + \sum_{0<k<n} a(k)a(n-k)$, the sign of $c(n)$ equals that of $a(n)$ whenever $\sum_{0<k<n} |a(k)a(n-k)| < 2|a(n)|$. For $n \le 2500$, conjecture 2 is checked in the kernel from a certified table of $a(n)$; for $n > 2500$, explicit estimates (rational arithmetic and elementary bounds only) bound the cross sum by $0.18 \cdot n! L_m(n)$, which is less than $2|a(n)|$.

@[category research solved, AMS 11, formal_proof using lean4 at "https://github.com/kei825/oeis-a185895-conjecture2/blob/8ddd5a7d2bde415940f944440921fd760283f79d/OeisA185895Conjecture2.lean#L4959-L4961"] theorem conjecture_2 (n : ℕ) (hn : 0 < n) : c n * c (n - 1) < 0 ↔ n.IsTriangular := n:ℕhn:0 < n⊢ c n * c (n - 1) < 0 ↔ n.IsTriangular All goals completed! 🐙set_option linter.style.formal_proof_palomar false in

The Gauss congruences $a(n \cdot p^k) \equiv a(n \cdot p^{k-1}) \pmod{p^k}$ hold for all primes $p$ and positive integers $n$ and $k$.

    Peter Bala, Mar 17 2022

@[category research solved, AMS 11, formal_proof using lean4 at "https://github.com/KitaKen1/oeis-a185895-conjecture3/blob/e40e3db2b47beeef22b00a481fc3a41b518168d9/lean/OeisA185895Conjecture3FC.lean#L579-L589"] theorem conjecture_3 (p : ℕ) (hp : p.Prime) (n k : ℕ) (hn : 0 < n) (hk : 0 < k) : a (n * p ^ k) ≡ a (n * p ^ (k - 1)) [ZMOD (p : ℤ) ^ k] := p:ℕhp:Nat.Prime pn:ℕk:ℕhn:0 < nhk:0 < k⊢ a (n * p ^ k) ≡ a (n * p ^ (k - 1)) [ZMOD ↑p ^ k] All goals completed! 🐙end OeisA185895