C++ 拉马努金纳盖尔猜想

拉马努金-纳盖尔 方程是指数丢番图方程的一个示例。丢番图方程是二个或更多未知数的整数系数多项式方程。丢番图方程要求只有整数解。

拉马努金-纳盖尔 方程是一个平方数和一个比2的幂小7的数之间的方程，其中2的幂只能是自然数。

拉马努金 猜想丢番图方程2y – 7 = x²有正整数解，并且之后由纳盖尔证明。

2y-7=x^2\text{有}x\epsilon\mathbb{Z_+}:x=1, 3, 5, 11, 181

三角数 是指以等边三角形排列的物体。第n个三角数是一个每边有n个物体的三角形中的物体总数。因此，第三个三角数是一个每边有3个物体的三角形中的物体总数=6。

三角数的公式为：

T_n=\sum_{k=1}^n k=1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}=\binom{n+1}{2}\text{其中}n\geq0

以第0个三角数开始的三角数序列：

0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, …

梅森数 是比2的幂少1的数。

梅森数的公式为：

M_m=2^m-1\text{其中}m\geq0

问题陈述

问题是要找出所有的拉马努金-纳盖尔数，即所有满足\mathrm{2^m-1=\frac{n(n+1)}{2}}的正整数解以及满足拉马努金-纳盖尔方程2y - 7 = x2的自然数。

示例

Input: x = 1, 3, 5, 11, 181

Expected Output: (0, 1, 3, 15, 4095), (3, 4, 5, 7, 15)

解决方案

从方程开始，

\mathrm{2^m-1=\frac{n(n+1)}{2}} ….(1)

清理(1)的分母

\mathrm{2^{m+1}-2=n^2+n} ….(2)

为了完成方程(2)右边的平方，两边乘以4

\mathrm{2^{m+3}-8=4n^2+4n} ….(3)

进一步简化方程(3)

\mathrm{2^m+3-7=(2n+1)^2} ….(4)

方程(4)是拉马努金-纳格尔(Ramanujan-Nagell)方程的形式，即\mathrm{2^y-7=x^2}。

根据拉马努金-纳格尔(Ramanujan-Nagell)方程，x只能取正整数值1、3、5、11、181。

因此，在方程(4)中，2n + 1可以取x = 1、3、5、11、181的值。将2n + 1与所有可能的x值一起求解，我们得到

\mathrm{\Rightarrow n = 0, 1, 2, 5, 90}

最终，满足\mathrm{2^m-1=\frac{n(n+1)}{2}}的梅森数也可以使用n的值计算。

当\mathrm{n = 0,2^m-1=0}

\mathrm{n = 1,2^m-1=1}

\mathrm{n = 2,2^m-1=3}

\mathrm{n = 5,2^m-1=15}

\mathrm{n = 90,2^m-1=4095}

因此，{0, 1, 3, 15, 4095}是三角形梅森或拉马努金-纳格尔(Ramanujan-Nagell)数。

给定\mathrm{2^y-7=x^2}中的x值，可以通过以下公式找到y，

\mathrm{y=log_2(x^2+7)}

对于x = 1，y = 3

对于x = 3，y = 4

对于x = 5，y = 5

对于x = 11，y = 7

对于x = 181，y = 15

伪代码

procedure rNagell (x[])
   ans[]
   for i = 0 to 4
      temp = (x[i] - 1) / 2
      ans[i] = (temp^2 + temp) / 2
end procedure

procedure rNagellNatural (x[])
   ans[]
   for i = 0 to 4
      temp = log2 (x[i]^2 + 7)
      ans[i] = temp
end procedure

示例：C++实现

在下面的程序中，我们使用上述部分进行的计算来找到三角形Mersenne数和满足Ramanujan-Nagell方程的自然数。

#include <bits/stdc++.h>
using namespace std;

// Functio for finding Triangular Mersenne or Ramanujan-nagell numbers
vector<int> rNagell(int x[]){
   vector<int> ans;
   for (int i = 0; i < 5; i++){
      // Applying the formula from the section above i.e. 2n-1 = x
      // 2^m - 1 = n(n+1)/2
      int temp = (x[i] - 1) / 2;
      ans.push_back((temp * temp + temp) / 2);
   }
   return ans;
}
// Function for finding natural numbers in Rmanujan-Nagell Equation i.e. 2^y - 7 = x^2
vector<int> rNagellNatural(int x[]){
   vector<int> ans;
   // y can be found as log2(x^2 + 7)
   for (int i = 0; i < 5; i++){
      int temp = (x[i] * x[i]) + 7;
      ans.push_back(log2(temp));
   }
   return ans;
}
int main(){
   int x[5] = {1, 3, 5, 11, 181};
   cout << "Triangular Mersenne Numbers = ";
   vector<int> triM = rNagell(x);
   for (int i = 0; i < 5; i++){
      cout << triM[i] << "  ";
   }
   cout << "\nNatural numbers sstisfying Ramanujan-Nagell Equation = ";
   vector<int> num = rNagellNatural(x);
   for (int i = 0; i < 5; i++){
      cout << num[i] << "  ";
   }
   return 0;
}

输出

Triangular Mersenne Numbers = 0  1  3  15  4095  
Natural numbers sstisfying Ramanujan-Nagell Equation = 3  4  5  7  15

结论

总之，可以通过将方程调制为丢番图逆规术方程的形式，并与方程中x的数值进行比较，来找到三角形的梅森数。使用数学公式可以在常数时间复杂度下找到解。