用3个1表示2进制的数

王守恩

用3个1表示2进制的数。
a(1)=111=7
a(2)=1011=11
a(3)=1101=13
a(4)=1110=14
a(5)=10011=19
a(6)=10101=21
a(7)=10110=22
a(8)=11001=25
a(9)=11010=26
问：a(100)是10进制中的那个数？

chaoshikong

硬算，算出来的，结果为：
10000110000（2进制）=1072
不知道对不对。。

天元酱菜院

没有0的有1个 (111)
1个0的有3个   (首位是1; 其他3个位置各有一次机会)
2个0的有C(2,4)   [注：首位是1，其他位置4选2]  = 6个
3个0的有C(3,5) = C(2,5) = 10 个
一般，n个0的有 C(2,(n+3-1)) =(n+2)(n+1)/2 个

有个公式： ∑(i=1 to n) ( i (i+1)/2 ) =n(n+1)(n+2)/6
可以先证一下这个公式，  当n=1时，左右两边都是1。
设公式对于k成立，查看k+1;     
∑(i=1 to k+1)  ( i (i+1)/2 )  = k(k+1)(k+2)/6    +  (k+1)(k+1+1)/2 =
(k+1)(k+2) *(k/6+ 1/2)=(k+1)(k+2)(k+3)/6 = (k+1)(k+1+1)(k+1+2)/6
即公式对k+1也成立。 证毕。

由于 7*8*9 / 6 =84;   8*9*10/6= 120
所以，a(100) 中含有 8-1=7 个0 （即，它有10位）； a(84)有6个0，a(85)有7个0
a(85)=1000000011;

再者，C(2,6)=15; 即 最后6位中选2位安放1，有15种放法，可以对应85到99，于是a(100)中的后7位是1000001
所以，a(100)=1000000000+1000001=1001000001

换成10进制： 2^9 +2^6+1 =512+64+1=577
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
做法2：   由于C(3,9) = 9*8*7 / 6 =3*4*7 =84;  即，9个数字位置上恰好放3个1，有84种变化。所以，a(85)必为10位有效数字中的最小者
即a(85)=1000000011;   以下同。

ataorj

b(1)=111

a(1)=b(1)

和b(m)等价的a(n)的第一个1后添加一个0成为a(n+1)，然后从a(n+1)右边开始，每个0和第二个1交换位置成为a()下一个项，并即刻和最右边1交换位置成为a()下一个项,这样从a(n+1)得到的最后那项a()成为b(m+1)

求a(100)
解：

a(2)=1011,有1个0，可产生1*2=2项a()，其最后那项=b(2)

同理即：
1个0，1*2
2个0，2*2
3个0，3*2
4个0，4*2
...

当有k个0时，全体项a()共有
2(1+2+3+4+...k)+k+1=(k+1)^2+1
设 (k+1)^2+1 =100，
k=9时得到的其实是第101项a()
，a(101)=111000000000
则a(100)=110100000000

ataorj

更新：
b(1)=111
b(2)=1011
b(3)=10011
...

a(1)=b(1)

从和b(m)等价的a(n)的右边开始，每个0和最右边1交换位置成为a()下一个项，并即刻同时和第二个1交换位置成为a()下一个项,如此从b(m)产生完当前a()后,下一项a()=b(m+1)

求a(100)
解：

a(2)=b(2)=1011,有1个0，可产生1*2=2项a()

同理即：
0个0，0*2
1个0，1*2
2个0，2*2
3个0，3*2
4个0，4*2
...

当有k个0时，全体项a()共有
2(1+2+3+4+...k)+k+1=(k+1)^2
设 (k+1)^2 =100，k=9时得到的其实就是第100项a()
，a(100)=111000000000

[a(99)=110100000000
a(101)=1011000000000]

ataorj

枚举[purebasic代码]
For b=%111 To 9999:m=0:s.s=Bin(b):le=Len(s)

For c=1 To le
  If Mid(s,c,1)="1":m+1
EndIf:Next

If m=3:n+1:If le>ll:ll=le:lel.s="=b("+p+")":p+1
   Else:lel="":EndIf
  Debug Str(n)+"_"+s+"_"+Str(Val("%"+s))+lel
  
  If n=100:Break
EndIf:EndIf
Next
Debug "0的个数="+Str(p-1)

