Project Euler Problem 276, 268, 347

〇〇

Problem 233
20 February 2009


Let f(N) be the number of points with integer coordinates that are on a circle passing through (0,0), (N,0),(0,N), and (N,N).

It can be shown that f(10000) = 36.

What is the sum of all positive integers N  1011 such that f(N) = 420 ?

〇〇

newkid 发表于 2012-1-13 23:37
#268 用递归，花了差不多一小时。没有考虑野花说的临界点的误差情况。顺便把36楼的代码精简了一下。

DEC ...

785478606870985

〇〇

Problem 224
26 December 2008


Let us call an integer sided triangle with sides a  b  c barely obtuse if the sides satisfy
a2 + b2 = c2 - 1.

How many barely obtuse triangles are there with perimeter  75,000,000?

〇〇

Problem 223
26 December 2008


Let us call an integer sided triangle with sides a  b  c barely acute if the sides satisfy
a2 + b2 = c2 + 1.

How many barely acute triangles are there with perimeter  25,000,000?

〇〇

〇〇 发表于 2012-1-14 13:56
Problem 223
26 December 2008

最后2题，边长到3千已经很慢了

with t as
(select level l,level*level s from dual connect by level<=2e3)
select count(*) from(
select/*+rule*/ a.l al,b.l bl,c.l cl from t a,t b,t c
where
a.s+b.s=c.s-1
and
a.l<=b.l
and
b.l<=c.l)
;


SQL> with t as
  2  (select level l,level*level s from dual connect by level<=2e3)
  3  select count(*) from(
  4  select/*+rule*/ a.l al,b.l bl,c.l cl from t a,t b,t c
  5  where
  6  a.s+b.s=c.s-1
  7  and
  8  a.l<=b.l
  9  and
10  b.l<=c.l)
11  ;

  COUNT(*)
----------
       257

已用时间:  00: 00: 02.91

SQL> 6
  6* a.s+b.s=c.s-1
SQL> c/-/+
  6* a.s+b.s=c.s+1
SQL> /

  COUNT(*)
----------
      5495

已用时间:  00: 00: 02.92

〇〇

〇〇 发表于 2012-1-14 14:55
最后2题，边长到3千已经很慢了

with t as

224改用plsql更慢很多 n<=1000 22秒vs1秒

create or replace procedure q224(n number default 1000)
as
s1 number;
s2 number;
s3 number;
cnt number:=0;
begin
for l1 in 2..n/1.414 loop
s1:=l1*l1;
for l2 in l1..n loop
s2:=l2*l2;
for l3 in l2..n loop
if s1+s2=l3*l3-1 then
cnt:=cnt+1;
exit;
end if;
end loop;
end loop;
end loop;

dbms_output.put_line(cnt);
end;
/

SQL> exec q224
126

PL/SQL 过程已成功完成。

已用时间:  00: 00: 22.14

with t as
(select level l,level*level s from dual connect by level<=1e3)
select count(*) from(
select/*+rule*/ a.l al,b.l bl,c.l cl from t a,t b,t c
where
a.s+b.s=c.s-1
and
a.l<=b.l
and
b.l<=c.l)
;

NT(*)
-----
  126

时间:  00: 00: 00.64

〇〇

如果改用数组保存平方数，更慢了
create or replace procedure q224a(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;
for l3 in l2..n loop
if t(l1)+t(l2)=t(l3)-1 then --s1+s2=l3*l3-1 then
cnt:=cnt+1;
exit;
end if;
end loop;
end loop;
end loop;

dbms_output.put_line(cnt);
end;
/

SQL> exec q224(400)
53

PL/SQL 过程已成功完成。

已用时间:  00: 00: 03.09
SQL> exec q224a(400)
53

PL/SQL 过程已成功完成。

已用时间:  00: 00: 07.00

〇〇

把第3边的取值范围修改了，就快了
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;
for l3 in floor(sqrt(s1+s2))..case when ceil(sqrt(s1+s2+1))<n then ceil(sqrt(s1+s2+1)) else n end loop
if /*t(l1)+t(l2)=t(l3)-1 then --*/s1+s2=l3*l3-1 then
cnt:=cnt+1;
exit;
end if;
end loop;
end loop;
end loop;

dbms_output.put_line(cnt);
end;
/

SQL> exec q224b
126

PL/SQL 过程已成功完成。

已用时间:  00: 00: 01.09

〇〇

〇〇 发表于 2012-1-14 16:09
把第3边的取值范围修改了，就快了
create or replace procedure q224b(n number default 1000)
as

实际上第3边只要测试一个数就行
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

〇〇

〇〇 发表于 2012-1-14 16:23
实际上第3边只要测试一个数就行
create or replace procedure q224b(n number default 1000)
as

从前几个数来看，a必须是偶数，但不知道怎么证明
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 1..n/2.828 loop
s1:=t(l1*2); --l1*l1;
for l2 in l1*2..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.03
SQL> exec q224b(2000)
257

PL/SQL 过程已成功完成。

已用时间:  00: 00: 01.02