Brain Storm,该如何解决

Brain Storm

C/C++ code

Give you a integer N and N is not equal to 10^i and i belongs to {0, 1, 2, 3, ...}.for example, N = 2, we get following data:1th: 2*2 = 42nd: 4*4 = 163rd: 16*16 = 2564th: 256*256 = 655365th: 65536*65536 = 42949672966th: 4294967296*4294967296 = 18446744073709551616construct a set with all the number character appeared in all result of power operation.please show me the minimum times of power operation to get a set equal to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.and prove your idea.

任给一个数N，N != 10^i (i = 0, 1, 2...)，N != 1, 10, 100, 1000, ...
如N=2

第一次：2*2 = 4
第二次：4*4 = 16
第三次：16*16 = 256
第四次：256*256 = 65536
第五次：65536*65536 = 4294967296
第六次：4294967296*4294967296 = 18446744073709551616

以各个幂的结果中出现的数字符为集合SET的元素（剔除重复数字符），
求至少要执行多少次幂运算才能使得SET = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
请给出证明。


[解决办法]
感觉6次应该就行了，不过证明可不容易，尤其是证明一定有0。
[解决办法]
证明起来，根本没思路，计算得到下面数据，希望对严格证明能有点帮助
19
{ 1 9 }
361 = 19 x 19
{ 1 3 6 }
130321 = 361 x 361
{ 0 1 2 3 }
16983563041 = 130321 x 130321
{ 0 1 3 4 5 6 8 9 }
288441413567621167681 = 16983563041 x 16983563041
{ 1 2 3 4 5 6 7 8 }
83198449060887472631428936505541918917761 = 288441413567621167681 x 288441413567621167681
{ 0 1 2 3 4 5 6 7 8 9 }
[解决办法]
2
{ 2 }
4 = 2 x 2
{ 4 }
16 = 4 x 4
{ 1 6 }
256 = 16 x 16
{ 2 5 6 }
65536 = 256 x 256
{ 3 5 6 }
4294967296 = 65536 x 65536
{ 2 4 6 7 9 }
18446744073709551616 = 4294967296 x 4294967296
{ 0 1 3 4 5 6 7 8 9 }
340282366920938463463374607431768211456 = 18446744073709551616 x 18446744073709551616
{ 0 1 2 3 4 5 6 7 8 9 }
[解决办法]
是啊。没思路啊。
我编了程序测了一下。似乎25000以上的数都只需要6次（含）以下。
最多的就是2，需要6次。

猜想下面几个方向解答：
1.用二进制处理或者什么别的进制处理？因为考虑到10^n不成立，所以这么猜。
2.用数学归纳法。比如对当对n成立时，对100+n或者什么都成立。然后验证2-101.
3.根据平方的末尾数字规律，验证10n+1...10n+9都成立。
4.分解质因数什么的？然后找到数字组成的数字和质因数或者乘方次数关系？

[解决办法]
数论的题目，看起来简单，做起来往往很难！
看起来每次平方以后都可以产生新的数字？
[解决办法]
我的意思是每次平方产生的数字集合比上一次平方产生的结合产生新的数字，不知道对不对

235^2==55225
55225^2=3049800625
...

如果是这样，那么这个数就至少小于10

探讨

引用:
数论的题目，看起来简单，做起来往往很难！
看起来每次平方以后都可以产生新的数字？
235^2==55225

[解决办法]
822^2 == 675684
675684^2 == 456548867856 <---没有产生新数字

这种看上去不像的猜想基本都是很容易找到反例的。
[解决办法]
转化成另一个命题?... 
比如说a有3位
那么a^(2^n)的后3位的数字也会出现在(b*10^3+a)^(2^n)里
可以先在1-999之内判断在6步以内后3位是否覆盖了所有的数字
对不满足的数,比如说2,判断2是否满足原命题,1002,2002,3002,...,9002是否后4位覆盖了所有的数字..

...很笨的想法T_T
[解决办法]
其实Arucart的思路挺好的，就是说假设小于k的数都成立，任何一个a，都可以通过mod k，转化为一个小于k的数，证明经过转化之后，与原命题是等价的或强于原命题。然后我们可以通过计算机枚举所有小于k的数，验证是否成立。
[解决办法]
这个k看来可能永远找不到，用宽搜找了一下，发现最后剩下的就是5的倍数和类似xxx99999999999999999999的数，看看能否把这部分单独证明一下（最大搜索到10^100)。

探讨

其实Arucart的思路挺好的，就是说假设小于k的数都成立，任何一个a，都可以通过mod k，转化为一个小于k的数，证明经过转化之后，与原命题是等价的或强于原命题。然后我们可以通过计算机枚举所有小于k的数，验证是否成立。

[解决办法]
有个思路也许能够证明一定能覆盖1-9，

10^k < x^(2^n) < 2 * 10^k => k*log(x,10) < 2^n < k*log(x,10) + log(x,2)

证明任何x都可以找到一对k和n，满足上面的不等式，log(x,2)虽然很小，但无理数的整数倍再取模，应该可以无限逼近0。

不过0的证明还有问题。另外这个最多能证明覆盖0-9，但6步就无法证明了
[解决办法]
下面是我用java写的方法，经测试还可以；int test(long a)其中a幂底数，方法将返回求幂次数；适用于任何大于2的数字。
有个缺点就是有可能long类型长度不够用，导致程序出错，如a=2时；这样大家可以换用BigInteger类型

public int test(long a) {
// 判断a是否是10的n次方
if (a == 1) {
return -1;
}
String temp = Long.toString(a);
if (temp.charAt(0) == '1' && Long.parseLong(temp.substring(1)) == 0) {
return -1;
}

Set<Integer> set = new HashSet<Integer>();
// 记录求幂次数
int count = 0;
boolean flag = true;
while (flag) {
a = a * a;
List<Integer> list = toArray(a);
for (int j = 0; j < list.size(); j++) {
int t = list.get(j);
set.add(t);
if (set.size() == 10) {
flag = false;
break;
}
}
count++;
}
return count;
}

/**
* 该方法将整数拆分为一个个0-9的数，保存到list中
* 
* @param num
* @return
*/
public List<Integer> toArray(long num) {
List<Integer> list = new ArrayList<Integer>();
while (num > 0) {
int t = (int) (num % 10);
list.add(t);
num = num / 10;
}
return list;
}
[解决办法]
牛叉叉的题目，正在思考ing
[解决办法]
我觉得可以通过从{4,5,9,6}开始,结果可能是这几个数开始得出的结果+1,因为任何数的平方末尾必然是 1,4,5,9,6,N不等于1.故从{4,5,9,6}开始

查看更多 下一篇