平方数数字和

mathe · 发表于 2008-7-10 08:30:09

呵呵，那应该还可以改善，看liangbch它们计算$10^9$以内素数的代码花不了多少时间的，抄袭一个过来，然后对每个素数计算一下数字和就可以了

mathe · 发表于 2008-7-10 08:41:45

发现
66...6(n个6)5的平方是
44...4(n个4)22...2(n+1个2)5
所以证明了对于任意6n+1,存在一个平方数，数字之和为6n+1
同样，
66...6(n个6)的平方是
44..4(n-1个4)35...5(n-1个5)6
所以证明了对于任意9的倍数9n，存在一个平方数，数字和为9n
现在只要能够对于6n+4也能够构造除平方数，数字和为6n+4,那么就证明了题目中的猜想。

gxqcn · 发表于 2008-7-10 09:09:09

原帖由 kofeffect 于 2008-7-9 19:03 发表
X=76 S=5599977889

上述结果有误，我算出 X=76 S=2896989988<5599977889

请 kofeffect 排查是否还有其它错误。

kofeffect · 发表于 2008-7-10 09:20:57

原帖由 gxqcn 于 2008-7-10 09:09 发表

上述结果有误，我算出 X=76 S=2896989988

使用google计算得：
sqrt(2 896 989 988) = 53 823.6936
sqrt(5 599 977 889) = 74 833

mathe · 发表于 2008-7-10 10:01:03

现在总于找到了一个构造CSDN中题目
http://topic.csdn.net/u/20080705 ... 7-95b1d700a69f.html
需要充分大步数才能够达到1的方法。
注意到对于$n>=2$,
数字99...9(n个9)1的立方是
99..9(n-1个9)730...0(n-2个0)2429...9(n-2个9)271
上面立方数的数字和为18*n+1
而数字99...9(n个9)1本身模18也为1，
我们可以构造序列
$T_1=991,S_1=T_1^3=973242271$
在已经知道$T_k$和$S_k$的情况下（其中$T_k=1(mod 18)$）
我们记$x_k=(T_k-1)/18$
定义$T_{k+1}$=99...9($x_k$个9)1,$S_{k+1}=T_{k+1}^3$
那么我们可以知道$S_k$是奇数,$S_k$的数字和为$18*x_{k-1}+1=T_{k-1}$
所以经过一步变换以后$S_k$会变换为$T_{k-1}^3=S_{k-1}$
现在的问题是所有的$S_k$都是奇数，不满足题目中初始数字是偶数的要求，为此，我们查看规律
66...6(n个6)5的平方为4..4(n个4)2...2(n+1个2)5,这个平方数的数字和是6n+7
由于$T_k=1(mod 6)$,所以我们可以构造数字
$X_k$=66...6($(T_k-7)/6$个6)5
然后我们取数字$Y_k$是一个长度为$X_k-1$的数字，$Y_k$末位为2，其他各位都是1，也就是
$Y_k=(10^{X_k}+8)/9$
于是我们知道$Y_k$是偶数，而且$Y_k$不是3的倍数（这是因为$X_k$不是3的倍数），$Y_k$所有数字之和为$X_k$
所以$Y_k$经过一步变换以后是$X_k^2$是奇数
而$X_k^2$的数字之和为$6*(T_k-7)/6+7=T_k$
所以$Y_k$经过两步变换以后变成$T_k^3=S_k$
然后继续根据前面的结论我们知道$Y_k$经过k+1步变换以后变成$S_1=973242271$
而
973242271==>50653==>6859==>21952==>361==>1000==>1
所以我们知道不是3的倍数的偶数$Y_k$总共需要k+7步才能够变换成1。
也就是通过这种方法，我们知道对于任意x>=8,我们都可以构造出一个数字需要x步变换变化到1。

gxqcn · 发表于 2008-7-10 10:02:15

原帖由 kofeffect 于 2008-7-10 09:20 发表
使用google计算得：
sqrt(2 896 989 988) = 53 823.6936
sqrt(5 599 977 889) = 74 833

这是优化程度比较高的代码，刚才误把“0xFFFF”多写了个“F”而成“0xFFFFF”！

