# Print a specific value in this generated binary matrix

Suppose we define an infinite matrix M, on N^2 -> {0, 1} (where N starts from 1 instead of 0) in this manner:

• M(1, 1) = 0.

• For every x > 1, M(x, 1) = 1 if x is prime, and 0 otherwise.

• For every y > 1, M(1, y) = the yth term in the Thue-Morse sequence.

• For every x, y > 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.

• I'm probably going to update the testing case to something slightly more elegant in a moment, so hang on with the testing until I edit the question again. Mar 19 '14 at 21:25
• @mbuettner Yes, it does. Mar 19 '14 at 21:27
• I fail to see how we need a new tag for "accuracy." This is just a [code-challenge]. Please run new challenge genre ideas through meta first (there's one thing we learned from [code-trolling]).
– Doorknob
Mar 19 '14 at 21:31
• ^ Noted. I'll remove that tag. Mar 19 '14 at 21:34
• @TheDoctor It's not too uncommon. The accepted answer changes over time. Mar 19 '14 at 23:47

# J - 42 38 char

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

([{+2&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<:


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:

(                                 )&<:  NB. decrement each of x and y
&(                        )        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:>:)&#         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&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<: 8
0
m =: ([{+2&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<:
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.

## Mathematica – 100% accuracy, 223193 189 bytes

f=(r=Array[0&,Max@##];For[s=2,s<=#+#2,++s,For[i=Max[1,s-#2],i<=Min[s-1,#],++i,j=s-i;r[[j]]=Which[i==1,PrimeQ@j,j==1,OddQ@Total@IntegerDigits[i-1,2],0<1,Xor@@r[[j-1;;j]]]]];If[r[[#2]],1,0])&


Here is a legible version:

f[x_,y_] := (
r = Array[0 &, Max[x,y]];
For[s = 2, s <= x + y, ++s,
For[
i = Max[1, s - y],
i <= Min[s - 1, x],
++i,

j = s - i;
r[[j]] = Which[
i == 1,
PrimeQ@j,
j == 1,
OddQ@Total@IntegerDigits[i - 1, 2],
0 < 1,
r[[j - 1]]~Xor~r[[j]]
]
]
];
If[r[[y]], 1, 0]
);


I basically precompute along diagonals of constant x+y.

Features:

• It's accurate.
• It runs in O(x*y).
• f[8192,8192] takes about 400 seconds. I suppose there is room for improvement (maybe RotateLeft could replace the inner loop).
• It only uses one array of up to max(x,y) intermediate results in memory. So there is no necessity to use more than about 32k (assuming 32-bit integers) for the algorithm itself (plus, whatever Mathematica uses). In fact, Mathematica uses 31M by itself on my system, but this works without an issue:

MemoryConstrained[f[8192, 8192], 2^21]

• Well, looks like you got it. I'll be making harder ones in the future, though :P Mar 19 '14 at 23:09
• Hm, in one of the changes I must have screwed up the runtime performance. The inner loop is still called O(x*y) times, but the total execution time increases faster than that. I'm not quite sure what's happening. If some Mathematica Guru could enlighten me, which operation in the loop is not O(1) that would be very helpful! :) (well, PrimeQ and Total@IntegerDigits aren't, but I've had them in there from the beginning, and they only called O(y) and O(x) times respectively) Mar 20 '14 at 0:01

# Matlab: 100% accuracy, 120 characters, unreasonable execution time

function z=M(x,y)
if y==1 z=(x>1)*isprime(x);elseif x==1 z=mod(sum(dec2bin(y-1)-48),2);else z=xor(M(x,y-1),M(x-1,y));end


To use:

> M(4,4)
ans =
0
> M(1, 9)
ans =
1

• Now here's the question, can you actually run this program and test it? Mar 19 '14 at 22:14
• If you can't run M(8192, 8192), I can't take it. Mar 19 '14 at 22:17
• @JoeZ It's M-code, you can run it in Matlab or Octave. Mar 19 '14 at 22:17
• @JoeZ It will accurately compute M(8192, 8192). The challenge didn't say anything about time to complete ;) Mar 19 '14 at 22:18
• @JoeZ well it looks like M(20,20) takes longer than I'm willing to wait. But hey, it's "accurate"! :P Mar 19 '14 at 22:21

# Python, 192 characters

100% accuracy, calculates M(8192,8192) in ~10 seconds on my machine.

R=range
def M(X,Y):
X+=1;c=[1]*X;r=[0]
while len(r)<Y:r+=[i^1 for i in r]
for i in R(2,X):
if c[i]:
for j in R(i+i,X,i):c[j]=0
r[0]=c[i]
for i in R(1,Y):r[i]^=r[i-1]
return r[Y-1]


# Haskell - 261 bytes - 100% - 1MB - I don't think it is going to end anytime soon

Takes about 10 seconds for m 16 16 with -O2, but as I have written it anyway I can show it despite this problem:

m x y=if n x y then 1 else 0 where n x 1=b x;n 1 y=(a!!13)!!(y-1);n x y=(n x (y-1))f(n(x-1)y)
f True False=True
f False True=True
f _ _=False
a=[False]:map step a where step a=a++map not a
b x=xelemtakeWhile(<=x)e
e=c [2..]where c(p:s)=p:c[x|x<-s,xmodp>0]


Maybe some good Haskeller is able to optimize it?

m' x y = if m x y then 1 else 0
where
m x 1 = isPrime x
m 1 y = morse' y
m x y = (m x (y-1)) xor (m (x-1) y)

xor True False = True
xor False True = True
xor _ _ = False

morse' x = (morse !! 13) !! (x-1)
morse = [False] : map step morse where step a = a ++ map not a

isPrime x = x elem takeWhile (<=x) primes
primes :: [Integer]
primes = sieve [2..] where sieve (p:xs) = p : sieve [x|x <- xs, x mod p > 0]

main = putStrLn $show$ m' 16 16

• i think the algorithm itself is flawed. anyway, there are many things you can do to golf this. mostly extra parentheses , but also f p|p=not|0<1=id should be better. also, try using morse = False : concat $iterate [True] (\a -> a ++ map not a) for increased laziness. I wonder how it will affect performance. Jan 1 '15 at 22:15 • also, you can golf True to 0<1 and False to 0>1. Jan 1 '15 at 22:15 ## Perl, 137 Not to 'win' :-), but since there's no Perl here yet and code was written anyway, here it is. sub f{($n,$m)=@_;@a=0;@a=(@a,map{0+!$_}@a)while@a<$n;for$k(2..$m){$p=0;O:{$k%$_?1:last O for 2..sqrt$k;$p=1}$p=$a[$_]^=$p for 1..$n-1}$p}


Takes several seconds if called print f(8192,8192), stores single line of matrix in memory (array of 8192 integers (scalars)), about 3.5 Mb whole Perl process. I tried to do it with string instead of array (either with regexps or accessing with substr), takes less memory and can be golfed further, but runs much slower.

Indented:

sub f{
($n,$m)=@_;
@a=0;                                  # @a will be current line.
@a=(@a,map{0+!$_}@a)while@a<$n;        # Fill it with Thue-Morse sequence.
for$k(2..$m){                          # Repeat until required line number.
$p=0; # Find out if current line number O:{ # is a prime.$k%$_?1:last O for 2..sqrt$k;
$p=1 # Store result (0 or 1) in$p.
}
$p=$a[$_]^=$p for 1..$n-1 # XOR previous value in current position } # with$p and store in $p.$p                                     # Return $p. }  # Haskell, 223 g n=div(filter(>=n)(iterate(*2)1)!!0)2 1%1=0>1 1%n=not$1%(n-g n)
n%1=and[rem n x>0|x<-[2..n-1]]
a%b=g[0<1]where g s|foldr seq(0>1)s=0<1|n==a+b=s!!(b-1)|0<1=g\$n%1:zipWith x s(tail s)++[1%n]where n=length s+1
x p|p=not|0<1=id


this has fast runtime (5.7 seconds with -O3). memory wasn't checked yet, though it should be linear.

this uses the diagonal algorithm seen here before.

as far as speed is concerned, the only things that matter are the diagonal algorithm, -O3 , and the |foldr seq(0>1)s=0<1 guard, which makes the list strict. everything else is implemented rather inefficiently - prime checking is done by checking all the lesser numbers for division, the Morse sequence's elements are recomputed constantly. but it is still fast enough :-).