Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 1

up vote 0 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.