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.

Assume I have N sequences of ones and zeros. Each sequence repeats every p terms. I want to find the minimum position where all sequences evaluate to "1"

Here is an example set of sequences for $N = 3$ and $p = \{2, 3, 5\}$:

$$ \begin{align} a_1 & = \{1, 0, 1, 0, ...\} \\ a_2 & = \{0, 1, 1, 0, 1, 1, ...\} \\ a_3 & = \{0, 1, 0, 0, 1, 0, 1, 0, 0, 1,...\} \\ \end{align} $$

Observing that $14 = 0\ mod\ 2$ and $14 = 2\ mod\ 3$ and $14 = 4\ mod\ 5$ all of which correspond to "1"s in the above sequence we can verify that 14 is a possible solution. By simply extending the pattern we can find that the 14th element is indeed the first to yield "1" for each sequence.

I attempted to solve this analytically by converting the patterns into closed form equations; however this seems impractical once N or p become non-trivial. I may be wrong but I can't find a good method for solving large systems of complex equation over integers.

For my problem it can be assume that all sequence repeat sizes (p) are coprime. It can also be assumed that $100 < N < p < 1000$. That is, I could be looking at 100 to 1000 sequences that have patterns that repeat every 1000 terms. Each pattern will have approximately $p/2$ "1"s. Therefor, trying to brute force the solution by solving every set of congruencies is not efficient.

Is there a general name for this type of problem? What are some efficient ways of finding the lowest common term position?

share|improve this question
    
I suspect this is a computationally infeasible ("NP-complete") problem. If you have access to a copy of Garey & Johnson, have a look to see whether this problem is listed there. –  Gerry Myerson Jul 21 '13 at 0:08
    
Related (not identical) problem: math.stackexchange.com/questions/257161/… –  Gerry Myerson Jul 21 '13 at 0:10

1 Answer 1

In my view this problem is hopeless in terms of computing an actual answer. If you let $p_i$ be an index where $a_i$ is 1 ($1\le p_i\le p$), and you do this for all $i$ ($1\le i\le N$), then you can solve this specific problem with the CRT. However there are over $50^N$ such problems that you are minimizing over, and the function you're trying to minimize is not particularly natural here, since $\mathbb{Z}/n\mathbb{Z}$ has no innate order, and you need to project to $\mathbb{N}$ to exploit the order there.

The simple method of just computing all the terms and waiting for all 1's won't work, because it will take on average $2^N$ steps to completion.

Induction won't help, because the optimal solution for $N$ sequences need have nothing at all to do with the optimal solution for $N+1$ sequences.

share|improve this answer

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.