论坛 › 趣题妙解 › 求证：若a^2+b^2=c^2-1，a,b,c均正整数则a,b必须都是偶数

〇〇 发表于 2012-1-14 17:07:47

求证：若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 OFBINARY_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 OFBINARY_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 发表于 2012-1-14 19:04:31

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

〇〇 发表于 2012-1-14 19:40:01

漏写了条件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 OFBINARY_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

〇〇 发表于 2012-1-14 19:58:17

好像是while loop比for loop慢，去掉了l2的赋值，还是差不多的时间


但为什么没有节省时间？

〇〇 发表于 2012-1-14 20:48:35

根据2楼的结论，c必须是奇数，那么下一个c=c+2,平方的间隔是4c+4,但速度依旧很慢
create or replace procedure q224e(n number default 1000)
as
TYPE t_row IS TABLE OFBINARY_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

〇〇 发表于 2012-1-15 19:56:33

5# 〇〇


明白了，这些条件过滤掉的执行步骤很有限
SQL> create or replace procedure q224f(n number default 1000)
2as
3TYPE t_row IS TABLE OFBINARY_INTEGER;
4T T_row:=t_row();
5s1 number;
6s2 number;
7s3 number;
8cnt number:=0;
9l2 number;
10u number;
11t2 number:=0;
12begin
13t.EXTEND(n);
14for i in 1..n loop
15t(i):=i*i;
16end loop;
17for l1 in 1..n/2.828 loop
18s1:=t(l1*2); --l1*l1;
19u:=case when s1/4<n/2 then s1/4 else n/2 end;
20for l2 in l1..u loop
21t2:=t2+1;
22s2:=t(l2*2); --l2*l2;
23s3:=sqrt(s1+s2+1);
24if s3>n then exit; end if;
25if s3=floor(s3) then
26cnt:=cnt+1;
27end if;
28end loop;
29end loop;
30
31dbms_output.put_line(t2);
32end;
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)
2as
3TYPE t_row IS TABLE OFBINARY_INTEGER;
4T T_row:=t_row();
5s1 number;
6s2 number;
7s3 number;
8cnt number:=0;
9l2 number;
10u number;
11t2 number:=0;
12begin
13t.EXTEND(n);
14for i in 1..n loop
15t(i):=i*i;
16end loop;
17for l1 in 1..n/2.828 loop
18s1:=t(l1*2); --l1*l1;
19u:=n/2; --case when s1/4<n/2 then s1/4 else n/2 end;
20for l2 in l1..u loop
21t2:=t2+1;
22s2:=t(l2*2); --l2*l2;
23s3:=sqrt(s1+s2+1);
24if s3>n then exit; end if;
25if s3=floor(s3) then
26cnt:=cnt+1;
27end if;
28end loop;
29end loop;
30
31dbms_output.put_line(t2);
32end;
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)
2as
3TYPE t_row IS TABLE OFBINARY_INTEGER;
4T T_row:=t_row();
5s1 number;
6s2 number;
7s3 number;
8cnt number:=0;
9l2 number;
10u number;
11t2 number:=0;
12begin
13t.EXTEND(n);
14for i in 1..n loop
15t(i):=i*i;
16end loop;
17for l1 in 1..n/2.828 loop
18s1:=t(l1*2); --l1*l1;
19--for l2 in l1..n/2 loop
20l2:=l1;
21u:=case when s1/4<n/2 then s1/4 else n/2 end;
22while l2<=u loop
23t2:=t2+1;
24s2:=t(l2*2); --l2*l2;
25s3:=sqrt(s1+s2+1);
26if s3>n then exit; end if;
27if s3=floor(s3) then
28cnt:=cnt+1;
29l2:=ceil(sqrt(s2+4*s3+4)/2);
30else
31l2:=l2+1;
32end if;
33end loop;
34end loop;
35
36dbms_output.put_line(t2);
37end;
38/

过程已创建。

已用时间:00: 00: 00.00
SQL> exec q224f
91137

PL/SQL 过程已成功完成。

已用时间:00: 00: 00.02
SQL>

〇〇 发表于 2012-1-15 19:58:32

从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 发表于 2012-1-19 09:23:54

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

wayne 发表于 2012-1-19 22:16:02

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 发表于 2012-1-19 22:20:51

比如
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}}

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