Work the least possible without ever seeing your coworkers, or minimize the sum of two coprime numbers such that their product is at least $n$

41 Views Asked by At

The solution to the associated continuous problem: $$ \min_{(x,y) \in S} x+y $$ where $$ S=\left\lbrace (x,y)\vert n \leq xy\right\rbrace $$ Is $x=y=\sqrt{n}$.

There is an associated problem where: $$ S=\left\lbrace (x,y)\vert n \leq xy,(x,y) \in \mathbb{Z}_{+}^2,\gcd(x,y)=1\right\rbrace $$ Or, find two positive integers with the smallest sum such that they are coprime and multiply to at least $n$.

This is akin to having two coworkers come into work regularly, every $x^\text{th}$ and $y^\text{th}$ day such that they never overlap (except for the first day) over the span of $n$ days (at least), while coming into work the least number of days over the span of $xy$ days, collectively.

Is there an analytical solution to this?

I've found that usually the solution takes the form: $$ x = \lfloor \sqrt{n}\rfloor - a, y = \lceil \sqrt{n}\rceil + b $$ Where it seems to be true that $-2\leq a,b \leq 2$.

Some example solutions are:

$n=8,x=2,y=5$ where $x+y=7$ and $xy=10$

$n=60,x=7,y=9$ where $x+y=16$ and $xy=63$

$n=144,x=9,y=16$ where $x+y=25$ and $xy=144$