这个图像看起来和原方程表达式一样的方程是怎么发现的？ - 以及是否有其他方法发现更多类似于这样的方程？ 陆zz，不断丰富自我 这张图见过许多次了，无论是在贴吧，微博还是知乎，都有人发过。不过基本上没有贴解释，大概是因为很多人看到 k 的数值就望而生畏，然后不明觉厉。 猜测作者发现这个图像的可能的原因： 1. 作者是计算机图形学领域的专家，应该会倾向从计算机的角度想问题。 2. 取整函数将离散的格点集变成可视化的一个个小方块 3. 类比了像素点 4. 利用了同余方程的周期性 5. 利用一类特殊的同余方程来导出一组格点 6. 分开表示每一个方块的表示，再取类似的”线性“组合，然后表示出任意图形,当然也能表示出图中的公式代表的图形 7. 为了让人不明觉厉，特定用了>1/2 首先取 k= 960939379918958884971672962127852754715004339660129306651505519271702802395266424689642842174350718121267153782770623355993237280874144307891325963941337723487857735749823926629715517173716995165232890538221612403238855866184013235585136048828693337902491454229288667081096184496091705183454067827731551705405381627380967602565625016981482083418783163849115590225610003652351370343874461848378737238198224849863465033159410054974700593138339226497249461751545728366702369745461014655997933798537483143786841806593422227898388722980000748404719 如果稍微试验一下，k 是被 17 整除的，这个整除性是偶然和图中的 17 巧合吗？ 今天就来讨论它背后的数学原理（trick）和解读其中的一些基本想法，希望能助于理解。 0. 背景 这是这个公式的 wiki：Tupper's self-referential formula 可见该方程作者Jeff Tupper 是计算机图像学方面的专家，这个公式是他发的 paper 中用来娱乐消遣用的小作品。 Paper 在线阅读地址为 Tupper, Jeff. "Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables" http://www.dgp.toronto.edu/people/mooncake/papers/SIGGRAPH2001_Tupper.pdf 这个公式严格来说不能算是自我指涉方程，因为我们要用到一个 k 值来确定图像，而图像中却缺少 k 的"显示". 公式更多依赖于计算机作图展现的效果，所用数学知识是初等的。 其实图像完全可以有各种变种，如： 令 k=185531049941770208926537803099260736452949966611112761302545006595111870578579162451136704284963688976000103407449554608414333028882354217082057393918094029669810255907671233542495756874373261742164929161036875720054298814326134964214603580077794831513263205572194342604530927978350940846400272783022944627746850589058193941153575534063181110390905632575139905557875980305111220761368993988608 以(x,y-k)作图，其中 ,就得到这样的一个图： 也完全可以自己做一个自我指涉式的图像： 设方程为： 令 k=4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721251530530642522971503 用同样的作图法有： 所以这样的公式有无穷多个。 其实分析后，你会发现计算 k 几乎是一件很简单的事。甚至可以说这个方程是一个很 trick 的东西，下面开始正式的分析. 假设 k>=17. 1. 方程的简化 原方程为： 首先，指出1/2 是完全不必要的。 事实上，由于任何数除以 2 的余数后都在[0,2)之间，因此的值介于 0 与 2 之间。 所以其向下取整只能为 0,1.所以其向下取整的值 > 1/2 也就只有一种可能： 这就是方程本来的样子，不知道为什么作者要取 1/2 这个数字，也许是为了起到障眼法的作用。 还原原貌后，然后我们来考虑定义域 这是一长为 106, 宽为 17 的矩形: 注意到 k<=y<=k+17，而 y-k=17 这一条直线不影响最终的图像，所以不妨考虑 y<k+17 注意到 y 的取值我们有 这就说明 为定值，记为 .…………① 原方程化为 M 为非负整数由 k 唯一决定。 现在来研究这个方程的图像与 k 的关系。 2. 二进制表示消解方程 原方程形如 其中 i, j 为自然数的形式. 对于上面的方程,我们先来思考在什么情况下会有： 其中 i, j 为自然数 首先 j 不能太大，因为当 时，显然左边 = 0，不可能成立等式。 既然是 2 的负整数次幂，而且左边 = 0 或 1，所以我们自然地想到了： i 的二进制表示 设 , 则在 时，我们有 所以 注意到 aj 即为 i 在二进制表示下第 j+1 位 因此我们有： 对给定的 i，方程的所有 j 的自然数解可由 i 的二进制表示给出 j 为解等价于 i 的二进制下第 j+1 位为 1 3. 原方程的解 考虑 设 的所有自然数解 j 构成集合 S. 由上面的讨论可知，j 在 S 中等价于 M 的二进制表示下第 j+1 位是 1 因而 S 有限，并且由 M 唯一决定，从而由 k 唯一决定。 继续前进前先举个例子： 如果 k=17058684 则 M=1003452， 求出 M 的二进制表示 11110100111110111100， 发现第 20, 19, 18, 17, 15, 12, 11, 10, 9, 8, 6, 5, 4, 3 位为 1 故 S={3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 17, 18, 19, 20} 这说明由 k 求 S，S 求 k 只需要简单的转换。 回到原方程 由上面可见，方程变成解许多个不同的简单方程： 注意到左边为一个 17 的倍数 + 一个＜17 的自然数,很明显对固定的这样的 j，左边两项都可以唯一确定，举个例子，37=17a+b，a,b 自然数，那么你应该很快通过两边除以 17 得到 a=2，b=3， 所以我们得到 两边一比较,有 ……② 从而 所以 ……（X） 只要知道了 ， 因为 只能是 0，1，2，……16 这 17 个互异的非负整数（由于 y-k 的范围在 0-17 之间） 只要知道了 ，就可以唯一确定 （X）式右边可能为负数，我们考虑在 mod17 意义下右边的值，右边总是介于 0-16 的整数 如果右边计算为负数等，如 -4，我们就认为右边是 13，这种认定下就会有： ……③ 如上面例子中 k=17058684, S={3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 17, 18, 19, 20} mod(k,17)为 103 452，j 取 18，则解得 于是由 j 唯一确定了不超过 x 的最小整数，不超过 y-k 的最小整数，注意最后作图是以 y-k 为纵坐标作图，我们有 每一个 j∈S 确定的 在新坐标系的解为②③，也就是说满足这个方程的点对应的 x，y-k 的不超过的最小整数都可以分别确定，故图像为： （四条黑边圈住的阴影部分去掉上方和右方的两条边，即为解集区域） 如例中 k=17058684,S={3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 17, 18, 19, 20}, j 取 18 对应的图像为一个方块 注意到 ……② 为了这个图像能够在矩形 上画出，我们还有要求: j<17X106，也就是说我们要求： 还注意到每个 j∈S 均得到一个正方形解集，故有|S|个正方形，但是不同的 j 可能有相同的正方形，所以互异正方形数不大于|S|,其中|S|为 S 的元素个数。 得到第一个结果： 定理 1 当 时 在约束下 不等式的解集为： S 为满足 的二进制表示下的第 j+1 位为 1 的所有 j 的集合。 解集 直观上来看为以②③所确定的格点为左下角点的所有半开半闭单位正方形（即包含左边和下边，上边和右边）之并。 且有估计互异正方形个数设为 N，则有 如上面我们的例子 k=17058684，M=1003452，M 二进制表示 11110100111110111100，第 20, 19, 18, 17, 15, 12, 11, 10, 9, 8, 6, 5, 4, 3 位为 1，故 S={3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 17, 18, 19, 20} 解集如下： 还记得我们说过的取 j=18对应的图像为一个方块{(x,y)|1<=x<2,1<y<=2}吗？你可以发现它就是上面的黑色方块之一，而且 S 的元素数为 14，图中方块数为 13，13<=14. 现在应该可以谈谈这个公式其中的原理，具体如下： 作者应该类比了像素点，即电脑上的每一个图像其实都是由一块块小的像素点生成的，每一个 k 就对应了一块由一个个小方块形成的图形。 我们的目的就是巧妙的选取 k，从而确定 S 中元素，然后 S 中每个元素对应一个小方块，最后所有对应小方块的并就是那个方程的图像。 这就是图像化的奥秘，所以我们在选择恰当的 k 后，可以使小方块拼成我们的想要的图形。 接下来就是证明这种选择是可行的： 即对于每一个形如一个个半开半闭的正方形之并的上述矩形区域中的图形 D，我们都能找到给定的 k，使 4. 利用好的 k, 构造任意图形 我们先假设这样的 k 存在，再寻找它要满足的充分必要条件。 由于，而 S 由 M 唯一决定，因此我们总可以将 k 微调，使 M 不变，从而 S 不变 我们不妨就假设 k 是 17 的倍数，既方便又好消去③中的 k，这时候有 ……② ……③ ……④ 现在假设 均为边长为 1 的半开半闭正方形，互不相同，且四个顶点横纵坐标都是自然数 设 左下角的格点在坐标为 ，由②③有 而且若, 我们立刻由②③得到 , 由 互不相同，便有 j=k，因此两两互异，这保证了 和 k 的选取的合理性。 因此，我们只要使 , 由 3 论证知，S 对应的图形就是 D 也就是说令 M 的第 位全为 1，其余位全为 0 即可，即得到第二个结果： 定理 2： 对于每一个形如一个个半开半闭的正方形之并的上述矩形区域中的图形 D，我们都能找到给定的 k，使 ，且要求 k 是 17 的倍数时，k 是唯一的。 若 ， 均为边长为 1 的半开半闭正方形，互不相同，且四个顶点横纵坐标都是自然数 设左下角的格点在坐标为 , 令 则取，则 以(x,y-k)作图且要求 ， 所得图形 。 我们把 D 对应的 S 称为 D 的 0-1 标，所有的 构成集合成为 D 的标志点集 显然 S,D, 标志点集彼此互相决定.我们借助标志点集可以方便而清楚的表示出 D 与 k. 举个例子： 我们可取 M=111111111111111111111111111111111111111111111111111（二进制） M=2251799813685247=2^51-1 k=17M k=38280596832649199 0-1 标为 {0，1，2，3，4，……，50} 能不能以更快的速度计算 k？ 对一个黑方块，我们从坐标系左下角出发，从下到上数行数 i，从左到右数列数 j 那么其对应的就是 M 的第 i+17(j-1) 位要是 1，对应 0-1 标中元素为 如图黑方块在第 9 行第 5 列，故要做出上面的图形，只要取 M=1000000000000000000000000000000000000000000000000000000000000000000000\ 0000000(二进制，1 在第 9+17X(5-1)=77 位后面 9+17X(5-1)-1=76 个 0） M=2^76 k=17*2^76=1284483683340543498125312 0-1 标为{76} 再回到我们开头的这家伙： 我们来看看这个 k k= 960939379918958884971672962127852754715004339660129306651505519271702802395266424689642842174350718121267153782770623355993237280874144307891325963941337723487857735749823926629715517173716995165232890538221612403238855866184013235585136048828693337902491454229288667081096184496091705183454067827731551705405381627380967602565625016981482083418783163849115590225610003652351370343874461848378737238198224849863465033159410054974700593138339226497249461751545728366702369745461014655997933798537483143786841806593422227898388722980000748404719 乍一看可能挺吓人的，我们用 Mathematica 把它除以 17 然后化成二进制，果然发现 k 是 17 的倍数。 那一串 0-1 即 M 的二进制表示，从中可用 Mathematica 的 Ordering 等函数求出来 0-1 标，从而求出标志点集，然后利用 Qt 之类的工具的画出 D，在此略去代码。 然后利用前人写好的程序，我们把图给导出来： ………… 为啥是倒的……………… 这和说好的不一样啊= = 等等，我们看一下原图： 查阅资料发现 wiki 上说： Tupper's self-referential formula If one graphs the set of points (x, y) in 0 ≤ x < 106 and k ≤ y < k + 17 satisfying the inequality given above, the resulting graph looks like this (note that the axes in this plot have been reversed, otherwise the picture comes out upside-down) 说明这张图片的坐标系是错的，应该是 0 在上，15 在下，否则只会产生颠倒的图片了…… 所以这哪里是不明觉厉啊，这明明是坑蒙拐骗了(╯‵□′)╯︵┴─┴ 做图片的可能以为大家都不会去检验那么大的 k 吧(╯‵□′)╯︵┴─┴ 为了使演示能进行，出来吧 令 k= 4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721248506352686630476300 其图像为： 通过 Mathematica 计算得 0-1 标为 共 334 个，即代表图像由 334 个黑方块组成。 5. 推广 考虑什么是对矩阵区域的大小的根本限制。 其宽度即纵方向伸长是由 17 决定的 我们可以把 17 换成任何一个别的 >2 的素数，如素数 p， 这样我们绘图的矩形区域的宽度可以为 p。 其长度是由计算机处理数据大小和枚举循环的能力决定的。 一方面，记得我们在定理 2 中得到的 k 表达式，其随着 D 的复杂度上升，是成指数级增长。 另一方面，设矩阵长度为 l，我们如果能够给出任意矩阵中的所述图形 D，类比 应该有 ，也就是说计算机要处理最大可能有将近 pl/8 字节的数据，幸好是二进制下的表示，所以这点问题可能在 pl 不超过 1000 时不大。 所以长度也可推广为更长的情况。 我们用 2 作为模也是考虑了计算机是采用二进制这样比较能算比较的大的 k。 之所以说其是一个小把戏，因为它的计算其实是非常复杂的，随着 D 的复杂度上升，不仅情况数变多，而且 k 的值也会变大，所以实用性不太强，大概可以用来让人震撼一会，不过也就一会。 作者自己也说了, It is for fun, 作者那篇发在 SIGGRAPH 的 paper 讨论的问题要比这个复杂多了。 6. 便利的在线绘图网站！ 最后福利送上，这篇回答也得益于这个网站的帮助 感谢别人提前写好的程序,可以方便的运用这个公式 下方是一个在线绘制图像网站，从此无需编程就可以自己画图来获取想要的图像了，然后得到 k 了。 同时还支持从输入的 k 来生成已有的图像。 地址如下： Tupper's Formula Tools 其中 + 号内有各种设置，附带绘图中的各种辅助功能 这个图像工具还是挺好玩的，其原理已经分析的很透彻了，代码其实也可以自己实现 现在就可以去试试绘制出自己的有趣图像吧，再配上一条所谓的图片说明， 令 k=XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX，然后作图， 是不是又让人觉得不（you）明（xia）觉（hu）厉（you）了呢？ 最后的最后，还是感叹一句： k=2107049502688971838329063513563172168955899681012806410390754144923626532135157621023031923466087863176143468290924096759567511357801403711718938794401099693561682114914994374955377516209625656799614796122852269746031140264857207003140484838019323695340354770270378536430701971621675126990271902052377699332225317039638700928135029079258801102020368448505896124833894102314797587617168280834935298038212029402495154112503238042502906064593892473822060631966713782236181481406433783780792014348940404866359006788344814658141056 查看知乎原文
