A387830 Least number of vertical or horizontal cuts required to divide a square into n equal parts.

0, 1, 2, 2, 4, 3, 6, 4, 4, 5, 10, 5, 12, 7, 6, 6, 16, 7, 18, 7, 8, 11, 22, 8, 8, 13, 10, 9, 28, 9, 30, 10, 12, 17, 10, 10, 36, 19, 14, 11, 40, 11, 42, 13, 12, 23, 46, 12, 12, 13, 18, 15, 52, 13, 14, 13, 20, 29, 58, 14, 60, 31, 14, 14, 16, 15, 66, 19, 24, 15

Offset

1,3

Comments

Each cut is required to go pass all the way through the square.

Equivalently, a(n) is the minimum of (d-1) + (n/d-1) over all divisors d of n.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..10000

Formula

a(p) = p - 1 for p prime.

a(n) = Min_{d|n} d + n/d - 2. - Andrew Howroyd, Oct 07 2025

a(n) = A063655(n) - 2. - Alois P. Heinz, Oct 07 2025

Example

a(6) = 3 since a square can be divided into 6 equal parts using 3 cuts (2 vertical and 1 horizontal).

Mathematica

a[n_]:= Min[Table[d + n/d - 2, {d, Divisors[n]}]]; Array[a, 70] (* Stefano Spezia, Oct 09 2025 *)

Prog

(PARI) a(n) = {my(m=n+1); fordiv(n, d, m=min(m, d+n/d)); m-2} \\ Andrew Howroyd, Oct 07 2025
(Python)
from sympy import divisors
def A387830(n): return (d:=divisors(n))[(l:=len(d))>>1]+d[l-1>>1]-2 # Chai Wah Wu, Oct 13 2025

Crossrefs

Cf. A063655.

Sequence in context: A334952 A220096 A122376 * A067240 A126080 A302043

Adjacent sequences: A387827 A387828 A387829 * A387831 A387832 A387833

Keyword

nonn

Author

Kiran Ananthpur Bacche, Oct 07 2025

Status

approved