一道高考数学题

northwolves

这里涉及到三个数列，

A059268

Concatenate subsequences [2^0, 2^1, ..., 2^n] for n = 0, 1, 2, ...

23

                                                                                       

1, 1, 2, 1, 2, 4, 1, 2, 4, 8, 1, 2, 4, 8, 16, 1, 2, 4, 8, 16, 32, 1, 2, 4, 8, 16, 32, 64, 1, 2, 4, 8, 16, 32, 64, 128, 1, 2, 4, 8, 16, 32, 64, 128, 256, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 1, 2, 4, 8, 16, 32, 64

A288349

Partial sums of A059268.

0

                                                                                       

1, 2, 4, 5, 7, 11, 12, 14, 18, 26, 27, 29, 33, 41, 57, 58, 60, 64, 72, 88, 120, 121, 123, 127, 135, 151, 183, 247, 248, 250, 254, 262, 278, 310, 374, 502, 503, 505, 509, 517, 533, 565, 629, 757, 1013, 1014, 1016, 1020, 1028, 1044, 1076, 1140, 1268, 1524, 2036

以及讨论之中的A288492

	NAME	Indices of terms of A288349 that are powers of 2.
	DATA	1, 2, 3, 18, 95, 440, 1897, 7882, 32139, 129804, 521741, 2092046, 8378383, 33533968, 134176785, 536789010, 2147319827, 8589606932, 34359083029, 137437642774, 549753192471, 2199018012696, 8796082536473, 35184351117338, 140737446412315, 562949869535260

我最初计算得到的通项公式是  a(k)=(2^k-3)(2^k-2)/2+k,k>=1

遇到两个问题：
1 正如我添加的评论，通项公式为什么算不出2？

Also,the integer 2 should be in the list,but 2 cann't be calculated by the formula.

2. Colin Barker提供的这个函数如何推导出来？有什么巧妙的办法？

FORMULA                                                                        

                                                                                    From Colin Barker, Jun 23 2017: (Start)                                

                                                            

                                                                                    G.f.: x*(1 - 6*x + 8*x^2 + 14*x^3 - 22*x^4 + 8*x^5) / ((1 - x)^2*(1 - 2*x)*(1 - 4*x)).

                                

欢迎大家参与讨论

northwolves

问题讨论页面：A288492

谢谢大家！

kastin

不难发现其指数规律是 : 0,  0,1,  0,1,2,  0,1,2,3,  0,1,2,3,4,  ... 记为 `b_n`
均加1，得到 1,  1,2,  1,2,3,  1,2,3,4,  1,2,3,4,5, ...，记为 `c_n`
设新数列第 `n` 项落在第 `k` 个循环块中，令 `n=\D\frac{k(k+1)}{2}`，显然该块内最大元素为 `k`，故求出正根并向上取整得到$$k=\lceil\frac{\sqrt{8n+1}-1}{2}\rceil$$此时说明前面有 `k-1` 个完整的周期块，所以$$c_n=n-\frac{k(k-1)}{2}\tag{1}$$于是 `b_n=c_n-1=n-1-\D\frac{k(k-1)}{2}`
从而原数列1,1,2,1,2,4,1,2,4,8,1,2,4,8,16,...的通项公式为 `a_n=2^{b_n}`.

由 `(1)` 可计算出前 `n` 项的指数，即 `0,~~0,1,~~0,1,2,~~0,1,2,3,~~\cdots,~~0,1,2,...,k-2,~~0,1,2,...,b_n` (注意, `b_n`可能小于 `k-2`，也可能大于 `k-2`)
于是部分和$$\begin{align*}S_n&=2^0+(2^0+2^1)+(2^0+2^1+2^2)+\cdots+(2^0+2^1+2^2+\cdots+2^{b_n})\\
&=(2-1)+(2^2-1)+\cdots+(2^{k-1}-1)+(2^{b_n+1}-1)\\
&=(2+2^2+\cdots+2^{k-1})-k+2^{b_n+1}\\
&=2^k+2^{c_n}-k-2\end{align*}$$

