平方数数字和

mathe

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

mathe

发现 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

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

上述结果有误，我算出 X=76 S=2896989988<5599977889 请 kofeffect 排查是否还有其它错误。

kofeffect

原帖由 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

现在总于找到了一个构造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

原帖由 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]

1. #include <stdlib.h>
2. #include <stdio.h>
4. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
6. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
7. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
9. #if 1
10. # define SQRT_DIGIT 8UL
11. # define SQRT_MAX 100000000UL
12. #else
13. # define SQRT_DIGIT 9UL
14. # define SQRT_MAX 1000000000UL
15. #endif
17. #define TEN_POW9 1000000000UL
19. // 返回余数；u32Num 作为输入的被除数，同时作为输出的商
20. __declspec(naked)
21. CONST UINT32 DivMod10( UINT32& u32Num )
22. {
23. __asm
24. {
25. mov ecx, dword ptr[esp + 0x04];
27. mov edx, dword ptr[ecx];
28. mov eax, 0xCCCCCCCD; // [ 2^35 / 10 + 0.5 ]
29. push edx;
31. mul edx;
32. shr edx, 3;
33. mov dword ptr[ecx], edx;
35. imul edx, 10;
37. pop eax;
38. sub eax, edx;
40. ret;
41. }
42. }
45. UINT32 SumOfDigits( UINT32 v )
46. {
47. UINT32 sum = 0;
49. while( 0 != v )
50. {
51. sum += DivMod10( v );
52. }
54. return sum;
55. }
58. int main( void )
59. {
60. UINT32 i, s, delta, v;
61. UINT32 high, high_delta;
63. UINT32 mark[ 164 ] = { 0 };
64. UINT32 cycleDelta[ 4 ] = { 1, 3, 3, 2 }; // 0, 1, 4, 7
66. HugeCalc::EnableTimer();
67. HugeCalc::ResetTimer();
69. v = 1;
70. delta = 1;
71. for ( i=1; i<0xFFFF; ++i )
72. {
73. s = SumOfDigits( v );
74. if ( 0 == mark[ s ] )
75. {
76. mark[ s ] = i;
77. }
78. delta += 2;
79. v += delta;
80. }
82. high = v / TEN_POW9;
83. v -= high * TEN_POW9;
85. high_delta = delta / TEN_POW9;
86. delta -= high_delta * TEN_POW9;
88. for ( ; i<=SQRT_MAX; ++i )
89. {
90. s = SumOfDigits( v ) + SumOfDigits( high );
91. if ( 0 == mark[ s ] )
92. {
93. mark[ s ] = i;
94. }
96. delta += 2;
97. if ( delta >= TEN_POW9 )
98. {
99. delta -= TEN_POW9;
100. ++high_delta;
101. }
103. v += delta;
104. if ( v >= TEN_POW9 )
105. {
106. v -= TEN_POW9;
107. high += high_delta + 1;
108. }
109. else
110. {
111. high += high_delta;
112. }
113. }
115. HugeCalc::EnableTimer( FALSE );
118. s = 0;
119. i = 0;
120. while ( s != 9*SQRT_DIGIT*2 )
121. {
122. s += cycleDelta[ i ];
123. if ( 4 == ++i )
124. {
125. i = 0;
126. }
128. if ( 0 != mark[ s ] )
129. {
130. if ( mark[ s ] <= 0xFFFF )
131. {
132. printf( "X = %u\tS = %u\n", s, mark[ s ] * mark[ s ] );
133. }
134. else
135. {
136. printf( "X = %u\tS = %I64u\n", s, UInt32x32To64( mark[ s ], mark[ s ] ));
137. }
138. }
139. else
140. {
141. printf( "X = %u\n", s );
142. }
143. }
145. printf( HugeCalc::GetTimerStr( FT_HHMMSS_ms ) );
146. printf( "\n" );
148. return 0;
149. }

复制代码

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

gxqcn

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

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

shshsh_0510

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

原帖由 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.