p^2=a^2&b^2

无心人

不搜索单个的了
浪费资源
改整体搜索了

1. 
   
2. #include <gmp.h>
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. 
   
6. mpz_t t;
   
7. unsigned int d[3] = {1, 4, 9}, maxlvl;
   
8. mpz_t l[32];
   
9. 
   
10. int check(int lvl, mpz_t n)
    
11. {
    
12. //    gmp_printf("%Zd\n", n);
    
13. 
    
14.     if (mpz_perfect_square_p(n))
    
15.     {
    
16.        mpz_sqrt(t, n);
    
17.        gmp_printf("%u: [%Zd, %Zd]\n", lvl, n, t);
    
18.     }     
    
19. }
    
20. 
    
21. int circle(int lvl)
    
22. {
    
23.    if (lvl < maxlvl)
    
24.      for (int i = 0; i < 3; i ++ )
    
25.        {
    
26.           mpz_mul_ui(l[lvl], l[lvl-1], 10);
    
27.           mpz_add_ui(l[lvl], l[lvl], d[i]);
    
28.           check(lvl+1, l[lvl]);
    
29.           circle(lvl + 1);        
    
30.        }
    
31. }
    
32. int main(void)
    
33. {
    
34.   int i;
    
35.   mpz_init(t);
    
36.   for (i = 0; i < 32; i ++)
    
37.   {
    
38.     mpz_init(l[i]);
    
39.     mpz_set_ui(l[i], 0);
    
40.   }
    
41.   printf("请输入最大数字长度：");
    
42.   scanf("%u", &maxlvl);
    
43.   for (i = 0; i < 3; i ++)
    
44.   {  
    
45.     mpz_set_ui(l[0], d[i]);
    
46.     circle(1);
    
47.   }
    
48. 
    
49.   for (i = 0; i < 32; i ++)
    
50.     mpz_clear(l[i]);
    
51.   mpz_clear(t);
    
52.   return 0;
    
53. }
    

复制代码

gxqcn

原帖由 medie2005 于 2009-3-24 14:17 发表
谁来解Q4?

注意到：

100202001² = 10040441004404001
10002020001² = 100040404100404040001
1000020200001² = 1000040400410040040400001
。。。
在100202001中“202”的两侧同时添上相同数目的“0”，其平方可仅由0、1、4构成，
（这是我刚刚通过 HugeCalc 发现的，不知是否已有人总结出来了？）

但上面最大的遗憾是其底数肯定为合数（因为其数字和=6，必被3整除）！


怎么办呢？


我继续使用 HugeCalc 去 try，又发现了一个类似的规律：
100222001² = 10044449484444001
10002220001² = 100044404948404440001
1000022200001² = 1000044400494840044400001
。。。
即：$(10^(2k+2)+222*10^k+1)^2=10^(4k+2)+444*10^(3k+2)+49484*10^(2k)+444*10^k+1$
注意到右侧多出了一个8，虽然8不是完全平方数，但凑巧484=22²，
这样可将右侧看作是：4*(k-2)个“0”、2个“1”、7个“4”、1个“9”和1个“484”构成。
且现在底数将有可能为素数了。于是赶紧编程进行搜索。

代码如下：

1. #include <stdio.h>
   
2. 
   
3. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"      // 公共接口
   
4. #include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h"       // 10进制系统
   
5. 
   
6. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
   
7. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
   
8. 
   
9. 
   
10. int main(int argc, char* argv[])
    
