A376138 a(n) is the smallest k such that n = ab + cd with 1 <= a,b,c,d <= k.

1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, 3, 4, 3, 4, 4, 3, 4, 4, 4, 4, 5, 4, 4, 5, 5, 4, 5, 5, 5, 4, 5, 5, 5, 5, 5, 6, 6, 5, 5, 6, 6, 6, 5, 6, 7, 6, 6, 5, 6, 6, 7, 6, 6, 6, 7, 7, 7, 6, 6, 7, 7, 7, 7, 6, 7, 8, 7, 7, 7, 6, 7, 7, 8, 8, 7, 7, 7, 8, 8, 8, 8, 7, 7, 8, 9, 8

Offset: 2

Author

Glen Whitney, Oct 14 2024

Keywords

• nonn

Comments

The least side length that is required to express n as the sum of two rectangular numbers.

The minimum height of an area-n generalized "L" polyomino (a union of two integer-side rectangles in portrait orientation).

The largest n such that a(n) = k is 2k^2 since that n can be written as k*k + k*k.

Examples

			For n = 7, we may write
  7 = 1*1 + 2*3,
  7 = 1*2 + 1*5,
  7 = 1*3 + 2*2.
Of these, the first and third have the smallest value for the largest factor appearing. Therefore, a(7) = 3.
		

Links

• Glen Whitney, Table of n, a(n) for n = 2..10000

Crossrefs

Cf. A033677 (as single rectangular number).

Programs

Maple

b:= proc(n) b(n):= min(select(x-> x^2>=n, numtheory[divisors](n))) end:
a:= proc(n) a(n):= min(seq(max(b(i), b(n-i)), i=1..n/2)) end:
seq(a(n), n=2..100);  # Alois P. Heinz, Oct 15 2024

Mathematica

b[n_] := SelectFirst[Divisors[n], #^2 >= n&];
a[n_] := Min[Table[Max[b[i], b[n-i]], {i, 1, n/2}]];
Table[a[n], {n, 2, 100}] (* Jean-François Alcover, Jan 26 2025, after Alois P. Heinz *)

Python

from sympy import divisors
from functools import cache
@cache
def b(n): return next(x for x in divisors(n) if x**2 >= n)
def a(n): return min(max(b(i), b(n-i)) for i in range(1, n//2+1))
print([a(n) for n in range(2, 100)]) # Michael S. Branicky, Oct 15 2024 after Alois P. Heinz

Formula

a(n) = min_{i=1..n/2} max(A033677(i), A033677(n-i)).