欧拉工程第63题：Powerful digit counts

题目链接

The 5-digit number, 16807=7⁵, is also a fifth power. Similarly, the 9-digit number, 134217728=8⁹, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

这个题目有点坑：

先说自己的思路<虽然方法不是很好>

根据题意可知道：

a的b次方除以最小的b位数（如：1，10,100,1000）的商在 1--9之间，则：a的b次方就是符合题意的

然后就根据这个遍历

先找到第一个数符合条件的数firstnum

再找到第一个符合条件之后的第一个不满足条件的数nextnum

则：这中间有 nextnum - firstnum个数

当b也就是次方数大于18的时候，Long都溢出了

此时：有46个数

下面是程序：

 1 package project61;
 2 
 3 import java.math.BigInteger;
 4 
 5 public class P63{
 6 //    a的b次方是b位数
 7 //    a的b次方 除以 b位的第一个数（如：1000） 商 在1 - 9之间
 8 //    以a为开始，找到第一个满足条件的数，如不存在返回 0 
 9 //    满足条件的数是连续的
10     long findFirst(long Base,int exp){
11         long res =(long) Math.pow(Base, exp);
12         long d = 1;
13         int Max_Cycle = 10000;
14         int texp = exp;
15         while(exp!=1){
16             d = d*10;
17             exp--;
18         }
19         boolean flag = true ;
20         int quot = 0;
21         while(Max_Cycle!=0){
22             quot = (int) (res/d);
23 //            System.out.println(quot+"res:"+res+" Base:"+Base+" d:"+d);
24             if(quot>=1 && quot<=9){
25                 return Base;
26             }
27             Base = Base + 1;
28             res = (long) Math.pow(Base, texp);
29             Max_Cycle--;
30         }
31         return 0 ;
32     }
33     
34     long findNext(long Base,int exp){
35         long res =(long) Math.pow(Base, exp);
36         long d = 1;
37         int Max_Cycle = 100000;
38         int texp = exp;
39         while(exp!=1){
40             d = d*10;
41             exp--;
42         }
43         boolean flag = true ;
44         int quot = 0;
45         while(Max_Cycle!=0){
46             quot = (int) (res/d);
47             System.out.println("商:"+quot +" 被除数:"+ res+" 除数:"+d+" 底数:"+Base+" 指数:"+texp);
48             if(quot==0 ||quot>9){
49                 
50                 return Base;
51             }
52             Base = Base + 1;
53             res = (long) Math.pow(Base, texp);
54             Max_Cycle--;
55         }
56         return 0 ;
57     }
58     void run(){
59         long result = 0;
60         int base = 1;
61         int exp = 1;
62 
63         while(exp<=18){
64             base = 1 ;
65             long firstNum = findFirst(base,exp);
66             if(firstNum !=0){
67             
68             long next = findNext(firstNum,exp);
69             System.out.println("第一个满足条件的底数:"+firstNum +" 第一个不满足条件的底数： "+ next);
70             result = result + next - firstNum;
71             
72             }
73             exp++;
74         }
75         System.out.println(result);
76     }
77     
78     public static void main(String[] args){
79         long begin= System.currentTimeMillis();
80         new P63().run(); 
81         long end = System.currentTimeMillis();
82         long Time = end - begin;
83         System.out.println("Time:"+Time/1000+"s"+Time%1000+"ms");
84     }
85 }

View Code

程序流程：

1.在相同的指数情况小，找符合条件的数

1.1找到第一个符合条件的数的底数

1.2找到符合条件数后面的第一个不符合条件的数

1.3这两个数的差，就是在这个指数下所以符合条件的数

2.增加指数。

下面是运行的结果：

可以看出，只有1-9的底数满足条件，上面红框中的是满足条件后的第一个不满足条件的数。

上面至少知道18，设成18以上，溢出，，，输入上面的46当然是不对的，应该是还有的

尝试直接在9的19,20,21...的数中找符合条件的数：

        BigInteger base = new BigInteger("9");
        BigInteger bigres = new BigInteger("0");
        String toStr = "";
        int exp = 18;
        
        for(exp=19;exp<25;exp++){
            bigres = base.pow(exp);
            toStr = bigres+"";
            if(toStr.length() ==exp)
            System.out.println(toStr);
        }

通过上面的程序，就只是把符合条件的其他三个数输出了。

答案是：49

上面的过程是不是太复杂了，如果直接利用BigInteger也不会这么复杂的。

然后看到别人是这样做的：

上面说的很详细。。。

void run1(){
        int count = 0;
        for(int x = 1;x<10;x++){
            count +=(int)(1.0/(1-Math.log(x)/Math.log(10)));

        }
        System.out.println(count);
    }

程序就成这样的了。。。

Python程序：

from math import log10

s = 0 
for n in range(1,10):
    s += int(1/(1-log10(n)))
    
print "result=",s

Python程序就是这样的了。。。

from math import log10


print sum(map(int, map(lambda a: 1.0/(1.0-log10(a)), range(1, 10))))

Python 也可以这样来。。。