title: Produce Dürer's magic square

text:
# Question
Title: Produce Dürer's magic square
# The challenge

Output an array or string representation of Dürer's famous magic square:

that is,

```
16  3  2 13
 5 10 11  8
 9  6  7 12
 4 15 14  1

```

Some properties of this square, which can perhaps be exploited, are:

* It contains each integer from `1` to `16` exactly once
* The sum of each column or row, as well as the the sum of each of the two diagonals, is the same. This is the defining property of a magic square. The sum is the *magic constant* of the square.
* In addition, for this particular square, the sum of each of the four quadrants also equals the magic constant, as do the sum of the center four squares and the sum of the corner four squares.

# Rules

Bultins that generate magic squares are not allowed (such as Matlab's `magic` or Mathematica's `MagicSquare`). Any other builtin can be used.

The code can be a program or a function.

There is no input.

The numbers must be in base 10. The output format is flexible as usual. Some possibilities are:

* A nested array (either function output, or its string representation, with or without separators, any type of matching brackets):

```
[[16, 3, 2, 13], [5, 10, 11, 8], [9, 6, 7, 12], [4, 15, 14, 1]]

```
* A 2D array:

```
{16, 3, 2, 13; 5, 10, 11, 8; 9, 6, 7, 12; 4, 15, 14, 1}

```
* An array of four strings, or a string consisting of four lines. The numbers may be right-aligned

```
16  3  2 13
 5 10 11  8
 9  6  7 12
 4 15 14  1

```

or left-aligned

```
16 3  2  13
5  10 11  8
9  6  7  12
4  15 14  1

```
* A string with two different separators for row and column, such as

```
16,3,2,13|5,10,11,8|9,6,7,12|4,15,14,1

```

The output format should clearly differentiate rows and columns. For example, it is not allowed to output a flat array, or a string with all numbers separated by spaces.

Code golf. Shortest wins.

# Answer
> 7 votes
# Jelly, 15 bytes

```
“¡6ṡƘ[²Ḳi<’ḃ⁴s4

```

**TryItOnline!**

Pretty boring, sorry:

Prep: Took the square, read it by rows, converted from bijective base 16, convert that to base 250, looked up the code page indexes for those "digits" (`¡6ṡƘ[²Ḳi<`).

Jelly then reads the indexes to make a base 250 number, converts to bijective base 16 (`ḃ⁴`) and splits into chunks of size 4 (`s4`).

---

If we are allowed to output a different orientation, upside-down is possible in **14**:

```
“#⁷ƙ¤ṆWȷỤ’ḃ⁴s4

```

Test

---

In theory, given enough memory for `16!` integers the following would give us the correct orientation in **14**:

```
⁴Œ!“ŒCġŀḌ;’ịs4

```

This would create all permutations of \[1,16\] with `⁴Œ!` and pick the value at index 19800593106060 (1-based) with  using the base 250 representation `ŒCġŀḌ;` and split it into chunks of length 4 with `s4`.

---

Since then I have added four new atoms (`Œ?`, `Œ¿`, `œ?`, and `œ¿`) to Jelly to address such situations.
The monad `Œ?` takes an integer (or iterable of integers) and returns the shortest possible permutation of running natural numbers which would have the given index (or indexes) in a list of lexicographically sorted list of all permutations of those numbers.
...and it does so without creating any permutation lists.
As such the following would now work for **12** (obviously non-competing):

```
“ŒCġŀḌ;’Œ?s4

```

Give It A Go!

# Answer
> 8 votes
## Pyth, 18 bytes

```
c4.PC"H#ût"_S16

```

Run the code.

```
c4.PC"H#ût"_S16

    C"H#ût"       Convert the packed string to the number 1122196781940
  .P       _S16   Take that-numbered permutation of the reversed range [16,15,...,1]
c4                Chop into piece of length 4

```

Reversing the range was meant to lower the permutation index, since the output starts with 16, but I think it only broke even.

This beat out a more boring strategy of converting the table directly to base 17 and then a string (link) for 20 bytes:

```
c4jC"úz(ás¸H"17

```

# Answer
> 8 votes
# Jelly, ~~16~~ 15 bytes

```
4Œ!.ịm0µZḂÞ’×4+

```

Try it online!

### Background

If we subtract **1** from the numbers in the square and divide them by **4** (computing quotient and remainder), a pattern becomes apparent.

```
quotients and remainders    quotients    remainders

   3 3  0 2  0 1  3 0        3 0 0 3      3 2 1 0
   1 0  2 1  2 2  1 3        1 2 2 1      0 1 2 3
   2 0  1 1  1 2  2 3        2 1 1 2      0 1 2 3
   0 3  3 2  3 1  0 0        0 3 3 0      3 2 1 0

```

The remainder matrix follows an obvious pattern and is easy to generate. The quotient matrix can be obtained by transposing the remainder matrix and swapping the middle rows.

### How it works

```
4Œ!.ịm0µZḂÞ’×4+  Main link. No arguments.

4Œ!              Compute the array of all permutations of [1, 2, 3, 4], in
                 lexicographical order.
   .ị            Take the permutations at the indices adjacent to 0.5, i.e., the
                 ones at indices 0 ([4, 3, 2, 1]) and 1 ([1, 2, 3, 4]).
     m0          Concatenate the resulting [[4, 3, 2, 1], [1, 2, 3, 4]] with a
                 reversed copy, yielding the matrix
                 M := [[4, 3, 2, 1], [1, 2, 3, 4], [1, 2, 3, 4], [4, 3, 2, 1]].
       µ         Begin a new, monadic chain. Argument: M
        Z        Zip/transpose M, yielding the matrix
                 [[4, 1, 1, 4], [3, 2, 2, 3], [2, 3, 3, 2], [1, 4, 4, 1]].
         ḂÞ      Sort the rows by the lexicographical order of their parities,
                 yielding [[4, 1, 1, 4], [2, 3, 3, 2], [3, 2, 2, 3], [1, 4, 4, 1]].
           ’     Subtract 1 to yield the matrix of quotients, i.e.,
                 [[3, 0, 0, 3], [1, 2, 2, 1], [2, 1, 1, 2], [0, 3, 3, 0]].
            ×4+  Multiply the quotient by 4 and add the result to M (remainders).

```

# Answer
> 5 votes
# J, ~~37~~ 27 bytes

*Saved 10 bytes thanks to miles!*

```
4 4$1+19800593106059 A.i.16

```

Now with less boring! This takes the `19800593106059` permutation of the list `i.16`, which is `15 2 1 12 4 9 10 7 8 5 6 11 3 14 13 0`. Then, that is incremented, then is shaped into a `4` by `4` list.

Alternate version, with no whitespace:

```
_4]\1+19800593106059&A.i.16

```

Output, for posterity:

```
   _4]\1+19800593106059&A.i.16
16  3  2 13
 5 10 11  8
 9  6  7 12
 4 15 14  1
   4 4$1+19800593106059 A.i.16
16  3  2 13
 5 10 11  8
 9  6  7 12
 4 15 14  1

```

# Answer
> 5 votes
# Ruby, 49 bytes (shorter than the naive solution!)

It took quite a few attempts to write a snippet for this challenge in a mainstream language that was shorter than what it evaluated to! Per usual rules I've made a program out of it by adding a `p`  to output it.

```
p [15,4,8,3].map{|i|[1+i,1+i^=13,1+i^=3,1+i^=13]}

```

It outputs (the string representation of) an array of arrays. It's longer than wat's Ruby solution that outputs a differently-formatted string, but one byte shorter than the naive program below that simply returns the literal array.

```
p [[16,3,2,13],[5,10,11,8],[9,6,7,12],[4,15,14,1]] #naive solution, 50 bytes
p [15,4,8,3].map{|i|[1+i,1+i^=13,1+i^=3,1+i^=13]}  #submission, 49 bytes

```

**Explanation: start with numbers 0..15 (38 bytes!)**

