matlab - 如果 3 个碱基的 gcd 为 1，则在不使用大量 for 循环的情况下评估碱基的幂

Question

我正在尝试编写一个程序来评估 3 个数字(基数)的 GCD，如果 base1 和 base2 的 GCD， base2 和base3，以及base3 和base1 都等于1，然后将底数计算为一个范围内的指数。基本上，我需要做的是弄清楚他们的 GCD 是否等于 1，然后计算数字的幂。这是它的样子:

bases = 150
powers = 150
base1 = all numbers 1-bases
base2 = all numbers 1-bases
base3 = all numbers 1-bases
if the GCD of all combinations = 1
    do base1^all numbers 3-powers
    do base2^all numbers 3-powers
    do base2^all numbers 3-powers
    then store all of those in an array

现在，我已经尝试使用可怕的 for 循环，但它非常慢，我不认为它是一个解决方案。它只有在底数和权力为 10 或以下时才能快速发挥作用。如何在不使用 for 循环的情况下执行此操作？或者，如果我必须使用 for 循环，我该如何减少使用的次数？我可以计算出哪些数字的 3 个 GCD 组合等于 1？我试过的 for 循环如下:

for i = 1:numbers
    for j = 1:numbers
        for k = 1:numbers
            if gcd(i,j) == 1 && gcd(i,k) == 1 && gcd(k,j) == 1
                for a = 3:powers
                    for b = 3:powers
                        for c = 3: powers
                            x = i^a
                            y = j^b
                            z = k^c
                        end
                    end
                end
            end
        end
    end
end

Answer 1

我认为这个问题可以用向量化的方式解决，如下所示

%Generate all possible triplets.
[x1,x2,x3]=ndgrid(1:3,1:3,1:3);
v=[x1(:) x2(:) x3(:)];

现在定义一个匿名函数。

gcd3_test=@(a,b,c)(gcd(a,b)==1 & gcd(b,c)==1 & gcd(a,c)==1)
gcdTest=gcd3_test(v(:,1),v(:,2),v(:,3));
v=v(gcdTest,:);

同样为你所有的力量生成三胞胎。

[x1,x2,x3]=ndgrid(3:10,3:10,3:10);
p=[x1(:) x2(:) x3(:)];

那么我猜你将不得不使用 for 循环(但只有一个)作为:

重要提示:我假设如果您运行 for 的幂 3:150 循环，并且您需要存储所有 x,y,z 那么你将需要大量内存(35034 GB，即使是单精度)。您没有在代码中这样做。

所以不要尝试下面的for循环。

%DO NOT RUN
for i=1:size(v,1)
    vReplicated=repmat(v(i,:),size(p,1),1);
    v_RaisedTo_P{i}=vReplicated.^p;
end

注意:观察您在进行 GCD 测试时不关心顺序(即您的 if 条件。所以我认为您可以过滤掉很多三元组，但这会影响您的能力计算。

allTriplets=sort(allTriplets,2);
allTriplets=unique(allTriplets,'rows'); %27 triplets reduce to 10