感激批评意见，欢迎继续批评——七答Equn及各位老师

平常心

cuda 发表于 2013-12-29 22:29
关于能被3整除的二进制数我找到了一个简单判别方法，你看是否满足要求：
若二进制数x其奇数位有p个1，偶数 ...

你的方法是对的。
有一点需要注意。十进制数结果判断后可以直接得知该数除以3之后的余数是几。而二进制数明确判断出该数可否被整除之后，不一定能够立即明显地看出余数是几。于是，我们的判断式可以再多一点内容。
我一直主张，搞懂一个问题。深入理解一个问题，比解决这个问题更重要。在下面的帖子里，我将谈谈我的一些看法，请指正。
渴望各位老师批评指正。

平常心

对在各种进制下判断数字能否被3整除问题的思考

       我们习惯十进制数的简单判断方法，但一般不追究其原因。

       其实原因很简单，这是由于10^k≡1(mod3)。这样我们可将10、100、1000……等都看做1，最后将各个数位的数字加起来，若能被3整除，原来的数即可被3整除。

       四、七、十三、十六……进制数与十进制数一样，都可以用这个方法。

       三、六、九、十二、十六……进制数很明显，可以直接看出。

       其他进制数略微麻烦一点，其中二进制数较简单，我们仅以此为例介绍如下：

       由于，2^2k≡1(mod3)  2^(2k+1)≡2(mod3)

       故： 2^2(k+i)+2^2k+1≡0(mod3) (k∈N, i∈N)

       例如：2^4+2^2+1=21;  2^8+2^4+ 1=273;   2^10+2^2+ 1=1029……

       当i=0时，2^2(k+i)+2^2k+1 =2^(2k+1)+1≡0(mod3)

       例如： 2^3+1=9;   2^5+ 1)=33;   2^7+1=129……

       将以上二式化作二进制数就是：

             10^2(k+i)+10^2k+1≡0(mod11)

             10^(2k+1)+1≡0(mod11)

       也就是说，以下三类字符串，定可被11(3)整除：

          ①11、1111、111111……（3、15、63……）

          ②1001、100001、10000001……（9、33、129……）

          ③10101，1010001，101000001……100010001……（21、81、321……273）

       在此基础上，可进一步推演出更实用的复杂组合:

       令：A=00……0（由奇数个连续的0组合的字符串）

             B=1……1（中间为任意多个字符组合，但不包含A字符串）

       任何二进制数均可由0、1与A、B字符串组合而成，其中：

            0≡0（mod11） 11≡0（mod11） 1A01≡0（mod11） 1ABA1≡0（mod11）

            1≡1（mod11） 1A0≡1（mod11） 1ABA≡1（mod11）

            1A≡10（mod11） 1A1≡10（mod11） 1AB≡10（mod11） 1 ABA0≡10（mod11）

       对于具体的二进制数，可由左至右逐个划去≡0（mod11）的字符串，由最后剩余的字符串即可确定该数是否可被11（3）整除，或者其余数是几。

       例如：10111111001110000111111000011111≡10（mod11）

                100111100011001001111000000001111111101≡0（mod11）

        10000110001100111110000001111110011000≡1（mod11）

cuda

平常心 发表于 2013-12-30 22:12
你的方法是对的。
有一点需要注意。十进制数结果判断后可以直接得知该数除以3之后的余数是几。而二进制数 ...

我给出的整除方法也可以求出余数，p-q和x是mod3同余的。
实际上这个方法上就是把10进制中的11整除判断方法简单照搬过来，对N进制中判断N+1整除都适用，也是一种普适的方法。
你的判别方法感觉有点复杂，所分成的3类特征串中：

          ①11、1111、111111……（3、15、63……）
          ②1001、100001、10000001……（17、33、129……）
          ③10101，1010001，101000001……100010001……（21、81、321……273）

按我的理解，第1类就是2n个1，第2类是两个1中间夹2n个0，第3类是1,2n+1个0,1,2m+1个0,1排列, 是不是这样？(第2类中1001应该是9，不是17)
若以上理解无误，可以帮你编程验证一下。

平常心

cuda 发表于 2013-12-31 12:18
我给出的整除方法也可以求出余数，p-q和x是mod3同余的。
实际上这个方法上就是把10进制中的11整除判断方 ...

那个17确实是写错了。谢谢！
我用这种方法判断、计算了大量较大的二进制数。我感到，后面较复杂的字符串很实用。
我一直希望有人帮助我编一个二进制数的计算程序（输入、输出都是二进制数，计算机内部不必经过十进制数转换，仅用于3x+1计算）。
最近，我想公布几个无限大的二进制数的计算结果，你理解了我的计算方法之后，如果觉得可以编写这样的计算程序，我们再联系。
我个人认为，理解、掌握二进制数的基本特点是破解3x+1问题的一个重要条件。

cuda

平常心 发表于 2013-12-30 22:14
对在各种进制下判断数字能否被3整除问题的思考
       我们习惯十进制数的简单判断方法，但一般不追究其原 ...

          ①11、1111、111111……（3、15、63……）

          ②1001、100001、10000001……（9、33、129……）

          ③10101，1010001，101000001……100010001……（21、81、321……273）

