python - A fast way to find an all zero answer -

for every array of length n+h-1 values 0 , 1, check if there exists non-zero array of length n values -1,0,1 h inner products zero. naive way is

import numpy np import itertools (n,h)= 4,3 longtuple in itertools.product([0,1], repeat = n+h-1):     bad = 0     v in itertools.product([-1,0,1], repeat = n):         if not any(v):             continue         if (not np.correlate(v, longtuple, 'valid').any()):             bad = 1             break     if (bad == 0):         print "good"         print longtuple 

this slow if set n = 19 , h = 10 test.

my goal find single "good" array of length n+h-1. there way speed n = 19 , h = 10 feasible?

the current naive approach takes 2^(n+h-1)3^(n) iterations, each 1 of takes n time. 311,992,186,885,373,952 iterations n = 19 , h = 10 impossible.

note 1 changed convolve correlate code considers v right way round.

---

july 10 2015

the problem still open no solution fast enough n=19 , h=10 given yet.

consider following "meet in middle" approach.

first, recast situation in matrix formulation provided leekaiinthesky.

next, note have consider "short" vectors s of form {0,1}^n (i.e., short vectors containing 0's , 1's) if change problem finding h x n hankel matrix h of 0's , 1's such hs1 never equal hs2 2 different short vectors of 0's , 1's. because hs1 = hs2 implies h(s1-s2)=0 implies there vector v of 1's, 0's , -1's, namely s1-s2, such hv = 0; conversely, if hv = 0 v in {-1,0,1}^n, can find s1 , s2 in {0,1}^n such v = s1 - s2 hs1 = hs2.

when n=19 there 524,288 vectors s in {0,1}^n try; hash results hs , if same result occurs twice h no , try h. in terms of memory approach quite feasible. there 2^(n+h-1) hankel matrices h try; when n=19 , h=10 that's 268,435,456 matrices. that's 2^38 tests, or 274,877,906,944, each nh operations multiply matrix h , vector s, 52 trillion ops. seems feasible, no?

since you're dealing 0's , 1's, not -1's, might able speed process using bit operations (shift, and, , count 1's).

update

i implemented idea in c++. i'm using bit operations calculate dot products, encoding resulting vector long integer, , using unordered_set detect duplicates, taking exit given long vector when duplicate vector of dot products found.

i obtained 00000000010010111000100100 n=17 , h=10 after few minutes, , 000000111011110001001101011 n=18 , h=10 in little while longer. i'm run n=19 , h=10.

#include <iostream> #include <bitset> #include <unordered_set>  /* count number of 1 bits in 32 bit int x in 21 instructions.  * /hackers delight/ henry s. warren, jr., 5-2  */ int count1bits(int x) {   x = x - ((x >> 1) & 0x55555555);   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);   x = (x + (x >> 4)) & 0x0f0f0f0f;   x = x + (x >> 8);   x = x + (x >> 16);   return x & 0x0000003f; }  int main () {   const int n = 19;   const int h = 10;   std::unordered_set<long> dotproductset;    // @ 2^(n+h-1) possibilities longvec   // upper n bits cannot 0 can start 1 in pos h   (int longvec = (1 << (h-1)); longvec < (1 << (n+h-1)); ++longvec) {      dotproductset.clear();     bool = true;      // @ n digit non-zero shortvecs     (int shortvec = 1; shortvec < (1 << n); ++shortvec) {        // longvec dot products shifted shortvecs generates h results       // each between 0 , n inclusive, can encode h digit number in       // base n+1, (n+1)^h = 20^10 approx 13 digits, need long       long dotproduct = 0;        // encode h dot products of shifted shortvec longvec       // base n+1 integer       for(int startshort = 0; startshort < h; ++startshort) {         int shortvecshifted = shortvec << startshort;         dotproduct *= n+1;         dotproduct += count1bits(longvec & shortvecshifted);       }        auto ret = dotproductset.insert(dotproduct);       if (!ret.second) {         = false;         break;       }     }      if (good) {       std::cout << std::bitset<(n+h-1)>(longvec) << std::endl;       break;     }   }    return 0; } 

second update

the program n=19 , h=10 ran 2 weeks in background on laptop. @ end, exited without printing results. barring kind of error in program, looks there no long vectors property want. suggest looking theoretical reasons why there no such long vectors. perhaps kind of counting argument work.