求证：若a^2+b^2=c^2-1，a,b,c均正整数则a,b必须都是偶数

〇〇

从2000以内的数测试是符合的 create or replace procedure q224b(n number default 1000) as TYPE t_row IS TABLE OF BINARY_INTEGER; T T_row:=t_row(); s1 number; s2 number; s3 number; cnt number:=0; begin t.EXTEND(n); for i in 1..n loop t(i):=i*i; end loop; for l1 in 2..n/1.414 loop s1:=t(l1); --l1*l1; for l2 in l1..n loop s2:=t(l2); --l2*l2; s3:=floor(sqrt(s1+s2))+1; if s3>n then exit; end if; if s1+s2=s3*s3-1 then cnt:=cnt+1; end if; end loop; end loop; dbms_output.put_line(cnt); end; / SQL> exec q224b 126 PL/SQL 过程已成功完成。 已用时间: 00: 00: 00.46 SQL> exec q224b(2000) 257 PL/SQL 过程已成功完成。 已用时间: 00: 00: 01.86 --其实b也必须是偶数 create or replace procedure q224c(n number default 1000) as TYPE t_row IS TABLE OF BINARY_INTEGER; T T_row:=t_row(); s1 number; s2 number; s3 number; cnt number:=0; begin t.EXTEND(n); for i in 1..n loop t(i):=i*i; end loop; for l1 in 1..n/2.828 loop s1:=t(l1*2); --l1*l1; for l2 in l1..n/2 loop s2:=t(l2*2); --l2*l2; s3:=floor(sqrt(s1+s2))+1; if s3>n then exit; end if; if s1+s2=s3*s3-1 then cnt:=cnt+1; end if; end loop; end loop; dbms_output.put_line(cnt); end; / SQL> exec q224c 126 PL/SQL 过程已成功完成。 已用时间: 00: 00: 00.20 SQL> exec q224c(2000) 257 PL/SQL 过程已成功完成。 已用时间: 00: 00: 00.70

wayne

1# 〇〇 如果a,b一奇一偶，那么a^2+b^2被4除余1，于是c必须为偶数，但 c^2-1被4整除余3，矛盾，故不存在。 如果a,b均为奇数，那么a^2+b^2被8除余2，于是c必须为奇数，但 c^2-1被8整除，矛盾，故不存在。 故a,b均为偶数 http://projecteuler.net/problem=224

〇〇

