A393547 - OEIS

%I #17 Mar 24 2026 22:54:50

%S 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,

%T 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,

%U 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

%N 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.

%C 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.

%C 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.

%C 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).

%e a(7) = 3 because the sequence starting at 7 is (7, 3, 1):

%e - x_1 = 7: the smallest k > 0 such that 7 + k^2 is a square is 3 (since 7 + 3^2 = 4^2).

%e - x_2 = 3: the smallest k > 0 such that 3 + k^2 is a square is 1 (since 3 + 1^2 = 2^2).

%e - x_3 = 1: no such k > 0 exists, as 1 + k^2 = m^2 implies k = 0.

%e The sequence length is 3.

%o (Python)

%o # a(n) is the length of the finite sequence starting at x_1 = n.

%o import math

%o def get_next_x(x):

%o     """Find the smallest positive integer k such that x + k^2 is a square."""

%o     if x % 4 == 2:

%o         return None

%o     limit = math.isqrt(x)

%o     if limit * limit == x:

%o         limit -= 1

%o     for a in range(limit, 0, -1):

%o         if x % a == 0:

%o             b = x // a

%o             if (b - a) % 2 == 0:

%o                 k = (b - a) // 2

%o                 if k > 0:

%o                     return k

%o     return None

%o def a(n):

%o     """Compute the number of terms in the sequence starting at n."""

%o     curr = n

%o     count = 1

%o     while True:

%o         nxt = get_next_x(curr)

%o         if nxt is None:

%o             break

%o         curr = nxt

%o         count += 1

%o     return count

%o # Example: generate first 100 terms

%o # print(", ".join(str(a(n)) for n in range(1, 101)))

%Y Cf. A034175.

%K nonn

%O 1,3

%A _Naoki Azuma_, Mar 20 2026