可分阶乘

最近，我完全被农场图书馆的这则推文迷住了：


“如果不乘而除以阶乘，就会发生这种情况。”

当我看到他时，我不得不放弃我的生意，拿起笔记本并检查配方。 结果草案似乎合乎逻辑。 自乘法版本 $$$n！$ 随着增加 $$$n$ 趋于无穷大，则“除法”版本应趋于零。 和 $$$\ frac {n ^ 2} {n！}$ 这样行事； 多项式函数 $$$n ^ 2$ 比幂函数增长慢 $$$n！$ 足够大 $$$n$ ：

$$

$$\ frac {1} {1}，\ frac {4} {2}，\ frac {9} {6}，\ frac {16} {24}，\ frac {25} {120}，\ frac {36 } {720}，\ frac {49} {5040}，\ frac {64} {40320}，\ frac {81} {362880}，\ frac {100} {3628800}$$

但是为什么除法结果采取形式 $$$\ frac {n ^ 2} {n！}$ ？ 它来自哪里 $$$n ^ 2$ ？

为了回答这个问题，我不得不拆除与分数分割有关的旧创伤，但是我却克服了痛苦。 从推文公式从左到右移动，我们首先得到 $$$\ frac {n} {n-1}$ 。 然后，将该值除以 $$$n-2$ 我们得到

$$

$$\ cfrac {\ frac {n} {n-1}} {n-2} = \ frac {n} {（n-1）（n-2）}$$

以这种方式继续下去，我们最终得到：

$$

$$n \ mathbin {/}（n-1）\ mathbin {/}（n-2）\ mathbin {/}（n-3）\ mathbin {/} \ cdots \ mathbin {/} 1 = \ frac {n } {（n-1）（n-2）（n-3）\ cdots 1} = \ frac {n} {（n-1）！}$$

要在推文中显示结果 $$$\ frac {n ^ 2} {n！}$ ，我们只需将分子和分母乘以 $$$n$ 。 （虽然我的口味， $$$\ frac {n} {（n-1）！}$ 更清楚。）

---

我是官方认可的析因迷。 随身携带斐波那契数列； 这是我最喜欢的功能。 每当我学习一种新的编程语言时，我的第一步就是编写一些计算阶乘的程序。 多年来，我想出了该主题的几种变体，例如，定义中的替代词 $$$\乘以$ 在 $$$+$ （这给了我们三角数）。 但似乎我从未想过要更换 $$$\乘以$ 在 $$$\ mathbin {/}$ 。 原来很奇怪。 由于乘法是可交换的和关联的，所以我们可以定义 $$$n！$ 就像来自的所有整数的乘积 $$$1$ 之前 $$$n$ 无需担心操作顺序。 但是在划分时，顺序不能忽略。 在一般情况下 $$$x \ mathbin {/} y \ ne y \ mathbin {/} x$ 和 $$$（x \ mathbin {/} y）\ mathbin {/} z \ ne x \ mathbin {/}（y \ mathbin {/} z）$ 。

在“农场图书馆”推文中，分隔符按降序排列： $$$n，n-1，n-2，\ ldots，1$ 。 最明显的是，它将被升序替换： $$$1，2，3，\ ldots，n$ 。 如果将除数的阶乘定义为 $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ ？ 再次返回学校分数除法算法，我们可以得到一个简单的答案：

$$

$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n = \ frac {1} {2 \乘以3 \乘以4 \乘以\ cdots \乘以n} = \压裂{1} {n！}$$

换句话说，当我们进行多次除法时， $$$1$ 之前 $$$n$ ，最终结果将等于倒数 $$$n！$ 。 （我想在这句话的末尾加上一个感叹号，但可惜！）如果您正在寻找一个规范的答案，那就是“除法而不是乘除，我们得到什么？ $$$n！$ ？”，那么我会说 $$$\ frac {1} {n！}$ 比一个更好的候选人 $$$\ frac {n} {（n-1）！}$ 。 我们为什么不接受 $$$n！$ 及其逆值？

当然，还有许多其他方法可以在集合中放置n个整数值 $$$\ {1 \ ldots n \}$ 。 但是多少呢？ 事实证明，正是 $$$n！$ ！ 因此，似乎有 $$$n！$ 定义除法函数的独特方法 $$$n！$ 。 但是，研究上面显示的两个排列的答案可以使我们理解，这里可以使用一种更简单的模式。 无论序列中的哪个元素首先出现，它都出现在较大分子的分子中，所有其他元素的乘积就是分母。 因此，最后只有 $$$n$ 结果不同（假设我们始终严格从左到右执行除法运算）。 对于任何整数 $$$k$ 范围从 $$$1$ 之前 $$$n$ 通过设置 $$$k$ 在行的开头，我们创建一个除法 $$$n！$ 等于 $$$k$ 除以所有其他因素。 您可以这样编写：

