找回密码
 欢迎注册
查看: 89412|回复: 127

[擂台] Ten digit numbers

[复制链接]
发表于 2009-1-11 23:28:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
精华
刚写了两篇文章:

Largest Ten Digit Powers

Smallest Ten Digit Powers

算得太累了,vb实在是太慢了,c++ 尚未学到家,谁能帮帮忙?或者提供相应的理论支持?

经过大家天衣无缝的协作,已得到结果,放在 119#;程序及源码在 70#
——gxqcn


OEIS对应结果,数目在A357755,  最小数在A154566, 最大数在A154532
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-1-11 23:34:06 | 显示全部楼层
通过计算,一个10位数,如果其n次方恰好含0-9各n次,其理论出现的个数为:
(10n)!*(10^10-10^(10-1/n))/((n!)^10 * 10^((10*n)-10^(10*n-1))

我已经计算出满足条件的 n<=18 的 最小10位数 和 n<=20 的最大10位数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 09:16:35 | 显示全部楼层
其实速度同语言应该关系不是太大。VB如果编译后执行,速度应该也就比C慢上几倍。
不过如果用C,所有大数运算可以直接调用gmp库,也许可以快一些,不知道VB里面是否能够使用,倒是你可以在VB里面调用gxq的HugeCalc。
不过你的程序里面枚举所有0-9各出现一次的10位数的方法,倒是可以改善一下,直接构造这9*9!个数就可以了,不过这部分影响可能不算太大。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 10:23:55 | 显示全部楼层
第一个版本
不过似乎有点慢

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <gmp.h>

  4.   int digitNum[1000000][10];
  5.   mpz_t m, t6;
  6.   
  7. void init(void)
  8. {
  9.   int i1, i2, i3, i4, i5, i6, n;
  10.   for (i1 = 0; i1 <= 9; i1 ++)
  11.     for (i2 = 0; i2 <= 9; i2 ++)
  12.       for (i3 = 0; i3 <= 9; i3 ++)
  13.         for (i4 = 0; i4 <= 9; i4 ++)
  14.           for (i5 = 0; i5 <= 9; i5 ++)
  15.             for (i6 = 0; i6 <= 9; i6 ++)
  16.             {
  17.                 n = (i1 << 16 + i1 << 15 + i1 << 10 + i1 << 9 + i1 << 7 + i1 << 5);
  18.                 n += (i2 << 13 + i2 << 11 - i2 << 8 + i2 << 4);
  19.                 n += (i3 << 10 - i3 << 4 - i3 << 3);
  20.                 n += (i4 << 6 + i4 << 5 + i4 << 2) + (i5 << 3 + i5 << 1) + i6;   
  21.                 digitNum[n][i1]++;
  22.                 digitNum[n][i2]++;
  23.                 digitNum[n][i3]++;
  24.                 digitNum[n][i4]++;
  25.                 digitNum[n][i5]++;
  26.                 digitNum[n][i6]++;               
  27.             }   
  28. }

  29. int test(mpz_t pow, int p)
  30. {
  31.   unsigned tmp, i;
  32.   int d[10];
  33.   for (i = 0; i < 10; i ++) d[i] = 0;
  34.   while (mpz_cmp_ui(pow, 0) == 0)
  35.   {
  36.     mpz_divmod(pow, m, pow, t6);
  37.     tmp = mpz_get_ui(m);
  38.     for (i = 0; i < 10; i ++)
  39.       d[i] += digitNum[tmp][i];
  40.   }
  41.   
  42.   for (i = 0; i < 10; i ++)
  43.       if (d[i] != p) return 0;
  44.   return 1;
  45. }
  46. int main(void)
  47. {
  48.   int p, b, i = 0;
  49.   mpz_t n, pow;
  50.   char start[16];
  51.   printf("输入方幂: ");
  52.   scanf("%d", &p);
  53.   printf("输入起始数字(最大16位): ");
  54.   scanf("%s", start);
  55.   mpz_init(pow);
  56.   mpz_init(n);
  57.   mpz_init(m);
  58.   mpz_init(t6);
  59.   mpz_set_ui(t6, 1000000);
  60.   mpz_set_str(n, start, 10);
  61.   b = 0;
  62.   printf("\n");
  63.   while (b == 0)
  64.   {
  65.     i ++;  
  66.     mpz_pow_ui(pow, n, p);
  67.     if (test(pow, p) == 1)
  68.     {
  69.       gmp_printf("找到[%Zd, %Zd]\n", n, pow);
  70.       break;
  71.     }
  72.     mpz_add_ui(n, n, 1);
  73.     if (i >= 100000000)
  74.     {
  75.       i = 0;
  76.       gmp_printf("搜索到%Zd\n", n);
  77.     }
  78.   }
  79.   mpz_clear(n);
  80.   mpz_clear(pow);
  81.   mpz_clear(m);
  82.   mpz_clear(t6);
  83.   return 0;
  84. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 10:32:14 | 显示全部楼层
搜索着19的呢
70秒一个亿
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 10:49:09 | 显示全部楼层
似乎, 好像, 19的不存在
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 11:00:39 | 显示全部楼层
可以用C++代码,类似

  1. #include <algorithm>
  2. using namespace std;
  3. char b[10]={0,1,2,3,4,5,6,7,8,9};
  4. int get_digit()
  5. {
  6.     int s=0,i;
  7.     for(i=0;i<10;i++){s*=10;s+=b[i];}
  8. }

  9. int r;
  10. do{
  11.        if(b[0]==0)continue;
  12.        r=get_digit();
  13.        mpz_init_ui(x,r);
  14.        mpz_pow_ui(y,x,n);
  15.        check(y,n);
  16. }while(next_permutation(b,b+10));
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 11:36:45 | 显示全部楼层
结果好像挺多的,所以LZ估算的误差好像太大了,下面是计数,括号里面是不允许0开头的数目,括号前面包含了0开头的数:
用的是gxq的HugeCalc,附件里给出了所有的结果
Total cost 164seconds
count[2]=887(703)
count[3]=237(174)
count[4]=138(94)
count[5]=117(89)
count[6]=118(75)
count[7]=130(83)
count[8]=122(73)
count[9]=140(89)
count[10]=168(98)
count[11]=202(111)
count[12]=222(92)
count[13]=255(123)
count[14]=304(123)
count[15]=348(158)
count[16]=371(142)
count[17]=386(133)
count[18]=471(173)
count[19]=533(178)
count[20]=622(188)

result.zip

342.63 KB, 下载次数: 11, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-1-12 11:39:45 | 显示全部楼层
代码

  1. #define MAX_N 20
  2. integer x;
  3. char b[10]={0,1,2,3,4,5,6,7,8,9};
  4. int cc[MAX_N+1],dd[MAX_N+1];
  5. void check(integer& x,integer& y, int k)
  6. {
  7.     LPCTSTR s=y.GetStr(FS_NORMAL);
  8.     int i;
  9.     int count[10];
  10.     for(i=0;i<10;i++)count[i]=0;
  11.     for(i=0;s[i]!='\0';i++){
  12.         if('0'<=s[i]&&s[i]<='9'){
  13.             int h=s[i]-'0';
  14.             count[h]++;
  15.             if(count[h]>k)return;
  16.         }
  17.     }
  18.     if(count[0]<k){
  19.         printf("[weak result]");
  20.     }else{
  21.         dd[k]++;
  22.     }
  23.     cc[k]++;
  24.     printf("%s^%d=%s\n",x.GetStr(FS_NORMAL),k,s);
  25. }

  26. void test()
  27. {
  28.     int i;
  29.     x=0;
  30.     for(i=0;i<10;i++){
  31.         x*=10;x+=b[i];
  32.     }
  33.     integer y(x);
  34.     for(i=2;i<=MAX_N;i++){
  35.         y*=x;
  36.         check(x,y,i);
  37.     }
  38. }

  39. int main(int argc, char* argv[])
  40. {
  41.     time_t t=time(NULL);
  42.     int i;
  43.     do{
  44.         if(b[0]==0)continue;
  45.         test();
  46.     }while(next_permutation(b,b+10));
  47.     t=time(NULL)-t;
  48.     printf("Total cost %dseconds\n",t);
  49.     for(i=2;i<=MAX_N;i++){
  50.         printf("count[%d]=%d(%d)\n",i,cc[i],dd[i]);
  51.     }
  52.     return 0;
  53. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-1-12 13:04:32 | 显示全部楼层
原帖由 mathe 于 2009-1-12 11:36 发表
结果好像挺多的,所以LZ估算的误差好像太大了,下面是计数,括号里面是不允许0开头的数目,括号前面包含了0开头的数:
用的是gxq的HugeCalc,附件里给出了所有的结果
Total cost 164seconds
count[2]=887(703)
coun ...


似乎与我的题目不一样。
我的要求是任意十位数,其n次方结果中,0-9 10个数字正好分别出现n次。
如:
9873773268^19=7855608929517570243129124902383848671305376350326251297158422748900643175003663401660063412051329789580670429726512989648355976426934188517557270873647143849124881043569143877856149091909632

等号后的数字为190位数,0-9分别出现了19次
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 13:51 , Processed in 0.050350 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表