多个正整数和与积相等问题的初步讨论

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 848 阅读时长 ≈ 3 分钟
一定数量的正整数，若其和与其积相等，则其中至少有几个 1 存在？

前言

这篇文章最初写于 2022 年 1 月 20 日。2023 年 9 月 23 日初次改写为博文。

过程不太严谨，但一定程度上反映了我的思考。只进行了部分格式修正以适应博文格式，未进行内容的修改。

问题

若 ai∈N∗∧a1+a2+⋯+an=a1a2⋯ana_i\in \N^{*}\land a_1+a_2+\cdots +a_n=a_1a_2\cdots a_n ，求数组 A=(a1,a2,⋯ ,an)A=\left\lparen a_1, a_2, \cdots , a_n\right\rparen 中为 11 元素的最少个数与不为 11 元素的最多个数。

规定

设 n∈N∗n\in \N^{*} 且 n⩾2n\ge 2

设 AnA_n 为数组 (a1,a2,⋯ ,an)\left\lparen a_1, a_2, \cdots , a_n\right\rparen ，且 AnA_n 满足 ∀i,ai∈N∗;  ∑i=1nai=∏i=1nai\forall_{i},a_i\in \N^{*};\;{\displaystyle \sum_{i=1}^{n}a_i=\prod_{i=1}^{n}a_i}

设 k(n)k(n) 是关于 nn 的函数，简记为 kk ，含义为 AnA_n 中为 11 元素的最少个数

设 t(n)t(n) 是关于 nn 的函数，简记为 tt ，含义为 AnA_n 中不为 11 元素的最多个数

引理

引理一

k+t=nk+t=n

由题设知正确。

引理二

∀n,n⩾2t−t\forall_{n},n\ge 2^t-t

原式   ⟺  \iff

1a2a3⋯an+1a1a3⋯an+⋯+1a1a2⋯an−1=1\dfrac{1}{a_2a_3\cdots a_n}+\dfrac{1}{a_1a_3\cdots a_n}+\cdots +\dfrac{1}{a_1a_2\cdots a_{n-1}}=1

不妨记 a1⩽a2⩽⋯⩽ana_1\le a_2\le \cdots \le a_n

若 a1, a2, ⋯ , ak=1a_1,\,a_2,\,\cdots ,\,a_k=1 ，假设 ak+1⩾2a_{k+1}\ge 2 ，则 an⩾an−1⩾⋯⩾ak+1⩾2a_n\ge a_{n-1}\ge \cdots \ge a_{k+1}\ge 2

即

1ak+1⋯an+1ak+1⋯an+⋯1ak+2⋯an+⋯+1ak+1⋯an−1=1⩽k⋅12n−k+(n−k)⋅12n−k−1\dfrac{1}{a_{k+1}\cdots a_n}+\dfrac{1}{a_{k+1}\cdots a_n}+\cdots \dfrac{1}{a_{k+2}\cdots a_n}+\cdots +\dfrac{1}{a_{k+1}\cdots a_{n-1}}=1\le k\cdot \dfrac{1}{2^{n-k}}+(n-k)\cdot \dfrac{1}{2^{n-k-1}}

即

k2n−k+n−k2n−k−1=2n−k2n−k⩾1\env{aligned}{\dfrac{k}{2^{n-k}}+\dfrac{n-k}{2^{n-k-1}}&=\dfrac{2n-k}{2^{n-k}}\\ &\ge 1}

由引理一知 n+t2t⩾1\dfrac{n+t}{2^t}\ge 1 ，即

n⩾2t−tn\ge 2^t-t

引理三

t(n)t(n) 是不减函数

 ⁣d(2t−t) ⁣dt=2tln⁡2−1>0\dfrac{\d\left(2^t-t\right)}{\d t}=2^t\ln 2-1>0 对 t⩾1t\ge 1 成立，而 t=0t=0 时有 2t−t=21−1=12^t-t=2^1-1=1 ，即 2t−t2^t-t 不减。

对于 2t+1−(t+1)>n⩾2t−t(t⩾1)2^{t+1}-(t+1)>n\ge 2^t-t\quad (t\ge 1) 中的 nn ，有 t(n)=tt(n)=t 恒成立。