$$

$$\ cfrac {k} {\ frac {n！} {k}}，\文本{可以转换为} \ frac {k ^ 2} {n！}$$

因此，我们解决了有关此推文中操作方式的一些困惑 $$$\ frac {n} {（n-1）！}$ 变成 $$$\ frac {n ^ 2} {n！}$ 。
值得注意的是，所有这些函数在 $$$n$ 到无限 从渐近的角度来看， $$$\ frac {1 ^ 2} {n！}，\ frac {2 ^ 2} {n！}，\ ldots，\ frac {n ^ 2} {n！}$ 完全一样

---

是的 任务完成。 问题解决了。 工作完成了。 现在，我们知道了除因数分解所需的一切，对吗？

好吧，也许还有一个问题。 电脑会说什么？ 如果我们采用自己喜欢的阶乘算法，并按照推文中的建议进行操作，则替换所有出现的运算符 $$$\乘以$ （或* ）放在/ ，会发生什么？ 哪个 $$$n$ 分割选项 $$$n！$ 该程序会给我们吗？

这是我最喜欢的在Julia上作为程序计算阶乘的算法：

 function mul!(n) if n == 1 return 1 else return n * mul!(n - 1) end end 

该算法将整代书呆子引入了递归的概念。 它以文本形式显示为：if $$$n$ 等于 $$$1$ 然后 $$$mul！（n）$ 等于 $$$1$ 。 否则，您需要计算函数 $$$mul！（n-1）$ 然后将结果乘以 $$$n$ 。

_{您可能会问如果} $$_{$n$ 将为零或负数。 你可以问，但是最好不要。 为了我们目前的目标} $$_{$n \ in \ mathbb {N}$ 。}

从任何积极的方面入手 $$$n$ ，递归调用的顺序或迟或早会降为 $$$n = 1$ 。

使用单行Julia定义样式可以更简洁地编写函数：

 mul!(n) = n == 1 ? 1 : n * mul!(n - 1) 

赋值运算符的右边部分是条件表达式还是a形式a ? b : c三元运算符a ? b : c a ? b : c 。 这里a是测试的布尔条件，应返回true或false 。 如果a为true ，则对表达式b求值，结果成为整个表达式的值。 否则，计算c 。

为了确保我做的一切正确，以下是该程序计算的前10个阶乘：

 [mul!(n) for n in 1:10] 10-element Array{Int64,1}: 1 2 6 24 120 720 5040 40320 362880 3628800 

现在，让我们更改此定义并转换/唯一出现的* ，使其他所有内容保持不变（函数名称除外）。

 div!(n) = n == 1 ? 1 : n / div!(n - 1) 

这是如果我们为值运行程序将返回的结果 $$$n$ 来自 $$$1$ 之前 $$$20$ ：

 [div!(n) for n in 1:20] 20-element Array{Real,1}: 1 2.0 1.5 2.6666666666666665 1.875 3.2 2.1875 3.657142857142857 2.4609375 4.063492063492063 2.70703125 4.432900432900433 2.9326171875 4.773892773892774 3.14208984375 5.092152292152292 3.338470458984375 5.391690662278897 3.523941040039063 5.675463855030418 

什么啊 绝对不是收敛到零，就像 $$$\ frac {1} {n！}$ 或 $$$\ frac {n} {n-1}$ 。 实际上，这些值看起来并不像这样，因为它们不会收敛。 从下图可以看出，该序列由两个间歇性成分组成，每个成分似乎都朝着无限远缓慢增长，并且也彼此偏离。


了解我们在这里观察到的内容后，更改div!函数的输出类型将非常有用div! 。 代替使用除法运算符/ ，该运算符将值返回为浮点数，我们可以将其替换为//运算符，该运算符将返回精确的有理值，并四舍五入到最低位。

 div!(n) = n == 1 ? 1 : n // div!(n - 1) 

这是n 1:20的值序列， n 1:20 ：

 20-element Array{Real,1}: 1 2//1 3//2 8//3 15//8 16//5 35//16 128//35 315//128 256//63 693//256 1024//231 3003//1024 2048//429 6435//2048 32768//6435 109395//32768 65536//12155 230945//65536 262144//46189 

