資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究拉馬努金-納格爾猜想
Ramanujan-Nagell 方程是指數丟番圖方程的一個例子。丟番圖方程是一個有兩個或多個未知數的，係數為整數的多項式方程。丟番圖方程只要求整數解。
Ramanujan-Nagell 方程是一個平方數與一個比2的冪小7的數之間的方程，其中2的冪只能是自然數。
拉馬努金猜想丟番圖方程 2y - 7 = x2 存在正整數解，後來被納格爾證明。
$$\mathrm{2y−7=x^2\:has\:x\epsilon\:Z_+:x=1, 3, 5, 11, 181}$$
三角形數 - 它計算以等邊三角形排列的物件的數量。第 n 個三角形數是在每邊排列 n 個物件的三角形中的物件的數量。因此，第 3 個三角形數是在每邊有 3 個物件的三角形中的物件總數 = 6。
三角形數的公式為：
$$\mathrm{T_n=\displaystyle\sum\limits_{k=1}^n \:k=1 + 2 + 3 + ⋅⋅⋅ +𝑛 =\frac{n(n+1)}{2}=\left(\begin{array}{c}n+1\ 2\end{array}\right)where\:n\geq0}$$
從第 0 個三角形數開始的三角形數序列為：
0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153 …
梅森數 - 它是一個比 2 的冪小 1 的數。
梅森數的公式為：
$$\mathrm{M_m=2^m−1\:where\:m\geq0}$$
問題陳述
問題是找到所有拉馬努金-納格爾數，即找到方程 $\mathrm{2^m−1=\frac{n(n+1)}{2}}$ 的所有正整數解，以及滿足拉馬努金-納格爾方程 2y7=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) 形式為拉馬努金-納格爾方程，即 $\mathrm{2^y−7=x^2}$。
根據拉馬努金-納格爾方程，x 只能取 1、3、5、11、181 的正整數。
因此，在方程 (4) 中，2n + 1 可以取 x = 1、3、5、11、181 的值。透過求解 2n + 1 與 x 的所有可能值，我們得到
$\mathrm{\Rightarrow𝑛 = 0, 1, 2, 5, 90}$
然後最終，可以使用 n 的值計算出滿足 $\mathrm{2^m−1=\frac{n(n+1)}{2}}$ 的梅森數。
當 $\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} 是三角梅森數或拉馬努金-納格爾數。
在 $\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++ 實現
在以下程式中，我們使用上面部分中完成的計算來找到三角梅森數和滿足拉馬努金-納格爾方程的自然數。
#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 的值進行比較來找到。可以使用數學公式以恆定的時間複雜度找到解決方案。
126 次檢視