又因为 2t−t2^t-t 不减，则 t(n)t(n) 不减

引理四

n=2t−tn=2^t-t 的反函数 n−1(n)=−(W−1(−2−nln⁡2)ln⁡2+n)n^{-1}(n)=-\left(\dfrac{W_{-1}(-2^{-n}\ln 2)}{\ln 2}+n\right)

对于 2t+1−(t+1)>n⩾2t−t(t⩾1)2^{t+1}-(t+1)>n\ge 2^t-t\quad (t\ge 1) 中的 nn ，有 t(n)=tt(n)=t 恒成立，记 n=2t−tn=2^t-t 的反函数为 n−1(n)n^{-1}(n)

接下来求 n−1(n)n^{-1}(n)

记 m=n+tm=n+t ，则

m=2m−n2−mm=2−n(−mln⁡2)e(−mln⁡2)=−2−nln⁡2\env{aligned}{m&=2^{m-n}\\ 2^{-m}m&=2^{-n}\\ (-m\ln 2)\e^{(-m\ln 2)}&=-2^{-n}\ln 2}

引入朗伯W函数，记作 W(x)W(x) ，是 xexx\e^{x} 的反函数。其中分 W0(x)W_0(x) 与 W−1(x)W_{-1}(x) 两支

则 −mln⁡2=W(−2−nln⁡2)-m\ln 2=W(-2^{-n}\ln 2) 得 t=−(W(−2−nln⁡2)ln⁡2+n)t=-\left(\dfrac{W(-2^{-n}\ln 2)}{\ln 2}+n\right)

因为 n⩾2n\ge 2 ，则 −2−nln⁡2∈[−ln⁡24,0)⫋[−1e,0)-2^{-n}\ln 2\in \left\lbrack -\dfrac{\ln 2}{4},0\right\rparen \subsetneqq \left\lbrack -\dfrac{1}{\e}, 0\right\rparen ，即 W(−2−nln⁡2)W(-2^{-n}\ln 2) 恒在多值区间

若取 W0(x)W_0(x) ，则 t=−(W0(−2−nln⁡2)ln⁡2+n)⩽1ln⁡2−n≈1.44−n<0t=-\left(\dfrac{W_0(-2^{-n}\ln 2)}{\ln 2}+n\right)\le \dfrac{1}{\ln 2}-n\approx 1.44-n<0 ，不成立

若取 W−1(x)W_{-1}(x) ，则 t=−(W−1(−2−nln⁡2)ln⁡2+n)⩾1ln⁡2−n≈1.44−nt=-\left(\dfrac{W_{-1}(-2^{-n}\ln 2)}{\ln 2}+n\right)\ge \dfrac{1}{\ln 2}-n\approx 1.44-n ，成立

故取 W−1(x)W_{-1}(x) ，即

n−1(n)=−(W−1(−2−nln⁡2)ln⁡2+n)n^{-1}(n)=-\left(\dfrac{W_{-1}(-2^{-n}\ln 2)}{\ln 2}+n\right)

解答

t(n)=⌊n−1(n)⌋=⌊−(W−1(−2−nln⁡2)ln⁡2+n)⌋t(n)=\left\lfloor n^{-1}(n)\right\rfloor=\left\lfloor -\left(\dfrac{W_{-1}(-2^{-n}\ln 2)}{\ln 2}+n\right)\right\rfloor

则 k(n)=n−t(n)=n−⌊−(W−1(−2−nln⁡2)ln⁡2+n)⌋k(n)=n-t(n)=n-\left\lfloor -\left(\dfrac{W_{-1}(-2^{-n}\ln 2)}{\ln 2}+n\right)\right\rfloor

综上所述，

{t=⌊−(W−1(−2−nln⁡2)ln⁡2+n)⌋k=n−⌊−(W−1(−2−nln⁡2)ln⁡2+n)⌋\env{cases}{t=\left\lfloor -\left(\dfrac{W_{-1}(-2^{-n}\ln 2)}{\ln 2}+n\right)\right\rfloor\\ k=n-\left\lfloor -\left(\dfrac{W_{-1}(-2^{-n}\ln 2)}{\ln 2}+n\right)\right\rfloor}