Как ускорить поиск пар для (y+n)^4 - y^4 = (x+k)^4 - x^4: двухуказательный скан и слияние потоков

Как ускорить поиск целочисленных решений четвертичных диофантовых уравнений: монотонность, два указателя, слияние потоков и куча для неограничённого поиска

Поиск целочисленных решений для четвертичных диофантовых уравнений может стремительно перерасти во времена выполнения, недостижимые на практике, если наивно перебирать огромные сетки. Типичный пример — поиск пар (x, y), где x ≠ y, удовлетворяющих (y + n)^4 − y^4 = (x + k)^4 − x^4 для фиксированных малых положительных целых n и k. Прямой двойной цикл по большим диапазонам x и y оказывается непозволительно медленным. Ниже — пошаговое руководство, как превратить такой грубый перебор в эффективный потоковый поиск, который масштабируется, поддерживает несколько наборов параметров и при необходимости может быть неограниченным.

Базовый грубый перебор и почему он не справляется

Вот прямой вариант, который проверяет каждую пару. Логика проста: вычислить обе стороны для всех x и y и сравнить, пропуская x == y. В принципе работает, но сложность квадратична по верхней границе поиска.

inc_n = 1
inc_k = 2
upper_bound = 10**6

for xx in range(1, upper_bound):
    val_right = (xx + inc_k)**4 - xx**4
    for yy in range(1, upper_bound):
        if xx == yy:
            continue
        val_left = (yy + inc_n)**4 - yy**4
        if val_left == val_right:
            print(f"Match found: x = {xx}, y = {yy}")

Такой подход выполняет порядка upper_bound в квадрате сравнений. Для диапазонов вроде от 1 до 1,000,000 это неприемлемо.

Ключевое наблюдение: монотонность позволяет сканировать двумя указателями

Функция z ↦ (z + t)^4 − z^4 возрастает по z для любого фиксированного положительного t. Значит, при фиксированных n и k последовательности слева по y и справа по x строго возрастают. Когда две последовательности отсортированы, вложенные циклы не нужны: их можно проходить в ногу классической техникой двух указателей — сравнивать текущие значения, продвигать ту сторону, где значение меньше, и фиксировать совпадение, когда они равны.

Эффективный поиск для одной пары (n, k)

Код ниже один раз проходит по x и y, сравнивая лишь согласованные позиции и монотонно продвигаясь вперед. Он сохраняет исходную логику и выводит только решения с x ≠ y.

inc_n = 1
inc_k = 2
upper_bound = 10**6

i_idx = 1
j_idx = 1
while i_idx < upper_bound and j_idx < upper_bound:
    right_now = (i_idx + inc_k)**4 - i_idx**4
    left_now = (j_idx + inc_n)**4 - j_idx**4
    if left_now == right_now:
        if i_idx != j_idx:
            print(f"Match found: x = {i_idx}, y = {j_idx}")
        i_idx += 1
        j_idx += 1
    elif left_now < right_now:
        j_idx += 1
    else:
        i_idx += 1

Так удается устранить квадратичный взрыв во внутреннем цикле благодаря упорядоченности.

Расширение на множество пар (n, k) с потоковым слиянием

Если нужно искать сразу по множеству значений n и k, думайте в терминах слияния отсортированных потоков. Для каждого фиксированного сдвига k последовательность по x значений (x + k)^4 − x^4 возрастает. Их можно порождать лениво и сливать в один поток за один проход. Та же идея работает и для n на левой стороне; фрагмент ниже показывает, как объединять множество правых последовательностей и обнаруживать равенства между соседними элементами объединенного потока.

from heapq import merge

cap = 10**4

def series(delta):
    for xi in range(1, cap):
        yield (xi + delta)**4 - xi**4, xi, delta

last_val = None
last_x = None
last_shift = None

for cur_val, cur_x, cur_shift in merge(*map(series, range(1, 101))):
    if last_val == cur_val:
        print(f'prev_n={last_shift}, cur_k={cur_shift}, x_now={cur_x}, y_prev={last_x}')
    last_val, last_x, last_shift = cur_val, cur_x, cur_shift

В такой конфигурации, при k от 1 до 100 и x от 1 до 10,000, подход занимает около 1,5 секунды и требует минимум памяти, воспроизводя те же решения, что и существующий поиск на тех же диапазонах. Например, среди совпадений вы увидите известный случай с положительными целыми n = 74 и k = 24, а также несколько других:

