0
$\begingroup$

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.

$\endgroup$

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.