A393547 a(n) is the length of the finite sequence of positive integers (x_1, x_2, ...), where x_1 = n and, for i >= 1, x_{i+1} = min { k > 0 | x_i + k^2 is a perfect square } if such a k exists; otherwise x_i is the last term of the sequence.

1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 2, 2, 1, 2, 3, 3, 1, 3, 2, 2, 1, 4, 2, 3, 1, 3, 2, 2, 1, 3, 2, 2, 1, 2, 3, 2, 1, 3, 3, 3, 1, 3, 2, 2, 1, 5, 2, 3, 1, 4, 3, 2, 1, 3, 3, 3, 1, 3, 2, 2, 1, 2, 2, 2, 1, 3, 4, 2, 1, 3, 3, 4, 1, 3, 2, 2, 1, 4, 2, 3, 1, 4, 2, 2, 1, 3, 3, 3, 1, 3, 2, 2, 1, 4, 2, 3, 1, 2, 3

Offset

1,3

Comments

The sequence terminates at x if x is 1, 4, or x is congruent to 2 mod 4. If x is congruent to 2 mod 4, then x cannot be represented as a difference of two squares.

This sequence is a variant of A034175, where the next term x_{i+1} is chosen greedily such that x_i + x_{i+1}^2 is a perfect square.

Let m_k = min { n > 0 | a(n) = k }. The first few values are m_1 = 1, m_2 = 3, m_3 = 7, m_4 = 23, m_5 = 47, m_6 = 291, m_7 = 1439. While m_k is prime for 1 < k < 6, m_6 is composite (3 * 97).

Links

Table of n, a(n) for n=1..100.

Example

a(7) = 3 because the sequence starting at 7 is (7, 3, 1):
- x_1 = 7: the smallest k > 0 such that 7 + k^2 is a square is 3 (since 7 + 3^2 = 4^2).
- x_2 = 3: the smallest k > 0 such that 3 + k^2 is a square is 1 (since 3 + 1^2 = 2^2).
- x_3 = 1: no such k > 0 exists, as 1 + k^2 = m^2 implies k = 0.
The sequence length is 3.

Prog

(Python)
# a(n) is the length of the finite sequence starting at x_1 = n.
import math
def get_next_x(x):
    """Find the smallest positive integer k such that x + k^2 is a square."""
    if x % 4 == 2:
        return None
    limit = math.isqrt(x)
    if limit * limit == x:
        limit -= 1
    for a in range(limit, 0, -1):
        if x % a == 0:
            b = x // a
            if (b - a) % 2 == 0:
                k = (b - a) // 2
                if k > 0:
                    return k
    return None
def a(n):
    """Compute the number of terms in the sequence starting at n."""
    curr = n
    count = 1
    while True:
        nxt = get_next_x(curr)
        if nxt is None:
            break
        curr = nxt
        count += 1
    return count
# Example: generate first 100 terms
# print(", ".join(str(a(n)) for n in range(1, 101)))

Crossrefs

Cf. A034175.

Sequence in context: A056692 A331600 A039637 * A394525 A194548 A274009

Adjacent sequences: A393544 A393545 A393546 * A393548 A393549 A393550

Keyword

nonn

Author

Naoki Azuma, Mar 20 2026

Status

approved