使用Python找到整數解系統的線性方程

Question

我想寫一個python程序來解決所有的形式x_1 + 2x_2 + ... + Tx_T = a多項式的正整數解x_0 + x_1 + ... + x_T = b。

例如，通過蠻力我可以證明x_1 + 2x_2 = 4的唯一正整數解決方案是x_0 + x_1 + x_2 = 2，它是(0,0,2)。但是，我希望一個程序能夠獨立完成此操作。

有什麼建議嗎？

Answer 1

您可以使用Numpy Linear Algebra來求解一個方程組，即一個線性矩陣方程的最小二乘解。你的情況，你可以考慮以下向量：

import numpy as np 
# range(T): coefficients of the first equation 
# np.ones(T): only 'ones' as the coefficients of the second equation 
A = np.array([range(T), np.ones(T)) # Coefficient matrix 
B = np.array([a, b]) # Ordinate or 「dependent variable」 values 

，然後找到解決方案如下：

x = np.linalg.lstsq(A, B)[0] 

最後，你可以實現一個solve方法傳遞變量T, a b：

import numpy as np 
def solve(T, a, b): 
    A = np.array([range(T), np.ones(T)]) 
    B = np.array([a, b]) 
    return np.linalg.lstsq(A, B)[0] 

整數解決方案： 如果你只想要整數解決方案項，那麼你正在尋找的線性不定方程一個system of linear diophantine equations.

每個系統可以被寫爲： AX = C，其中甲是米×整數的n個矩陣，X是一個n×1列矩陣的未知數和C是一個整數的列矩陣m×1。

線性丟番圖方程的每個系統都可以通過計算其矩陣的Smith normal form來解決。