This is where I started and it´s much easier. If we convert the 0..15 square into binary, we note that each cell contains the value at the bottom of its column XORed with the value at the right hand side of its row:

```
15 2  1  12            1111 0010 0001 1100
4  9  10 7             0100 1001 1010 0111
8  5  6  11            1000 0101 0110 1011
3  14 13 0             0011 1110 1101 0000

```

From this we derive the code below. But by using the first column instead of the last column, we save one byte, as shown.

```
p [12,7,11,0].map{|i|[i^3,i^14,i^13,i]}            #0..15 square, 39 bytes
p [15,4,8,3].map{|i|[i,i^13,i^14,i^3]}             #0..15 square, 38 bytes

```

The required 1..16 version was more difficult. In the end I realised the way to do it was to add 1 to each cell of the 0..15 square. But as `^` has lower priority than `+` I needed a lot of parentheses, which ate bytes. Finally I hit on the idea of using `^=`. The new value of `i` is calculated by augmented assignment `^=` before the 1 is added to it, so the calculation is done in the correct order.

# Answer
> 4 votes
# 05AB1E, ~~18~~ 17 bytes

Thanks to *Emigna* for saving a byte!

```
•3øÑ¼ž·Üý;•hSH>4ô

```

Uses the **CP-1252** encoding. Try it online!

# Answer
> 3 votes
# JavaScript (ES6), 43 bytes

```
_=>`16,3,2,13
5,10,11,8
9,6,7,12
4,15,14,1`

```

Separated by newlines, then commas. I doubt there's any shorter way...

# Answer
> 2 votes
# sed 39 bytes

```
c16,3,2,13|5,10,11,8|9,6,7,12|4,15,14,1

```

Try it Online!

It can't get much simpler than this. And, unfortunately, I don't think it can get any shorter either.

# Answer
> 2 votes
# Jelly, 20 bytes

```
“Ñ¤£Æ¦½¿®µ©¬€¥ÐÇ¢‘s4

```

**Try it online!**

This simply looks up the Jelly code point of each character, then slices into subarrays of length 4 with `s4`.

# Answer
> 2 votes
# Javascript ES6, ~~66~~ ~~65~~ 55 bytes

Yes, it isn't the shortest one. And yes, it can be reduced.

```
_=>`f21c
49a7
856b
3ed0`.replace(/./g,_=>'0x'+_-~0+' ')

```

For now, it isn't perfect. But is something!

---

Thanks to @Neil's suggestion that could save 5-8 bytes, and that inspired @ETHproductions suggestion that saves 10 bytes!

This makes the answer only 12 bytes longer than his 43 bytes solution.

# Answer
> 2 votes
# DASH, 24 bytes

```
<|>4tc"................"

```

Replace the periods with the characters of charcodes 16, 3, 2, 13, 5, 10, 11, 8, 9, 6, 7, 12, 4, 15, 14, and 1 respectively.

# Explanation

Simply converts the characters to an array of charcodes and chunks by 4.

# Answer
> 2 votes
# Actually, 22 bytes

```
4"►♥☻♪♣◙♂◘○♠•♀♦☼♫☺"♂┘╪

```

Try it online!

Explanation:

```
4"►♥☻♪♣◙♂◘○♠•♀♦☼♫☺"♂┘╪
 "►♥☻♪♣◙♂◘○♠•♀♦☼♫☺"     push a string containing the numbers in the magic square, encoded as CP437 characters
                   ♂┘   convert to ordinals
4                    ╪  chunk into length-4 slices

```

# Answer
> 2 votes
# Groovy, 57 bytes / 46 bytes

```
"F21C49A7856B3ED0".collect{Eval.me("0x$it")+1}.collate(4)

```

Parse each as hexidecimal digit and add 1, collate by 4 into a 2D array.

```
[[16, 3, 2, 13], [5, 10, 11, 8], [9, 6, 7, 12], [4, 15, 14, 1]]

```

Shorter, but also lamer:

```
print '16,3,2,13|5,10,11,8|9,6,7,12|4,15,14,1'

```

# Answer
> 1 votes
## PowerShell v2+, 40 bytes

```
'16,3,2,13
5,10,11,8
9,6,7,12
4,15,14,1'

```

A literal multiline string, left on the pipeline. Output via implicit `Write-Output` happens at program completion. Nice and boring.

---

Constructed version, 77 bytes

```
'f21c59a7856b3dc0'-split'(....)'-ne''|%{([char[]]$_|%{"0x$_+1"|iex})-join','}

```

Takes the string, `-split`s it every four elements, loops on them, changes each to a hex `0x$_` and adds `1`, pipes that to `iex` (short for `Invoke-Expression` and similar to `eval`), then `-join`s the result into a string with `,` as the separator. Outputs four strings onto the pipeline, with implicit printing.

# Answer
> 1 votes
## Ruby, 60 bytes - first attempt

```
%w(f21c 49a7 856b 3ed0).map{|i|i.chars.map{|i|i.to_i(16)+1}}

```

## Ruby, 45 bytes - cheap

```
puts '16,3,2,13|5,10,11,8|9,6,7,12|4,15,14,1'

```

# Answer
> 1 votes
# Pyth - 17 bytes

Base conversion. This unfortunately beats @xnor's approach

```
c4jC"úz(ás¸H"17

```

Try it online here.

# Answer
> 1 votes
## Matlab, ~~38~~ 35 bytes

Anonymous function:

```
@()['pcbm';'ejkh';'ifgl';'dnoa']-96

```

Direct printing (38 bytes):

```
disp(['pcbm';'ejkh';'ifgl';'dnoa']-96)

```

In Matlab best way to produce an array of integers is though a string.

# Answer
> 1 votes
# 05AB1E, 15 bytes

```
16Lœ•iPNÍš¯•è4ä

```

**Explanation**

```
16L              # range [1 ... 16]
   œ             # compute all permutations of the range
    •iPNÍš¯•è    # take the permutation at index 19800593106059
             4ä  # split the permutation into 4 parts

```

The index of the permutation was found using the formula:

`a*15! + b*14! + c*13!+ ... + o*1! + p*0!`

Where the variables are replaced with the number of succeeding elements which are smaller than the number at the current index for each number in the target list
`[16, 3, 2, 13, 5, 10, 11, 8, 9, 6, 7, 12, 4, 15, 14, 1]`

which for our sought after permutation is
`a=15, b=2, c=1, d=10, e=2, f=6, g=6, h=4, i=4, j=2, k=2, l=2, m=1, n=2 o=1, p=0`

This gives us the formula: `15*15!+2*14!+1*13!+10*12!+2*11!+6*10!+6*9!+4*8!+4*7!+2*6!+2*5!+2*4!+1*3!+2*2!+1*1!+0*0!`

which is equal to `19800593106059`.

# Answer
> 1 votes
# Scala, 52 bytes

```
()=>Seq(15,4,8,3)map(x=>Seq(x,x^13,x^14,x^3)map(1+))

```

Ungolfed:

```
()=>
  Seq(15, 4, 8, 3)
  .map(x=>
    Seq(x, x^13, x^14, x^3)
    .map(1+)
  )

```

Inspired by Level River St's ruby answer.

# Answer
> 1 votes
# Python 3, ~~51~~ 47 bytes

```
print("16,3,2,13|5,10,11,8|9,6,7,12|4,15,14,1")

```

Try it online!

Some solutions @xnor mentioned in the comments.

# Python 3, 54 bytes (construction)

```
for a in 12,7,11,0:print([(a^b)+1for b in[3,14,13,0]])

```

Try it online!

# Python 3, ~~43~~ 41 bytes (0 to 15)

```
for a in 12,7,11,0:print(a^3,a^14,a^13,a)

```

Try it online!

-2 thx to @Steffan

---
Tags: code-golf, kolmogorov-complexity, arithmetic, integer
---


title: Codegolf the Hafnian

