I am trying to optimize an algorithm that right now uses bruteforce to find a solution. Since the set of permissible solutions is known and very limited compared to the number of inputs to try, I am wondering if I can backtrace it.

Let $winner = \{0,3,7,\dots\}$ be a given set of allowed numbers in the solution, $w$ be any vector with $\{w_i|w_i\in winner\}$ and $|w| = 20$. Since the set $winner$ is small, I can easily find all permutations $w$, so that would be allowed solutions. The problem is that these solutions need to be generated by some function $f(n)$ as described below.

Right now the algorithm to find candidates looks like this: \begin{align*} c_0 &= f(0) \cdot2^k\\ c_n &= (c_{n - 1}\ \%\ 2^k) + f(n)\cdot 2^k \end{align*} ($\%$ represents modulo as an operator here, and again $|f(n)| = 20$, so it's a vector)

I am iterating $n$ to find a $c_n = w$, i. e. a candidate that only contains "winners". The problem is that n can grow quite large, so it's very slow. Also $f(0)$ might yield something that will never lead to a solution.

So the idea is to run through all possible $w$ and find $n$ that way.

Unfortunately I have no experience with series like this one. I am not even sure if it is possible to find a closed form with the modulo.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.