0
$\begingroup$

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.

  • 0
    Landau's function gives approximate answers to this problem, but the possible values of $P$ (the range of the function) are too widely spaced.2011-03-07

1 Answers 1

0

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.

  • 0
    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.2011-03-07