该列表充满了有趣的模式。 这是一个双螺旋，锯齿形中的偶数和奇数在互补螺纹中移动。 偶数不只是偶数，还都是度数 $$$2$ 。 此外，它们成对出现-首先出现在分子中，然后出现在分母中-并且它们的顺序不减。 但是有差距。 并非所有学位都存在 $$$2$ 。 奇数线程看起来更加复杂，不同的小的简单系数在数字中出现和消失。 （素数必须小，至少要少 $$$n$ ）

这个结果令我惊讶。 我希望看到更柔和的序列，就像我在纸上计算出的那样。 所有这些断断续续的跳跃毫无意义。 比率无限增长的总体趋势也没有道理。 在接收越来越多的数字的同时，我们如何不断地划分？

在这一点上，您可以暂停阅读，并尝试提出自己的理论，以了解这些曲折数字的来源。 如果您需要一个提示，那么就拥有它，还有一个非常强大的提示，几乎是一个破坏者：在“在线整数序列百科全书”中寻找分子序列或分母序列 。

---

这是另一个线索。 div!程序中的一个小变化div! 完全转换输出。 只需通过将n // div!(n - 1)替换为div!(n - 1) // n更改最后一个表达式。

 div!(n) = n == 1 ? 1 : div!(n - 1) // n 

现在结果看起来像这样：

 10-element Array{Real,1}: 1 1//2 1//6 1//24 1//120 1//720 1//5040 1//40320 1//362880 1//3628800 

这是我们已经看到的阶乘的逆函数，它是通过以递增的除数顺序从左到右生成的一系列值 $$$1 \ mathbin {/} 2 \ mathbin {/} 3 \ mathbin {/} \ cdots \ mathbin {/} n$ 。

毫不奇怪，更改过程中的最后一个表达式会更改结果。 最后，我们知道除法既不是可交换的也不是关联的。 但是很难理解为什么原始程序生成的值序列会产生如此奇怪的锯齿形。 什么样的机制会产生这样的成对的2和奇数和偶数交替的幂？

我发现，在此过程的迭代版本中，比之于递归的过程，更容易解释之字形序列中发生的事情。 （对于那些发现递归定义更简单的人来说，此语句似乎很烦人，但它只是发生了。）程序如下所示：

 function div!_iter(n) q = 1 for i in 1:n q = i // q end return q end 

我声明，具有功能循环的该过程与递归函数相同，就这一点而言，如果div!(n)和div!_iter(n)返回某个正整数n的结果，则它将始终相同。 这是我的证明：

 [div!(n) for n in 1:20] [div!_iter(n) for n in 1:20] 1 1//1 2//1 2//1 3//2 3//2 8//3 8//3 15//8 15//8 16//5 16//5 35//16 35//16 128//35 128//35 315//128 315//128 256//63 256//63 693//256 693//256 1024//231 1024//231 3003//1024 3003//1024 2048//429 2048//429 6435//2048 6435//2048 32768//6435 32768//6435 109395//32768 109395//32768 65536//12155 65536//12155 230945//65536 230945//65536 262144//46189 262144//46189 

要了解生成这些数字的过程，请考虑变量的顺序值 $$$我$ 和 $$$q$ 每次运行循环时。 本来 $$$我$ 和 $$$q$ 相等 $$$1$ ; 因此，在循环的第一遍之后，表达式q = i // q给出 $$$q$ 价值 $$$\ frac {1} {1}$ 。 然后 $$$我= 2$ 和 $$$q = \ frac {1} {1}$ ，即新的含义 $$$q$ 等于 $$$\ frac {2} {1}$ 。 在第三次迭代中 $$$i = 3$ 和 $$$q = \ frac {2} {1}$ 这给了我们 $$$\ frac {i} {q} \ rightarrow \ frac {3} {2}$ 。 如果这仍然令人困惑，那就想像一下 $$$\ frac {i} {q}$ 怎么 $$$i \ times \ frac {1} {q}$ 。 这里的一个重要观察是每个循环周期 $$$q$ 得到相反的值，成为 $$$\ frac {1} {q}$ 。

如果扩展这些运算并查看该系列的每个元素中包含的乘法和除法，则将出现一种模式：

$$

$$\ frac {1} {1}，\ quad \ frac {2} {1}，\ quad \ frac {1 \ cdot 3} {2}，\ quad \ frac {2 \ cdot 4} {1 \ cdot 3 }，\ quad \ frac {1 \ cdot 3 \ cdot 5} {2 \ cdot 4} \ quad \ frac {2 \ cdot 4 \ cdot 6} {1 \ cdot 3 \ cdot 5}$$

