毕达哥拉斯三胞胎中没有倍数

Question

基于 Matlab 中的物理建模一书（可在线获取here），我有以下函数来查找毕达哥拉斯三元组

# Function isintegral. Checks whether a number is integer

function res = isintegral(x)
    if round(x) == x
        res = 1;
    else
        res = 0;
    end
end

# function hypotenuse computes the length 
# of the hypotenuse of a right triangle if 
# the lengths of the adjacent sides are a and b

function res = hypotenuse(a,b)
res = sqrt(a^2+b^2);
end

# function find_triples
# A function to search for “Pythagorean triples”

function res = find_triples (n)
    for a = 1:n
        for b = a:n 
            c = hypotenuse(a,b);
            flag = isintegral(c);
            if flag
                [a,b,c]
            end
        end
    end
end

这样

>> find_triples(15)
ans =

   3   4   5

ans =

    5   12   13

ans =

    6    8   10

ans =

    8   15   17

ans =

    9   12   15

除了三角形 5、12、13 和 8、15、17 之外，其他三角形都是三角形 3、4、5 的倍数。那么，如果我们执行 find_triples(15)，如何修改代码使其 returns 仅 [3,4,5]、[5,12,13]、[8,15,17]？

Answer 1

使用@rahema 的建议，您的程序变得简短：

table = [];
for a = 1:n
    for b = a:n
        c = sqrt(a^2+b^2);
        flag = round(c) == c && gcd(a,b)==1;
        if flag
            table = [table; a,b,c];
        end
    end
end

它运行顺利，找到了没有倍数的三元组。

但是，使用

可以更有效地完成计算

i = kron(ones((n+1)/2,1),[1:2:n]');
j = kron([1:2:n]',ones((n+1)/2,1));

isok = i>j & gcd(i,j)==1;
i = i(isok);
j = j(isok);

a = i .* j;
b = (i.^2-j.^2)/2;
c = (i.^2+j.^2)/2;

table2 = [min(a,b),max(a,b),c];

I 运行 Octave 中的两个程序，用于不同数量的 n（30、60、120、240、480 和 960) 并找到以下结果：

Method 1: found 5 triples in 0.0207 seconds
Method 2: found 91 triples in 0.0014 seconds
The first 5 triples are the same

Method 1: found 11 triples in 0.0723 seconds
Method 2: found 364 triples in 0.0016 seconds
The first 8 triples are the same

Method 1: found 22 triples in 0.2724 seconds
Method 2: found 1455 triples in 0.0022 seconds
The first 11 triples are the same

Method 1: found 42 triples in 1.0705 seconds
Method 2: found 5841 triples in 0.0052 seconds
The first 16 triples are the same

Method 1: found 88 triples in 4.2629 seconds
Method 2: found 23357 triples in 0.0201 seconds
The first 25 triples are the same

Method 1: found 173 triples in 16.9313 seconds
Method 2: found 93337 triples in 0.0970 seconds
The first 25 triples are the same

毕达哥拉斯三胞胎中没有倍数

No multiples in Pythagorean triplets

matlab

octave