A063655 Smallest semiperimeter of integral rectangle with area n.

2, 3, 4, 4, 6, 5, 8, 6, 6, 7, 12, 7, 14, 9, 8, 8, 18, 9, 20, 9, 10, 13, 24, 10, 10, 15, 12, 11, 30, 11, 32, 12, 14, 19, 12, 12, 38, 21, 16, 13, 42, 13, 44, 15, 14, 25, 48, 14, 14, 15, 20, 17, 54, 15, 16, 15, 22, 31, 60, 16, 62, 33, 16, 16, 18, 17, 68, 21, 26

Offset: 1

Author

Floor van Lamoen, Jul 24 2001

Keywords

• nonn

Comments

Similar to A027709, which is minimal perimeter of polyomino of n cells, or equivalently, minimal perimeter of rectangle of area at least n and with integer sides. Present sequence is minimal semiperimeter of rectangle with area exactly n and with integer sides. - Winston C. Yang (winston(AT)cs.wisc.edu), Feb 03 2002

Semiperimeter b+d, d >= b, of squarest (smallest d-b) integral rectangle with area bd = n. That is, b = largest divisor of n <= sqrt(n), d = smallest divisor of n >= sqrt(n). a(n) = n+1 iff n is noncomposite (1 or prime). - Daniel Forgues, Nov 22 2009

From Juhani Heino, Feb 05 2019: (Start)

Basis for any thickness "frames" around the minimal area. Perimeter can be thought as the 0-thick frame, it is obviously 2a(n). Thickness 1 is achieved by laying unit tiles around the area, there are 2(a(n)+2) of them. Thickness 2 comes from the second such layer, now there are 4(a(n)+4) and so on. They all depend only on a(n), so they share this structure:

Every n > 1 is included. (For different thicknesses, every integer that can be derived from these with the respective formula. So, the perimeter has every even n > 2.)

For each square n > 1, a(n) = a(n-1).

a(1), a(2) and a(6) are the only unique values - the others appear multiple times.

(End)

Gives a discrete Uncertainty Principle. A complex function on an abelian group of order n and its Discrete Fourier Transform must have at least a(n) nonzero entries between them. This bound is achieved by the indicator function on a subgroup of size closest to sqrt(n). - Oscar Cunningham, Oct 10 2021

Also two times the median divisor of n, where the median of a multiset is either the middle part (for odd length), or the average of the two middle parts (for even length). The version for mean instead of median is A057020/A057021. Other doubled medians of multisets are: A360005 (prime indices), A360457 (distinct prime indices), A360458 (distinct prime factors), A360459 (prime factors), A360460 (prime multiplicities), A360555 (0-prepended differences). - Gus Wiseman, Mar 18 2023

Examples

			Since 15 = 1*15 = 3*5 and the 3*5 rectangle gives smallest semiperimeter 8, we have a(15)=8.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• Roy Meshulam, An uncertainty inequality for finite abelian groups, arXiv:math/0312407 [math.CO], 2003.
• Roy Meshulam, An uncertainty inequality for finite abelian groups, European Journal of Combinatorics, 27 (2006) 63-67.

Crossrefs

Cf. A027709, A033676, A033677, A092510, A162348.

Positions of odd terms are A139710.

Positions of even terms are A139711.

A000005 counts divisors, listed by A027750.

A000975 counts subsets with integer median.

Cf. A003601, A026424, A057020/A057021, A325347, A359893, A359901.

Programs

Maple

A063655 := proc(n)
    local i,j;
    for i from floor(sqrt(n)) to 1 by -1 do
        j := floor(n/i) ;
        if i*j = n then
            return i+j;
        end if;
    end do:
end proc:
seq(A063655(n), n=1..80); # Winston C. Yang, Feb 03 2002

Mathematica

Table[d = Divisors[n]; len = Length[d]; If[OddQ[len], 2*Sqrt[n], d[[len/2]] + d[[1 + len/2]]], {n, 100}] (* T. D. Noe, Mar 06 2012 *)
Table[2*Median[Divisors[n]],{n,100}] (* Gus Wiseman, Mar 18 2023 *)

PARI

A063655(n) = { my(c=1); fordiv(n,d,if((d*d)>=n,if((d*d)==n,return(2*d),return(c+d))); c=d); (0); }; \\ Antti Karttunen, Oct 20 2017

Python

from sympy import divisors
def A063655(n):
    d = divisors(n)
    l = len(d)
    return d[(l-1)//2] + d[l//2] # Chai Wah Wu, Jun 14 2019

Formula

a(n) = A033676(n) + A033677(n).

a(n) = A162348(2n-1) + A162348(2n). - Daniel Forgues, Sep 29 2014

a(n) = Min_{d|n} (n/d + d). - Ridouane Oudra, Mar 17 2024

Extensions

Corrected and extended by Larry Reeves (larryr(AT)acm.org) and Dean Hickerson, Jul 26 2001