寻找最小的幂，其首部由连续若干个相同数字构成

gxqcn

这个问题必须借助高精度大数算法库。
它看似乘幂，实则为高精度开方，如果需要追求高效搜索的话。

我刚才用 6# 的代码搜索 a(200)，结果如下：90832044031629032072266808763200776597377591732476977169715120443019881412500755990159501693981554567930162406118174820455381598058901681451049443406788180959583740354008958099702541401274789601262
其 200 次方的前 200 个连续数字均为 4
搜索耗时用了不到半小时，期间进行大数开方 352724 次，最大被开方数有 39392 位。

该算法效率比我最初预估的高了不少。

无心人

我觉得用浮点数计算似乎要快点
有点懒得算，呵呵
还要装mpf

另外，为什么不用个记号呢
$mIn(p)$表示$p$位数字，其中前$n$位是由$m$重复得到的

〇〇

import  java.math.BigDecimal;
import  java.math.MathContext;
public class root
{
public  static  void  main(String[]  args)  {

/*
System.out.println(Math.pow(2,  1.0  /  5));

System.out.println(root(2,  5));

BigDecimal  b  =  root(new  BigDecimal(2),  5);
System.out.println(b.toString());   
//可以用下面两条Java句子解决：
System.out.println(Integer.MAX_VALUE);//打印最大整数:2147483647
System.out.println(Integer.MIN_VALUE);//打印最小整数:-2147483648
//相应的浮点数：
System.out.println(Float.MAX_VALUE);
System.out.println(Float.MIN_VALUE);
//双精度：
System.out.println(Double.MAX_VALUE);
System.out.println(Double.MIN_VALUE);

for(int n=1;n<=14;n++)
label1:for(int m=1;m<=200;m++)
for(int j=1;j<9;j++)
{
if(Math.floor(Math.pow(Math.pow(10,m)*(Math.pow(10,n)-1)/9*j,1.0/n))+1
==Math.floor(Math.pow(Math.pow(10,m)*((Math.pow(10,n)-1)/9*j+1),1.0/n)))
{
System.out.print(n+":\t");
System.out.println(Math.floor(Math.pow(Math.pow(10,m)*((Math.pow(10,n)-1)/9*j+1),1.0/n)));

break label1;
}
}
*/
BigDecimal ONE=BigDecimal.ONE;
BigDecimal TEN=BigDecimal.TEN;
BigDecimal N9=TEN.subtract(ONE);
for(int n=1;n<=14;n++)
label2:for(int m=1;m<=200;m++)
for(int j=1;j<9;j++)
{
BigDecimal J=new BigDecimal(j);

BigDecimal M=root(TEN.pow(m).multiply(TEN.pow(n).add(ONE.negate()).divide(N9).multiply(J)),n).add(ONE);
BigDecimal N=root(TEN.pow(m).multiply(TEN.pow(n).add(ONE.negate()).divide(N9).multiply(J).add(ONE)),n);
if(M.toBigInteger().compareTo(N.toBigInteger())==0)
{
System.out.print(n+":\t");
System.out.println(M.toBigInteger());

break label2;
}
}


}


//  算法来源：http://bbs.51js.com/thread-59522-1-197.html，9楼的回帖
//  原算法使用  JavaScript  写的，使用  Java  改进了一下
//  这个算法的收敛速度很快，可以堪称优秀了
public  static  double  root(double  num,  int  radix)  {
double  result  =  1.0;
double  pow  =  result;
double  r  =  pow  /  result;
double  error  =  pow  -  num;
double  p  =  r  *  radix;
double  epsilon  =  1.0e-10;
while  (Math.abs(error)  >  epsilon)  {
  result  =  result  -  error  /  p;   
  pow  =  result;
  int  k  =  1;
  while  (k  <  radix)  {
   pow  *=  result;
   k++;
  }
  r  =  pow  /  result;
  error  =  pow  -  num;
  p  =  r  *  radix;
}
return  result;
}

//  BigDecimal  的  pow()  方法只能是  int  类型的，这样就不能计算
//  方根，按上述算法新增一个
public  static  BigDecimal  root(BigDecimal  num,  int  radix)  {
int  precision  =  6;  //  增大可以提高运算精度
BigDecimal  result  =  new  BigDecimal(1);
BigDecimal  pow  =  result;
BigDecimal  r  =  pow.divide(result);
BigDecimal  error  =  pow.subtract(num);
BigDecimal  p  =  r.multiply(new  BigDecimal(radix));
BigDecimal  epsilon  =  new  BigDecimal(10).pow(-precision,  new  MathContext(precision));
while  (error.abs().compareTo(epsilon)  >  0)  {
  result  =  result.subtract(error.divide(p,  new  MathContext(precision)));   
  pow  =  result;
  int  k  =  1;
  while  (k  <  radix)  {
   pow  =  pow.multiply(result);
   k++;
  }
  r  =  pow.divide(result);
  error  =  pow.subtract(num);
  p  =  r.multiply(new  BigDecimal(radix));
}
return  result;
}
}

gxqcn

牛顿迭代法是高精度算法中经常用要用到的基本技巧之一，包括用在开方运算中。

本题若无高效的大数算法库支持，效率和精度将无法保证，很难进行下去。

〇〇

要提高效率，怎么修改算法呢

无心人

首先就不能选Java语言
呵呵

mathe

这个题目里面Java不见得会比C效率差.主要是大数运算库的效率问题

knate

1. 
   
2. 
   
3. //n 为首部由连续相同数字的长度
   
4. // 令 11111......111   = m (n 位相同的数字1)
   
5. //k 为相同的数字( 1--9)
   
6. //  [X] 取整
   
7. 
   
8. for(k = 1;k<= 9;++k){//可能的首位相同的数字
   
9.      for(i = 0;i<n;i++){//后面追加的0的个数
   
10.     x = (m × 10^i) ^(1/n) ;  // ^(1/n)  开n次方
    
11.     x = [x];
    
12.     y = ((m+1) × 10^i) ^(1/n) ;  
    
13.     y = [y];
    
14.     if(x != y)
    
15.    M.push_back(y);
    
16.     }
    
17. }
    
18. 
    
19. return  min(M);
    
20. 
    
21. //开方次数为 2 × 9  × n
    
22. //手上没有现成的高精度大数运算接口.没程序.
    
23. //使用上面的一些结果.符合.
    

复制代码

knate

剔除 999999 n个9的情况。

无心人

我不认为虚拟机语言的高精度计算能比C更好

除了几个底层就支持高精度计算的语言，比如Smalltalk外
Java等，必须用包装了整数运算的类再包装高精度运算
而且很多语言不能解决双精度运算问题，只能模拟双精度运算
不过java等是否语言层次支持双精度运算，俺不清楚

包括C都无法避免双精度计算问题，只能用内嵌汇编避开
虚拟机语言做双精度计算效率更低

研究过C#的il，很失望的发现，内核级的双精度计算指令没有