筛法中需要用到的初等数论
引言 (总该需要记录一点学习进度了,)虽然说在过去这段时间内已经简单的过了一遍陈景润的"1+2"定理,对其用到的Selberg筛法以及加权的思想也有了那么一点点的理解与认识了.但是张益唐的工作,我应该还是得开始看原始论文才行. 目前Halberstam的第一章也还在进行中,其中当然也涉及到了一些初等数论的知识,这倒不是什么大问题,遇到的最大阻碍还是文章风格方面的不适应(感觉Serre写的都是友善的了). 但是一些初等数论的知识我也还是需要记录一下,一方面也是为了准备初等数论的考试,当然另一方面就是因为我确实对初等数论的知识不够了解与熟练.🤡 以下都是关于同余式的解的存在性以及数量问题.实际上,由算术基本定理和中国剩余定理(CRT)可知,mod n\textrm{mod}\ nmod n的问题通通可以化为mod pa\textrm{mod}\...
一个有趣的应用 -- 抽象代数在排列算法中的应用
引言 本篇将记录我对一道算法题的一些思考,而这题的思路应该比较明显一些.因为它直接就说了,是对1−n1-n1−n的一个排列,那么对称群SnS_nSn应约而至.并且利用一些关于置换的性质,其实便能够很好地解决这个问题,毕竟抽代本身就是为了抽离出一个便于操作与计算的代数结构,直接抓住重点. 在此之前,我对于抽代也只是学习群环域这些理论知识,虽然知道计算机系也要学抽代,用抽代,但一直没有直观的感受.而对这个问题的思考过程中,之前学过的抽代知识自动地蹦出来并且很快地解决了问题,并没有用到多少复杂的内容.虽然对于抽代知识的考察并没有多少,但是在一个非数学的题目下,发现熟悉的身影,肯定还是觉得惊奇的,即使冥冥之中已经有所暗示. 因此我认为这还是很好的一个题,可以去启发其他同学的思考,不管是非数学系的还是数学系的.因此我打算写一篇比较详细的文章,所以写的内容里一半是抽代的一些概念,一半是解释概念时用的例子,解决算法问题的部分并没有多少.因此那一篇我就不会再搬过来了,在此处直接贴一个图片即可. 问题 题目来源可见原题链接,下面给出题目图片: 然后就是!『著名算法大师』Anon...
一个有趣的应用 -- 特征函数在确定『混乱度』算法中的应用
引言 本篇将记录我对一道算法题的一些思考,用到了特征这一概念进行解答,以及特征的具体构造式实际上是由圆法所启发的. 但是实际上也只要求提供一种有效的算法而已,因此构造式并没有发挥出作用来,只需要利用到特征函数这一概念就能比较好的说明思路了(可能其他人看来还是会一头雾水,一下子蹦出这么多符号来). 或许利用具体的构造式,可能就通过对aia_iai的分析,便能得到混乱度上下界的一个估计(应该吧,我也不确定hhh).但是由于aia_iai的不确定性,我也没有什么好的手段进一步探究特征函数的作用. 这里说明一下:这些内容我并没有详细参考资料,纯粹是记录一下自己的一个idea在具体问题下的使用.因此可以说,肯定是不严谨的,一些想法可能还是错误的,不要太认真即可. 问题 题目来源可见原题链接,下面给出题目图片: 然后是『著名算法大师』Anon Xau对该问题的简单翻译: 给定一个有限长度的数列a[n]a[n]a[n],其中n∈[0,n−1]n\in...
筛法读书笔记(哥德巴赫猜想 by 潘承洞) -- 特征与Gauss和
引言 这一篇博客将记录一些我读『哥德巴赫猜想』第一章内容的一些知识点.大概可能应该只是抄一些定理命题(数学类博客的通病),以及一些自己的片面见解,(但是有可能会出错).但是如果在后面的学习中发现有错误或者是新的领悟,我还是会在这边做补充修改的.不会直接修改,而是保留我原来的想法. 本文的主要参考资料为: 哥德巴赫猜想,第二版 by 潘承洞 & 潘承彪 第一章可以说也是性质的罗列,但是我基本上也都是跟着证明了一遍.其中模qqq特征的构造我还是主要参考二潘的『初等数论』,这里边对特征的构造更详细一些,但我应该也是会拆掉脚手架,直接摆一个让人莫名其妙的构造式了.(混沌邪恶!😈) 虽然说本文将只是知识点的罗列,但感觉最后的篇幅应该也不会短,只希望一篇能够解决就行.后续我觉得也不应该是学完一章才更一次博客,而是每周定时更新一次更好. 特征的定义 此处直接给出模qqq特征的表达式,详细的推导过程见参考资料[2].但是定义还是得写一遍: 定义1: 设q≥1q\ge...
筛法读书笔记(Sieve Methods by Halberstam) -- intro of "筛法圣经"
引言 最近得开始记录一下读书进度才行了,敦促一下自己的学习进度,否则就只能毙业了.😥 而我目前看的这本主要的参考资料则是: Sieve Methods by H.Halberstam & H.E.Richert 不知道是不是作者Richert是德国人的原因,这本书的文章风格和我之前读过的英文教材都不相同:直接长难句起手,一句话八九行,从句里套从句,词汇也及其考验我的积累,适合作为六级备考阅读资料.😭 但是与二潘的『哥德巴赫猜想』一书不同,其主要就是围绕陈景润的"1+2"定理(Chen’s Theorem)展开,而此书则是更加详细的介绍了各种筛法(Sieve...
丢番图逼近之二 -- 用连分数的方法求解Pell方程
引言 上一篇的连分数主要也只是一个科普内容,还有一些内容不便于放在上篇里边,于是加在本文中. 由于本文并不像上一篇那样会面向学高数的同学,因此本文不会那么通俗,而是会比较严肃一点. Pell方程 形如x2−dy2=±1x^2-dy^2=\pm 1x2−dy2=±1的二元二次不定方程便称为佩尔(Pell)方程,其中ddd为不含平方因子的正整数(毕竟我们要研究的是Pell方程的所有有理整数解). 最早碰到这个问题还是高中阶段,兜兜转转又要面对它了,而且还有可能出现在我初等数论的考试中😫.当初面对的还只是x2−2y2=1x^2-2y^2=1x2−2y2=1这种比较仁慈的Pell方程的解(恶心的下面马上就能见到了),但是我也只是计算机枚举法求出的几个特殊值,还是算法代师Anon...
丢番图逼近之一 -- 为什么355/113能很好地代替圆周率pi?
引言 本文实际上是我在我们自己的学辅网站上写的帖子,稍加修改直接搬过来,免得到现在都没有一篇正式的帖子. 如果知道以下知识可能更容易理解:...