漏写了条件a<=b<=c,谢谢wayne 帮我贴出了原始出处 但奇怪的事：加上数学分析，反而更慢了 因为当a固定时，对一个b，只能有一个c，那么下一个待尝试的第3边至少是c+1。而(c+1)^2=c^2+2c+1 所以下一个b^2和当前b^2的差至少2c+1，设下一个b=当前b+d， (b+d)^2=b^2+2bd+d^2, d^2+2bd>=2c+1解不等式d>=sqrt(b^2+2c+1)-b 跨度小于此数的b都是无效的尝试。所以： 当求出一个c以后，下一个b=ceil(sqrt(b^2+2c+1) create or replace procedure q224e(n number default 1000) as TYPE t_row IS TABLE OF BINARY_INTEGER; T T_row:=t_row(); s1 number; s2 number; s3 number; cnt number:=0; l2 number; begin t.EXTEND(n); for i in 1..n loop t(i):=i*i; end loop; for l1 in 1..n/2.828 loop s1:=t(l1*2); --l1*l1; --for l2 in l1..n/2 loop l2:=l1; while l2<=n/2 loop s2:=t(l2*2); --l2*l2; s3:=sqrt(s1+s2+1); if s3>n then exit; end if; if s3=floor(s3) then cnt:=cnt+1; l2:=ceil(sqrt(s2+2*s3+1)/2); else l2:=l2+1; end if; end loop; end loop; dbms_output.put_line(cnt); end; / SQL> exec q224e 126 PL/SQL 过程已成功完成。 已用时间: 00: 00: 00.20 SQL> exec q224e(2000) 257 PL/SQL 过程已成功完成。 已用时间: 00: 00: 00.80 SQL> exec q224e(4000) 502 PL/SQL 过程已成功完成。 已用时间: 00: 00: 03.00 SQL> exec q224e(8000) 996 PL/SQL 过程已成功完成。 已用时间: 00: 00: 11.70 SQL> exec q224d(8000) 996 PL/SQL 过程已成功完成。 已用时间: 00: 00: 09.40

〇〇

好像是while loop比for loop慢，去掉了l2的赋值，还是差不多的时间 但为什么没有节省时间？

〇〇

根据2楼的结论，c必须是奇数，那么下一个c=c+2,平方的间隔是4c+4,但速度依旧很慢 create or replace procedure q224e(n number default 1000) as TYPE t_row IS TABLE OF BINARY_INTEGER; T T_row:=t_row(); s1 number; s2 number; s3 number; cnt number:=0; l2 number; begin t.EXTEND(n); for i in 1..n loop t(i):=i*i; end loop; for l1 in 1..n/2.828 loop s1:=t(l1*2); --l1*l1; --for l2 in l1..n/2 loop l2:=l1; while l2<=n/2 loop s2:=t(l2*2); --l2*l2; s3:=sqrt(s1+s2+1); if s3>n then exit; end if; if s3=floor(s3) then cnt:=cnt+1; l2:=ceil(sqrt(s2+4*s3+4)/2); else l2:=l2+1; end if; end loop; end loop; dbms_output.put_line(cnt); end; / SQL> exec q224e(4000) 502 PL/SQL 过程已成功完成。 已用时间: 00: 00: 03.00 SQL> exec q224e(8000) 996 PL/SQL 过程已成功完成。 已用时间: 00: 00: 11.07

〇〇

5# 〇〇 明白了，这些条件过滤掉的执行步骤很有限 SQL> create or replace procedure q224f(n number default 1000) 2 as 3 TYPE t_row IS TABLE OF BINARY_INTEGER; 4 T T_row:=t_row(); 5 s1 number; 6 s2 number; 7 s3 number; 8 cnt number:=0; 9 l2 number; 10 u number; 11 t2 number:=0; 12 begin 13 t.EXTEND(n); 14 for i in 1..n loop 15 t(i):=i*i; 16 end loop; 17 for l1 in 1..n/2.828 loop 18 s1:=t(l1*2); --l1*l1; 19 u:=case when s1/4n then exit; end if; 25 if s3=floor(s3) then 26 cnt:=cnt+1; 27 end if; 28 end loop; 29 end loop; 30 31 dbms_output.put_line(t2); 32 end; 33 / 过程已创建。 已用时间: 00: 00: 00.00 SQL> exec q224f 91241 PL/SQL 过程已成功完成。 已用时间: 00: 00: 00.02 SQL> create or replace procedure q224f(n number default 1000) 2 as 3 TYPE t_row IS TABLE OF BINARY_INTEGER; 4 T T_row:=t_row(); 5 s1 number; 6 s2 number; 7 s3 number; 8 cnt number:=0; 9 l2 number; 10 u number; 11 t2 number:=0; 12 begin 13 t.EXTEND(n); 14 for i in 1..n loop 15 t(i):=i*i; 16 end loop; 17 for l1 in 1..n/2.828 loop 18 s1:=t(l1*2); --l1*l1; 19 u:=n/2; --case when s1/4n then exit; end if; 25 if s3=floor(s3) then 26 cnt:=cnt+1; 27 end if; 28 end loop; 29 end loop; 30 31 dbms_output.put_line(t2); 32 end; 33 / 过程已创建。 已用时间: 00: 00: 00.00 SQL> exec q224f 98446 PL/SQL 过程已成功完成。 已用时间: 00: 00: 00.02 SQL> create or replace procedure q224f(n number default 1000) 2 as 3 TYPE t_row IS TABLE OF BINARY_INTEGER; 4 T T_row:=t_row(); 5 s1 number; 6 s2 number; 7 s3 number; 8 cnt number:=0; 9 l2 number; 10 u number; 11 t2 number:=0; 12 begin 13 t.EXTEND(n); 14 for i in 1..n loop 15 t(i):=i*i; 16 end loop; 17 for l1 in 1..n/2.828 loop 18 s1:=t(l1*2); --l1*l1; 19 --for l2 in l1..n/2 loop 20 l2:=l1; 21 u:=case when s1/4n then exit; end if; 27 if s3=floor(s3) then 28 cnt:=cnt+1; 29 l2:=ceil(sqrt(s2+4*s3+4)/2); 30 else 31 l2:=l2+1; 32 end if; 33 end loop; 34 end loop; 35 36 dbms_output.put_line(t2); 37 end; 38 / 过程已创建。 已用时间: 00: 00: 00.00 SQL> exec q224f 91137 PL/SQL 过程已成功完成。 已用时间: 00: 00: 00.02 SQL>

〇〇

从http://projecteuler.net/problem=224看来的 这种构造怎么保证没有遗漏？ a = 2u, b = 2v, and c = 2w + 1, u^2 + v^2 = w(w+1) both w and (w+1) can be written as sum of 2 squares ie. if w can be written as (m^2+n^2) and (w+1) as (p^2+q^2), then w(w+1) can be written as (mp+nq)^2+(mq-np)^2 or (mp-nq)^2 + (mq+np)^2 0 <= m, n, p, q and 1 <= w

wayne

7# 〇〇 高斯整数 此题让我想起了hujunhua版主

wayne

7# 〇〇 对于给定的x，m^2+n^2=x 的解的个数仅由x的4k+1型的素因子来确定 设x分解之后，4k+1型素因子对应的指数分别为a1,a2,....an 那么方程的解的个数为 C=(1+a1)(1+a2)(1+a3)*...*(1+an) 规定m<=n之后，则 C=Ceiling（(1+a1)(1+a2)(1+a3)*...*(1+an)/2）

wayne

比如 x = 2^2*7^2*5^5*17^7 ，C=6*8/2=24 Mathematica解得正好是24组 {{198254,15852228},{567420,15843310},{1031730,15819860},{1399916,15791538},{1862350,15743700},{2620380,15635410},{3439100,15475950},{4248300,15273650},{4980850,15050700},{5045740,15029070},{5765550,14767900},{6196092,14592494},{6534290,14444220},{7284942,14080556},{7634802,13893964},{7956340,13712370},{8354990,13473180},{8666532,13274926},{8995812,13054034},{9052050,13015100},{9669940,12562830},{9959922,12334196},{10317300,12036850},{10936100,11477550}}