Print a specific value in this generated binary matrix Suppose we define an infinite matrix M, on N^2 -&gt; {0, 1} (where N starts from 1 instead of 0) in this manner:


M(1, 1) = 0.
For every x &gt; 1, M(x, 1) = 1 if x is prime, and 0 otherwise.
For every y &gt; 1, M(1, y) = the yth term in the Thue-Morse sequence.
For every x, y &gt; 1, M(x, y) = M(x, y-1) + M(x-1, y) mod 2.


The top-left 16x16 section of this matrix looks like (with x being rows and y being columns):

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1
1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0
0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1
1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1
0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1
1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1
0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1
0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1
0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0
1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1
0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1
1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0
0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1
0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1
0 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1


Your task is to build a program that will evaluate the value of an arbitrary entry in this matrix as accurately as possible.

Your program will take two integers x and y as input, in any form you choose, and return M(x, y), which will be either 0 or 1.

Your code may be written in any language, but must not exceed 64 kilobytes (65,536 bytes) of source code size or 2 MB (2,097,152 bytes) of total memory usage. Your program must start with empty memory (i.e. it cannot load data from somewhere else) and run independently for each input (that is, it may not store common data for multiple runs). Your program must also be able to evaluate all the entries in the top-left 8192x8192 square in a reasonable amount of time.

The program that evaluates the most entries correctly in the top-left 8192 x 8192 square will be the winner, with shorter code acting as a tie-breaker.
J - 42 38 char

Pretty fast, 100% accurate, and well within the memory constraints.

([{+2&amp;(~:/@#:@#@],~:/\,(p:&gt;:)&amp;#)0:)&amp;&lt;:


The strategy is as follows: we will calculate successive antidiagonals of this matrix, performing a pairwise XOR to move along and adding the current Thue-Morse and prime bits to the ends. We then pull the required digit out of the antidiagonal when we get there.

Explanation by explosion:

(                                 )&amp;&lt;:  NB. decrement each of x and y
     &amp;(                        )        NB. apply the following function...
   +                                    NB. ... (x-1)+(y-1) times...
                                0:      NB. ... starting with a zero:
    2             ~:/\                  NB.   pairwise XOR on the argument
                      ,(p:&gt;:)&amp;#         NB.   append prime bit (is 1+length prime?)
       ~:/@#:@#@],                      NB.   prepend TM bit (XOR of binary)
 [{                                     NB. take the x-th bit (at index x-1)


Usage of this verb is x m y for M(x, y) as specified in the question, where m is the verb.

   5 ([{+2&amp;(~:/@#:@#@],~:/\,(p:&gt;:)&amp;#)0:)&amp;&lt;: 8
0
   m =: ([{+2&amp;(~:/@#:@#@],~:/\,(p:&gt;:)&amp;#)0:)&amp;&lt;:
   1+i.16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
   m/~ 1+i.16
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1
1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0
0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1
1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1
0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1
1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1
0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1
0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1
0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0
1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1
0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1
1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0
0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1
0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1
0 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1


To save keystrokes we don't try to tell if we still need more prime or Thue-Morse bits, so we compute the entire antidiagonal to get the bit we want. However, 8192 m 8192 still runs in less than 0.07 s and about 100 KiB on my modest laptop.