n=74, k=24, x=134, y=59
n=75, k=25, x=133, y=59
n=27, k=5, x=497, y=271
n=63, k=35, x=257, y=193
n=64, k=36, x=256, y=193
n=54, k=10, x=994, y=542
n=81, k=15, x=1491, y=813

Секрет в том, чтобы рассматривать каждую фиксацию параметра как отсортированный генератор и сливать их, не материализуя большие массивы. Вы сравниваете каждый полученный элемент только с непосредственным предыдущим в порядке слияния.

Неограниченное перечисление с кучей

Можно снять верхние границы и по x, и по параметру k, если построить слияние вручную на куче. Стартуем с k = 1 и постепенно добавляем поток для k + 1, когда текущий поток продвигается от x = 1 к x = 2. Это удерживает число активных потоков минимальным и позволяет исследовать сколь угодно большие области, пока вы даете программе работать.

from heapq import heappush, heappop
from time import time

stop_at = time() + 3

minheap = []

def push_state(shift, x_idx):
    heappush(minheap, ((x_idx + shift)**4 - x_idx**4, shift, x_idx))

push_state(1, 1)
prev_val = None
prev_x = None
prev_shift = None

while time() < stop_at:
    curr_val, k_shift, x_pos = heappop(minheap)
    if prev_val == curr_val:
        print(f'prev_n={prev_shift}, cur_k={k_shift}, x_now={x_pos}, y_prev={prev_x}')
    push_state(k_shift, x_pos + 1)
    if x_pos == 1:
        push_state(k_shift + 1, 1)
    prev_val, prev_x, prev_shift = curr_val, x_pos, k_shift

Запущенный с небольшим временным окном, этот способ выдаёт десятки решений. Жесткие ограничения на x и k исчезают благодаря ленивому расширению фронтира поиска по мере необходимости.

Что происходит под капотом

Все улучшения опираются на возрастающие последовательности и потоковую обработку. При фиксированных n или k разность четвертых степеней растет с x, поэтому вложенные циклы не нужны — кандидатов можно просматривать за один проход. Для множества параметров вы объединяете отсортированные генераторы в единую возрастающую последовательность. Слияние на базе кучи гарантирует, что вы всегда сравниваете ближайших соседей в пространстве значений, без выделения больших буферов. Версия с двумя указателями заменяет O(B^2) обход сетки на O(B) шагов для границы B на последовательность. Варианты с объединением потоков обрабатывают суммарное число элементов, пропорциональное области поиска, поддерживая лишь небольшой фронтир.

Тонкий, но важный нюанс

В вариантах с объединенными потоками равенство проверяется только с непосредственным предыдущим значением в порядке слияния. Если одно и то же число встречается три раза и более в разных потоках, код напечатает совпадения лишь для соседних пар в этом порядке. Например, если три различных выбора (x, k) дают одинаковое значение, совпадение между первым и третьим напрямую не печатается. Если нужны все попарные комбинации среди равных значений, соберите их в «корзину», а затем перечислите все пары внутри нее.

Почему это важно

Даже для на вид простых уравнений диофантовы пространства поиска огромны. Структурные свойства, такие как монотонность, позволяют заменить грубую силу потоковыми алгоритмами с предсказуемым поведением и малым потреблением памяти. Прием масштабируется от проверки одной пары параметров до сканирования широких полос значений n и k и поддерживает открытое исследование, когда вы можете запускать поиск настолько долго, насколько хватает терпения. То, что метод быстро переоткрывает известные решения в положительных целых, например n = 74 и k = 24, показывает его практическую эффективность.

Практические рекомендации

Сначала устраните квадратичный внутренний цикл, применив сканирование двумя указателями для фиксированных параметров. Когда понадобится просмотреть множество наборов параметров, мыслите категориями слияния отсортированных генераторов: Python’s heapq.merge помогает, когда набор потоков известен заранее, а ручная куча дает гибкость наращивать набор на лету. Помните о проверке равенства только с соседним значением, если ожидаете, что одно и то же число встретится чаще двух раз, и соответствующим образом скорректируйте шаг вывода. С этими элементами можно перейти от наивного перебора к экономному по памяти, высокопроизводительному поиску, который уверенно справляется с требовательными диапазонами.