p-adic numbers

我们希望找出形如 $n^2 + 7$ 的数字，并且希望其 $2$ 的幂次越高越好。

由于 $\lim_{n\to\infty}\left| 2^n \right|_2 = \lim_{n \to \infty}\frac 1 n = 0$，因此，我们希望找到 $n^2 + 7 = 0$ 的解。

通过牛顿方法，我们可以逼近 $n$。即： $$ x \mapsto x - \frac {f(x)} {f'(x)} = x - \frac {x^2 + 7} {2x} $$

我们通过牛顿法求出有理数（如左图），再转换成 p-adic 数（如右图）。可以发现，p-adic 数确实随着迭代次数的增加，趋近于一个值。

我们取其共同处，即得：

$(101110110110001110011100100110001100000010110101)_2$ = $(206036503412917)_{10}$

而：$206036503412917 * 206036503412917 + 7$

附上我的代码。按照我的粗浅理解，应该可以计算各种 $p$。但是发现，自从 $p=3$ 及以后，就不好使了。

from pyadic import PAdic
from fractions import Fraction
import sys

sys.set_int_max_str_digits(10000000)
sys.setrecursionlimit(300000) 

# Parameters

## Desired form:
## polynomial(x) = p^k * n
## where k can be arbitrarily large.

polynomial = [7, 0, 1]  # 7*x^0+0*x^1+1*x^2 = x^2 + 7
p = 2                   

## `x0` represents the initial guess for Newton's method.
## `n` is the number of iterations.
## `digits` is the number of p-adic digits to calculate.

x0 = Fraction(1)
n = 15
digits = 30

# Newton's Method

def f(x):
    return sum(c * x ** i for i, c in enumerate(polynomial))

def f_prime(x):
    result = 0
    for i, c in enumerate(polynomial):
        if (i == 0):
            continue
        result += c * i * x ** (i - 1)
    return result


def newton_root_finding(f, f_prime, x0, n):
    x = Fraction(x0)
    for i in range(n):
        x -= f(x) / f_prime(x)
        print(f"Round {i+1:02}", PAdic(x, p, digits).as_tuple)
    return x


root = newton_root_finding(f, f_prime, x0, n)

padic = PAdic(root, p, digits)
print(f"Original p-adic number: {padic}")
padic_num = padic.num
print(f"10-based p-adic number: {padic_num}")
result = f(padic_num)

with open("output.txt", "w") as f:
    f.write(str(result))

$p=2$ 很有规律：

Round 01 (1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Round 02 (1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0)
Round 03 (1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1)
Round 04 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0)
Round 05 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0)
Round 06 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0)
Round 07 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0)
Round 08 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0)
Round 09 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0)
Round 10 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0)
Round 11 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0)
Round 12 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0)
Round 13 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0)
Round 14 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0)
Round 15 (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0)

$p=3$ 却乱作一团……

Round 01 (2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2)
Round 02 (2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2)
Round 03 (1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
Round 04 (2, 0, 1, 1, 0, 0, 2, 0, 2, 1, 0, 0, 1, 1, 1, 0, 1, 0, 2, 2, 2, 0, 2, 0, 1, 2, 2, 1, 1, 1)
Round 05 (1, 0, 1, 2, 2, 1, 2, 1, 2, 2, 0, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 0, 0, 1, 2, 0, 1)
Round 06 (2, 1, 1, 1, 1, 1, 1, 1, 0, 2, 2, 0, 1, 2, 2, 2, 0, 1, 0, 2, 2, 1, 2, 1, 1, 1, 1, 2, 2, 1)
Round 07 (1, 2, 2, 2, 2, 1, 0, 2, 1, 2, 0, 2, 2, 1, 1, 2, 0, 1, 2, 1, 1, 2, 1, 1, 1, 2, 2, 1, 2, 0)
Round 08 (2, 2, 0, 1, 2, 1, 2, 2, 2, 0, 2, 0, 1, 2, 2, 2, 0, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 1)
Round 09 (1, 1, 2, 1, 0, 1, 1, 2, 2, 1, 1, 2, 0, 1, 1, 0, 2, 0, 0, 0, 0, 2, 1, 0, 0, 1, 2, 2, 0, 2)
Round 10 (2, 0, 2, 1, 1, 2, 2, 1, 1, 0, 2, 1, 1, 0, 1, 0, 2, 2, 0, 2, 2, 2, 2, 2, 2, 0, 0, 2, 2, 0)
Round 11 (1, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 2, 2, 1, 2, 1, 2, 0, 2, 0, 2, 2, 0, 1, 2, 0, 2, 2, 2, 1)
Round 12 (2, 1, 2, 0, 2, 0, 2, 2, 1, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 1, 2, 1, 0, 2, 0, 2, 0, 2, 1)
Round 13 (1, 2, 1, 2, 0, 1, 0, 0, 2, 1, 2, 0, 2, 2, 1, 2, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 2, 1)
Round 14 (2, 2, 1, 2, 0, 2, 2, 1, 0, 0, 0, 1, 2, 0, 1, 2, 2, 0, 0, 0, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1)
Round 15 (1, 1, 1, 2, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 0, 0, 2, 1, 1, 0, 0, 0, 1, 2, 1, 0, 1)

大概还是我对 p-adic number 的认识不够。我还要去补一补才行……

另外我的程序优化也不够。而且 Python 本身就慢……