kastin

因为题目说 `n>100`，于是可知 `k \geqslant 14`，要使得 `S_n` 为2的整数幂，根据3楼部分和的最后表达式，可知其必要条件为：`k+2` 也是2的整数幂。故 `k=14,30,62...`
检验 `k=14`，`S_n=2^{14}+2^{n-91}-2^4=2^4(2^{10}-1+2^{n-95})`，只能是 `2^{n-95}=1`，否则 `S_n` 不可能是2的整数幂，此时 `n=95<100`，舍去。
检验 `k=30`，`S_n=2^{30}+2^{n-435}-2^5=2^5(2^{25}+2^{n-440}-1)`，只能是 `2^{n-440}-1=0`，否则 `S_n` 不可能是2的整数幂，得到 `n=440>100`，符合要求。即选A.

至于为何上面说“只能是……，否则……”，这可以从二进制数中看出来：`2^x-1+2^y=(1\underbrace{000\cdots00}_{x个0})_2+(\underbrace{111\cdots11}_{y个1} )_2`，显然 `y` 只能等于0，否则结果不可能是2的整数幂。

zeroieme

1. Table[Array[2^(#-1)&,i],{i,200}]//Flatten//Accumulate//MapIndexed[If[IntegerQ[Log2[#1]],#2,{}]&,#]&//Flatten

复制代码

northwolves

按3楼公式：
n=1,k=1,cn=1,sn=1
n=2,k=1,cn=2,sn=3
最终的序列是 1, 2, 3, 18, 95, 440, 1897, 7882,，显然2也是跳过去了。

kastin

根据4楼方法，可求出满足 `S_N` 为2的正整数幂的那些 `N` 的通项公式:
令 `k=2^i-2\;(i=0,1,2,3,\cdots)`，那么 `S_n=2^k+2^{N-k(k-1)/2}-2^i=2^i\left(2^{2^i-i-2}+2^{N-2^{2i-1}+5\*2^{i-1}-i-3}\right)`，有$$N=2^{2i-1}-5\*2^{i-1}+i+3~(i=0,1,2,3,\cdots)\tag{2}$$计算得到 `N= 1,\,1,\,3,\,18,\,95,\,440,\,1897,\,7882,\,32139,\,129804,\,521741,\cdots`

northwolves

kastin 发表于 2017-7-3 10:07
根据4楼方法，可求出满足 `S_N` 为2的正整数幂的那些 `N` 的通项公式:
令 `k=2^i-2\;(i=0,1,2,3,\cdots)` ...

谢谢Kastin!
第二项应该是2啊。你的第二项也是1

northwolves

                                      GP/PARI CALCULATOR Version 2.5.5 (released)
                               i686 running mingw (ix86/GMP-5.0.1 kernel) 32-bit version
                                        compiled: Sep 20 2013, gcc-4.6.3 (GCC)
                                    (readline v6.2 enabled, extended help enabled)

                                        Copyright (C) 2000-2013 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 4000000, primelimit = 500509
? Vec(x*(1 - 6*x + 8*x^2 + 14*x^3 - 22*x^4 + 8*x^5) / ((1 - x)^2*(1 - 2*x)*(1 - 4*x)) + O(x^30))
%1 = [1, 2, 3, 18, 95, 440, 1897, 7882, 32139, 129804, 521741, 2092046, 8378383, 33533968, 134176785, 536789010, 2147319827, 8589606932, 34359083029, 137437642774, 549753192471, 2199018012696, 8796082536473, 35184351117338, 140737446412315, 562949869535260, 2251799645913117, 9007198919196702, 36028796347875359]
?

northwolves

您的公式跟我的是一样的：

parisize = 4000000, primelimit = 500509
?
? for(k=0, 20, p=(2^k-3)*(2^k-2)/2+k; print1(p, ", "))
1, 1, 3, 18, 95, 440, 1897, 7882, 32139, 129804, 521741, 2092046, 8378383, 33533968, 134176785, 536789010, 2147319827, 8589606932, 34359083029, 137437642774, 549753192471,