# Minimize $\sum f(p_i)$ for given $\prod p_i$

A signal which is a function of a set of periodic signals with periods $p_1,\dotsc, p_n$ will have a period $P$ which is the least common multiple of all $p_i$. (If $p_i$ are relatively prime, which is the only relevant case here, then $P = \prod_i p_i$.)

Assume that each $p_i$ must be an integer and greater than some constant $k$.

What is a straightforward algorithm which will list, for each possible $P$ in increasing order, the values of $n$ and $p_1,\dotsc, p_n$ which minimize $\sum_i (12 + 3\lceil (p_i - 1)/4 \rceil)$ (the cost of the signal generators)?

For those curious about the application, or wondering if this is homework, I am constructing a virtual logic circuit in the game Minecraft; I wish to produce a long (relative to the logic elements' propagation time) delay using a minimum of resources. I am using a group of clocks with differing periods and ORing the outputs, so that the output has a period which is the product of the individual periods as described. I have found a satisfactory result by trial and error, but I'd like to also find and document a systematic solution.

-
If you wanted to maximize $lcm(\{ p_i \})$ for a given $\sum_i p_i$, you'd end up with Landau's function (en.wikipedia.org/wiki/Landau's_function). Perhaps that will help. – Michael Lugo Mar 7 '11 at 0:20
Landau's function gives approximate answers to this problem, but the possible values of $P$ (the range of the function) are too widely spaced. – Kevin Reid Mar 7 '11 at 0:35

## 1 Answer

If the $p_i$ are all prime, then $P$ must be squarefree and a given $P$ can only come from one set of $p_i$-its prime factorization. In that sense there is no minimization to be done, unless you mean a $P$ which has a lower value of $\sum_i (12 + 3\lceil (p_i - 1)/4 \rceil)$ than lower $P$'s. For a given prime $p$ its contribution to $\log P$ is $\log p$, while its contribution to the sum is as you see. So the ratio of these gives a figure of merit for primes. It is above 0.04 from about 5 to 33, so primes in there are what you want, and the $4n+1$ ones are somewhat better due to your ceiling function.

-
D'oh! OK, so my problem can be reduced to listing squarefree numbers (possible $P$s) and their factorization (in terms of $p_i = 4a + b + 1$ for this particular application). I had originally been confused and thought that $p_i = 4a + 1$, which constrains the usable primes. ($k$ still does; but that can be handled by multiplying together factors of $P$ until they are all above $k$, which still needs minimization of the sum but is more obviously a small problem.) Thanks! – Kevin Reid Mar 7 '11 at 0:41
The other comment is to ask whether the $p$'s really need to be prime, or just relatively prime to the other $p$'s. The $12 + 3\lceil (p_i - 1)/4 \rceil$ looks like the cost to implement a loop for $p_i$, but why can't you have $p_1=30$ as long as no other $p$ has a factor of $2,3,$or $5$? Just a thought. – Ross Millikan Mar 7 '11 at 0:50
Ah, so it is not just squarefree numbers; but each number needs to be factored into relatively prime factors. (The more factors, the lower the cost, to a point.) Hm. This is starting to turn into "Factor each integer, try all partitions of the factors, and pick the lowest" — which is still straightforward, and probably cheap enough since it only needs to be computed once to make a table, but not pretty. Perhaps your figure of merit could be used as a shortcut in choosing the factorization. – Kevin Reid Mar 7 '11 at 1:00
True, but there aren't many choices under 33, after that it decreases pretty monotonically, and 30 is notably worse than 15. So probably you can count 15 a prime, 2,3, and 5 not primes, and take any squarefree (odd) P. This ignores that you wanted all factors greater than k. By the way, I used base 10 logs if you try to reproduce my values. It just rescales anyway. – Ross Millikan Mar 7 '11 at 1:52