Prime Nerd Sniping Pattern

Question

Longest day of the year - here's something to waste the extra time...

---

Overview

Note this is not a popularity contest and not a graphical output challenge - you are only required to output a string of 65,536 zeroes and ones. The Stack Snippet at the bottom of the question will display this as a 256 by 256 black and white image and calculate your official score. You can then save the image and upload it to your answer alongside your code (since the string output will not fit in a 30,000 character Stack Exchange answer).

---

Scoring

The score of an image is the sum of the scores of its individual pixels. The score of an individual pixel is the sum of the subscores for each of the non-orthogonal, prime distance pixels that are of opposite colour to the pixel being scored. The subscore for each such pixel is 1/p where p is the prime distance.

In the context of this question, the terms have the following definitions:

• Non-orthogonal: A pixel is non-orthogonal to the pixel being scored if it is not in the same row and is not in the same column.

• Prime distance: A pixel is at a prime distance from the pixel being scored if they are separated by a Euclidean distance that is exactly a prime number. In particular, distance is the minimum distance measured toroidally - the top left pixel is a distance of sqrt(2) from the bottom right pixel (all 4 edges wrap).

• Opposite colour: A pixel is of opposite colour to the pixel being scored if their values sum to 1. That is, the first is 0 and the second is 1, or the first is 1 and the second is 0.

The Stack Snippet includes example code that shows how to score an image, but does not include any optimisations or an efficient approach, just correct code so scoring of final images can be done consistently.

If anything in the code is not correct, please let me know either in the comments or in chat.

JavaScript may not necessarily be the best language for answering this particular challenge. Note that the Snippet code deliberately gives no clues as to faster approaches. It will only have efficiencies introduced that have already been demonstrated in an existing answer.

---

Visualisation

The scoring pixels

For an intuitive feel for the distribution of the scoring pixels, here (in purple) are the non-orthogonal prime distance pixels for pixel (128, 128) of a 256 by 256 image:

---

A random image

This is the randomly generated image from the example Python 3 answer. It has a score of 138,267.64 and gives you something to beat.

---

Input

The code does not require input.

Output

The code should output a string of 65,536 zeroes and ones, representing the pixels of a black and white 256 by 256 image. The digits should be a continuous string, with no separators. You may find copying and pasting easier if you output to a file, but this is up to you.

Your code may also output other information that you find useful, as long as the string can be copied and pasted into the Stack Snippet. For example, you may wish to output the best yet string to a file and the best yet score to STDOUT at regular intervals, allowing the user to choose when to stop the search.

---

Stack Snippet

As pointed out by Sp3000, the snippet was taking 10 minutes to calculate a score, which is a little too slow, even for a deliberately inefficient reference implementation. I've edited in Sp3000's suggested improvement of precomputing the pixel offsets for the scoring, and it now takes a few seconds to calculate a score.

canvas = document.getElementById('canvas')
ctx = canvas.getContext('2d')
scoreArea = document.getElementById('scoreArea')
pastedData = document.getElementById('pastedData')
timeout = 0

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499]

primesSquared = []
for (i=0; i<primes.length; i++) {
    primesSquared.push(primes[i] * primes[i])
}

width = canvas.width
height = canvas.height
area = width * height

scoringFilter = calculateScoringFilter()

function calculateScore() {
    var percentage = Math.floor(currentIndex / 65536 * 10000) / 100
    scoreArea.value = 'Calculating:' + percentage + '%'
    for (var t=0; t<1000; t++) {
        if (currentIndex < 65536) {
            partialScore += pixelScore(currentIndex)
            currentIndex += 1
        } else {
            scoreArea.value = 'Score: ' + partialScore
            return
        }
    }
    
    timeout = setTimeout(calculateScore, 10)
}