==结果:==
1_111_7=b(0)
2_1011_11=b(1)
3_1101_13
4_1110_14
5_10011_19=b(2)
6_10101_21
7_10110_22
8_11001_25
9_11010_26
10_11100_28
11_100011_35=b(3)
12_100101_37
13_100110_38
14_101001_41
15_101010_42
16_101100_44
17_110001_49
18_110010_50
19_110100_52
20_111000_56
21_1000011_67=b(4)
22_1000101_69
23_1000110_70
24_1001001_73
25_1001010_74
26_1001100_76
27_1010001_81
28_1010010_82
29_1010100_84
30_1011000_88
31_1100001_97
32_1100010_98
33_1100100_100
34_1101000_104
35_1110000_112
36_10000011_131=b(5)
37_10000101_133
38_10000110_134
39_10001001_137
40_10001010_138
41_10001100_140
42_10010001_145
43_10010010_146
44_10010100_148
45_10011000_152
46_10100001_161
47_10100010_162
48_10100100_164
49_10101000_168
50_10110000_176
51_11000001_193
52_11000010_194
53_11000100_196
54_11001000_200
55_11010000_208
56_11100000_224
57_100000011_259=b(6)
58_100000101_261
59_100000110_262
60_100001001_265
61_100001010_266
62_100001100_268
63_100010001_273
64_100010010_274
65_100010100_276
66_100011000_280
67_100100001_289
68_100100010_290
69_100100100_292
70_100101000_296
71_100110000_304
72_101000001_321
73_101000010_322
74_101000100_324
75_101001000_328
76_101010000_336
77_101100000_352
78_110000001_385
79_110000010_386
80_110000100_388
81_110001000_392
82_110010000_400
83_110100000_416
84_111000000_448
85_1000000011_515=b(7)
86_1000000101_517
87_1000000110_518
88_1000001001_521
89_1000001010_522
90_1000001100_524
91_1000010001_529
92_1000010010_530
93_1000010100_532
94_1000011000_536
95_1000100001_545
96_1000100010_546
97_1000100100_548
98_1000101000_552
99_1000110000_560
100_1001000001_577
0的个数=7

王守恩

天元酱菜院 发表于 2017-11-1 17:27
没有0的有1个 (111)
1个0的有3个   (首位是1; 其他3个位置各有一次机会)
2个0的有C(2,4)   [注：首位是1 ...

a(1)=1
a(2)=10a(1)=11
a(3)=100a(3)=110a(1)=111
a(4)=1000a(6)=1100a(4)=1110a(1)=1111
a(5)=10000a(10)=11000a(10)=11100a(5)=11110a(1)=11111
a(6)=100000a(15)=110000a(20)=111000a(15)=111100a(6)=111110a(1)=111111
a(7)=1000000a(21)=1100000a(35)=1110000a(35)=1111000a(21)=1111100a(7)=1111110
a(8)=10000000a(28)=11000000a(56)=11100000a(70)=11110000a(56)=11111000a(28)=11111100
a(9)=100000000a(36)=110000000a(84)=111000000a(126)=111100000a(126)=111110000a(84)=
..........................
我用的是杨辉三角。
打也打不好，好心的网友来帮帮忙编排一下。谢谢!

天元酱菜院

王守恩 发表于 2017-11-2 12:39
a(1)=1
a(2)=10a(1)=11
a(3)=100a(3)=110a(1)=111

这一层楼没看懂。

王守恩

天元酱菜院 发表于 2017-11-3 08:09
这一层楼没看懂。

a(1)=1
a(2)=10                 a(1)=11
a(3)=100               a(3)=110               a(1)=111
a(4)=1000             a(6)=1100             a(4)=1110               a(1)=1111
a(5)=10000         a(10)=11000         a(10)=11100             a(5)=11110             a(1)=11111
a(6)=100000       a(15)=110000       a(20)=111000         a(15)=111100           a(6)=111110         a(1)=111111
a(7)=1000000     a(21)=1100000     a(35)=1110000       a(35)=1111000       a(21)=1111100       a(7)=1111110
a(8)=10000000   a(28)=11000000   a(56)=11100000     a(70)=11110000     a(56)=11111000   a(28)=11111100
a(9)=100000000 a(36)=110000000 a(84)=111000000 a(126)=111100000 a(126)=111110000 a(84)=111111000
..........................
我用的是杨辉三角。
有1个1;2个1;3个1;.....n个1 这些不同情况。在杨辉三角中都可以找到答案。
杨辉三角对应的2进制数列在上面。
杨辉三角对应的10进制数列在下面。
a(1)=1
a(2)=2       a(1)=3
a(3)=4       a(3)=6       a(1)=7
a(4)=8       a(6)=12     a(4)=14       a(1)=15
a(5)=16   a(10)=24   a(10)=28       a(5)=30       a(1)=31
a(6)=32   a(15)=48   a(20)=56     a(15)=60       a(6)=62     a(1)=63
a(7)=64   a(21)=96   a(35)=112   a(35)=120   a(21)=124   a(7)=126
a(8)=128 a(28)=192 a(56)=224   a(70)=240   a(56)=248 a(28)=252
a(9)=256 a(36)=384 a(84)=448 a(126)=480 a(126)=496 a(84)=504
..........................

王守恩

王守恩 发表于 2017-11-3 11:00
a(1)=1
a(2)=10                 a(1)=11
a(3)=100               a(3)=110               a(1)=111
...

这一层楼没看懂。