论坛 › 难题征解 › 一道高考数学题

northwolves 发表于 2017-7-1 22:10:22

一道高考数学题

这里涉及到三个数列，

A059268                  
Concatenate subsequences 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 发表于 2017-7-1 22:15:21

问题讨论页面：A288492

谢谢大家！

kastin 发表于 2017-7-2 15:02:23

不难发现其指数规律是 : 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 发表于 2017-7-2 15:58:36

因为题目说 `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 发表于 2017-7-2 19:23:58

本帖最后由 zeroieme 于 2017-7-2 22:04 编辑

Table,{i,200}]//Flatten//Accumulate//MapIndexed],#2,{}]&,#]&//Flatten

northwolves 发表于 2017-7-2 22:03:13

按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 发表于 2017-7-3 10:07:41

根据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 发表于 2017-7-3 23:05:53

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 发表于 2017-7-3 23:06:30

                                    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 =
?

northwolves 发表于 2017-7-3 23:12:56

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

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,

查看完整版本: 一道高考数学题