text:
# Question
Title: Codegolf the Hafnian
The challenge is to write codegolf for the Hafnian of a matrix. The Hafnian of an \\$2n \times 2n\\$ symmetric matrix \\$A\\$ is defined as:

$$\operatorname{haf}(A) = \frac 1 {n!2^n} \sum\_{\sigma \in S\_{2n}} \prod^n\_{j=1} A\_{\sigma(2j-1),\sigma(2j)}$$

Here \\$S\_{2n}\\$ represents the set of all permutations of the integers from \\$1\\$ to \\$2n\\$, that is \\$\[1, 2n\]\\$.

The Wikipedia link talks about adjacency matrices but your code should work for any real valued symmetric input matrices.

For those interested in applications of the Hafnian, the mathoverflow link discusses some more.

Your code can take input however it wishes and give output in any sensible format but please include in your answer a full worked example including clear instructions for how to supply input to your code.

The input matrix is always square and will be at most 16 by 16. There is no need to be able to handle the empty matrix or matrices of odd dimension.

## Reference implementation

Here is some example python code from Mr. Xcoder.

```
from itertools import permutations
from math import factorial

def hafnian(matrix):
    my_sum = 0
    n = len(matrix) // 2
    for sigma in permutations(range(n*2)):
        prod = 1
        for j in range(n):
            prod *= matrix[sigma[2*j]][sigma[2*j+1]]
        my_sum += prod
    return my_sum / (factorial(n) * 2 ** n)

print(hafnian([[0, 4.5], [4.5, 0]]))
4.5
print(hafnian([[0, 4.7, 4.6, 4.5], [4.7, 0, 2.1, 0.4], [4.6, 2.1, 0, 1.2], [4.5, 0.4, 1.2, 0]])
16.93
print(hafnian([[1.3, 4.1, 1.2, 0.0, 0.9, 4.4], [4.1, 4.2, 2.7, 1.2, 0.4, 1.7], [1.2, 2.7, 4.9, 4.7, 4.0, 3.7], [0.0, 1.2, 4.7, 2.2, 3.3, 1.8], [0.9, 0.4, 4.0, 3.3, 0.5, 4.4], [4.4, 1.7, 3.7, 1.8, 4.4, 3.2]])
262.458

```

---

The wiki page has now (March 2 2018) been updated by ShreevatsaR to include a different way of calculating the Hafnian. It would be very interesting to see this golfed.

# Answer
> 9 votes
# , ~~150~~ ~~142~~ ~~127~~ 119 bytes

```
function(A,N=nrow(A),k=1:(N/2)*2)sum(apply(gtools::permutations(N,N),1,function(r)prod(A[cbind(r[k-1],r[k])])))/prod(k)

```

Try it online!

Uses the same trick I discovered golfing down this answer to index the matrix `P`, and @Vlo suggested an approach to entirely remove the `for` loop for -6 bytes!

To create a new test case, you can do `matrix(c(values,separated,by,commas,going,across,rows),nrow=2n,ncol=2n,byrow=T)`.

Explanation: (the code is the same; it uses an `apply` rather than a `for` loop but the logic is otherwise identical).

```
function(A){
N <- nrow(A)                   #N = 2*n
k <- 1:(N/2) * 2               #k = c(2,4,...,N) -- aka 2*j in the formula
P <- gtools::permutations(N,N) #all N-length permutations of 1:N
for(i in 1:nrow(P))
 F <- F + prod(A[cbind(P[i,k-1],P[i,k])]) # takes the product of all A_sigma(2j-1)sigma(2j) for fixed i and adds it to F (initialized to 0)
F / prod(k)                    #return value; prod(k) == n! * 2^n
}

```

# Answer
> 8 votes
# Pyth, 24 bytes

```
sm*Fmc@@Qhkek2d{mScd2.pU

```

**Try it here!**

---

### Old version, 35 bytes

```
*c1**FK/lQ2^2Ksm*Fm@@Q@dtyk@dykK.pU

```

Try it here!

# Answer
> 7 votes
# Stax, 23 22 19 17 bytes

```
ü;Y╙◘▌Φq↓ê²╧▐å↑┌C

```

Run and debug it online

The corresponding ascii representation of the same program is this.

```
%r|TF2/{xsE@i^H/m:*+

```

The program suffers from some floating point rounding error. In particular, it reports `33673.5000000011` instead of `33673.5`. But I think the accuracy is acceptable given that this program operates on floating point values. It's also very slow, taking almost a minute for the example inputs on this machine.

```
%                             get size of matrix
 r|T                          get all permutations of [0 ... size-1]
    F                         for each, execute the rest of the program
     2/                       get consecutive pairs
       {        m             map each pair...
        xsE@                      the matrix element at that location
            i^H/                  divided by 2*(i+1) where i=iteration index
                 :*           product of array
                   +          add to running total

```

# Answer
> 6 votes
# 05AB1E, 21 bytes

```
ā<œε2ô{}Ùεε`Isèsè;]PO

```

Try it online!

---

### Old version, 32 bytes

```
āœvIg;©Lε·UIyX<èèyXèè}P}Oθ®!/®o/

```

Try it online!

**How it works?**

```
āœvIg;©Lε·UIyX<èèyXèè}P}Oθ®!/®o/ – Full program. Argument: A matrix M.
ā                                – The range [1 ... len(M)].
 œ                               – Permutations.
  v                    }         – Iterate over the above with a variable y.
   Ig;©                          – Push len(M) / 2 and also store it in register c.
       Lε            }           – For each integer in the range [1 ... ^]:
         ·U                      – Double it and store it in a variable X.
            yX<                  – Push the element of y at index X-1.
           I   è                 – And index with the result into M.
                yXè              – Push the element of y at index X.
                   è             – And index with the result into ^^.
                      P          – Take the product of the resulting list.
                        O        – Sum the result of the mapping.
                         θ       – And take the last element*.
                          ®!     – Take the factorial of the last item in register c.
                             ®o  – Raise 2 to the power of the last item in register c.
                            /  / – And divide the sum of the mapping accordingly.

* – Yeah, this is needed because I mess up the stack when pushing so many values in the loop and not popping correctly ;P

```

# Answer
> 6 votes
# , ~~84~~ 78 bytes

```
h=function(m)"if"(n<-nrow(m),{for(j in 2:n)F=F+m[1,j]*h(m[v<--c(1,j),v]);F},1)

