快速测试n^2 +（n + 1）^ 2是否完美的方法

我试图编写代码来测试n^2 + (n+1)^2是否完美。由于我在编程方面没有太多的经验，所以我只能使用Matlab。到目前为止，这是我曾尝试快速测试n^2 +（n + 1）^ 2是否完美的方法

function [ Liste ] = testSquare(N) 

     if exist('NumberTheory') 
      load NumberTheory.mat 
     else 
      MaxT = 0; 
     end 

     if MaxT > N 
      return 
     elseif MaxT > 0 
      L = 1 + MaxT; 
     else 
      L = 1; 
     end 


    n = (L:N)';   % Makes a list of numbers from L to N 
    m = n.^2 + (n+1).^2; % Makes a list of numbers on the form A^2+(A+1)^2 
    P = dec2hex(m);  % Converts this list to hexadecimal 

    Length = length(dec2hex(P(N,:))); %F inds the maximum number of digits in the hexidecimal number 
    Modulo = ['0','1','4','9']';  % Only numbers ending on 0,1,4 or 9 can be perfect squares in hex 

    [d1,~] = ismember(P(:,Length),Modulo); % Finds all numbers that end on 0,1,4 or 9 

    m = m(d1);        % Removes all numbers not ending on 0,1,4 or 9 
    n = n(d1);        % -------------------||----------------------- 
    mm = sqrt(m);       % Takes the square root of all the possible squares 

    A = (floor(mm + 0.5).^2 == m);   % Tests wheter these are actually squares 
    lA = length(A(A>0));     % Finds the number of such numbers 

    MaxT = N; 
    save NumberTheory.mat MaxT; 

if lA>0 

    m = m(A);        % makes a list of all the square numbers 
    n = n(A);        % finds the corresponding n values 
    mm = mm(A);        % Finds the squareroot values of m 

    fid = fopen('Tallteori.txt','wt');  % Writes everything to a simple text.file 
     for ii = 1:lA 
      fprintf(fid,'%20d %20d %20d\t',n(ii),m(ii),mm(ii)); 
      fprintf(fid,'\n'); 
     end 
    fclose(fid); 

end 

end

这将写有与对应的n值到文件的平方。现在我看到使用十六进制是一种在C++中找到完美正方形的快速方法，并试图在matlab中使用它。不过，我不确定这是否是最好的方法。

由于十六进制转换，上述代码在m > 2^52时发生故障。

是否有另一种方法/更快地将n^2 + (n+1)^2上的所有完美正方形写入从1到N的文本文件？

来源

2013-05-20 N3buchadnezzar

有一种更快的方式，甚至不需要测试。你需要一点点初等数论中找到这种方式，但这里有云：

如果n² + (n+1)²是一个完美的正方形，这意味着有一个m，使得该类型的

 m² = n² + (n+1)² = 2n² + 2n + 1 
<=> 2m² = 4n² + 4n + 1 + 1 
<=> 2m² = (2n+1)² + 1 
<=> (2n+1)² - 2m² = -1

方程迎刃而解中，从 “最小的”（正）

1² - 2*1² = -1

的溶液起始

x² - 2y² = -1

对应于数1 + √2，则乘以与的

a² - 2b² = 1

原始溶液是(1 + √2)² = 3 + 2*√2的功率获得的所有进一步的解决方案。

写的是矩阵形式，你获得的所有x² - 2y² = -1解决方案，

|x_k| |3 4|^k |1| 
|y_k| = |2 3| * |1|

和所有x_k必然是奇数，因此可以写为2*n + 1。

最初的几个解决方案(x,y)是

(1,1), (7,5), (41,29), (239,169)

通过

(n_(k+1), m_(k+1)) = (3*n_k + 2*m_k + 1, 4*n_k + 3*m_k + 2)

对应(n,m)

(0,1), (3,5), (20,29), (119,169)

你可以得到下一个(n,m)解决方案对从(n_0, m_0) = (0,1)开始。

快速Haskell代码，因为我不说话MatLab的：

Prelude> let next (n,m) = (3*n + 2*m + 1, 4*n + 3*m + 2) in take 20 $ iterate next (0,1) 
[(0,1),(3,5),(20,29),(119,169),(696,985),(4059,5741),(23660,33461),(137903,195025) 
,(803760,1136689),(4684659,6625109),(27304196,38613965),(159140519,225058681) 
,(927538920,1311738121),(5406093003,7645370045),(31509019100,44560482149) 
,(183648021599,259717522849),(1070379110496,1513744654945),(6238626641379,8822750406821) 
,(36361380737780,51422757785981),(211929657785303,299713796309065)] 
Prelude> map (\(n,m) -> (n^2 + (n+1)^2 - m^2)) it 
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

编辑由EitanT：

这里的MATLAB代码来计算第一N数字：

res = zeros(1, N); 
nm = [0, 1]; 
for k = 1:N 
    nm = nm * [3 4; 2 3] + [1, 2]; 
    res(k) = nm(1); 
end

The结果数组res应该保持满足完美平方条件的值n。

来源

2013-05-20 17:47:07

+1：我冒昧地将MATLAB代码添加到您的答案中。 –

谢谢。我可以理解它，但我无法写出它;） –

+1：非常好的解释。很好的答案。 – Schorsch

快速测试n^2 +（n + 1）^ 2是否完美的方法

回答

相关问题