一般形式：

$$

$$\ frac {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n} {2 \ cdot 4 \ cdot \ cdots \ cdot（n-1）} \ quad（\ text {odd} n）\ qquad \ frac {2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n} {1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot（n-1）} \ quad（\文本{even} n）$$

---

功能介绍 $$$1 \ cdot 3 \ cdot 5 \ cdot \ cdots \ cdot n$ 奇数 $$$n$ 和 $$$2 \ cdot 4 \ cdot 6 \ cdot \ cdots \ cdot n$ 甚至 $$$n$ 有自己的名字！ 它们称为双阶乘，写为 $$$n !!$ 。

_{糟糕的术语，对不对？ 如果将它们称为“半工厂”会更好。 如果我不知道，我会读} $$_{$n !!$ 作为阶乘。}

双阶乘n被定义为n与相同奇偶校验的所有较小正整数的乘积。 所以我们奇怪的之字形值序列只是 $$$\ frac {n !!} {（n-1）!!}$ 。

亨利·W·古尔德（Henry W.Gould）和乔斯林·昆腾斯（Jocelyn Quentens）（alas，在付费专栏后面）在2012年发表的一篇文章探讨了双重析因的使用。 它们比您想像的要普遍得多。 在17世纪中叶，约翰·沃利斯（John Wallis）得出以下身份：

$$

$$\ frac {\ pi} {2} = \ frac {2 \ cdot 2 \ cdot 4 \ cdot 4 \ cdot 6 \ cdot 6 \ cdots} {1 \ cdot 3 \ cdot 3 \ cdot 5 \ cdot 5 \ cdot 7 \ \ cdots} = \ lim_ {n \ rightarrow \ infty} \ frac {（（（2n）!!）^ 2} {（2n + 1）!!（2n-1）!!}$$

涉及一个双因子乘方多维数据集的甚至更陌生的序列总结如下 $$$\ frac {2} {\ pi}$ 。 除了Srinivasa Ramanujan之外，他都没有被发现。

Gould和Kientens还考虑了二项式系数的双阶乘等价。 标准二项式系数定义为：

$$

$$\ binom {n} {k} = \ frac {n！} {k！ （n-k）！}$$

双重版本如下所示：

$$

$$\左（\！\ Binom {n} {k} \！\右）= \ frac {n !!} {k !! （n-k）!!}$$

请注意，我们的曲折编号与此描述相对应，因此可以认为是双阶乘的二项式系数。 更具体地说，它们是这样的数字：

$$

$$\ left（\！\ binom {n} {1} \！\ right）= \ left（\！\ binom {n} {n-1} \！\ right）= \ frac {n !!} {1 !! （n-1）!!}$$

普通豆 $$$\ binom {n} {1}$ 不太有趣； 他是平等的 $$$n$ 。 但是双版 $$$\左（\！\ Binom {n} {1} \！\右）$ 如我们所见，一种更加生动的舞蹈正在跳舞。 与通常的二项式不同，它并不总是整数。 （唯一的整数值为 $$$1$ 和 $$$2$ ）

将之字形数看成是双阶乘数的商，可以解释它们的很多特性，从交替的偶数和奇数开始。 我们还可以看到为什么序列中所有偶数都是2的幂。 $$$n = 6$ 。 这个分数的分子是 $$$2 \ cdot 4 \ cdot 6 = 48$ 收到 $$$6$ 乘数 $$$3$ 。 但是分母是 $$$1 \ cdot 3 \ cdot 5 = $ 1$ 。 上下的三元组收缩，使我们离开 $$$\ frac {16} {5}$ 。 这种减少在每种情况下都会发生。 每次偶数序列中出现奇数因子 $$$m$ ，它必然具有以下形式 $$$2 \ cdot m$ 但是到这个时候 $$$m$ 应该已经出现在奇数序列中。

---

锯齿形数字序列是对以下问题的合理答案：“如果我们除以而不是乘以会发生什么？ $$$n！$ ？ 还是生成它们的计算机程序只是一个错误的算法？ 我个人认为 $$$\ frac {1} {n！}$ -更直观的答案，但是 $$$\ frac {n !!} {（n-1）!!}$ -更有趣。