```

Try it online!

Edit: Thanks to Vlo for -6 bytes.

It seems that everybody here is implementing the standard reference algorithm with permutations, but I tried to take advantage of the community knowledge gained in the related challenge, which is basically the same task targeted for fastest code instead of golf.

It turns out that for a language that is good at slicing matrices (like R), the recursive algorithm: `hafnian(m) = sum(m[i,j] * hafnian(m[-rows and columns at i,j])` is not only faster, but also quite golfy. Here is the ungolfed code:

```
hafnian<-function(m)
{
    n=nrow(m)
    #Exits one step earlier than golfed version
    if(n == 2) return(m[1,2])
    h = 0
    for(j in 2:n) {
        if(m[1,j] == 0) next
        h = h + m[1,j] * hafnian(m[c(-1,-j),c(-1,-j)])
    }
    h
}

```

# Answer
> 5 votes
# Jelly, 19 bytes

```
LŒ!s€2Ṣ€QḅL_LịFHP€S

```

Try it online!

### Alternate version, 15 bytes, postdates challenge

```
LŒ!s€2Ṣ€QœịHP€S

```

Jelly *finally* got n-dimensional array indexing.

Try it online!

### How it works

```
LŒ!s€2Ṣ€QœiHP€S  Main link. Argument: M (matrix / 2D array)

L                Take the length, yielding 2n.
 Œ!              Generate all permutations of [1, ..., 2n].
   s€2           Split each permutation into pairs.
      Ṣ€         Sort the pair arrays.
        Q        Unique; deduplicate the array of pair arrays.
                 This avoids dividing by n! at the end.
           H     Halve; yield M, with all of its elements divided by 2.
                 This avoids dividing by 2**n at the end.
         œị      At-index (n-dimensional); take each pair of indices [i, j] and
                 yield M[i][j].
            P€   Take the product the results corresponding the same permutation.
              S  Take the sum of the products.

```

The 19-byte version works in a similar fashion; it just has to implement `œị` itself.

```
...ḅL_LịFH...    Return value: Array of arrays of index pairs. Argument: M

    L            Length; yield 2n.
   ḅ             Convert each pair of indices [i, j] from base 2n to integer,
                 yielding ((2n)i + j).
     _L          Subtract 2n, yielding ((2n)(i - 1) + j).
                 This is necessary because indexing is 1-based in Jelly, so the
                 index pair [1, 1] must map to index 1.
        F        Yield M, flattened.
       ị         Take the indices to the left and get the element at these indices
                 from the array to the right.
         H       Halve; divide all retrieved elements by 2.

```

# Answer
> 3 votes
# C (gcc), ~~288~~ ~~285~~ ~~282~~ ~~293~~ ~~292~~ ~~272~~ ~~271~~ 263 bytes

* Saved three bytes by fiddling with two post-increments and for loop placement.
* Saved three bytes by fiddling with anothter post-increment, moving both variable initializations before the branch -- golfed `if(...)...k=0...else...,j=0...` to `if(k=j=0,...)...else...` -- and performed an index shift.
* Required eleven bytes by supporting `float` matrices.
* Saved a byte thanks to Mr. Xcoder; golfing `2*j+++1` to `j-~j++`.
* Saved twenty bytes by removing a superfluous `int` variable type declaration and not using a factorial function but instead calculating the factorial value by using an already existing for loop.
* Saved a byte by golfing `S=S/F/(1<<n);` to `S/=F*(1<<n);`.
* Saved eight bytes thanks to ceilingcat.

```
float S,p,F;j,i;s(A,n,P,l,o,k)float*A;int*P;{if(o-l)for(k=0;k<l;s(A,n,P,l,o+1))P[o]=k++;else{for(p=j=l;j--;)for(i=l;i--;)p-=P[j]==P[i];if(!p){for(F=p=1,j=0;j<n;F*=j)p*=A[P[2*j]*2*n+P[j+++j]];S+=p;}}}float h(A,n)float*A;{int P[j=2*n];S=0;s(A,n,P,j,0);S/=F*(1<<n);}

```

Try it online!

# Explanation (271 bytes version)

```
float S,p,F;                    // global float variables: total sum, temporary, factorial
j,i;                            // global integer variables: indices
s(A,n,P,l,o,k)float*A;int*P;{   // recursively look at every permutation in S_n
 if(k=j=0,o-l)                  // initialize k and j, check if o != l (possible  permutation not yet fully generated)
  for(;k<l;s(A,n,P,l,o+1))      // loop through possible values for current possible  permuation position
   P[o]=k++;                    // set possible  permutation, recursively call (golfed into the for loop)
 else{for(p=-l;j<l;j++)         // there exists a possible permutation fully generated
  for(i=0;i<l;)                 // test if the possible permutation is a bijection
   p+=P[j]==P[i++];             // check for unique elements
  if(!p){                       // indeed, it is a permutation
   for(F=p=1,j=0;j<n;F*=j)      // Hafnian product loop and calculate the factorial (over and over to save bytes)
    p*=A[P[2*j]*2*n+P[j-~j++]]; // Hafnian product
   S+=p;}}}                     // add to sum
float h(A,n)float*A;{           // Hafnian function
 int P[j=2*n];S=0;              // allocate permutation memory, initialize sum
 s(A,n,P,j,0);                  // calculate Hafnian sum
 S/=F*(1<<n);}                  // calculate Hafnian

```

Try it online!

At the program's core is the following permutation generator which loops through `S_n`. All Hafnian computation is simply build upon it -- and further golfed.

```
j,i,p;Sn(A,l,o,k)int*A;{          // compute every element in S_n
 if(o-l)                          // o!=l, the permutation has not fully been generated
  for(k=0;k<l;k++)                // loop through the integers [0, n)
   A[o]=k,Sn(A,l,o+1);            // modify permutation, call recursively
 else{                            // possible permutation has been generated
  for(p=-l,j=0;j<l;j++)           // look at the entire possible permutation
   for(i=0;i<l;i++)p+=A[j]==A[i]; // check that all elements appear uniquely
  if(!p)                          // no duplicat elements, it is indeed a permutation
   for(printf("["),j=0;j<l        // print
   ||printf("]\n")*0;)            //  the
    printf("%d, ",A[j++]);}}      //   permutation
main(){int l=4,A[l];Sn(A,l,0);}   // all permutations in S_4

```

Try it online!

# Answer
> 2 votes
# Haskell, 136 bytes

*-14 bytes thanks to ovs.*

```
import Data.List
f m|n<-length m`div`2=sum[product[m!!(s!!(2*j-2)-1)!!(s!!(2*j-1)-1)/realToFrac(2*j)|j<-[1..n]]|s<-permutations[1..n*2]]

```

Try it online!

Ugh...

# Answer
> 2 votes
# Jelly, 29 bytes

```
LHµ2*×!
LŒ!s€2;@€€Wị@/€€P€S÷Ç

```

Try it online!

I think the `;@€€Wị@/€€P€` part can likely be golfed down. Need to come back later to check and add an explanation.

# Answer
> 2 votes
# MATL, ~~29~~ ~~24~~ 22 bytes

```
Zy:Y@!"G@2eZ{)tn:E/pvs

```

Try it online! Or verify all test cases: , , .

### How it works

```
Zy       % Size of (implicit) input: pushes [2*n 2*n], where the
         % input is a 2*n × 2*n matrix.
:        % Range: gives row vector [1 2 ... 2*n]
Y@       % All permutation of that vector as rows of a matrix
!"       % For each permutation
  G      %   Push input matrix
  @      %   Push current permutation
  2e     %   Reshape as a 2-row array
  Z{     %   Split rows into a cell array of size 2
  )      %   Reference indexing. With a cell array as index this
         %   applies element-wise indexing (similar to sub2ind).
         %   Gives a row vector with the n matrix entries selected
         %   by the current permutation
  t      %   Duplicate
  n:     %   Number of elements, range: this gives [1 2 ... n]
  E      %   Double, element-wise: gives [2 4 ... 2*n]
  /      %   Divide, element-wise
  p      %   Product
  vs     %   Vertically concatenate and sum
         % End (implicit). Display (implicit)

```

# Answer
> 2 votes
# JavaScript (Node.js), ~~121~~ ~~119~~ ~~117~~ ~~115~~ 101 bytes

```
A=>(F=(a,t,r)=>{a--?A[t].map((x,i)=>F[i]=F[i]||F(F[i]=a,i,a%2?r:r*x/(a+2))):s+=r})(A.length,s=0,1)||s

```

Try it online!

## Explanation & Ungolfed

```
function hafnian(A) {            // Main function taking an array
 return (
  F = function(                  //  Helper function, and also a temporary storage
   a,                            //   how many numbers left
   t,                            //   previous number
   r                             //   the product
  ) {                            //   The braces are to avoid returning value
   a-- ?                         //   If a > 0:
    A[t].map((x, i) =>           //    Loop from i = 2n - 1 downto 0:
     F[i] = F[i] || F(           //     Skip if F[i] is truthy, i.e. i used in the permutation
      F[i] = a,                  //     Otherwise: Set F[i] to truthy* & start a new recursion
      i,                         //      with i as the previous number
      a % 2                      //      If a - 1 is odd:
       ? r                       //       r does not change
       : r * x / (a + 2)         //      Otherwise: multiply A[t][i] to r, divide by a + 1
     )                           //      Set back F[i] to undefined after the recursion
    )
   : s += r;                     //   Otherwise: add r to s. The factor 1/(n!*2^n) = 1/(2n)!!
  }                              //   has been included in the recursion
 )(
  A.length,                      //  2n = size of the array
  s = 0,                         //  Initial sum s = 0
  1                              //  Initial product r = 1
 ) || s;                         //  Return s
}

/* Note that when a = 1 F[i] will be falsy, but the next recursion will just
   skip this part anyway. */

```

# Answer
> 1 votes
# Coconut, ~~165~~ ~~145~~ ~~128~~ 127 bytes

-1 byte thanks to Mr. Xcoder

```
m->sum(reduce((o,j)->o*m[p[2*j]][p[j-~j]]/-~j/2,range(len(m)//2),1)for p in permutations(range(len(m))))
from itertools import*

```

Try it online!

# Answer
> 1 votes
# Wolfram Language (Mathematica), 84 bytes

```
aTr[1##&@@(a[[##]]&@@@#~Partition~2)&/@Permutations@Range[n=Tr[1^a]]]/(n/=2)!/2^n

```

Try it online!

---

# Wolfram Language (Mathematica), 68 bytes

```
If[#=={},1,Sum[d=Rest@*Delete[i];#[[1,i]]#0@d[d/@#],{i,2,Tr[1^#]}]]&

```

Try it online!

# Answer
> 1 votes
## Perl 6, 86 bytes

```
{my \n=$^m/2;^$m .permutations.map({[*] .map(->\a,\b{$m[a][b]})}).sum/(2**n*[*] 1..n)}

```

# Answer
> 1 votes
# JavaScript (Node.js), ~~87~~ 86 bytes

```
f=A=>A[0]?A[0].reduce((y,x,i)=>i&&y+x*f((g=B=>B.filter((_,j)=>j&&i-j))(A).map(g)),0):1

```

Try it online!

This is a port of Kirill's algorithm, and this turns out to be shorter than the naive approach! However I'm retaining my original answer and posting this as a separate one.

### Explanation

```
f = A =>                               // A function receiving an array as input
 A[0]                                  //  If A is not empty:
  ? A[0].reduce((y, x, i) =>           //   Calculate the sum
   i                                   //   for i = 1 to 2n - 1:
   && y + x * f(                       //    A[0][i] * the hafnian of
    (g = B =>
     B.filter((_, j) => j && i - j)    //    array A removing rows 0 and i
    )(A).map(g)                        //    as well as columns 0 and i
   ),
   0
  )
  : 1                                  //  If A is empty: return 1

```

# Answer
> 1 votes
# Pari/GP, 51 bytes

```
h(m)=if(#m,sum(n=2,#m,m[1,n]*h(m[^n,^n][^1,^1])),1)

```

Try it online!

# Answer
> 1 votes
# Python 3.8 (pre-release), ~~185~~ 181 bytes

```
def f(m):
 a=0;n=len(m)//2
 for x in itertools.permutations(range(n*2)):p=1;[p:=p*m[x[2*j]][x[2*j+1]]for j in range(n)];a+=p
 return a/(math.factorial(n)*2**n)
import math,itertools

```

Try it online!

Golfed reference implementation provided in the question.

---
Tags: code-golf, math, permutations, matrix, linear-algebra
---


title: Prime generating function

text:
# Question
Title: Prime generating function
# Background

The Python code

```
((((((((n%35)^11)*195)|53)&181)+n)%168)*n)+83

```

produces 74 distinct primes for \\$0 \le n \le 73\\$. This code also works in Java. The operators are as follows:

* `+` is addition
* `*` is multiplication
* `%` is modulus
* `&` is bitwise AND
* `|` is bitwise OR
* `^` is bitwise XOR

The produced primes are: `83, 97, 113, 251, 311, 173, 197, 503, 571, 281, 313, 787, 863, 421, 461, 1103, 547, 593, 1361, 1451, 743, 797, 1733, 1831, 1931, 1033, 1097, 2243, 1231, 1301, 1373, 2687, 1523, 1601, 3041, 3163, 1847, 1933, 3541, 3671, 2203, 2297, 4073, 4211, 2591, 2693, 4637, 4783, 3011, 3121, 5233, 3347, 3463, 5701, 5861, 3823, 3947, 6353, 6521, 6691, 4463, 4597, 7213, 4871, 5011, 5153, 7937, 5443, 5591, 8501, 8693, 6047, 6203, 9281`.

# Task

Given an input integer \\$n\\$ output one of the primes from the above list, such that every output is distinct.

# Rules

* \\$n\\$ will be between 0 and 73, inclusive.
* You can receive input through any of the standard IO methods.
* Leading zeroes are not allowed in output.
* This is , so shortest code in bytes wins!

# Answer
# x86 Machine Code, 23 bytes

```
86 89 C8 D4 23 34 0B 6B C0 C3 0C 35 24 B5 00 C8 D4 A8 F6 E1 83 C0 53 C3

```

**Try it online!**

The above bytes of code define a function that returns the \\$n\\$th prime, according to the formula given in the challenge. The function accepts a single argument, \\$n\\$, which is passed in the `ECX` register. It returns the result in the `AX` register. (Note: A 16-bit value is returned—the caller is responsible for zero-extending that 16-bit value in `AX` to a 32-bit value in `EAX`, if desired. Add one byte for a `CWDE` instruction if you think that is cheating!)

This is a custom calling convention, but it isn't particularly "weird", and machine/assembly language submissions are allowed to define a custom calling convention.

Credit where credit is due: this code is based on EasyasPi's x86 submission, but carefully optimized for size. In particular, I've chosen to target 32-bit x86 so that I can use the long-obsolete `AAM` instruction, which is not supported in x86-64 "long" mode. `AAM` was designed into the architecture as a way to convert from binary to binary-coded decimal (BCD). To do this, it divides the `AL` register by 10, storing the quotient in `AH` and the remainder in `AL`. (Note that this is the *reverse* of what the `DIV` instruction produces!) Intel's original manuals documented `AAM` as a one-byte instruction, but it was actually encoded with two bytes, where the second byte was 10—the divisor for `AL`. Changing that second byte to another value allows dividing `AL` by an arbitrary value, essentially giving x86 an instruction to divide by an 8-bit intermediate. This trick is used twice, to great effect. (There is also a complementary `AAD` instruction, which allows multiplying by an arbitrary 8-bit immediate value, but that did not result in any savings, since it actually performs the multiplication on `AH`, instead of `AL`, and the shift that is required to support that requires 2 bytes, plus the 2 bytes for `AAD`, which is more than the 3 bytes required to encode the `IMUL reg, reg, imm`.) There are myriad other size optimizations as well, compared to EasyasPi's code.

Here are the ungolfed assembly mnemonics:

```
            ; Input(s):
            ;   ecx = The zero-based index of the prime to generate (i.e., "n").
            ;         (Note: This is assumed to be a value from 0 to 73.)
            ; Output(s):
            ;   ax  = The nth prime.
            ;         (Note: This is a 16-bit unsigned integer;
            ;                caller must zero-extend if desired.)
            ; Clobbers:
            ;   eax, flags
            GenerateNthPrime:
89 C8         mov   eax, ecx       # make a copy of the input (ecx) in eax
D4 23         aam   35             # al %= 35        ; ah = al / 35
34 0B         xor   al, 11         # al ^= 11
6B C0 C3      imul  eax, eax, -61  # ax  = (al * 195)
0C 35         or    al, 53         # al |= 53
24 B5         and   al, 181        # al &= 181
00 C8         add   al, cl         # al += cl
D4 A8         aam   168            # al %= 168       ; ah = al / 168
F6 E1         mul   cl             # ax  = (al * cl)
83 C0 53      add   eax, 83        # ax += 83
98          # cwde                 # eax = ax (sign-extend, assuming sign bit is 0)
C3            ret

```

Note the `cwde` instruction immediately before the `ret`urn instruction there, which is commented out. For the purposes of this submission, this instruction is functionally equivalent to `movzx eax, ax`, which is what the caller of this function would normally use to zero-extend its 16-bit result (`ax`) to a 32-bit result (`eax`). However, `cwde` is encoded in only 1 byte, as opposed to the 3 bytes required by `movzx`. As I mentioned above, if you don't think it's legit that I return a 16-bit result, then add the `cwde` instruction to increase the total size of the function by only one byte.
> 10 votes

# Answer
# JavaScript (ES6),  ~~38~~  36 bytes

*Saved 2 bytes thanks to @tsh*

A slightly size-optimized version of the original formula.

```
n=>(((n%35^11)*6.09&4?13:53)+n)*n+83

```

Try it online!
> 7 votes

# Answer
# 05AB1E, ~~23~~ ~~22~~ 21 bytes

<sup>-1 byte thanks to Command Master</sup>

The first part of the code is shorter when replaced by a binary lookup table.

```
•4àт©Á•bsè40*13++*83+

```

Try it online!
> 6 votes

# Answer
# Retina 0.8.2, ~~168~~ 166 bytes

```
.+
$*1¶$&$*
\G1{35}

^((1{16})*)(1{8}|())(1{4})?(11|())(1|())
$1$#4$*8$*1$5$#7$*2$*1$#9$*
\G1
195$*
1{256}

(1{128})?1*¶
$1$'53$*1¶
1{168}

1(?=1*¶(1*))
$1
¶1*
83$*
1

```

Try it online! Link includes test suite that generates the results for `n=0..73`. Based on @Arnauld's rearrangement that reduces the bitwise or into an addition. Explanation:

```
.+
$*1¶$&$*

```

Make two unary copies of `n`.

```
\G1{35}

```

Reduce modulo 35.

```
^((1{16})*)(1{8}|())(1{4})?(11|())(1|())
$1$#4$*8$*1$5$#7$*2$*1$#9$*

```

Bitwise Xor with 11. This is done by breaking the number down into a multiple of 16 plus optional matches of 8, 4, 2 and 1, adding 8, 2, and 1 only when the corresponding match is absent in the original number.

```
\G1
195$*

```

Multiply by 195.

```
1{256}

(1{128})?1*¶
$1$'53$*1¶

```

Bitwise And with 128 (implemented via %256/128\*128) and add on 53 and `n`.

```
1{168}

```

Reduce modulo 168. (No `\G` is necessary as `n` is less than 168.)

```
1(?=1*¶(1*))
$1

```

Multiply by `n`.

```
¶1*
83$*

```

Add 83 and remove the copy of `n`.

```
1

```

Convert to decimal.
> 2 votes

# Answer
# , 40 bytes

```
83+]*168|]+181 AND 53 OR 195*11 XOR 35|]

```

Try it online!

Boring translation of formula. But nice demo of J's "evaluate right to left / read out loud left to right" property:

* 83 plus input times 168 divided into input plus 181 bitwised and with 53 bitwised or with 195 times 11 xor'd with 35 divided into input.
> 2 votes

# Answer
# C (gcc), 43 bytes

```
f(n){n=('v3ff'>>n%35%31&1?13+n:53+n)*n+83;}

```

Try it online!

Tio link based on noodle9's post.
> 2 votes

# Answer
# Charcoal, 38 bytes

```
ＮθＩ⁺⁸³×θ⁺θ⎇＆¹²⁸×¹⁹⁵⁻｜¹¹﹪θ℅#＆¹¹﹪θ℅#¹³℅5

```

Try it online! Link is to verbose version of code. Explanation: Basically a translation of the original expression, except for the following changes:

* Where possible, the arguments to operators were reversed, to avoid placing numeric constants consecutively
* Otherwise some numeric constants calculated using ASCII codes to avoid consecutive numeric constants
* No bitwise XOR, so calculated longhand
* @tsh's ternary idea on his comment to @Arnauld's answer turned out to be the shortest way to choose between 13 and 53.

```
Ｎθ                                      Input `n`
                       ﹪θ℅#   ﹪θ℅#      `n` modulo ASCII code 35 of literal `#`
                    ｜¹¹                 Bitwise Or with literal `11`
                           ＆¹¹          Bitwise And with literal `11`
                   ⁻                    Subtract, giving the bitwise Xor
               ×¹⁹⁵                     Multiply by literal `195`
           ＆¹²⁸                         Bitwise And with literal `128`
          ⎇                             If nonzero
                                  ¹³    Then literal `13`
                                    ℅5  Else ASCII code 53 of literal `5`
        ⁺θ                              Add `n`
      ×θ                                Multiply by `n`
   ⁺⁸³                                  Add literal `83`
  Ｉ                                     Cast to string
                                        Implicitly print

```
> 2 votes

# Answer
# x86\_64, 33 bytes

```
89 c1 b2 23 f6 f2 80 f4  0b b0 c3 f6 e4 0c 35 66
25 b5 00 01 c8 b2 a8 f6  f2 86 c4 f6 e1 83 c0 53
c3

```

```
        .intel_syntax noprefix
        # in: eax (zero extended)
        # out: eax
        .globl primegen
primegen:
        mov     ecx, eax
        mov     dl, 35
        div     dl
        xor     ah, 11
        mov     al, 195
        mul     ah
        or      al, 53
        and     ax, 181
        add     eax, ecx
        mov     dl, 168
        div     dl
        xchg    al, ah
        mul     cl
        add     eax, 83
        ret

```

Try it online!

Nothing special, it is pretty much a direct translation of the example code.
> 2 votes

# Answer
# MathGolf, 22 bytes

```
I6E6V057]yâ§Z⌠*C++*Zx+

```

Port of *@theDefault.*'s 05AB1E answer, so make sure to upvote him/her as well!

Try it online.

**Explanation:**

```
I                      # Push 20
 6                     # Push 6
  E                    # Push 15
   6                   # Push 6
    V                  # Push 34
     0                 # Push 0
      5                # Push 5
       7               # Push 7
        ]              # Wrap all values on the stack into a list
         y             # And join them together: 20615634057
          â            # Convert it from an integer to a binary-list:
                       #  [1,0,0,1,0,0,0,1,0,0,1,1,1,0,0,1,1,0,0,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1]
           §           # (0-based) index the (implicit) input-integer into this list
            Z⌠         # Push 38, and increment it by 2 to 40
              *        # Multiply the current value by this 40
               C+      # Add 13
                 +     # Add the (implicit) input-integer
                  *    # Multiply it by the (implicit) input-integer
                   Zx  # Push 38, and reverse it to 83
                     + # Add this 83 to the value
                       # (after which the entire stack joined together is output implicitly)

```

---

MathGolf doesn't contain any builtins for bitwise-AND, OR, nor XOR. But even if it did, this approach above would still be 2 bytes shorter than implementing the formula in the challenge description would have been:

**24 bytes:**

```
W%A^CE**Wx|G1§&+BD*%*Zx+

```

**Explanation:**

```
W%                       # Modulo the (implicit) input-integer by 35
  A^                     # Bitwise-XOR by 11
                         # (assuming `^` would have been a bitwise-XOR builtin)
    CE*                  # Push 13, push 15, multiply them together to 195
       *                 # Multiply the value by this 195
        Wx               # Push 35, reverse it to 53
          |              # Bitwise-OR by this 53
                         # (assuming `|` would have been a bitwise-OR builtin)
           G1§           # Push 18, push 1, concatenate them together to 181
              &          # Bitwise-AND by this 181
                         # (assuming `&` would have been a bitwise-AND builtin)
               +         # Add the (implicit) input-integer
                BD*      # Push 12, push 14, multiply them together to 168
                   %     # Modulo by this 168
                    *    # Multiply to the (implicit) input-integer
                     Zx  # Push 38, reverse it to 83
                       + # Add this 83 to the value
                         # (after which the entire stack joined together is output implicitly)

```
> 2 votes

# Answer
# Julia 1.0, 39 bytes

```
!n=(n+(195(n%35⊻11)|53)&181%168)*n+83

```

Try it online!
> 2 votes

# Answer
# Jelly, ~~26~~ 25 bytes

```
%35^11×195&Ø⁷+53+%168×+83

```

Try it online!

-1 thanks to the default.
> 1 votes

# Answer
# FALSE, 57 bytes

```
[[$2ø\/*-]m:$$35m;!11$2ø~&@@~&|195*53|181&+168m;!*83+.]

```

Try it online!

Function that takes a number as input.

## Explanation:

```
[$2ø\/*-]m: {Define modulo function as m (a - (n * trunc(a/n)))}
    $2ø {Duplicate both a and n to have the stack be a, n, n, a}
    \/ {swap n and a and divide, which auto-truncates}
    *- {then multiply by n and subtract a by everything}
$$35m;!11$2ø~&@@~&|195*53|181&+168m;!*83+. {Prime generation}
    $$ {duplicate n twice because we need to add and multiply by n later on}
    35m;! {n % 35}
    11$2ø~&@@~&| { ^ 11 (xor has be done as (not a and b) or (a and not b) as there is no built-in in FALSE)}
        $2ø {get stack to be a, b, b, a}
        ~&@@ {do b and not a, and rotate twice, stack is now result, a, b}
        ~&| {then do a and not b and or the results together to finish the xor}
    195* { * 195}
    53| { | 53}
    181& { & 181}
    + { + n}
    168m;! { % 168}
    * { * n}
    83+ { + 83}
    . {output resulting prime}

```
> 1 votes

# Answer
# Pyth, 30 bytes

```
+83*%+.&181.|*195x%Q35hT53Q168

```

Try it online!
> 1 votes

# Answer
# Python 3, ~~48~~ 46 bytes

```
lambda n:(n+(((n%35^11)*195|53)&181)%168)*n+83

```

Try it online!
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 38 bytes

```
n=>(((n%35^11)*195)&181|53+n)%168*n+83

```

I just removed all the paracenteses I could.

Try it online!
> 0 votes

# Answer
# C (gcc), ~~48~~ 46 bytes

Saved 2 bytes thanks to Neil!!!

```
f(n){n=((((n%35^11)*195&128)+53+n)%168*n)+83;}

```

Try it online!

Simple port.
> 0 votes

# Answer
# Perl 5 -`p`, 43 bytes

```
$_=(((($_%35^11)*195|53)&181)+$_)%168*$_+83

```

Try it online!
> 0 votes

---
Tags: code-golf, primes
---


# Question
Title: find the pattern in this number sequence of 1's and 0's
Write the shortest program or function which generates these 1000 numbers or a sequence (0- or 1-indexed) which begins with them.

```
[0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0,
 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1,
 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0,
 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1,
 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0,
 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1,
 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0,
 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1,
 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0,
 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1,
 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0,
 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1,
 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0,
 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1,
 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1,
 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0,
 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1,
 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0,
 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1,
 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0,
 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1,
 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0,
 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1,
 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0,
 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1,
 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0,
 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1,
 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0,
 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1,
 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0,
 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1,
 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0,
 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1,
 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0,
 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1,
 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0,
 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1,
 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0,
 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1,
 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0,
 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1,
 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]

```

# Answer
> 19 votes
# Jelly, ~~11~~ 10 bytes

*Saved 1 byte thanks to @Dennis*

```
ȷḶ×⁽q£:ȷ5Ḃ

```

Try it online!

### How?

I first noticed that the pattern alternates between runs of length 4 and length 3, skipping the length-4 step every few runs. This led me to look for a number which could be divided into the current index, then taken mod 2 and floored—i.e. retrieving the least significant bit—to give the bit at that index in the series. After much trial and error, I found that `3.41845` does exactly that, but multiplying by its approximate reciprocal (`.29253`) is a byte shorter.

```
ȷḶ×⁽q£:ȷ5Ḃ    Main link. Arguments: none
ȷ             Yield 1e3, i.e. 1000.
 Ḷ            Lowered range; yield [0, 1, 2, ..., 999].
  ×⁽q£        Multiply each item by 29253.
      :ȷ5     Floor-divide each item by 1e5, i.e. 100000.
         Ḃ    Take each item mod 2.

```

# Answer
> 6 votes
# Ruby, ~~34 29 26~~ 22 bytes

```
$.+=184while p$./629%2

```

Try it online!

Quick explanation: this works because of the magic number 629. I noticed that the sequence starts repeating after the 629th element, and I tried to "improve" some existing answer, using only integer math. I found that the other "magic number" (0.29253) is actually 184/629.

# Answer
> 3 votes
# Dyalog APL, ~~99~~ ~~83~~ 82 bytes

```
a←{⍵/0 1}¨(↓3 2⍴4 3 3)
{a⊢←↓⍉↑a{⍺∘{⍵/⊂⍺}¨⍵}¨↓3 3⍴⍵}¨(9/5)∘⊤¨1386531 496098
1000⍴∊a

```

Try it online!

Definitely not the intended solution as this still has a lot of hardcoded data, but it's a start.

# Answer
> 3 votes
# Jelly, 31 bytes

Given the pattern there is probably an even shorter way...

```
ĖŒṙḂ
“ṁ⁽⁺ḄæI’BḤ+3żḂ$ẎÇo2Ç+3Çḣȷ¬

```

**Try it online!**

### How?

Exploits the repeating run length structure that is apparent to a depth of three.

```
ĖŒṙḂ - Link 1, make runs of bits: list of lengths    e.g. [5,3,5,3,3]
Ė    - enumerate                      [[1,5],[2,3],[3,5],[4,3],[5,3]]
 Œṙ  - run-length decode      [1,1,1,1,1,2,2,2,3,3,3,3,3,4,4,4,5,5,5]
   Ḃ - bit (modulo by 2)      [1,1,1,1,1,0,0,0,1,1,1,1,1,0,0,0,1,1,1]

“ṁ⁽⁺ḄæI’BḤ+3żḂ$ẎÇo2Ç+3Çḣȷ¬ - Main link: no arguments
“ṁ⁽⁺ḄæI’                   - literal 234931870193324
        B                  - to binary = [1,1,0,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,1,0,1,0,1,0,1,1,0,0]
         Ḥ                 - double    = [2,2,0,2,0,2,0,2,2,0,2,0,2,0,2,2,0,2,0,2,0,2,2,0,2,0,2,0,2,0,2,2,0,2,0,2,0,2,2,0,2,0,2,0,2,2,0,0]
          +3               - add three = [5,5,3,5,3,5,3,5,5,3,5,3,5,3,5,5,3,5,3,5,3,5,5,3,5,3,5,3,5,3,5,5,3,5,3,5,3,5,5,3,5,3,5,3,5,5,3,3]
              $            - last two links as a monad:
             Ḃ             -   bit     = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
            ż              -   zip     = [[5,1],[5,1],[3,1],[5,1],[3,1],[5,1],[3,1],[5,1],[5,1],[3,1],[5,1],[3,1],[5,1],[3,1],[5,1],[5,1],[3,1],[5,1],[3,1],[5,1],[3,1],[5,1],[5,1],[3,1],[5,1],[3,1],[5,1],[3,1],[5,1],[3,1],[5,1],[5,1],[3,1],[5,1],[3,1],[5,1],[3,1],[5,1],[5,1],[3,1],[5,1],[3,1],[5,1],[3,1],[5,1],[5,1],[3,1],[3,1]]
               Ẏ           - tighten   = [5,1,5,1,3,1,5,1,3,1,5,1,3,1,5,1,5,1,3,1,5,1,3,1,5,1,3,1,5,1,5,1,3,1,5,1,3,1,5,1,3,1,5,1,5,1,3,1,5,1,3,1,5,1,3,1,5,1,3,1,5,1,5,1,3,1,5,1,3,1,5,1,3,1,5,1,5,1,3,1,5,1,3,1,5,1,3,1,5,1,5,1,3,1,3,1]
                Ç          - call the last Link (1) as a monad
                           -           = [1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0]
                 o2        - OR 2      = [1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,1,1,2,1,1,1,1,1,2,1,1,1,2,1,1,1,2]
                   Ç       - Link 1... = [1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0]
                    +3     - add three = [4,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,4,3,3,4,3,4,3,3,4,3,4,3,3]
                      Ç    - Link 1... = [1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0]
                        ȷ  - literal 1000
                       ḣ   - head      = [1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1]
                         ¬ - NOT       = [0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0]

```

# Answer
> 3 votes
# Java 8, ~~75~~ ~~64~~ 62 bytes

```
v->{for(int i=0;i<1e3;)System.out.print((int)(i++*.29253)%2);}

```

Prints the entire sequence without delimiter to save bytes, because they will only be `0` and `1` anyway.

Ports of *@ETHproductions*' Jelly answer, because I doubt I find anything shorter..

Try it online.

**Explanation:**

```
v->{                     // Method with empty unused parameter and no return-type
  for(int i=0;i<1e3;)    //  Loop `i` in range [0,1000)
    System.out.print(    //   Print:
      (int)(i++*.29253)  //    `i` multiplied with 0.29253,
                         //    and then truncated of their decimal values by casting to int
      %2);}              //    Modulo-2 to result in either 0 or 1

```

---

Old answer returning the resulting array (**75 bytes**):

```
v->{int i=1000,r[]=new int[i];for(;i-->0;)r[i]=(int)(i*.29253)%2;return r;}

```

Try it online.

**Explanation:**

```
v->{                   // Method with empty unused parameter and integer-array return-type
  int i=1000,          //  Index `i`, starting at 1000
      r[]=new int[i];  //  Result-array of size 1000
  for(;i-->0;)         //  Loop `i` in range (1000,0]
    r[i]=              //   Set the item in the array at index `i` to:
      (int)(i*.29253)  //    `i` multiplied with 0.29253,
                       //    and then truncated of their decimal values by casting to int
      %2;              //    Modulo-2 to result in either 0 or 1
  return r;}           //  Return the resulting integer-array

```

# Answer
> 3 votes
# Wolfram Language (Mathematica), 96 bytes

I searched for a cellular automaton that looks at the 4 neighbors to the left and produces the walking left pattern seen in the data when you Partition the data into length 7 and keep every third row.

This cellular automaton will run for 29 generations each of which is triplicated, matching the sequence perfectly for characters 1 to 629. However the sequence starts repeating at the 630th character rather than continuing the observed pattern, so extra code is needed to handle the repeat of the truncated pattern. I generate the main pattern twice to get to 1258 characters.

```
Most@Flatten[{#,#,#}&/@CellularAutomaton[{271,2,-{{4},{3},{2},{1}}},{0,0,0,0,1,1,1},29]]~Table~2

```

Without that glitch we could do it in a shorter 74 bytes. The 47 is the number of generations needed to get to 1000 characters (this actually goes to 1008=48\*7\*3)

```
{#,#,#}&/@CellularAutomaton[{271,2,-{{4},{3},{2},{1}}},{0,0,0,0,1,1,1},47]

```

Try it online!

# Answer
> 3 votes
# Python 3, 42 bytes

```
x=184
while x/629%2:print(x//629%2);x+=184

```

Try it online!

Port of G.B.'s answer.

# Answer
> 2 votes
# Stax, ~~13~~ 11 bytes

```
í?♫~╘äqx-G▄

```

Run and debug it at staxlang.xyz!

Port to Stax of @ETHproductions's Jelly answer (before its modification) with some modifications by @recursive to save two bytes.

# Answer
> 2 votes
# JavaScript (Node.js), ~~41~~ 33 bytes, port

Thank Rick Hitchcock for 4+ bytes

```
f=i=>i>999?'':(i*.29253&1)+f(-~i)

```

Try it online!

# JavaScript (Node.js), 121 bytes, original

```
_=>'8888y888'[s='replace'](/8/g,'aaa3yyy')[s](/y/g,'aaa3aa3')[s](/a/g,34)[s](/./g,t=>(_=+!+_+[]).repeat(t)).slice(3,1003)

```

Try it online!

# Answer
> 2 votes
# Z80Golf, 27 bytes

```
00000000: 018d 2b7b 1f1f e601 f630 ff09 3001 1313  ..+{.....0..0...
00000010: 7bfe 9220 ee7a fe04 20e9 76              {.. .z.. .v

```

Try it online!

Translated from this C code:

```
for (n = 0; n >> 16 != 1170; n += 11149 + 65536)
    putchar('0'|n>>18&1);

```

Disassembly:

```
  ld bc, 11149
loop:
  ld a, e
  rra
  rra
  and 1
  or '0'
  rst $38           ; putchar
  add hl, bc        ; Add 11149 to n = DEHL.
  jr nc, just_one   ; Add 65536 to n, possibly with carry from low 16 bits.
  inc de
just_one:
  inc de
  ld a, e
  cp 1170 & 255
  jr nz, loop
  ld a, d
  cp 1170 >> 8
  jr nz, loop
  halt

```

This is essentially a fixed-point arithmetic approach: (11149 + 65536) / 218 ≈ 0.29253, the constant used by other answers.

# Answer
> 1 votes
# Japt, 13 bytes

```
A³Ç*.29#ý f u
A³             // Given 10³,
  Ç            // map over it as a range, returning the given number
   *.29253     // times the constant,
           f u // floored and mod-2.

```

Japt version of ETHproduction's Jelly answer.
Bug fixed thanks to Oliver.

Try it here.

# Answer
> 1 votes
# , 17 bytes

```
2|<.0.29253*i.1e3

```

A J port of ETHproduction's Jelly answer.

Try it online!

# Answer
> 1 votes
# C, ~~55~~ ~~53~~ 52 bytes

```
f(i,j){for(i=0;j=.29253*i,i++-1e3;)putchar(j%2+48);}

```

Port of Kevin Cruijssen's Java answer. Try it online here.

Thanks to vazt for golfing 2 bytes and to Jonathan Frech for golfing one more.

Ungolfed version:

```
f(i, j) { // function taking two dummy arguments (implicitly int) and implicitly returning an unused int
    for(i = 0; j = .29253*i, i++ - 1e3; ) //  loop 1000 times, multiply i with 0.29253, truncating to an integer
        putchar(j % 2 + 48);  // modulo the truncated integer by 2, yielding 0 or 1, then convert to ASCII (48 is ASCII code for '0') and print
}

```

# Answer
> 1 votes
# Charcoal, 13 bytes

```
Ｅφ§01×·²⁹²⁵³ι

```

Try it online! Link is to verbose version of code. Explanation:

```
 φ              Predefined variable 1000
Ｅ               Map over implicit range
            ι   Current value
      ·²⁹²⁵³    Literal constant `0.29253`
     ×          Multiply
   01           Literal string `01`
  §             Cyclically index
                Implicitly print each result on its own line

```

Thanks to @ASCII-only for allowing indexing to accept floats which are cast to integer (and then automatically reduced modulo 2 in this case).

# Answer
> 1 votes
# ///, 63 bytes

```
/b/000111//A/b1b//B/b0b//C/0BA1//X/CACACACA0bCBCBCB/0bXXCBXCAC0

```

Try it online!

# Answer
> 1 votes
# Deadfish~, 1301 bytes

```
{iiiii}ddccccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdcccicccdccccicccdccccicccdccccicccdccciccccdccciccccdccciccccdcccicccdccccicccdccccicccdccciccccdccciccccdc

```

---
Tags: code-golf, sequence, kolmogorov-complexity
---