function pixelScore(i) {
    var score = 0
    var x = i % width
    var y = Math.floor(i / width)
    var a, b, xd, yd, j, k, d, m
    for (k=0; k<scoringFilter.length; k++) {
        bundle = scoringFilter[k]
        m = bundle[0]
        a = m % width
        b = Math.floor(m / width)
        j = ((x+a) % width) + width * ((y+b) % height)
        d = bundle[1]
        score += Math.abs(pixels[i] - pixels[j]) / d
    }
    return score
}

function display(pixels) {
    for (var i=0; i<area; i++) {
        ctx.fillStyle = pixels[i] ? 'white' : 'black'
        ctx.fillRect(i % width, Math.floor(i / width), 1, 1)
    }
}

function stop() {
    clearTimeout(timeout)
    scoreArea.value = 'Calculation cancelled.'
}

function isPrimeSquared(n) {
    return primesSquared.indexOf(n) > -1
}

function applyToImage() {
    var potentialPixels = []
    var pastedString = pastedData.value
    if (pastedString.length !== 65536) {
        scoreArea.value = 'Incorrect length:' + pastedString.length
        return
    }
    var i, digit
    for (i=0; i<pastedString.length; i++) {
        digit = pastedString.substring(i, i + 1)
        if (digit === '0') {
            potentialPixels.push(0)
        } else if (digit === '1') {
            potentialPixels.push(1)
        } else {
            scoreArea.value = 'Invalid character ' + i + ':' + digit
            return
        }
    }
    pixels = potentialPixels
    display(pixels)
    scoreArea.value = 'Calculating score...'
    partialScore = 0
    currentIndex = 0
    
    timeout = setTimeout(calculateScore, 10)
}

function calculateScoringFilter() {
    var scoringFilter = []
    var i, x, y, xd, yd
    for (i=0; i<area; i++) {
        x = i % width
        y = Math.floor(i / width)
        xd = Math.min(x,(-x+width)%width)
        yd = Math.min(y,(-y+height)%height)
        dSquared = xd*xd + yd*yd
        if (xd && yd && isPrimeSquared(dSquared)) {
            d = Math.sqrt(dSquared)
            scoringFilter.push([i, d])
        }
    }
    return scoringFilter
}

<canvas id='canvas' width='256' height='256'></canvas>
<br>
<input id='scoreArea' rows='1' readonly></input>
<br>
<button onclick='applyToImage()'>Apply string to image</button>
<button onclick='stop()'>Stop</button>
<br>
<br>
Paste in string of 65,536 zeroes and ones here:
<br>
<input id='pastedData'></input>

---

If you use the output or the code of another answer as the starting point for your own code, please remember to give credit and link to the supporting answer. Answers to this question do not need to credit the example answer or the code in the question.

Credit to Randall Munroe for the term Nerd Sniping

Answer 1

CJam, score 276496.9062958626

2,128*_(]128*

It turns out to be optimal, because: There aren't any non-orthogonal pairs with distance 2. So the distance must be odd, and so is the distance squared. As p²=x²+y², one of x and y (squared or not) must be odd, and the other must be even. Those points are always in the opposite color in this image.

This and its negative are also the only optimal solutions. In an optimal solution, no non-orthogonal, prime distance pixels should have the same color. There are diagonally adjacent opposite pixels like (3,4) and (4,3). By filling pixels of the opposite of opposite color, etc, we can get a diagonal with the same color. Starting from each pixel in the diagonal, we can get all the anti-diagonals filled in the same way. Note that they wrap around. It is still optimal if they don't, though.

Answer 2

Python 3, score 138267.64

This is a minimal answer as an example of what is required, and as something to beat...

It includes

• The language name.
• The score from the Stack Snippet in the question.
• The image saved from the Stack Snippet.
• The code used to produce the string of 65,536 zeroes and ones.

Output

Code

from random import random

output_string = ''
filename = '65536digits.txt'

for t in range(65536):
    digit = int(random() * 2)
    output_string += str(digit)

with open(filename, 'w') as output_file:
    output_file.write(output_string)

This is just an example. Python may not necessarily be the best language for competitive answers to this particular challenge.