看了你的整除判断方法，根据我的理解，你的方法相当于首先找到一个必能被3整除的表达式2^2(k+i)+2^2k+1，这个表达式中令i=0就得到你的特征串②，其他情况则对应特征串③，然后你认为任何能被3整除的数可以由三种特征串组合得到。不知这样理解是否正确？

感觉这里逻辑上有2个问题：
首先这些串是否完备缺乏证明。能被3整除的表达式可以写出很多种，表达式2^2(k+i)+2^2k+1只是其中一种，显然没有涵盖所有的情况，逻辑上不能直接看出为什么被3整除的数必须只能由这几种串组合得到。
第2个问题是为什么X能被3整除那么它的组成部分也都必须能被3整除？对于类似X=AAAABBBB能被3整除而其中AAAA部分mod3=1而BBBB部分mod3=2这样的情况你是如何考虑的？这个最好也要说明一下。

此外特征串①的由来文中没有介绍？似乎不是由前面这个表达式得到？这样会给读者以突兀的感觉。

zichen

平常心 发表于 4 天前

谢谢！望多批评。批评就是对我最大的支持。

批评不敢当，建议和经验倒是有一些，希望与学弟共勉！你的言行已经超越我对小学生的想象！小学时间比较多，研究一些自己喜欢的东西这很好(我记得我上小学时没少破坏家里的家用电器。)如果你的理解能力足够，我希望你能去研究函数，这对数学研究很重要，了解下一次函数也许你对数学会有一个全新的认识！对于你说的二进制，我还真没研究过。实在是惭愧啊。来自: Android客户端

cuda

平常心 发表于 2013-12-30 22:14
对在各种进制下判断数字能否被3整除问题的思考
       我们习惯十进制数的简单判断方法，但一般不追究其原 ...

帮你编程简单验证了一下，发现有不少被3整除的数并不能由你给出的几种特征串组合得到，如：

165 (10100101)
549 (1000100101)

你看是否还有什么办法改进？

平常心

cuda 发表于 2013-12-31 18:10
看了你的整除判断方法，根据我的理解，你的方法相当于首先找到一个必能被3整除的表达式2^2(k+i)+2^2k+1， ...

谢谢，你看得很仔细。

其实我是通过较多的实际计算之后才总结出这些规律的。

我的方法看起来比较复杂，但实质问题是一样的，都是基于“2^2k≡1(mod3)  2^(2k+1)≡2(mod3)”。

①11、1111、111111……（3、15、63……）

②1001、100001、10000001……（9、33、129……）

这2个看似不同，实际是一类，只不过为了大家看起来方便，我才将其分开。一句话，它们的特点是“两个1中间有偶数个0”，0也算偶数，所以11以及偶数个1字符串都可被整除（11就是十进制数3，自然可以被它自身整除）。

这类字符串前后的两个1，一个若在“奇数位”另一个则一定在“偶数位”， “p-q”就相当于在二进制数中将它们全部变为0。这时剩余的字符要么全部在奇数位，要么在偶数位，也就是说，任意两个1之间必定是奇数个0。若x能被3整除，它们必须组成若干个另一类字符串，绝不会出现其它字符串。

10101，1010001，101000001……100010001……（21、81、321……273）

我随意写出这样一个二进制数：1011001011011100101000001011（187550219）

我们将奇偶数位上对应的1 逐步变为0：

1000001011011100101000001011

1000001000011100101000001011

1000001000000100101000001011

1000001000000000001000001011

1000001000000000001000001000

然后去掉另一类字符串：

1000

显然，这个数不能被11（3）整除。

但我们知道，101100101101110010100000101101（最右边加了一个“01”）必定可被11（3）整除。

既然如此为什么我不使用较简单方法，而要自找麻烦呢？不仅如此，为什么还要搞出更繁琐的判断字符串呢？

这与我的使用目的要求以及计算方法有关。（今天没有时间了，明天接着说）

cuda

平常心 发表于 2014-1-2 13:18
我随意写出这样一个二进制数：1011001011011100101000001011（187550219）
我们将奇偶数位上对应的1 字符全部变为0： 1000000010
显然，这个数不能被11（3）整除。
但我们知道，10110010110111001010000010111（最右边家了一个1）必定可被11（3）整除。

愿闻后续。
在你举的这个例子中，10110010110111001010000010111=375100439，并不能被3整除。你再检查一下？

cuda

平常心 发表于 2014-1-2 13:18

我随意写出这样一个二进制数：1011001011011100101000001011（187550219）

我们将奇偶数位上对应的1 逐步变为0：

1000001011011100101000001011

1000001000011100101000001011

1000001000000100101000001011

1000001000000000001000001011

1000001000000000001000001000

很不错，这样分析就清楚了。这种做法相当于先对X进行化简，再利用特征串进行判断，这样的确是可行的。

不过还有个问题，如果允许先利用奇偶位相消的方法进行化简，那么你的①,②类特征串就都完全不需要了(化简过程中会被处理掉)，只要有特征串③就足够。

