葛立恒数的尾数

定义数列 $f_n = 3\char`\^{f_{n-1}}$ , $f_0 = 3$

我们有 $f(1)=3^3 = 9$ , $f(2) = 3^{3^3}= 7625597484987$ , f(3) 的话就写不出来了.

现假设 $f_n = f_{n-1} \pmod {10^{n-1}}$

$n = 2$ 时有:

$f_2 \pmod {10} = f_1 \pmod {10} = 7$

假设成立

$n=k+1$ 时有:

$$\begin{aligned} f_{k+1} &= 3^{f_k}\\ &= 3^{f_{k-1}+k\cdot10^{k-1}}\\ &= 3^{f_{k-1}}×3^{k\cdot10^{k-1}}\\ &= f_k×3^{k\cdot10^{k-1}}\\ \end{aligne$$

欧拉定理指出,若 $n$ ,$a$ 为正整数,且两数互素($\gcd(a,n)=1$ ),则
$\displaystyle{a^{\varphi(n)} \equiv 1 \pmod n}$

$a \leftarrow 3$ , $n \leftarrow 10^{n-1}$ :

$$ 3^{\varphi(10^{n-1})}=3^{10^{n-1}} \equiv 1 \pmod {10^{n-1}}$$


观测

计算辐射出的熵把整个宇宙蒸的热寂了,

计算是不需要消耗任何能量的, 观测才要消耗能量.

指定任意, 只需要付出结果 kT

\ln2{}

不管怎么说 葛立恒数 只是 I 类大数, I 类大数都是可计算数

II 类大数大多是不可计算数, 那才玩完了...

几何概型

在边长为1的正方形中随机取三个点,构成三角形的面积期望是多少?

https://www.zhihu.com/question/50499895

随机从1x1大小的正方形平面上取3个点,构成锐角三角形的概率是多少?

https://www.zhihu.com/question/37403137

求球面上随机均匀分布的三点所围的球面三角形的面积的期望?

https://www.zhihu.com/question/47636187

在一个半径为1的圆内,任取四个点A,B,C,D,则线段AB与CD相交的概率为多少?

https://www.zhihu.com/question/50555865

在三个同心圆上分别取一个点连接成三角形,何时面积最大?何时周长最大?

https://www.zhihu.com/question/40401977

已知四边形的三条边长,能否求出四边形的最大面积?

https://www.zhihu.com/question/312781542

m 个 a 和 n 个 b 任意排序,之后从左向右读取,则其中始终满足「a 的个数大于 b 的个数」概率为多少?

https://www.zhihu.com/question/21095573

无向图中三角形的计数

https://www.zhihu.com/question/36652212

https://m.tau.ac.il/~nogaa/PDFS/ayz97.pdf
https://www.zhihu.com/question/63596038

http://mathworld.wolfram.com/GraphCycle.html

符号:给定简单无向图 $G = (V, E)$ ,分别用 $n$$m$ 表示顶点和边的个数,即 $n=|V|$$m=|E|$

我们用 $A$ 表示 $G$ 的邻接矩阵,用 $\Delta$ 表示 $G$ 中三角形的个数,用 $\omega<2.376$ 表示矩阵乘法的指数,用 $(u - v - w)$ 表示一条长度为 $2$ 的简单路径(顶点依次为 $u, v, w$ )。

$\Delta =trace(A^3)/6$ 。这个方法的复杂度为 $O(n^\omega) = O(n^{2.376})$

$\gamma = m^{(\omega - 1)/(\omega + 1)}$ 。根据顶点的度数,将 $G$ 的顶点 $V$ 划分成两个集合:

  • $V_1 = \{v \in V \ \mid\ d_v \leq \gamma\}$

  • $V_2= \{v \in V \ \mid\ d_v > \gamma\}$

这里, $d_v$ 表示 $v$ 的度数。

我们首先枚举所有满足 $v \in V_1 的 (u - v - w)$ 。这一步可以在 $O(m \cdot \gamma)$ 内完成(对于每条边 $(u, v)$ ,如果 $v \in V_1$ ,则进一步遍历 $v$ 的邻接边)。

对于每条找到的 $(u - v - w)$ ,如果 $(u, w) \in E$ ,则 $u , v , w$ 构成三角形。这一步可算出所有包含了 $V_1$ 的点的三角形的个数。

对于任意一个在第一步中没有被统计到的三角形,它的3个顶点都属于 $V_2$ 。因此,我们首先构造 $V_2$ 的生成子图(induced subgraph),并用之前提到的基于矩阵乘法的代数方法算出剩余三角形的数量。其复杂度为 $O(|V_2|^\omega)$ 。由 $\textstyle{2m \geq \sum_{v\in V_2} d_v > |V_2|\cdot \gamma}$ ,可知 $|V_2| < 2m/\gamma$

总体复杂度为:

$$O\left(m\cdot \gamma + \left(\frac{2m}{\gamma}\right)^\omega\right) = O\left(m^{2\omega/(\omega + 1)}\right) = O\left(m^{1.41}\right)$$

讨论:在稀疏图里面,我们有 $m = O(n\log n)$ ,因此第2个方法要比第1个方法有更好的渐进复杂度。

对于稠密图有 $m = \Omega(n^2)$ , 此时第1个方法更好。

是否存在各棱长面积和体积均为整数的四面体

integer tetrahedron

http://mathworld.wolfram.com/HeronianTetrahedron.html

是否存在三棱锥(四面体)各棱长,面积和体积均为整数?修改
如题,是否存在一个三棱锥,即四面体,使其六棱各自的长,四面各自的面积,和四面体的体积均为整数?
若有,其各棱长组成数组(a,b,c,d,e,f),则a~f之和最小为多少?不考虑成整倍数关系的,是否存在无数个这样的数组?

n! 能否是完全平方数

https://www.zhihu.com/question/322658245

n ! 能否是完全平方数

根据Bertrand's postulate(虽然叫postulate但是实际上是一个已经证明的定理),对任意大于2的正整数n,n/2和n之间存在一个素数p。在n的阶乘中,素因子p一定仅出现1次。因此n的阶乘不是完全平方数。
对于$p^m\ ||\ n!$$p^{m}\ |\ n!$$p^{m+1}\ \not\mid\ n!$ ),有如下公式:

$m=pot_p(n!)=\sum_{k=1}^{\infty}{\left[ \frac{n}{p^k}\right]}$

实际上我们只要证明:不超过$n>1$ ,但离$n$ 最近的质数,其最大指数一定是$1$ ,即需证

$\sum_{k=1}^{\infty}{\left[ \frac{n}{p^k}\right]}=1$

即证

$\left[ \frac{n}{p^k} \right]=\begin{cases} 1&k=1\\ 0& k>1 \end{cases}$

$\Leftrightarrow$

$1=\frac{p}{p}\leq \frac{n}{p}< \frac{2p}{p}=2$

$\Leftrightarrow$

$p\leq n< 2p$

证明:分两种情况:

$n \in \mathbb{P}$ ,则命题显然;

$n \ \bar \in \ \mathbb{P}$ ,命$p=\max\left\{ q\in \mathbb{P}\ \ |\ \ q

现在只需证明$n<2p$ 即可。若不然,则$\exists \ p^*$ 满足

$p

成立原因是伯特兰假设。如此一来,$p^*$ 的出现与$p$ 的极大性相矛盾. 所以大于1的阶乘皆非完全平方数.

$Q. E. D$

Handler[hr, {}, {}]

下面我列出 20 以内阶乘的质因数分解式(除 1 外):

$2!=2$

$3!=2\cdot 3$

$4!=2^3\cdot3$

$5!=2^3\cdot3\cdot5$

$6!=2^4\cdot3^2\cdot5$

$7!=2^4\cdot3^2\cdot5\cdot7$

$8!=2^7\cdot3^2\cdot5\cdot7$

$9!=2^7\cdot3^4\cdot5\cdot7$

$10!=2^8\cdot3^4\cdot5^2\cdot7$

$11!=2^8\cdot3^4\cdot5^2\cdot7\cdot11$

$12!=2^{10}\cdot3^5\cdot5^2\cdot7\cdot11$

$13!=2^{10}\cdot3^5\cdot5^2\cdot7\cdot11\cdot13$

$14!=2^{11}\cdot3^5\cdot5^2\cdot7^2\cdot11\cdot13$

$15!=2^{11}\cdot3^6\cdot5^3\cdot7^2\cdot11\cdot13$

$16!=2^{15}\cdot3^6\cdot5^3\cdot7^2\cdot11\cdot13$

$17!=2^{15}\cdot3^6\cdot5^3\cdot7^2\cdot11\cdot13\cdot17$

$18!=2^{16}\cdot3^8\cdot5^3\cdot7^2\cdot11\cdot13\cdot17$

$19!=2^{16}\cdot3^8\cdot5^3\cdot7^2\cdot11\cdot13\cdot17\cdot19$

$20!=2^{18}\cdot3^8\cdot5^4\cdot7^2\cdot11\cdot13\cdot17\cdot19$

容易发现分解式中的最后一个质数的指数总是 1,更进一步,只要满足$p\leq n<2p$ 的质数,其指数也总是 1.

素数公式

Willson 定理

$p>1$ 是素数, 当且仅当 $(p-1)!=-1\bmod p$

$$\mathtt{isPrime}(x) = \left\lfloor \cos^{2} \pi \frac {(x - 1) ! + 1} {x} \right\rfloor =\begin{cases} 1, x\in \mathbb{P}\cup\{1\}\\ 0, \mathrm{others} \end{cases}$$

$$\mathtt{countPrime} (n) = \sum_{x = 1}^{n} \mathtt{isPrime}(x)- 1$$

给定自然数 $n$ , 满足 $\pi(m) 的数的数量就是 $p_n -1$ .

$$p_{n} = 1 + \sum_{m = 1}^{\infty} \mathrm{is}[\pi (m) < n]$$

接下来要用到一些素数密度的估计.

对于任意自然数 $n$$2n$ 之间至少有一个素数.

也就是说小于等于 $2^n$ 的素数至少有 $n$ 个.

于是我们可以把这个无穷大消掉了,

$$\mathtt{isLess}(x , y) = \left\lfloor \sqrt[ y ] {\frac {y} {1 + x}} \right\rfloor =\begin{cases} 1, x

$$p_n = 1 + \sum_{m = 1}^{2^{n}} \left\lfloor \sqrt[ n ] {\frac {n} {1 + \pi (m)}} \right\rfloor$$

https://www.zhihu.com/question/311834230/answer/595009063

http://mathworld.wolfram.com/PrimeFormulas.html

Page210
http://read.pudn.com/downloads133/ebook/566944/%E9%AB%98%E6%95%88%E7%A8%8B%E5%BA%8F%E7%9A%84%E5%A5%A5%E7%A7%98.pdf

http://www.m-hikari.com/ams/ams-2012/ams-73-76-2012/kaddouraAMS73-76-2012.pdf