Ten digit numbers

northwolves · 发表于 2009-1-11 23:28:42

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

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

×

刚写了两篇文章： Largest Ten Digit Powers Smallest Ten Digit Powers 算得太累了,vb实在是太慢了，c++ 尚未学到家，谁能帮帮忙？或者提供相应的理论支持？

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

OEIS对应结果，数目在A357755, 最小数在A154566，最大数在A154532

northwolves · 发表于 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位数。

mathe · 发表于 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

第一个版本不过似乎有点慢

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
int digitNum[1000000][10];
mpz_t m, t6;
void init(void)
{
int i1, i2, i3, i4, i5, i6, n;
for (i1 = 0; i1 <= 9; i1 ++)
for (i2 = 0; i2 <= 9; i2 ++)
for (i3 = 0; i3 <= 9; i3 ++)
for (i4 = 0; i4 <= 9; i4 ++)
for (i5 = 0; i5 <= 9; i5 ++)
for (i6 = 0; i6 <= 9; i6 ++)
{
n = (i1 << 16 + i1 << 15 + i1 << 10 + i1 << 9 + i1 << 7 + i1 << 5);
n += (i2 << 13 + i2 << 11 - i2 << 8 + i2 << 4);
n += (i3 << 10 - i3 << 4 - i3 << 3);
n += (i4 << 6 + i4 << 5 + i4 << 2) + (i5 << 3 + i5 << 1) + i6;
digitNum[n][i1]++;
digitNum[n][i2]++;
digitNum[n][i3]++;
digitNum[n][i4]++;
digitNum[n][i5]++;
digitNum[n][i6]++;
}
}
int test(mpz_t pow, int p)
{
unsigned tmp, i;
int d[10];
for (i = 0; i < 10; i ++) d[i] = 0;
while (mpz_cmp_ui(pow, 0) == 0)
{
mpz_divmod(pow, m, pow, t6);
tmp = mpz_get_ui(m);
for (i = 0; i < 10; i ++)
d[i] += digitNum[tmp][i];
}
for (i = 0; i < 10; i ++)
if (d[i] != p) return 0;
return 1;
}
int main(void)
{
int p, b, i = 0;
mpz_t n, pow;
char start[16];
printf("输入方幂: ");
scanf("%d", &p);
printf("输入起始数字(最大16位): ");
scanf("%s", start);
mpz_init(pow);
mpz_init(n);
mpz_init(m);
mpz_init(t6);
mpz_set_ui(t6, 1000000);
mpz_set_str(n, start, 10);
b = 0;
printf("\n");
while (b == 0)
{
i ++;
mpz_pow_ui(pow, n, p);
if (test(pow, p) == 1)
{
gmp_printf("找到[%Zd, %Zd]\n", n, pow);
break;
}
mpz_add_ui(n, n, 1);
if (i >= 100000000)
{
i = 0;
gmp_printf("搜索到%Zd\n", n);
}
}
mpz_clear(n);
mpz_clear(pow);
mpz_clear(m);
mpz_clear(t6);
return 0;
}

复制代码

无心人 · 发表于 2009-1-12 10:32:14

搜索着19的呢 70秒一个亿

无心人 · 发表于 2009-1-12 10:49:09

似乎，好像， 19的不存在

mathe · 发表于 2009-1-12 11:00:39

可以用C++代码，类似

#include <algorithm>
using namespace std;
char b[10]={0,1,2,3,4,5,6,7,8,9};
int get_digit()
{
int s=0,i;
for(i=0;i<10;i++){s*=10;s+=b[i];}
}
int r;
do{
if(b[0]==0)continue;
r=get_digit();
mpz_init_ui(x,r);
mpz_pow_ui(y,x,n);
check(y,n);
}while(next_permutation(b,b+10));

复制代码

mathe · 发表于 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)

mathe · 发表于 2009-1-12 11:39:45

代码

#define MAX_N 20
integer x;
char b[10]={0,1,2,3,4,5,6,7,8,9};
int cc[MAX_N+1],dd[MAX_N+1];
void check(integer& x,integer& y, int k)
{
LPCTSTR s=y.GetStr(FS_NORMAL);
int i;
int count[10];
for(i=0;i<10;i++)count[i]=0;
for(i=0;s[i]!='\0';i++){
if('0'<=s[i]&&s[i]<='9'){
int h=s[i]-'0';
count[h]++;
if(count[h]>k)return;
}
}
if(count[0]<k){
printf("[weak result]");
}else{
dd[k]++;
}
cc[k]++;
printf("%s^%d=%s\n",x.GetStr(FS_NORMAL),k,s);
}
void test()
{
int i;
x=0;
for(i=0;i<10;i++){
x*=10;x+=b[i];
}
integer y(x);
for(i=2;i<=MAX_N;i++){
y*=x;
check(x,y,i);
}
}
int main(int argc, char* argv[])
{
time_t t=time(NULL);
int i;
do{
if(b[0]==0)continue;
test();
}while(next_permutation(b,b+10));
t=time(NULL)-t;
printf("Total cost %dseconds\n",t);
for(i=2;i<=MAX_N;i++){
printf("count[%d]=%d(%d)\n",i,cc[i],dd[i]);
}
return 0;
}

复制代码

northwolves · 发表于 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次

账号		自动登录	找回密码
密码			欢迎注册

[擂台] Ten digit numbers

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