此外如果允许先进行化简，那么还有一些更有趣的整除判断方法，有时间我也来介绍一种。

cuda

续上，一种我觉得比较有意思的化简判别方法：
有一种类似俄罗斯方块的方块类游戏，规则是一些不同花色的方块从天上落下，如果相邻的方块花色相同那么就可以消去，非常的简单。
我们可以把判断X能否被3整除的化简过程看作一个这样的方块游戏，这里只有0和1两种花色，如果两个相邻的数字花色相同(即00或11)那么就可以消掉。
消到最后剩下的只可能是0,1或1010..这样1和0相间的形式，此时只要数剩下的1的个数，即可知道X能否被3整除。

例如我前面举的例子X=165(10100101)：
其中有00，消去得：101101
其中有11，消去得：1001
其中有00，消去得：11
其中有11，消去得0，所以X能被3整除。

而如果X=329(101001001)
其中有2个00，消去得：10111
其中有11，消去得：101
剩下1的个数为2，因此不能被3整除。

感觉这种化简方法趣味性更强一些，并且不需要找不相邻的1，不容易出错。

平常心

匆忙之间除了差错，请谅解。

但这个差错也正是我想要讨论的问题。面对长达几十位甚至上百位的二进制数字，一个个地去数奇数位、偶数位个网友几个1字符，或者一个个去消除对应的1字符，是很容易出现差错的，何况我们面对的一个个的二进制数组成的序列。我们需要的是直观的迅速的判断。

为此我进一步推演出有点复杂但比较实用的组合。

0≡0（mod11）这是一目了然的，但从理论上必须要写。

11≡0（mod11）、1A01≡0（mod11）就是字符串①②，也容易理解。

关键的是1ABA1字符串组合。

我们令：A=00……0（由奇数个连续的0组合的字符串）

必须指出，不存在AA字符串组合，因为AA=A0，或者说AA=0A.

起先我发现：10101与101101非常类似，我主观地认为后者不能被11（3）整除。但是我错了。反复地验算之后，我终于明白了，101101实质上是两个1001的重叠组合，或者说，是100001与11的嵌套组合字符串。之后，我逐步认识到，1ABA1≡0（mod11）。这个字符串组合是两类不同的组合:一个完全是字符串①、②的嵌套组合，其中有一个且只有一个字符串②的被一分为二（两边的0字符都是奇数个）；另一个是一个字符串③与若干字符串①、②的嵌套组合。这两种组合天上是一家人，配合地天衣无缝、浑然一体。虽然它看起来有点复杂，但实际应用时，我们只需从某个1字符开始，如果其后是奇数个连续的0（A），我们可一直向有找到下一个连续的奇数个0字符串（A）以及紧接其后的1字符，这样就确定了一个1ABA1字符串组合，无需考虑中间字符的多少、排列、嵌套等问题。一个长达几十位、上百位的二进制数常常会出现这样较长的字符串。

在此基础上，较短的二进制数，往往一眼就可以作出判断，长一些的，我们可以从左至右将其分为以下几段，从而可以直观地做出判断。仍然以前面的数字为例：

101100101  1011100101  00000 10  11

当然，还有更长的数字，如：

10101 100000110010001 1111 000 10111100111001001000011100000110001111001111000011100100000001

至于哪些判断余数的字符串，我想也就不难理解了。

cuda

你的意思是仍然可以不经过化简直接用特征串进行判断？下面这句话比较含糊，能否具体用例子说明一下？

我们只需从某个1字符开始，如果其后是奇数个连续的0（A），我们可一直向有找到下一个连续的奇数个0字符串（A）以及紧接其后的1字符，这样就确定了一个1ABA1字符串组合，无需考虑中间字符的多少、排列、嵌套等问题。

平常心

cuda 发表于 2014-1-3 15:08
你的意思是仍然可以不经过化简直接用特征串进行判断？下面这句话比较含糊，能否具体用例子说明一下？

例，下面的几个字符串是逐步演变的，我们判断其中任何一个字符串时，只需注意最前面和最后面的连续0字符是奇数个，中间个连续的0字符是偶数个，其他都无锡考虑。当然你还可以在其中间增加或减少若干字符，只要不违背我们的判断原则就可以。
101100000001
101111001100000001
1011110011100100000001
101111001110010010000100000001
10111100111001001000011100000001

cuda

我验证了一下，在你17#帖子的原始描述中，如果把特征字符串③换为你后面所说的"1+奇数个0+任意B字符串+奇数个0+1"这种推广形式，你的整除判别法就没有问题了。
不过后面求余数部分是不是还有问题？你说"由左至右逐个划去≡0（mod11）的字符串"，那么剩下的串只能在最后还是前面后面都可以有？
如果允许前面有划剩下的串那么求余数可能会不正确，比如你举的例子中最后一个余数就算错了。

       例如：10111111001110000111111000011111≡10（mod11）

                100111100011001001111000000001111111101≡0（mod11）

        1000011000110011111000000111111011000≡1（mod11）

这里(1000011000110011111000000111111011000)=72049496024，除以3的余数是2，不是1。