11. {   
    
12.     // 初始化
    
13.     HugeCalc::EnableTimer( TRUE );
    
14.     HugeCalc::ResetTimer();
    
15.    
    
16.     // 100 222 001
    
17.     CHugeInt hHead( 100000000 );
    
18.     CHugeInt hMid( 222000 );
    
19.     CHugeInt hSum;
    
20. 
    
21.     UINT32 k = 3;
    
22. 
    
23.     do
    
24.     {
    
25.         ++(( hSum = hHead ) += hMid );
    
26.         if ( hSum.IsPrime() )
    
27.         {
    
28.             printf( "\n%s\tk=%u\t", HugeCalc::GetTimerStr( FT_DOT06SEC_s ), k );
    
29.             printf( "%s ^ 2 = ", (LPCTSTR)hSum );
    
30.             printf( "%s", (LPCTSTR)hSum.Pow(2) );
    
31.         }
    
32. 
    
33.         hHead.DecLShift(2);
    
34.         hMid.DecLShift(1);
    
35.     } while ( ++k <= 1024 );
    
36.    
    
37.     printf( "\n" );
    
38.     HugeCalc::EnableTimer( FALSE );   
    
39.    
    
40.     system( "pause" );
    
41.    
    
42.     return 0;
    
43. }

复制代码

在 k <= 1024 范围内搜索其底数恰好为素数者，结果如下：

1. 0.000183 s      k=4
   
2. 0.047009 s      k=98
   
3. 2.671768 s      k=300
   
4. 19.800347 s     k=498
   
5. 124.983792 s    k=788
   
6. 187.051473 s    k=860
   
7. 请按任意键继续. . .

复制代码

其中当 k=98 时，
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000022200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 ^ 2 = 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000044400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000494840000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000044400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
可以看作 Q4 的一个解。

无心人

所以他限定不能有0
否则平凡解太多了啊

无心人

刚去尝试暴力找28位以下的
后来一算
需要的时间忒多了点
（恐怕要几十年）
只好先找24位以下的了

这个也估计要几个小时到几天吧

gxqcn

我没见他有如此限制。

当要求为素数的完全平方数，即便含上“0”也是凤毛麟角啊。

无心人

不是吧
有0的很多吧

07^2 = 0049
007^2 = 000049
...
...

哈哈

无心人

3: [100, 10]
5: [10000, 100]
7: [1000000, 1000]
7: [1004004, 1002]
7: [1014049, 1007]
5: [10404, 102]
7: [1040400, 1020]
7: [1100401, 1049]  //素数
5: [11449, 107]   //素数
7: [1144900, 1070]
8: [11909401, 3451]
8: [14010049, 3743]
8: [14040009, 3747]
3: [144, 12]
5: [14400, 120]
7: [1440000, 1200]
4: [1444, 38]
6: [144400, 380]
8: [14440000, 3800]
5: [19044, 138]
7: [1904400, 1380]
7: [1940449, 1393]
8: [19909444, 4462]
3: [400, 20]
5: [40000, 200]
7: [4000000, 2000]
7: [4004001, 2001]
5: [40401, 201]
7: [4040100, 2010]
8: [40411449, 6357]
6: [419904, 648]
8: [41990400, 6480]
3: [441, 21]
5: [44100, 210]
7: [4410000, 2100]
5: [44944, 212]
7: [4494400, 2120]
2: [49, 7]
4: [4900, 70]
6: [490000, 700]
8: [49000000, 7000]
8: [49014001, 7001] //素数
6: [491401, 701] //素数
8: [49140100, 7010]
8: [49999041, 7071]
3: [900, 30]
5: [90000, 300]
7: [9000000, 3000]
6: [904401, 951]
8: [90440100, 9510]
4: [9409, 97] //素数
6: [940900, 970]
8: [94090000, 9700]
8: [94109401, 9701]
7: [9909904, 3148]
6: [994009, 997] //素数
8: [99400900, 9970]
7: [9941409, 3153]
8: [99940009, 9997]
如果不限制0
其中素数是6个

gxqcn

原帖由 无心人 于 2009-3-24 16:08 发表


不是吧
有0的很多吧

07^2 = 0049
007^2 = 000049
...
...

哈哈

但 0049 和 000049 它们代表的是同一个数，
应该不能算作不同的解。

所以即便加上“0”（其实它本身就是合法的，只是再肯定一下而已），
也不致于让问题难度退化到一般情形。

无心人

不玩了

暴力穷举太消耗时间了

无心人

1，4，9的留给有能力的去算吧
我只得到19位以下无比Q3大的了

响应郭老大的建议，我算下0, 1, 4, 9的16位以内的结果