而且，之字形序列的存在拓宽了我们的视野。 如上所述，如果您坚持除法算法应始终按分子列表顺序进行 $$$n$ ，在每一步中，将左侧的数字除以右侧的数字，得出总计 $$$n$ 可能的结果，它们看起来都非常相似。 但是之字形解决方案提供了更多的可能性。 我们可以将问题表述为：用分子集 $$$\ {1 \点数n \}$ ，选择其子集并反转该子集的所有元素； 现在我们将所有分子乘以反和正。 如果倒置子集为空，则结果将是常规阶乘 $$$n！$ 。 如果所有分子都变成了相反的值，那么我们得到相反的结果 $$$\ frac {1} {n！}$ 。 如果第二个分子被转换，则从 $$$n-1$ ，则结果将为锯齿形序列的元素。

这些只是可用的许多选项中的一部分。 总共有 $$$2 ^ n$ 的子集 $$$n$ 元素。 例如，您可以取质数或质数幂的每个数字的倒数 $$$（2、3、4、5、7、8、9、11，\点）$ 。 在小 $$$n$ 结果是跳跃的，但持续小于 $$$1$ ：


但是，如果我继续此图表以了解更多信息 $$$n$ ，他将飞入平流层。 质数在数字线上变得非常稀疏。

---

现在我要问一个问题。 我们看到阶乘接近零 $$$n$ 以无穷大为例 $$$1 / n！$ 。 我们已经看到其他变化随着增长而增加 $$$n$ 无限，包括我自己 $$$n！$ 和曲折数字。 阶乘过程中是否有任何种类收敛到不为零的有限边界？

首先，我想到了以下算法：

 function greedy_balance(n) q = 1 while n > 0 q = q > 1 ? q /= n : q *= n n -= 1 end return q end 

我们循环遍历来自 $$$n$ 下降到 $$$1$ 计算过程中的当前产品/商 $$$q$ 。 在每一步，如果当前值 $$$q$ 更多 $$$1$ ，我们将其除以下一个分子，否则执行乘法。 该方案实现某种反馈管理或目标搜索行为。 如果 $$$q$ 太大，我们减少它； 如果太小，我们增加它。 我建议在努力的同时 $$$n$ 到无穷大 $$$q$ 将收敛到旁边的不断缩小的值范围 $$$1$ 。

但是实验给我带来了另一个惊喜：


这样的锯齿波并不是我所期望的。 奇怪的是，曲线不是对称的 $$$1$ ; 与上方的偏差幅度大于与下方的偏差幅度。 但是这种失真比数学上更直观。 由于 $$$q$ 是私人的，距离 $$$1$ 之前 $$$10$ 与距 $$$1$ 之前 $$$\ frac {1} {10}$ 但在线性范围上看起来并非如此。 您可以通过编译商的对数图来解决此问题：


现在图形是对称的，或至少近似相同，并且相对于值居中 $$$0$ 这是对数 $$$1$ 。 但是，还有一个更严重的秘密。 锯齿波很规则并且有一个周期 $$$4$ ，但未在预期极限方向上显示出压缩迹象 $$$\ log q = 0$ 。 数值表明 $$$n$ 到无穷大，曲线的峰值收敛到稍高的值 $$$q = \ frac {5} {3}$ ，并且低点接近一个略低的值 $$$q = \ frac {3} {5}$ 。 （对应的基本对数 $$$10$ 大约相等 $$$\ pm0.222$ ） 我不知道为什么会这样。 也许有人可以解释。

此贪婪算法的失败并不意味着我们无法将阶乘收敛除以 $$$q = 1$ 。

_{如果我们使用分子的对数，则此过程将成为众所周知的计算问题“分裂一组数字的问题”的情况。 我们给了很多实数，我们必须将它们分成两组，总和相等，或者尽可能接近相等。 这是一项非常困难的任务，但也被称为（ PDF ）“最简单的复杂任务”。}

对于任何 $$$n$ 我们可以发现，使用分子的其他一些子集的逆值可以使我们更好地近似于 $$$n！ = 1$ 。 对于小 $$$n$ 我们可以用蛮力解决这个问题：只需考虑一切 $$$2 ^ n$ 子集并选择最佳。

我计算出最佳分区 $$$n = 30$ 当您需要从十亿个选项中进行选择时。


显然，图表变得越来越扁平。 您可以使用相同的方法强制收敛到范围为 $$$0$ 之前 $$$n！$ 。

这样我们就对推文提出的问题有了另一个答案，并开始了我们的旅程。 如果我们相除而不相乘会发生什么 $$$n！$ ？ 我们想要的任何东西。