居然被罚了一枝[img=http://www.emath.ac.cn/image/bbs/smiley/50.gif]鲜花[/img]，我 [img=http://www.emath.ac.cn/image/bbs/smiley/41.gif]去撞墙[/img]

#include <stdlib.h>
#include <stdio.h>
#include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
#pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#if 1
# define SQRT_DIGIT 8UL
# define SQRT_MAX 100000000UL
#else
# define SQRT_DIGIT 9UL
# define SQRT_MAX 1000000000UL
#endif
#define TEN_POW9 1000000000UL
// 返回余数；u32Num 作为输入的被除数，同时作为输出的商
__declspec(naked)
CONST UINT32 DivMod10( UINT32& u32Num )
{
__asm
{
mov ecx, dword ptr[esp + 0x04];
mov edx, dword ptr[ecx];
mov eax, 0xCCCCCCCD; // [ 2^35 / 10 + 0.5 ]
push edx;
mul edx;
shr edx, 3;
mov dword ptr[ecx], edx;
imul edx, 10;
pop eax;
sub eax, edx;
ret;
}
}
UINT32 SumOfDigits( UINT32 v )
{
UINT32 sum = 0;
while( 0 != v )
{
sum += DivMod10( v );
}
return sum;
}
int main( void )
{
UINT32 i, s, delta, v;
UINT32 high, high_delta;
UINT32 mark[ 164 ] = { 0 };
UINT32 cycleDelta[ 4 ] = { 1, 3, 3, 2 }; // 0, 1, 4, 7
HugeCalc::EnableTimer();
HugeCalc::ResetTimer();
v = 1;
delta = 1;
for ( i=1; i<0xFFFF; ++i )
{
s = SumOfDigits( v );
if ( 0 == mark[ s ] )
{
mark[ s ] = i;
}
delta += 2;
v += delta;
}
high = v / TEN_POW9;
v -= high * TEN_POW9;
high_delta = delta / TEN_POW9;
delta -= high_delta * TEN_POW9;
for ( ; i<=SQRT_MAX; ++i )
{
s = SumOfDigits( v ) + SumOfDigits( high );
if ( 0 == mark[ s ] )
{
mark[ s ] = i;
}
delta += 2;
if ( delta >= TEN_POW9 )
{
delta -= TEN_POW9;
++high_delta;
}
v += delta;
if ( v >= TEN_POW9 )
{
v -= TEN_POW9;
high += high_delta + 1;
}
else
{
high += high_delta;
}
}
HugeCalc::EnableTimer( FALSE );
s = 0;
i = 0;
while ( s != 9*SQRT_DIGIT*2 )
{
s += cycleDelta[ i ];
if ( 4 == ++i )
{
i = 0;
}
if ( 0 != mark[ s ] )
{
if ( mark[ s ] <= 0xFFFF )
{
printf( "X = %u\tS = %u\n", s, mark[ s ] * mark[ s ] );
}
else
{
printf( "X = %u\tS = %I64u\n", s, UInt32x32To64( mark[ s ], mark[ s ] ));
}
}
else
{
printf( "X = %u\n", s );
}
}
printf( HugeCalc::GetTimerStr( FT_HHMMSS_ms ) );
printf( "\n" );
return 0;
}

复制代码

备注：代码中，仅调用了 HugeCalc 的高精度计时部分。

gxqcn · 发表于 2008-7-10 10:03:07

X = 1 S = 1
X = 4 S = 4
X = 7 S = 16
X = 9 S = 9
X = 10  S = 64
X = 13  S = 49
X = 16  S = 169
X = 18  S = 576
X = 19  S = 289
X = 22  S = 1849
X = 25  S = 4489
X = 27  S = 3969
X = 28  S = 17956
X = 31  S = 6889
X = 34  S = 27889
X = 36  S = 69696
X = 37  S = 98596
X = 40  S = 97969
X = 43  S = 499849
X = 45  S = 1887876
X = 46  S = 698896
X = 49  S = 2778889
X = 52  S = 4999696
X = 54  S = 9696996
X = 55  S = 19998784
X = 58  S = 46689889
X = 61  S = 66699889
X = 63  S = 79869969
X = 64  S = 277788889
X = 67  S = 478996996
X = 70  S = 876988996
X = 72  S = 3679999569
X = 73  S = 1749999889
X = 76  S = 5599977889
X = 79  S = 7998976969
X = 81  S = 8998988769
X = 82  S = 17999978896
X = 85  S = 36799899889
X = 88  S = 88998998929
X = 90  S = 297889998849
X = 91  S = 299879997769
X = 94  S = 897977978689
X = 97  S = 975979998889
X = 99  S = 3957779999889
X = 100 S = 2699997789889
X = 103 S = 9879498789889
X = 106 S = 9998768898889
X = 108 S = 29998985899689
X = 109 S = 85986989688889
X = 112 S = 97888999968769
X = 115 S = 386999898769969
X = 117 S = 429998989997889
X = 118 S = 578889999977689
X = 121 S = 898999897988929
X = 124 S = 1959999889996996
X = 126 S = 6788999798879769
X = 127 S = 3699998989898689
X = 130 S = 9895699989899689
X = 133
X = 135
X = 136
X = 139
X = 142
X = 144
00:00:11.243
Press any key to continue

若设定 SQRT_DIGIT 为 9UL 时，运行结果如下（133前的不再重复贴出）：

X = 133 S = 38896878989988889
X = 135 S = 67699789959899889
X = 136 S = 38999699989995889
X = 139 S = 188997899869998769
X = 142 S = 279869897899999969
X = 144 S = 498999778899898896
X = 145
X = 148 S = 989879999979599689
X = 151
X = 153
X = 154
X = 157
X = 160
X = 162
00:02:06.074
Press any key to continue

gxqcn · 发表于 2008-7-10 10:34:49

还可采用查表法来减少除法运算次数，
比如每三位一分段。

shshsh_0510 · 发表于 2008-7-10 10:55:59

x=100的会很多，最小的是$1643167^2=2699997789889$
其他的小于10000000的数如下：
1643167,
2827313,2880937,2946167,2997764,
3127267,3142133,3143087,3144833,3146417,3160583,3870386,
4168333,4241456,4323887,4345676,4347413,4348333,4357063,4438333,4448357,4448593,4449583,4454207,4460714,4469786,4469887,
4470983,4471417,
5068333,5087917,5329117,5357042,5366456,5373937,5383214,5384134,5384233,5447917,5457563,5458843,5458933,5466077,5467076,
5467814,5475383,5821417,5914117,5914286,5972687,5991634,
6058043,6066053,6079472,6161077,6164414,6185386,6210314,6232886,6241634,6244757,6292853,6299117,6308407,6314903,6316613,
6322814,6322886,6322958,6403114,6542083,6700447,6706637,6744626,6766822,6774164,6833663,6839576,6846166,6846886,6848333,
6854626,6904324,6907886,6910714,6912937,6913583,6920164,6925886,6926687,6927083,6927236,6967567,6976378,6978464,6983333,
6985583,6989417,6992063,6992126,6992137,6999164,
7020683,7047613,7048187,7048333,7055281,7056883,7063228,7063957,7068167,7068833,7069483,7070077,7070707,7070714,7071067,
7318333,7327133,7340824,7341587,7341634,7395938,7456526,7473887,7521886,7534567,7542917,7542937,7543043,7547833,7549172,
7549687,7589386,7592687,7601183,7601833,7603937,7615043,7628813,7646437,7647614,7666667,7667137,7667317,7668044,7670528,
7676587,7678333,7679134,7679836,7680817,7707133,7725133,7730974,7731667,7733033,7736833,7737886,7738667,7738784,7740728,
7742672,7743887,7745707,7745824,7745833,7745957,7873937,7923313,7997437,
8109863,8117567,8123336,8123786,8123887,8123914,8124031,8162083,8166367,8166637,8170678,8181667,8184583,8212186,8220583,
8226044,8227313,8227387,8234063,8235883,8238887,8239472,8239537,8240077,8242687,8243117,8244863,8245817,8252236,8270423,
8280692,8281117,8287336,8287937,8292133,8292707,8293967,8298667,8299324,8305937,8306542,8306587,8310583,8316667,8318593,
8330563,8333666,8334386,8336636,8336663,8339417,8346664,8347393,8347814,8348633,8351407,8353286,8356913,8357563,8359363,
8359417,8360083,8360614,8363593,8365877,8365978,8366516,8423117,8476957,8482924,8483336,8490583,8525836,8532233,8537563,
8636417,8641063,8642267,8647543,8652167,8653843,8654363,8654437,8658937,8668333,8699293,8705458,8710264,8712037,8715446,
8715824,8752114,8765083,8765614,8766413,8769167,8773192,8773813,8774164,8774333,8814113,8814176,8818163,8818633,8818667,
8820424,8820883,8823824,8824114,8826067,8826092,8831024,8842114,8848333,8848666,8859176,8863633,8868878,8870563,8870714,
8871076,8871272,8872867,8874613,8875133,8875583,8876728,8876933,8877437,8879626,8881417,8882387,8882567,8887058,8887067,
8887328,8887463,8887733,8887913,8904437,8910386,8910667,8921872,8924617,8926264,8927144,8927317,8931824,8932517,8933023,
8933077,8933633,8935714,8935876,8937343,8937946,8938333,8938657,8938666,8940167,8940637,8942437,8942986,8943544,8944037,
8944093,8944136,8994437,8998327,
9044317,9048187,9054827,9104833,9109214,9109736,9147617,9148114,9157886,9163187,9164933,9181367,9208637,9212437,9216827,
9217313,9218458,9245528,9246077,9251378,9251972,9262288,9262817,9266822,9267076,9271783,9273214,9298333,9298817,9299386,
9300536,9309617,9310733,9311122,9311228,9312083,9313957,9316583,9316637,9320707,9321319,9321886,9325063,9325223,9325583,
9326717,9326816,9326836,9327133,9358417,9359423,9363167,9363583,9363637,9368558,9369413,9369613,9372133,9372833,9374374,
9374417,9374833,9375173,9377083,9378667,9379117,9379178,9380186,9380242,9380719,9385883,9401786,9410563,9411587,9412433,
9412633,9412687,9418013,9420164,9421624,9421676,9421714,9422567,9422722,9428572,9428626,9428678,9431117,9432163,9433133,
9433286,9433333,9433414,9433423,9433864,9433891,9433963,9433972,9443458,9458324,9459386,9464617,9465083,9465173,9465614,
9469313,9469736,9470359,9470474,9470728,9470897,9473626,9474164,9474643,9474686,9475424,9476117,9476126,9476216,9478333,
9479386,9479926,9480664,9480817,9481033,9481186,9481292,9481483,9484192,9484613,9484687,9484714,9485083,9485614,9485767,
9486037,9486406,9486622,9486667,9486827,9537814,9581122,9581228,9590563,9602083,9638407,9639917,9642313,9642457,9643391,
9678583,9683333,9687563,9689633,9690614,9694684,9694828,9730817,9736417,9738937,9740636,9740836,9746063,9746117,9746272,
9746684,9746686,9746783,9761086,9771886,9775367,9777313,9779417,9782126,9784063,9786187,9791317,9793772,9796886,9797336,
9797417,9797437,9797617,9797867,9797887,9807083,9818333,9823283,9828478,9833336,9833417,9836513,9836614,9836666,9837163,
9838693,9840167,9840223,9841067,9841634,9841697,9842687,9843067,9846314,9847324,9847817,9847837,9867563,9874207,9878633,
9883214,9883313,9883772,9883817,9884026,9887617,9888067,9891658,9892313,9893836,9894266,9894286,9894437,9896714,9896957,
9897317,9897976,9898217,9898327,9898424,9898433,9898813,9898822,9898867,9898883,9898937,9898957,9899164,9899308,9899333,
9899378,9899387,9908567,9912617,9919657,9924112,9924641,9926117,9927613,9927683,9928736,9929233,9929737,9933517,9934183,
9934228,9934586,9934786,9939214,9939763,9939817,9943264,9943813,9943822,9944063,9944144,9944164,9944234,9944324,9944333,
9944684,9944686,9944837,9945793,9946808,9947863,9948214,9948736,9948824,9948914,9949114,9949814,9954836,9959813,9959914,
9964286,9967447,9973214,9974863,9974917,9977417,9977867,9979363,9979417,9979777,9981917,9983366,9983917,9984286,9984322,
9984583,9984736,9984878,9984907,9987391,9987886,9988228,9988343,9988433,9988687,9988793,9988883,9988937,9989324,9989333,
9989614,9992267,9992386,9993167,9993367,9993772,9993788,9993878,9993887,9993923,9993943,9994643,9994843,9994913,9994933,
9996886,9997433,9998333,
以上用maple，500多秒
问题：是否x=100的有无穷多？

mathe · 发表于 2008-7-10 11:06:44

原帖由 shshsh_0510 于 2008-7-10 10:55 发表
... 问题：是否s=100的有无穷多？

很显然，对于任意s,如果存在那么就有无穷多组
这个是因为：如果x满足条件，那么x*100也满足条件。
如果要排除所有末位是0的数字，一般来说比较难证明了，但是对于n=100倒还是比较容易的，因为100是完全平方数。
我们可以构造一个长度为10的自然数序列，要求这10个数字互不相同，而且它们两两之和也各不相同，
比如序列{1,2,4,8,16,32,64,128,256,512}.而显然这样的序列可以有无穷多个，对于每个这样的序列${x_k}$
我们构造一个整数X，对所有的10各k,其中第$x_k$为1，其它位数据的值都是0。
那么我们可以知道$X^2$首位和末尾都是1，其它中间的数字都是0或2，而且所有数字之和为10*10=100.
实际上通过这个方法我们可以知道对于任意的完全平方数s,都存在无穷个末位数不是0的完全平方数，数字之和是s.

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

[擂台] 平方数数字和

评分

评分

运行结果

评分