Find Integer Solutions to Quartic Diophantine Equations with Two-Pointer Scans and Heap-Merged Streams

Boost searches for integer solutions to quartic Diophantine equations with two-pointer scans, streaming merges, and Python generators. Ditch brute force.

Searching for integer solutions to quartic Diophantine equations can quickly spiral into infeasible runtimes if you iterate naively over huge grids. A common example is looking for pairs (x, y), with x ≠ y, that satisfy (y + n)^4 − y^4 = (x + k)^4 − x^4 for fixed small positive integers n and k. The straightforward double loop over large ranges of x and y is prohibitively slow. Below is a step-by-step guide to turning that brute force into an efficient streaming search that scales, supports multiple parameter sets, and can even be made unbounded.

Baseline brute force and why it struggles

Here is a direct implementation that checks every pair. The logic is simple: compute both sides for all x and y and compare, skipping x == y. It works in principle but is quadratic in the search bound.

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}")

This approach performs on the order of upper_bound squared comparisons. For ranges like 1 to 1,000,000 that’s not viable.

The core observation: monotonicity enables two-pointer scanning

The function z ↦ (z + t)^4 − z^4 increases as z increases for any fixed positive t. That means, for fixed n and k, the left-hand sequence over y and the right-hand sequence over x are both strictly increasing. When two sequences are sorted, you do not need nested loops. You can walk both sequences in lockstep using the classic two-pointer technique: compare current values, advance the side that is smaller, and record a match when they are equal.

Efficient search for a single pair (n, k)

The following code scans x and y once, comparing only aligned positions and moving forward monotonically. It preserves the original logic and only emits solutions with 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

This eliminates the quadratic blowup in the inner loop by taking advantage of ordering.

Extending to many pairs (n, k) with streaming merge

If you want to search across many values of n and k simultaneously, think in terms of merging sorted streams. For each fixed shift k, the sequence over x of (x + k)^4 − x^4 is increasing. You can generate each stream lazily and merge them all with a single pass. The same idea applies to n on the left-hand side; the snippet below demonstrates merging many right-hand sequences and detecting equalities between consecutive merged items.

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

In this configuration, scanning k from 1 to 100 and x from 1 to 10,000, the approach takes about 1.5 seconds and minimal memory to reproduce the same solutions as an existing search over the same ranges. For example, among the matches you will see the well-known positive-integer case with n = 74 and k = 24, alongside several others:

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

The trick here is to treat each fixed-parameter evaluation as a sorted generator, then merge them without materializing large arrays. You only compare each produced value to the immediately prior one in the merged order.

Unbounded enumeration with a heap

You can lift both the search bound on x and the range of parameter k by constructing the merge yourself with a heap. Start from k = 1 and incrementally add the stream for k + 1 when the current stream advances from x = 1 to x = 2. This keeps the number of active streams minimal and supports arbitrarily large exploration as long as you let it run.

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

Run with a small time window, this approach produces dozens of solutions. It removes hard limits on x and k by lazily expanding the frontier of the search as needed.

What’s happening under the hood

The improvements hinge on increasing sequences and streaming. For fixed n or k, the quartic difference grows with x, so you can avoid nested loops and walk through candidates in one pass. For exploring many parameter choices, you combine sorted generators into a single ascending sequence. Using heap-based merging ensures you always compare nearest neighbors in value space without allocating large buffers. The two-pointer version replaces the O(B^2) grid scan with O(B) steps for a bound B per sequence. The merged-stream variants process a total number of emitted values proportional to the search envelope while maintaining only a small frontier.

A subtle but important caveat

In the merged-stream variants, equality is checked only against the immediately prior value in the merged order. If the same numeric value appears three or more times across different streams, the code prints matches only for adjacent pairs in that order. For example, if three distinct (x, k) choices share the same value, the match between the first and the third is not printed directly. If you need all pairwise combinations among equal values, you would collect equals into a bucket and then enumerate all pairs within that bucket.

Why this matters

Diophantine search spaces are enormous even for simple-looking equations. Structural properties, such as monotonicity, let you trade brute force for streaming algorithms with predictable behavior and small memory footprints. The technique scales from checking a single parameter pair to scanning wide bands of n and k, and it supports open-ended exploration where you can run the search for as long as you have patience. The fact that the method quickly rediscovers known positive-integer solutions, like n = 74 and k = 24, shows it is effective in practice.

Practical takeaways

Start by eliminating the quadratic inner loop using a two-pointer scan for fixed parameters. When you want to sweep many parameter sets, think in terms of merging sorted generators; Python’s heapq.merge helps when the set of streams is known, and a manual heap gives you the flexibility to grow the set on the fly. Be aware of the neighbor-only equality check if you expect the same value to arise more than twice and adjust the output step accordingly. With these pieces in place, you can move from a naive scan to a memory-efficient, high-throughput search that keeps up with demanding ranges.