text:
(Somewhat) Pedantic Birthday Paradox
Background
The birthday paradox is a popular problem in probability theory which defies (most people's) mathematical intuition. The problem statement is:

Given N people, what is the probability that at least two of them have the same birthday (disregarding the year).

The problem is usually simplified by ignoring leap days entirely. In this case, the answer for N = 23 is P(23) ≈ 0.5072972 (as a common example). The linked Wikipedia article explains how to arrive at this probability. Alternatively, this Numberphile video does a really good job.
However, for this challenge we want to do it right and don't ignore leap years. This is slightly more complicated, since now the 29th of February needs to be added, but this particular birthday is less likely than all the others.
We'll also use the full leap year rules:

If a year is divisible by 400 it's a leap year.
Else, if a year is divisible by 100 it's not a leap year.
Else, if a year is divisible by 4 it's a leap year.
Else, it's not a leap year.

Confused? It means that the years 1700, 1800, 1900, 2100, 2200, 2300 are not leap years, but 1600, 2000, 2400 are (as well as any other year divisible by 4). This calendar repeats every 400 years, and we will assume a uniform distribution of birthdays over those 400 years.
The corrected result for N = 23 is now P(23) ≈ 0.5068761.
The Challenge
Given an integer 1 ≤ N < 100, determine the probability that among N people at least two have the same birthday under consideration of the leap year rules. The result should be a floating-point or fixed-point number, accurate to at least 6 decimal places. It is acceptable to truncate trailing zeroes.
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and output the result via STDOUT (or closest alternative), function return value or function (out) parameter.
Your solution must be able to produce output for all 99 inputs in a matter of seconds. This is mainly to rule out Monte Carlo methods with tons of samples, so if you're using a principally fast and exact algorithm in an excessively slow esoteric language, I'm willing to give leeway on this rule.
Test Cases
Here is the full table of results:
 1 => 0.000000
 2 => 0.002737
 3 => 0.008195
 4 => 0.016337
 5 => 0.027104
 6 => 0.040416
 7 => 0.056171
 8 => 0.074251
 9 => 0.094518
10 => 0.116818
11 => 0.140987
12 => 0.166844
13 => 0.194203
14 => 0.222869
15 => 0.252642
16 => 0.283319
17 => 0.314698
18 => 0.346578
19 => 0.378764
20 => 0.411063
21 => 0.443296
22 => 0.475287
23 => 0.506876
24 => 0.537913
25 => 0.568260
26 => 0.597796
27 => 0.626412
28 => 0.654014
29 => 0.680524
30 => 0.705877
31 => 0.730022
32 => 0.752924
33 => 0.774560
34 => 0.794917
35 => 0.813998
36 => 0.831812
37 => 0.848381
38 => 0.863732
39 => 0.877901
40 => 0.890932
41 => 0.902870
42 => 0.913767
43 => 0.923678
44 => 0.932658
45 => 0.940766
46 => 0.948060
47 => 0.954598
48 => 0.960437
49 => 0.965634
50 => 0.970242
51 => 0.974313
52 => 0.977898
53 => 0.981043
54 => 0.983792
55 => 0.986187
56 => 0.988266
57 => 0.990064
58 => 0.991614
59 => 0.992945
60 => 0.994084
61 => 0.995055
62 => 0.995880
63 => 0.996579
64 => 0.997169
65 => 0.997665
66 => 0.998080
67 => 0.998427
68 => 0.998715
69 => 0.998954
70 => 0.999152
71 => 0.999314
72 => 0.999447
73 => 0.999556
74 => 0.999645
75 => 0.999717
76 => 0.999775
77 => 0.999822
78 => 0.999859
79 => 0.999889
80 => 0.999913
81 => 0.999932
82 => 0.999947
83 => 0.999959
84 => 0.999968
85 => 0.999976
86 => 0.999981
87 => 0.999986
88 => 0.999989
89 => 0.999992
90 => 0.999994
91 => 0.999995
92 => 0.999996
93 => 0.999997
94 => 0.999998
95 => 0.999999
96 => 0.999999
97 => 0.999999
98 => 0.999999
99 => 1.000000

(Of course, P(99) is only 1.0 due to rounding. The probability won't reach exactly 1.0 until P(367).)

If you're going to be pedantic then you should take into account that birthdays aren't uniformly distributed throughout the year. 2. The precise relevance of the leap year rules depends on what assumptions are made about human longevity. Is the idea to amortise over the full 400 year cycle?

@PeterTaylor Yes, assume uniform distribution over the full 400 year cycle. I never said the set of N people was alive at the same time. ;)

Pyth, 31 34 bytes
Jt.2425K366-1c.xX0rK-KQ*JQ^+KJQ

Demonstration, Test Harness
This works similarly to the old version, except that instead of separately generating the (366 + n * (.2425 - 1)) value and multiplying it on, it starts by generating a list which extends from 366 to 365 - n + 2, then modifies the 366 in place to become (366 + n * (.2425 - 1)), and then takes the product of the list. Also, the constants 366 and -.7575 are used instead of 365 and .2425.

Old version:
Pyth, 34 bytes
J.2425K365-1c*+hK*QtJ.xrK-hKQ^+KJQ

There are two possible ways for there to be no pair of people with the same birthday: everyone to have different birthdays, and no one has a birthday on February 29th, and someone to have a birthday on the 29th, and everyone else to have different birthdays on normal days.
The probability of the first occurring is (365 * 364 * ... 365 - n + 1) / (365.2425^n).
The probability of the second occurring is (365 * 364 * ... 365 - n + 2) * .2425 * n / (365.2425^n)
These can be written together as (365 * 364 * ... 365 - n + 2) * (365 - n + 1 + .2425 * n) / (365.2425^n) = (365 * 364 * ... 365 - n + 2) * (365 + 1 + (.2425 - 1) * n) / (365.2425^n).
This is the probability of no pairs, so the probability of at least one pair is one minus the above number.
J = .2425
K = 365
.xrK-hKQ = (365 * 364 * ... 365 - n + 2)
+hK*QtJ = (365 + 1 + n * (.2425 - 1))
^+KJQ = (365.2425 ^ n)

Python, 179 178 144 143 140 136 135 133
f=.2425
g=365+f
a=lambda n:(n and(365-n)*a(n-1)or 365)/g
b=lambda n:(n<2and f or(367-n)*b(n-1)+a(n-2)*f)/g
p=lambda n:1-a(n-1)-b(n)

p(n) gives the result. Change .2425 to fractions.Fraction(97,400) to get an exact result.

You don't need a space between 2 and and.

Can you not put in 1/ for g and divide by it instead?

@xnor Yep, over time these things get lost :) What once was an optimization becomes suboptimal later.

you could introduce e=365 and replace 365 by e and 367 by e+2

@willem That's not shorter.

@orlp you're right, its still the same length

you can remove the space here ) or

Reordering (365-n)*a(n-1) cuts another space and likewise for (367-n)*b(n-1).

Python 155 153 151 142 140 bytes
d=146097
b=d/400
c=97/d
e=lambda n:n<2and 1-97/d or e(n-1)*(366-n)/b
f=lambda n:n<2and c or f(n-1)*(367-n)/b+e(n-1)*c
a=lambda n:1-e(n)-f(n)

Call a(n) for the result. For exact results, wrap d in a fraction.
Test here
Uses same technique as here, but with modified constants.

You don't need a space between 2 and and.

I thought it was 98 (although I may have mad a calculation mistake...)

80386 machine code, 43 bytes
Hexdump of the code:
68 75 6e 33 3b 68 5a eb 07 3b 8b c4 49 d9 e8 d9
e8 d8 00 d9 e8 d9 40 04 de ea d8 c9 d9 00 de eb
e2 f3 d8 ca d9 e8 d8 e1 58 58 c3

I started from the following formula (for the complementary probability):

(here d = 366 * 400 - 303 is the number of days in 400 years)
Here is c++ code that implements it (it's already optimized a little):
double it_opt(int k)
{
    double d = 366 * 400 - 303; // number of days in 400 years
    double result = 1; // probability of no coincidences
    const float const1 = float(400 / d);
    const float const2 = float(303 / d);
    double v1 = 1 + const2;
    double v2 = 1;

    for (int i = 0; i < k - 1; ++i)
    {
        v1 -= const1;
        result *= v1;
        v2 -= const2;
    }
    result *= v2;
    return 1 - result;
}

The code is arranged so it requires the minimum number of constants - only two (400 / d and 303 / d). I use the float type to represent them because it occupies less space (4 bytes per constant). In addition, I didn't want to multiply const2 by k - 1 (because that would require converting k - 1 to float); the code subtracts const2 repeatedly instead.
Here is the assembly language listing:
    ; // fastcall convention - parameter k is in ecx
    ; // result must be returned in st
    push dword ptr 0x3b336e75; // const1 = [esp + 4]
    push dword ptr 0x3b07eb5a; // const2 = [esp]
    mov eax, esp;              // use [eax] instead of [esp] - 1 byte less
    dec ecx;                   // calculate k - 1
    fld1;                      // initiaze result = 1
    fld1;                      // initialize v1
    fadd [eax];
    fld1;                      // initialilze v2
myloop:
    fld dword ptr [eax + 4];
    fsubp st(2), st;            // update v1
    fmul st, st(1);             // update result
    fld dword ptr [eax];
    fsubp st(3), st;            // update v2
    loop myloop;                // loop
    fmul st, st(2);             // update result by v2
    fld1;
    fsub st, st(1);             // complement result
    pop eax;                    // restore stack
    pop eax;                    // restore stack
    ret;                        // return


text:
Randomized Brainfuck Compiler
Joe is your average BF developer. He is about to check in his code changes to their repository when he gets a call from his boss. "Joe! The new client's machine is broken! The brainfuck interpreter sets all the cells to random values before program execution. No time to fix it, your code will have to deal with it." Joe doesn't think much of it, and is about to write a program to set the first million cells to zero, when his boss interrupts him again - "... and don't think about using brute force, the code has to be as small as possible." Now you have to help poor Joe!
Specifications

You will get some valid brainfuck code as input
Your program will then modify the code so that it should work on a randomized brainfuck interpreter
This means that before program execution, the cells can be set to any value.
The new program should have the exact same behavior no matter the initial conditions.
The interpreter will have max-cell value of 255 with wrapping, and an infinite length tape.

Scoring
Your score is 10 times the compiler size in bytes plus the sum of the test case sizes. Lowest score obviously wins.To mitigate against test-case optimization, I reserve the right to change the test-cases around if I suspect anything, and probably will do so before picking a winner.
Test Cases
(I got these from the esolangs page and this webpage: http://www.hevanet.com/cristofd/brainfuck/). Also thanks to @Sparr for the last test case.

Hello World: ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
Reverse Input: >,[>,]<[.<]
Powers of Two (Infinite Stream): >++++++++++>>+<+[[+++++[>++++++++<-]>.<++++++[>--------<-]+<<]>.>[->[
<++>-[<++>-[<++>-[<++>-[<-------->>[-]++<-[<++>-]]]]]]<[>+<-]+>>]<<]
Squares Under 10000: ++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+>>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]<<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]
Fibonacci Stream: >++++++++++>+>+[[+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[[-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>]<<<]
ASCII Sequence till input: ,[.[>+<-]>-] (This one requires varying cell numbers based on the input)

Comments are not for extended discussion; this conversation has been moved to chat.

sed, 46 byte compiler
s/</<</g
s/>/>[->[-]>[-]+<<]>/g
s/^/[-]>[-]+</

I didn't notice that the output was also supposed to be golf until after writing the program, so I will go for the short compiler. Also it was far too much work to test, so please notify if it does not function correctly :)

I'm confused. Your third line replaces the empty string? What does the empty string match in sed?
"sed: first RE may not be empty"

@Sparr All right, try with caret instead.

ok, let's see if I follow... zero the cell 0, set the cell 1 to one. replace all < with << and > with >X>. now any time the original program accessed cell n the new program accesses cell 2n, the even numbered cells. X zeros the odd cell being passed over, and if it's not zero then it zeros the next cell (an even cell) and sets the next odd cell to 1. do I have that right?

You know, if you're going for a short compiler, this would be only 35 bytes in Retina. ;)

This is actually an extremely elegant solution, compiler-wise. I suspect choice of language would reduce the regex overhead a little, and a little string trickery can squeeze ">[->[-]>[-]+<<]>", but you've done really well.

@MartinBüttner shameless plug! :P

C++
Compiler size : 630 bytes ( -10 bytes thanks to Zacharý )
Hello World compile result size : 139
Square under 10000 : 319
Compiler :
#include<string>
#include<map>
#include<stack>
#define B break
#define C case
#define S 30000
#define R m[(p<0)?(p%S)+S:p]
using s=std::string;using P=std::pair<int,int>;s a(s c){char m[S];memset(m,0,S);int p=0,i=0;P r{0,0};std::map<int,int>j;std::stack<int>t;for(int d=0;d<c.size();++d){if(c[d]==91)t.push(d);if(c[d]==93){j[d]=t.top();j[t.top()]=d;t.pop();}}while(i<c.size()){switch(c[i]){C'>':++p;B;C'<':--p;B;C'+':++R;B;C'-':--R;B;C'[':if(!R)i=j[i];B;C']':i=j[i]-1;B;default:B;}++i;r.first=p<r.first?p:r.first;r.second=p>r.second?p:r.second;}s n;for(int i=r.first;i<r.second;++i){n+="[-]>";}n+="[-]"+s(r.second,60)+c;return n;}

The randomized brainfuck interpreter :
void interpret(const std::string& code) {
    char memory[30000];
    for (int i = 0; i < 30000; ++i)
        memory[i] = std::rand()%256;
    int memPtr = 0, insPtr = 0;
    std::map<int, int> jump_map;

    {
        std::stack<int> jstack;
        for (int i = 0; i < code.size(); ++i) {
            if (code[i] == '[')
                jstack.push(i);
            if (code[i] == ']') {
                jump_map[i] = jstack.top();
                jump_map[jstack.top()] = i;
                jstack.pop();
            }
        }
    }
    while (insPtr < code.size()) {
        switch (code[insPtr]) {
        case '>': ++memPtr; break;
        case '<': --memPtr; break;
        case '+': ++memory[memPtr]; break;
        case '-': --memory[memPtr]; break;
        case '.': std::cout << memory[memPtr]; break;
        case ',': std::cin >> memory[memPtr]; break;
        case ']': if (memory[memPtr] != 0) insPtr = jump_map[insPtr]; break;
        case '[': if (memory[memPtr] == 0) insPtr = jump_map[insPtr]; break;
        default:break;
        }
        ++insPtr;
    }
}

Some notes :

The compiler will execute the program to determine the memory cells that are used. If your program is an infinite loop, the compiler will loop infinitely.

You can reduce your score by changing the name of pii to P, and changing the definition of R to m[p<0?p%30000+30000:p], and modifying all the calls/references to them accordingly. Also, he modified the test cases. I haven't checked this, but it might save some bytes to define something to be 30000, since you use it so often.

Would changing R to m[p<0?p%S+S:p] work?

Removing the parentheses in the definition of R should save a few bytes.

398 bytes

Fail on ,[[>++<-]>.](take an input, double and output till zero), get [-],[[>++<-]>.]

rs, 33 bytes, Score: 2659
Mostly just a simple port of the sed answer.
</<<
>/>[->[-]>[-]+<<]>
[-]>[-]+<

Did you publish this language prior to yesterday? Languages that postdate the creation of a question aren't valid for submitting answers.

@Sparr Well, I had, but then I wrecked my Git commit history and had to re-create the repo...

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Y-Wing Strategy for Sudoku
I recently got a new Sudoku app that produces really hard Sudoku's, which can't be solved using the standard strategies. So I had to learn a few new ones. One of these strategies is the Y-Wing Strategy. It is ranked under "Tough Strategies", but it is actually not that hard.
Example
For this strategy only 4 cells are important. Therefore I ignored all other cells in the images.
We look at all candidates for each cell. In the following example we have a cell with the candidates 3 7 (that means we have already rejected the candidates 1 2 4 5 6 8 9, for instance because there is a 1 in the same row, a 2 in the same 3x3 box, ...), a cell with the candidates 6 7, a cell with the candidates 3 6 and a cell with the candidates 2 6. The Y-Wing strategy will suggest, that the 6 can be removed from the candidates of the downright cell, leaving only a 2 as candidate, which you can fill in. So we found a correct number and are one step closer in solving the full Sudoku.

Why can the 6 be removed?
Explanation
Let us assume that the 6 is the correct number for the downright cell. Now there is a 6 in this column, therefore we can remove the 6 from the candidates of the top right cell, leaving only a 7, which we can fill in. The same happens with the down left cell. We can remove the 6 and fill in the 3. Now if we look at the top left cell we get a contradiction. Because now there's already a 7 in the same row and a 3 in the same column, so we can remove the 7 and the 3 of the candidates, leaving no candidates at all. Which is clearly not possible. Therefore the 6 cannot be the correct number of the downright cell.
More precisely: If we have 4 cells with the candidates [A B] [A C] [C D] [B C] (in this order or circular rotated) and the cells are connected (via same row, same column or same 3x3 box) in a circle (Cell 1 is connected to Cell 2, which is connected to Cell 3, which is connected to Cell 4, which is connected to Cell 1), than you can remove C from the [C D] cell. It is crucial, that the three cells [A B], [A C] and [B C] only contain two candidates each. Differently the cell [C D], which may contain more or less (D can be zero, one or even more candidates).

Notice that I explicitly said they can be connected either way. In the next example you can see the strategy applied again. But this time the 4 cells doesn't form a rectangle. The down left and downright cells are simply connected, because they are in the same 3x3 box. Y-Wing says, that we can remove the 1 as candidate of the top left cell. This time there are still 2 candidates in this cell left, so we didn't actually found a new correct number. But nevertheless the removal of the 1 can open doors to different strategies.

If you want more information about the strategy or want a few more examples, visit sudokuwiki.org.
Challenge Specifications
You will receive 4 lists as input, representing the candidates of the cells. The four cells are connected like a circle (Cell 1 is connected to Cell 2, which is connected to Cell 3, which is connected to Cell 4, which is connected to Cell 1). You can assume that each list is sorted in ascending order.
Your job is to remove one candidate (by applying the Y-Wing strategy) and returning the resulting candidates lists in the same order. If you can't apply the strategy, just return the same candidates lists.
If there are two possible solutions (you could remove A of cell B or remove C of cell D), than return only one solution. It doesn't matter which one.
The input can be in any native list or array format. You could also use a list of lists or something similar. You can receive the input via STDIN, command-line argument, prompt or function argument and return the output via return value or simply by printing to STDOUT.
This is code-golf. The shortest code (in bytes) wins.
Test Cases
[3 7] [6 7] [2 6] [3 6]       => [3 7] [6 7] [2] [3 6]   # Example 1
[6 7] [2 6] [3 6] [3 7]       => [6 7] [2] [3 6] [3 7]   # Example 1, different order
[2 6] [3 6] [3 7] [6 7]       => [2] [3 6] [3 7] [6 7]   # Example 1, different order
[3 6] [3 7] [6 7] [2 6]       => [3 6] [3 7] [6 7] [2]   # Example 1, different order
[1 2 8] [1 8] [8 9] [1 9]     => [2 8] [1 8] [8 9] [1 9] # Example 2
[3 8] [4 8] [3 4 8] [3 4]     => [3 8] [4 8] [3 8] [3 4]
[1 3 6 7 8] [3 8] [3 4] [4 8] => [1 3 6 7] [3 8] [3 4] [4 8]
[7 8] [7 8] [4 7] [4 8]       => [7 8] [8] [4 7] [4 8] or [7] [7 8] [4 7] [4 8]
[4 7] [7 8] [4 8] [4]         => [4 7] [7 8] [4 8] []    # Fictional example
[3 7] [2 6] [6 7] [3 6]       => [3 7] [2 6] [6 7] [3 6] # Y-Wing can't be applied here
[4 7] [2 7 8] [4 8] [1 4]     => [4 7] [2 7 8] [4 8] [1 4] # -||-

Can multiple sets in a single input be exactly same ?

@Optimizer Yes, for instance in the 8th test case, 7 8 is are the candidates for the first and the second cell. The Y-Wing strategy can still be applied.

@Jakube ah okay, didn't see that.

If more than 1 solutions are possible, can I output any one of them ?

Yes, I clarified it in the question.

CJam, 90 bytes
Ugghhh, this is too long because of the constraint that the other 3 cells should have only 2 candidates.
l~_:_(a+2/::&_{,}$2>:&:Y;{:PY&Y{P1<}?~}%:X,3>1${,}$W=_,2>\Y&,1?*{X:_(+2/{~:I=}#)_2$=I-t}&p

This expects input as a list of list in CJam format. For ex.:
[[2 6] [3 6] [3 7] [6 7]]

gives output in a CJam list of list format:
[[2] [3 6] [3 7] [6 7]]

Will add explanation once I am done golfing..
Try it online here or try the whole test suite here.

Mathematica, 124 110 bytes
Cases[e@n_:>n]/@(Plus@@e/@#&/@#/.NestList[RotateLeft/@#&,{x:a_+b_,y:b_+c_,z:c_+a_,w:a_+_.}->{x,y,z,w-a+1},3])&

Examples:
In[1]:= yWing = Cases[e@n_:>n]/@(Plus@@e/@#&/@#/.NestList[RotateLeft/@#&,{x:a_+b_,y:b_+c_,z:c_+a_,w:a_+_.}->{x,y,z,w-a+1},3])& ;

In[2]:= yWing[{{3, 7}, {6, 7}, {2, 6}, {3, 6}}]

Out[2]= {{3, 7}, {6, 7}, {2}, {3, 6}}

In[3]:= yWing[{{4, 7}, {7, 8}, {4, 8}, {4}}]

Out[3]= {{4, 7}, {7, 8}, {4, 8}, {}}

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Shifty XORyption
Write a program or function (or set of programs/functions) to encrypt and decrypt data given the following specification:
Encryption

Calculate an XOR hash of the input by XOR-ing every byte with each-other.
XOR every byte of the input by this hash.
Shift the result four bits left.
Pad the left side with the first four bits of the XOR hash.
Pad the right side with the last four bits of the XOR hash.

Example

Given input: "G0lf" (0x47306C66)
Calculate XOR hash: 0x47 ^ 0x30 ^ 0x6C ^ 0x66 = 0x7D
XOR every byte by hash: 0x3A4D111B
Expected result (after shift and pad): "s¤Ñ\x11½" (0x73A4D111BD)

Rules

Your program/function can input/output of whatever type makes sense in your golfing language of choice (String, Byte Array, etc) as long as the input/output are the actual bytes. For example, you may not output a hexidecimal string.
Encryption and decryption can be separated into separate programs (score will be the their combined size) or a single one. Single methods can take an argument for whether it should encrypt or decrypt.
Input for encryption can be expected to be at least 1 byte in size.
Input for decryption can be expected to be at least 2 bytes.
Non-printable bytes do not need to be escaped in the output.

Could an decimal array be used as an output form?

@ɐɔıʇɥʇuʎs It would be acceptable to take input and output as an array of integers to represent bytes.

Is there a maximum input length (for example, 14 bytes  (56 bits), so that the final result fits in a 64-bit integer)?

Just a note: From a cryptography point of view this is not an encryption, as it has no key (or a 0-bit key).

@Doorknob No restrictions on input size. It can be expected to fit in memory though.

@PaŭloEbermann What would the correct terminology be for this? I don't want to say it's an encoding because the result is definitely obfuscated. Would it qualify as a cipher?

I'm just waiting for someone to post something about never rolling your own encryption, ignoring the site this is on...

Funny random comment, I pronounce XOR "zorr", so I expect to see "a XOR hash" not "an XOR hash"

What is the character encoding you use for the encrypted result?

Is it allowed to receive input as an 8 × n array where each row of the array contains one byte represented as a vector of eight bits?

@FUZxxl no encoding is necessary. A two dimensional array of bits is okay.

@nderscore Could you un-accept my answer, so I can delete it? (Turns out to be broken.)

@MartinEnder sorry for the late reply. it's been un-accepted.

CJam, 36 + 34 = 70 bytes
A bit different approach using binary forms
Encrypter:
q_:^:Hf^H+{i2b8Ue[}%)4/~@\]e_8/2fb:c

How it works:
q_:^                                  e# Read input as string, copy and XOR all the chars
    :Hf^                              e# Store the XOR in H and XOR each char with H
        H+                            e# Append H to the char array
          {       }%                  e# On each of the elements in the array
           i2b                        e# Convert the ASCII value to binary
              8Ue[                    e# Pad with 0 so that the length is 8
                    )                 e# Pop out the last array element, which is H
                     4/~@\            e# Put first 4 bits of H before the input array
                                      e# And rest 4 after it
                          ]e_8/       e# Flatten everything into a single array and group
                                      e# into pieces of 8 bits
                               2fb:c  e# Convert each 8 bit part to integer and then to
                                      e# its character form

Decrypter:
q{i2b8Ue[4/~}%)\(@+2b\:+8/2fb\f^:c

How it works:
q{          }%                      e# For each character of the input string
  i2b                               e# Convert to ASCII code and then to its binary form
     8Ue[                           e# Pad with enough 0 so that length is 8 bit
         4/~                        e# Split into parts of 4 and unwrap
              )\(@+                 e# Take out the first and last 4 bit group and join
                                    e# them together to get the XOR Hash H
                   2b\              e# Convert H to decimal form and swap to put the
                                    e# remaining converted input array on top
                      :+8/          e# Join all bits together and split into groups of 8
                          2fb       e# Convert each 8 but group to decimal form
                             \f^    e# Swap to put H on top and XOR each number with H
                                :c  e# Get character from each of the ASCII value

Try the encrypter and decrypter online

Pyth, 69 bytes
Ksm>+0jCd16_2zJ?,hKeKQmxFdCcK2=KsmmxFkC,dJc?tPKQK2smCid16c?KQ++hJKeJ2

This combines encryption and decryption, simply add a 0 as argument for encryption or a 1 for decryption. The reason for this is simple. Converting strings into bits (or 4 bit integer) or the reverse is really really long in Pyth. By combining the both functions into one program, I can save a lot of bytes.
Online demonstrations: Encryption and Decryption.
Explanation:
The first part converts the input into a list of 4-bit integer (each char get converted into 2 4-bit integer) and stores it in K.
  m          z   map each character d of input (=z) to:
       Cd            the ascii-value of d
      j  16          convert the result into base 16
   >+0     _2        insert a zero to the front and take the last 2 values
                     (so that each char gets mapped to exactly 2 numbers)
Ks               chain all these tuples and assign them to K

The second part determines the hash values and stores them in J. If Q==0 it computes them by xor, otherwise it takes the first and last value of K.
 ?     Q           ... if Q (=second input) else ...
  ,hKeK            [K[0], K[-1]]
        m   CcK2   map each d of zipped(K chopped into pairs) to:
                   [zipped(...) gives me 2 lists, one with the values of the even indices, and one with the odd indices]
         xFd           fold the list d by xor
J                  store the result in J (this is the hash value)

The next part does the xor using the hash values. When Q == 0 it is performed on the complete list K, otherwise only on the list K without the first and last value.
=KsmmxFkC,dJc?tPKQK2
             ?tPKQK    K[1:-1] if Q else K
   m        c      2   map each d of [... chopped into pairs] to:
    m   C,dJ              map each pair k of zip(d,J) to:
     xFk                     apply xor to the 2 values in k
=Ks                    chain all these tuples and assign them to K

And the last part converts K back to chars:
smCid16c?KQ++hJKeJ2
        ?KQ++hJKeJ    K if Q else J[0] + K + J[1]
 m     c          2   map each pair of [... chopped into pairs] to:
   id16                  convert d into a single integer
  C                      convert to char
s                     join all chars and print

Javascript (ES6) 83 + 73 = 156
Both functions take input as and ouput an array of numbers to represent bytes.
Encrypt 85 84 83
E=s=>s.concat((h=s.reduce((x,y)=>x^y))<<4&240^h).map(x=>a<<4&240|(a=x^h)>>4,a=h>>4)

Decrypt 75 73
D=s=>s.map(x=>(a<<4&240|(a=x)>>4)^h,h=(a=s.shift())&240|s[~-s.length]&15)

Demonstration (Firefox only)

E=s=>s.concat((h=s.reduce((x,y)=>x^y))<<4&240^h).map(x=>a<<4&240|(a=x^h)>>4,a=h>>4)
D=s=>s.map(x=>(a<<4&240|(a=x)>>4)^h,h=(a=s.shift())&240|s[~-s.length]&15)

toHexString = x=>'0x'+x.map(y=>y.toString(16)).join('')

input = [...'G0lf'].map(x=>x.charCodeAt());
document.write('Input: ' + toHexString(input) + '
');

encrypted = E(input);
document.write('Encrypted: ' + toHexString(encrypted) + '
');

decrypted = D(encrypted);
document.write('Decrypted: ' + toHexString(decrypted) + '
');

Using Strings 131 + 129 = 260
And just for fun... here's some versions which use strings for input/output instead.
E=(s,h=0)=>[for(x of s)(h^=y=x.charCodeAt(),y)].concat(h<<4&240^h).map(x=>String.fromCharCode(a<<4&240|(a=x^h)>>4),a=h>>4).join('')

D=s=>(s=[s.charCodeAt(j=i)for(i in s)]).map(x=>String.fromCharCode((a<<4&240|(a=x)>>4)^h),h=(a=s.shift())&240|s[~-j]&15).join('')

E('G0lf') // 's¤Ñ\x11½'
D('s¤Ñ\x11½') // 'G0lf'

Jelly, 25 + 17 = 42 bytes
Oµ^^/;^/b⁴Ż€-.ịⱮµṪjFs2ḅ⁴Ọ

Try it online!
Ob⁴FµḢ,Ṫ,s2$ḅ⁴^/Ọ

Try it online!
Full round trip.
+6 bytes correcting a bug which looks like it also plagues Martin's CJam answer
How they work
Encryption
Oµ^^/;^/b⁴Ż€-.ịⱮµṪjFs2ḅ⁴Ọ - Main link. Takes S on the left
O                         - Convert S to char codes; Call this O
 µ                        - Discard S and use O as the left argument
   ^/                     - Reduce O by XOR to get the hash, X
  ^                       - XOR each element in O by X
      ^/                  - X
     ;                    - Concatenate to the end of O
         ⁴                - 16
        b                 - Convert each to base 16
          Ż€              - Prepend a 0 to each
               Ɱ          - For each:
            -.ị           -   Get the -0.5th index
                              This returns the last 2 elements of the list
                              As the ị atom returns [floor(x)ị, ceil(x)ị] for
                              non-integer x, and uses 1-indexing. Therefore,
                              -.ị = -0.5ị = [floor(-.)ị, ceil(-.)ị]
                                  = [-ị, 0ị] = last 2 elements

                              For a integer < 16, b⁴ returns a singleton list
                              Otherwise, it'll return (here) a pair
                              We then prepend 0 so each list has either 2 or 3 elements
                              and ignore the leading 0 if it already had 2 elements

                            Call this list of nibbles N
                            Currently, N = [[a, b], [c, d], ..., [x, y]]
                            where [a, b] are the nibbles of the XOR'ed elements
                            and [x, y] are the nibbles of X

                µ         - Discard O and use N as the left argument
                 Ṫ        - Remove [x, y] from N
                  j       - Join [x, y] with N, yielding [x, [a, b], ..., y]
                   F      - Flatten; [x, a, b, c, d, ..., y]
                    s2    - Split into pairs; [[x, a], [b, c], ...]
                      ḅ⁴  - Convert each from base 16
                        Ọ - Convert back to characters

Decryption
Ob⁴FµḢ,Ṫ,s2$ḅ⁴^/Ọ - Main link. Takes S on the left
O                 - Convert to char codes
 b⁴               - Convert to hex
   F              - Flatten; Call this list of hex bytes H = [x, a, b, ..., y]
    µ             - Discard S and use H as the left argument
     Ḣ            - Remove the first element of H, x
       Ṫ          - Remove the final element of H, y
      ,           - Pair; [x, y]
           $      - Group the previous two links as a monad f(H):
         s2       -   Split into pairs
        ,         - Pair with [x, y]; [[x, y], [[a, b], ...]]
            ḅ⁴    - Convert each from hex
              ^/  - Reduce by XOR
                Ọ - Convert into chararacters

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Counting in pyramids
You should write a program or function which receives a list of distinct integers as input and outputs or returns the number of occurrences of the input numbers in the following upside-down number pyramid.
Starting from the original list in every step we create a new one with the maximal values of every pair of adjacent numbers (e.g. 5 1 2 6 becomes 5 2 6). We stop when there is only one number in the list.
The full pyramid for 5 1 2 6 is
5 1 2 6
 5 2 6
  5 6
   6

The resulting number of occurrences are 3 1 2 4 (for 5 1 2 6 respectively).
Input

A list of one or more integers with no repetition. (e.g. 1 5 1 6 is invalid.)

Output

A list of positive integers. The ith element of the list is the number of occurrences of the ith input number in the pyramid.

Examples
Input => Output
-5 => 1

8 4 => 2 1

5 9 7 => 1 4 1

1 2 3 9 8 6 7 => 1 2 3 16 3 1 2

6 4 2 1 3 5 => 6 4 2 1 3 5

5 2 9 1 6 0 => 2 1 12 1 4 1

120 5 -60 9 12 1 3 0 1200 => 8 2 1 3 16 1 4 1 9

68 61 92 58 19 84 75 71 46 69 25 56 78 10 89 => 2 1 39 2 1 27 6 5 1 6 1 2 14 1 12

This is code-golf so the shortest entry wins.
Bonus puzzle: can you solve the problem in O(n*log n) time?

For a function submission, do I have to print them to STDOUT or simply output them ?

Pyth, 19 17 bytes
m/smmeSb.:QhkUQdQ

Check out the Online Demonstration or the complete Test Suite (first 4 byte iterate over the examples).
This one is a little bit more clever than the naive approach. Each number of the triangle can be represented as the maximal value of a connected subset of Q. In the first line it uses the subsets of length 1, the second line of the triangle uses the subsets of length 2, ...
Explanation
m/smmeSb.:QhkUQdQ    implicit: Q = input()
   m         UQ         map each k in [0, 1, 2, ..., len(Q)-1] to:
        .:Qhk              all subsets of Q of length (k + 1)
    meSb                   mapped to their maximum
  s                     join these lists together
m               Q    map each d of Q to:
 /             d        its count in the computed list

To visualize this a little bit. m.:QhdUQ and the input [5, 1, 2, 6] gives me all possible subsets:
[[[5], [1], [2], [6]], [[5, 1], [1, 2], [2, 6]], [[5, 1, 2], [1, 2, 6]], [[5, 1, 2, 6]]]

And mmeSk.:QhdUQ gives me each of their maxima (which corresponds exactly to the rows in the pyramid):
[[5, 1, 2, 6], [5, 2, 6], [5, 6], [6]]

Pyth, 23 22 bytes
|u&aYGmeSd.:G2QQm/sYdQ

This is just the simple "do what you're told" approach.
Check out the Online Demonstration or a complete Test Suite (first 4 byte iterate over the examples).
Explanation
meSd.:G2 maps each pair of [(G[0], G[1]), (G[1], G[2]), ...] to the maximal element.
Y is an empty list, therefore aYG appends G to the Y.
u...QQ repeatedly applies these two functions (len(Q) times) starting with G = Q and updating G after each run.
m/sYdQ maps each element of the input list to their count in the flattened Y list.

your 17 byte version uses the same algorithm as mine, I guess that is now naive too :P

Python, 81
def f(L):
 if L:i=L.index(max(L));L=f(L[:i])+[~i*(i-len(L))]+f(L[i+1:])
 return L

A divide-and-conquer solution. The maximum element M seeps all the way down the pyramid, splitting it into a rectangle of M's and two subpyramids.
* * * M * *
 * * M M *
  * M M M
   M M M
    M M
     M

So, the overall result is the output for the left sublist, followed by the area of the rectangle, followed by the output for the right sublist.
The input variable L is reused to stored the result so that the empty list is mapped to the empty list.
The constructs in solution are wordy in Python. Maybe some language with pattern-matching can implement the following pseudocode?
def f(L):
 [] -> []
 A+[max(L)]+B -> f(A)+[(len(A)+1)*(len(B)+1)]+f(B)

I can do one byte shorter with Mathematica's pattern matching, but it doesn't even beat the existing Mathematica submission: f@{}=##&@@{};f@{a___,l_,b___}/;l>a~Max~b:={f@{a},Length@{a,0}Length@{b,0},f@{b}}

CJam, 23 22 bytes
Still looking for golfing options.
{]_,{)W$ew::e>~}%fe=~}

This is a CJam function (sort of). This expects the input numbers on stack and returns the corresponding output counts on the stack too. An example:
5 1 2 6 {]_,{)W$ew::e>~}%fe=~}~

leaves
3 1 2 4

on stack.
Pretty sure that this is not in O(n log n) time.
Code expansion:
]_                     e# Wrap the input numbers on stack in an array and take a copy
  ,{          }%       e# Take length of the copy and run the loop from 0 to length - 1
    )W$                e# Increment the iterating index and copy the parsed input array
       ew              e# Get overlapping slices of iterating index + 1 size
         ::e>          e# Get maximum from each slice
             ~         e# Unwrap so that there can be finally only 1 level array
                fe=    e# For each of the original array, get the occurrence in this
                       e# final array created by the { ... }%
                   ~   e# Unwrap the count array and leave it on stack

Lets take a look at how it works by working up an example of 5 1 2 6
In the second row, 5 1 2 6 becomes 5 2 6 because 5, 2 and 6 are the maximum of [5 1], [1 2] and [2 6] respectively. In the third row, it becomes 5 6 because 5 and 6 are maximum of [5 2] and [2 6] respectively. This can also be written as maximum of [5 1 2] and [1 2 6] respectively. Similarly for last row, 6 is maximum of [5 1 2 6].
So we basically create the proper length slices starting from slice of length 1, which is basically the original numbers, each wrapped in an array, to finally a slice of length N for the last row, where N is the number of input integers.
Try it online here

Mathematica, 72 bytes
Last/@Tally[Join@@NestList[MapThread[Max,{Most@#,Rest@#}]&,#,Length@#]]&

Python, 81
lambda L:[sum(x==max(L[i:j])for j in range(len(L)+1)for i in range(j))for x in L]

Each entry of the pyramid is the maximum of the sublist atop its upward cone. So, we generate all these sublists, indexed by intervals [i,j] with 0 < i < j <= len(L), and count how many time each element appears as a maximum.
A shorter way to enumerate the subintervals would likely save characters. A single-index parametrization of the pairs [i,j] would be a plausible approach.

JavaScript, 109 bytes
I think I found an interesting way to go about this, but only after I was done realized the  code was too long to compete. Oh well, posting this anyway in case someone sees further golfing potential.
f=s=>{t=[];for(i=-1;s.length>++i;){j=k=i;l=r=1;for(;s[--j]<s[i];l++);for(;s[++k]<s[i];r++);t[i]=l*r}return t}

I'm making use of the following formula here:

occurrences of i = (amount of consecutive numbers smaller than i to its left + 1) * (amount of consecutive numbers smaller than i to its right + 1)

This way one doesn't need to actually generate the entire pyramid or subsets of it. (Which is why I initially thought it would run in O(n), but tough luck, we still need inner loops.)

MATLAB : (266 b)

the correction of the code costs more bytes, i will struggle how to reduce it later.

v=input('');h=numel(v);for i=1:h,f=(v(i)>v(1));l=(v(i)>v(h));for j=h-1:-1:i+1,l=(v(i)>v(j))*(1+l);end,if(i>1),l=l+(v(i)>v(i-1))*l;end;for j=2:i-1,f=(v(i)>v(j))*(1+f);end,if(i<h),f=f+(v(i)>v(i+1))*f;end;s=f+l+1;if(i<h&&i>1),s=s-((v(i)>v(i+1))*(v(i)>v(i-1)));end;s
end

INPUT
a vector must be of the form [a b c d ...]

example:
[2 4 7 11 3]

OUTPUT
pattern occurences.
s =

 1

s =

 2

s =

 3

s =

 8

s =

 1

EXPLANATION:
if [a b c d] is an input the program calculates result g h i j as
g= (a>b) + (a>b)(a>c) + (a>b)(a>c)*(a>d) = (a>b)(1+(a>c)(1+(a>c) )))
h= (b>a) + (b>c) + (b>a)(b>c) + (b>c)(b>d)+(b>a)(b>c)(b>d) = ... 'simplified'
i= (c>b) + (c>d) + (c>b)(c>d) + (c>b)(c>a)+(c>d)(c>b)(c>a) = ..
j= (d>c) + (d>c)(d>b) + (d>c)(d>b)*(d>a) = ...

Pip, 56 + 1 = 57 bytes
Not competing much with the CJam voodoo, I'm afraid. Looks like I need a better algorithm. Run with -s flag to get space-delimited output.
l:gr:0*,#gg:0*g+1WrFir:{c:r@[a--a]c@($<l@c)}M1,#r++(gi)g

Ungolfed, with comments:
l:g                              l = input from cmdline args
r:0*,#g                          r = current row as a list of indices into l
g:0*g+1                          Repurpose g to store the frequencies
Wr                               Loop until r becomes empty
 Fir:{c:r@[a--a]c@($<l@c)}M1,#r  Redefine r (see below) and loop over each i in it
  ++(gi)                         Increment g[i]
g                                Output g

The redefinition of r each time through works as follows:
{c:r@[a--a]c@($<l@c)}M1,#r
{                   }M1,#r       Map this function to each a from 1 to len(r) - 1:
 c:r@[a--a]                      c is a two-item list containing r[a] and r[a-1]
                l@c              The values of l at the indices contained in c
              $<                 Fold/less-than: true iff l[c[0]] < l[c[1]]
           c@(     )             Return c[0] if the former is greater, c[1] otherwise

APL (24)
{+/⍵∘.={⍵≡⍬:⍵⋄⍵,∇2⌈/⍵}⍵}

This is a function that takes a list, like so;
      {+/⍵∘.={⍵≡⍬:⍵⋄⍵,∇2⌈/⍵}⍵}68 61 92 58 19 84 75 71 46 69 25 56 78 10 89
2 1 39 2 1 27 6 5 1 6 1 2 14 1 12

Explanation:

{...}⍵: apply the following function to ⍵:

⍵≡⍬:⍵: if ⍵ is empty, return ⍵
2⌈/⍵: generate the next list
⍵,∇: return ⍵, followed by the result of applying this function to the next list

⍵∘.=: compare each element in ⍵ to each element in the result of the function
+/: sum the rows (representing elements in ⍵)

Haskell, 78 bytes
l=length
f x=[l[b|b<-concat$take(l x)$iterate(zipWith max=<<tail)x,a==b]|a<-x]

Usage: f [68,61,92,58,19,84,75,71,46,69,25,56,78,10,89]-> [2,1,39,2,1,27,6,5,1,6,1,2,14,1,12].
How it works
zipWith max=<<tail   -- apply 'max' on neighbor elements of a list
iterate (...) x      -- repeatedly apply the above max-thing on the
                     -- input list and build a list of the intermediate
                     -- results
take (l x) ...       -- take the first n elements of the above list
                     -- where n is the length of the input list
concat               -- concatenate into a single list. Now we have
                     -- all elements of the pyramid in a single list.
[ [b|b<-...,a==b] | a<-x]
                     -- for all elements 'a' of the input list make a
                     -- list of 'b's from the pyramid-list where a==b.
 l                   -- take the length of each of these lists

J (49)
I suppose there is some room for improvement...
[:+/~.="1 0[:;([:i.#)<@:(4 :'(}:>.}.)^:x y')"0 1]


text:
Matrix property X revisited (or the Joy of X)
This challenge is partly an algorithms challenge, partly an optimization challenge and partly simply a fastest code challenge.
A T matrix is fully specified by its first row r and first column c. Each remaining element of the matrix is just a copy of the element that is diagonally up and left. That is M[i,j] = M[i-1,j-1]. We will allow T matrices which are not square. We do however always assume that the number of rows is no more than the number of columns. For example, consider the following 3 by 5 T matrix.
10111
11011
11101

We say a matrix has property X if it contains two non-empty sets of columns with non-identical indices which have the same (vector) sum. The vector sum of one or more columns is simply an element-wise summation of their columns.  That is the sum of two or more columns containing x elements each is another column containing x elements. The sum of one column is trivially the column itself.
The matrix above trivially has property X as the first and last columns are the same. The identity matrix never has property X.
If we just remove the last column of the matrix above then we get an example which does not have property X and would give a score of 4/3.
1011
1101
1110

The task
The task is to write code to find the highest scoring T matrix with binary entries  and which does not have property X. For clarity, a matrix with binary entries has the property that each one of its entries is either 0 or 1.
Score
Your score will be the number columns divided by the number of rows in your best scoring matrix.
Tie Breaker
If two answers have the same score, the one submitted first wins.
In the (very) unlikely event that someone finds a method to get unlimited scores, the first valid proof of such a solution will be accepted.  In the even more unlikely event that you can find a proof of optimality of a finite matrix I will of course award the win too.
Hint
All the answers at Find highest scoring matrix without property X are valid here but they are not optimal. There are T matrices without property X which are not cyclic.
For example, there is a 7 by 12 T matrix without property X but no such cyclic matrix.
21/11 would beat all the current answers from this and the previous challenge.
Languages and libraries
You can use any language which has a freely available compiler/interpreter/etc. for Linux and any libraries which are also freely available for Linux.
Bonus The first answer with a score greater than 2 gets an immediate 200 point bounty award.  Ton Hospel has now achieved this!

Current leader board

C++. Score 31/15 by Ton Hospel
Java. Score 36/19 by Peter Taylor
Haskell. Score 14/8 by alexander-brett

By the " two non-empty sets of columns with non-identical indices" you mean two sets of columns that are disjoint? Or, to rephrase this, is {1 ,3}, {1, 5} a valid two subsets of columns?

@pawel.boczarski No not disjoint.  Just non-identical. So {1 ,3}, {1, 5} is valid.

Ok. What about M[i,1] - is it a "borrow" from the last column of M[i-1] (zero is not a valid matrix column index)? And actually this is "up and left" rather than "up and right".

@pawel.boczarski "right" was a typo. Thanks.  The first row and column can be set to anything you like. They define the whole rest of the matrix. Does that answer your question?

Ok, I got it. It was my fault to not have read carefully that the first column is also defined.

For the bonus, do you mean the first answer with a score greater than 2 gets 100 bounty? Otherwise that might cost you... :)

@trichoplax I do!

@Lembik: (continuing the comments from the now delted answer) As one particular sum of columns you consider the sum of all columns in a particular set S. Do you also allow the empty set S={} as one of those sets in your definition? This would just eliminate all matrices that contian a column that consists only of zeros. If i is the index of the said column, then the matrix would have the property X with the sets {},{i}.

@flawr No I don't allow the empty set (see the definition of property X). However we know that a matrix (with 2 or more columns) with a column consisting only of zeros always has property X in any case as that column plus any other column equals that other column.

Ah ok, well then it does not matter whether you allow the empty sum or not, except for the matrix 1x1 matrix 0=)

Is there any reason for calling the space of matrices T rather than Toeplitz?

@PeterTaylor No, not really.  I was hoping for a pun involving T and X but in the end couldn't come up with a good one.

@Lembik: I'm having trouble fully understanding property X.  Previously you state that any matrix containing a column of zeros because it is functionally an identity property.  This indicates that the same column can appear in both sets.  If I have column A which is some non-zero column, and column B which consists only of zeros, then the Matrix has property X because S1(A) = S2(A+B).  So the "non-identical indices" property is met by any difference between the sets?  Is the number of columns in each comparison set limited to 2, or can it be larger?

@CChak Yes the same column can appear in both sets. The two sets don't have to be disjoint, just not-identical (because that would trivially be uninteresting). The number of columns in each comparison set can be as large as you like.

@Lembik: Thanks for the quick response, but  I hit return and it posted before I was done.  The real question I was getting to was is there a limit on the number of columns in the summation set?  or is it simply 1 or 2?  I am assuming that each column index can be used once and only once per set.  Again because that would make the problem uninteresting.

@CChak I also replied to that I think (after an edit). Is it clear now?

Yep.  I've got it.  thanks!

For the vector sum, since the matrix is binary, is the addition also performed in the binary system? For example, is 1 + 1 == 2 or 1 + 1 == 0?

@RetroKoradi 1+1=2

C++, Score 23/12 25/13 27/14 28/14 31/15
Finally a result with ratio > 2:
rows=15,cols=31
1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0
1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1
1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1
1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0
1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1
0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1
0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1
1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1
0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0
0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0
1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1
0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0
0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0
1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1

I completely explored 1 to 14 rows. 15 would take too long to completely explore. The results are:
1/1   = 1
2/2   = 1
4/3   = 1.333
5/4   = 1.25
7/5   = 1.4
9/6   = 1.5
12/7  = 1.714
14/8  = 1.75
16/9  = 1.778
18/10 = 1.8
20/11 = 1.818
23/12 = 1.917
25/13 = 1.923
28/14 = 2

The code given below is an older version of the program. The newest version is at https://github.com/thospel/personal-propertyX.
/*
  Compile using something like:
    g++ -Wall -O3 -march=native -fstrict-aliasing -std=c++11 -g propertyX.cpp -lpthread -o propertyX
*/
#include <cstdint>
#include <climits>
#include <ctgmath>
#include <iostream>
#include <vector>
#include <array>
#include <chrono>
#include <mutex>
#include <atomic>
#include <thread>

using namespace std;

const int ELEMENTS = 2;

using uint    = unsigned int;
using Element = uint64_t;
using Column  = array<Element, ELEMENTS>;
using Set     = vector<Column>;
using Sum     = uint8_t;
using Index   = uint32_t;
using sec = chrono::seconds;

int const PERIOD = 5*60;
int const MAX_ROWS = 54;
int const COL_FACTOR = (MAX_ROWS+1) | 1;                // 55
int const ROW_ZERO   = COL_FACTOR/2;                    // 27
int const ROWS_PER_ELEMENT = CHAR_BIT * sizeof(Element) / log2(COL_FACTOR); //11
Element constexpr ELEMENT_FILL(Element v = ROW_ZERO, int n = ROWS_PER_ELEMENT) {
    return n ? ELEMENT_FILL(v, n-1) * COL_FACTOR + v : 0;
}
Element constexpr POWN(Element v, int n) {
    return n ? POWN(v, n-1)*v : 1;
}
Element const ELEMENT_TOP = POWN(COL_FACTOR, ROWS_PER_ELEMENT -1);
int const MAX_COLS = ROWS_PER_ELEMENT * ELEMENTS;       // 22

atomic<Index> col_next;
atomic<uint>  period;
chrono::steady_clock::time_point start;
mutex period_mutex;

uint ratio_row;
uint ratio_col;
mutex ratio_mutex;

auto const nr_threads = thread::hardware_concurrency();
// auto const nr_threads = 1;

struct State {
    State(uint cols);
    void process(Index i);
    void extend(uint row);
    void print(uint rows);
    Index nr_columns() const { return static_cast<Index>(1) << cols_; }

    Column last_;
    Element top_;
    int top_offset_;
    uint ratio_row_ = 0;
    uint ratio_col_ = 1;
    uint cols_;
    array<Sum, MAX_ROWS + MAX_COLS -1> side;
    vector<Set> sets;
};

ostream& operator<<(ostream& os, Column const& column) {
    for (int i=0; i<ELEMENTS; ++i) {
        auto v = column[i];
        for (int j=0; j<ROWS_PER_ELEMENT; ++j) {
            auto bit = v / ELEMENT_TOP;
            cout << " " << bit;
            v -= bit * ELEMENT_TOP;
            v *= COL_FACTOR;
        }
    }
    return os;
}

State::State(uint cols) : cols_{cols} {
    sets.resize(MAX_ROWS+2);
    for (int i=0; i<2; ++i) {
        sets[i].resize(2);
        for (int j=0; j < ELEMENTS; ++j) {
            sets[i][0][j] =  ELEMENT_FILL();
            sets[i][1][j] =  static_cast<Element>(-1) - ELEMENT_FILL(1);
        }
    }
    top_ = POWN(COL_FACTOR, (cols_-1) % ROWS_PER_ELEMENT);
    top_offset_ = ELEMENTS - 1 - (cols_-1) / ROWS_PER_ELEMENT;
}

void State::print(uint rows) {
    for (auto c=0U; c<cols_;c++) {
        for (auto r=0U; r<rows;r++) {
            cout << static_cast<int>(side[cols_-c+r-1]) << " ";
        }
        cout << "\n";
    }
    cout << "----------" << endl;
}

void check(uint cols, uint t) {
    State state(cols);

    Index nr_columns = state.nr_columns();
    while (1) {
        Index col = col_next++;
        if (col >= nr_columns) break;
        state.process(col);

        auto now = chrono::steady_clock::now();
        auto elapsed = chrono::duration_cast<sec>(now-start).count();
        if (elapsed >= period) {
            lock_guard<mutex> lock{period_mutex};
            if (elapsed >= period) {
                cout << "col=" << col << "/" << nr_columns << " (" << 100.*col/nr_columns << "% " << elapsed << " s)" << endl;
                period = (elapsed/PERIOD+1)*PERIOD;
            }
        }
    }
}

void State::process(Index col) {
    last_.fill(0);
    for (uint i=0; i<cols_; ++i) {
        Element bit = col >> i & 1;
        side[i] = bit;
        Element carry = 0;
        for (int j=0; j<ELEMENTS; ++j) {
            auto c = last_[j] % COL_FACTOR;
            last_[j] = last_[j] / COL_FACTOR + carry * ELEMENT_TOP;
            if (j == top_offset_ && bit) last_[j] += top_;
            carry = c;
        }
    }
    // cout << "col=" << col << ", value=" << last_ << "\n";
    extend(0);
}

void State::extend(uint row) {
    // cout << "Extend row " << row << " " << static_cast<int>(side[cols_+row-1]) << "\n";
    if (row >= MAX_ROWS) throw(range_error("row out of range"));

    // Execute subset sum. The new column is added to set {from} giving {to}
    // {sum} is the other set.
    auto const& set_from = sets[row];
    auto const& set_sum  = sets[row + 1];
    auto      & set_to   = sets[row + 2];
    if (set_to.size() == 0) {
        auto size = 3 * set_from.size() - 2;
        set_to.resize(size);
        for (int j=0; j<ELEMENTS; ++j)
            set_to[size-1][j] = static_cast<Element>(-1) - ELEMENT_FILL(1);
    }

    // Merge sort {set_from - last_} , {set_from} and {set_from + last_}
    auto ptr_sum    = &set_sum[1][0];
    auto ptr_low    = &set_from[0][0];
    auto ptr_middle = &set_from[0][0];
    auto ptr_high   = &set_from[0][0];
    Column col_low, col_high;
    for (int j=0; j<ELEMENTS; ++j) {
        col_low   [j] = *ptr_low++  - last_[j];
        col_high  [j] = *ptr_high++ + last_[j];
    }

    auto ptr_end = &set_to[set_to.size()-1][0];
    auto ptr_to  = &set_to[0][0];
    while (ptr_to < ptr_end) {
        for (int j=0; j<ELEMENTS; ++j) {
            if (col_low[j] < ptr_middle[j]) goto LOW;
            if (col_low[j] > ptr_middle[j]) goto MIDDLE;
        }
        // low == middle
        // cout << "low == middle\n";
        return;

      LOW:
        // cout << "LOW\n";
        for (int j=0; j<ELEMENTS; ++j) {
            if (col_low[j] < col_high[j]) goto LOW0;
            if (col_low[j] > col_high[j]) goto HIGH0;
        }
        // low == high
        // cout << "low == high\n";
        return;

      MIDDLE:
        // cout << "MIDDLE\n";
        for (int j=0; j<ELEMENTS; ++j) {
            if (ptr_middle[j] < col_high[j]) goto MIDDLE0;
            if (ptr_middle[j] > col_high[j]) goto HIGH0;
        }
        // middle == high
        // cout << "middle == high\n";
        return;

      LOW0:
        // cout << "LOW0\n";
        for (int j=0; j<ELEMENTS; ++j) {
            *ptr_to++  = col_low[j];
            col_low[j] = *ptr_low++ - last_[j];
        }
        goto SUM;

      MIDDLE0:
        // cout << "MIDDLE0\n";
        for (int j=0; j<ELEMENTS; ++j)
            *ptr_to++ = *ptr_middle++;
        goto SUM;

      HIGH0:
        // cout << "HIGH0\n";
        for (int j=0; j<ELEMENTS; ++j) {
            *ptr_to++ = col_high[j];
            col_high[j] = *ptr_high++ + last_[j];
        }
        goto SUM;
      SUM:
        for (int j=-ELEMENTS; j<0; ++j) {
            if (ptr_to[j] > ptr_sum[j]) {
                ptr_sum += ELEMENTS;
                goto SUM;
            }
            if (ptr_to[j] < ptr_sum[j]) goto DONE;
        }
        // sum == to
        for (int j=-ELEMENTS; j<0; ++j)
            if (ptr_to[j] != ELEMENT_FILL()) {
                // sum == to and to != 0
                // cout << "sum == to\n";
                // cout << set_sum[(ptr_sum - &set_sum[0][0])/ELEMENTS-1] << "\n";
                return;
            }
      DONE:;
    }
    // cout << "Wee\n";
    auto row1 = row+1;
    if (0)
        for (uint i=0; i<row1+2; ++i) {
            cout << "Set " << i << "\n";
            auto& set = sets[i];
            for (auto& column: set)
                cout << column << "\n";
        }

    if (row1 * ratio_col_ > ratio_row_ * cols_) {
        ratio_row_ = row1;
        ratio_col_ = cols_;
        lock_guard<mutex> lock{ratio_mutex};

        if (ratio_row_ * ratio_col > ratio_row * ratio_col_) {

            auto now = chrono::steady_clock::now();
            auto elapsed = chrono::duration_cast<sec>(now-start).count();
            cout << "cols=" << cols_ << ",rows=" << row1 << " (" << elapsed << " s)\n";
            print(row1);
            ratio_row = ratio_row_;
            ratio_col = ratio_col_;
        }
    }

    auto last = last_;

    Element carry = 0;
    for (int j=0; j<ELEMENTS; ++j) {
        auto c = last_[j] % COL_FACTOR;
        last_[j] = last_[j] / COL_FACTOR + carry * ELEMENT_TOP;
        carry = c;
    }

    side[cols_+row] = 0;
    extend(row1);

    last_[top_offset_] += top_;
    side[cols_+row] = 1;
    extend(row1);

    last_ = last;
}

void my_main(int argc, char** argv) {
    if (!col_next.is_lock_free()) cout << "col_next is not lock free\n";
    if (!period.  is_lock_free()) cout << "period is not lock free\n";

    int min_col = 2;
    int max_col = MAX_COLS;
    if (argc > 1) {
        min_col = atoi(argv[1]);
        if (min_col < 2)
            throw(range_error("Column must be >= 2"));
        if (min_col > MAX_COLS)
            throw(range_error("Column must be <= " + to_string(MAX_COLS)));
    }
    if (argc > 2) {
        max_col = atoi(argv[2]);
        if (max_col < min_col)
            throw(range_error("Column must be >= " + to_string(min_col)));
        if (max_col > MAX_COLS)
            throw(range_error("Column must be <= " + to_string(MAX_COLS)));
    }

    for (int cols = min_col; cols <= max_col; ++cols) {
        cout << "Trying " << cols << " columns" << endl;
        ratio_row = 0;
        ratio_col = 1;
        col_next = 0;
        period = PERIOD;
        start = chrono::steady_clock::now();
        vector<thread> threads;
        for (auto t = 1U; t < nr_threads; t++)
            threads.emplace_back(check, cols, t);
        check(cols, 0);
        for (auto& thread: threads)
            thread.join();
    }
}

int main(int argc, char** argv) {
    try {
        my_main(argc, argv);
    } catch(exception& e) {
        cerr << "Error: " << e.what() << endl;
        exit(EXIT_FAILURE);
    }
    exit(EXIT_SUCCESS);
}

This is great. The great mystery is if you can ever get a score of 2.

By extrapolation, 28/14 ought to exist I think which would be really exciting. But is it just out of reach?

n=14 would take about 200 days with my current code on my 8-core CPU. The code can probably be sped up by 30% or so. After that I run out of ideas. And your extrapolation seems rather optimistic anyways...

I think the circulant 50 by 25 matrix with first row 01011011100010111101000001100111110011010100011010 might work.  This was found by an optimization heuristic which might be useful.

140 hours for exhaustive cover of n=14 is very impressively fast I have to say.

This is pretty amazing. How did you do it?

Haskell 14/8 = 1.75
1 1 0 0 0 1 0 1 1 0 1 1 0 0
1 1 1 0 0 0 1 0 1 1 0 1 1 0
0 1 1 1 0 0 0 1 0 1 1 0 1 1
1 0 1 1 1 0 0 0 1 0 1 1 0 1
0 1 0 1 1 1 0 0 0 1 0 1 1 0
0 0 1 0 1 1 1 0 0 0 1 0 1 1
0 0 0 1 0 1 1 1 0 0 0 1 0 1
0 0 0 0 1 0 1 1 1 0 0 0 1 0

Previously 9/6 = 1.5
1 0 1 0 1 1 0 0 1
1 1 0 1 0 1 1 0 0
1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1
1 1 1 1 1 0 1 0 1
1 1 1 1 1 1 0 1 0

I wrote this, then looked at the answers to the other question and was... discouraged.
import Data.List
import Data.Hashable
import Control.Monad
import Control.Parallel.Strategies
import Control.Parallel
import qualified Data.HashSet as S

matrix§indices = [ matrix!!i | i<-indices ]

powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])

hashNub :: (Hashable a, Eq a) => [a] -> [a]
hashNub l = go S.empty l
    where
      go _ []     = []
      go s (x:xs) = if x `S.member` s
        then go s xs
        else x : go (S.insert x s) xs

getMatrix :: Int -> Int -> [Int] -> [[Int]]
getMatrix width height vector = [ vector § [x..x+width-1] | x<-[0..height-1] ]

hasDuplicate :: (Hashable a, Eq a) => [a] -> Bool
hasDuplicate m = go S.empty m
    where
        go _ [] = False
        go s (x:xs) = if x `S.member` s
            then True
            else go (S.insert x s) xs

hasProperty :: [[Int]] -> Bool
hasProperty matrix =
    let
        base = replicate (length (matrix !! 0)) 0::[Int]
    in
        if elem base matrix then
            False
        else
            if hasDuplicate matrix then
                False
            else
                if hasDuplicate (map (foldl (zipWith (+)) base) (powerset matrix)) then
                    False
                else
                    True

pmap = parMap rseq

matricesWithProperty :: Int -> Int -> [[[Int]]]
matricesWithProperty n m =
    let
        base = replicate n 0::[Int]
    in
    filter (hasProperty) $
    map (getMatrix n m) $
    sequence [ [0,1] | x<-[0..n+m-1] ]

firstMatrixWithProperty :: Int -> Int -> [[Int]]
firstMatrixWithProperty n m = head $ matricesWithProperty n m

main = mapM (putStrLn. show) $ map (firstMatrixWithProperty 8) [1..]

Thank you! A Haskell answer is always very welcome. I think the first interesting case is 12/7. Can you get that?

I was running it on a dual-core 2009 laptop, so no :) I'll try again on a faster machine though

Very nice.  I just added a comment that 21/11 would beat all previous answers.

Could you explain what your code outputs exactly please?

In main, the number (in this case 8) is the height of the matrix, and the program iterates through widths [1..]. For each height/width combination, it prints out an array of columns of a valid matrix.

I awarded you the bounty as the best new answer. Congratulations :)

C
Here's an answer which works and is significantly more memory-efficient than the Haskell. Unfortunately, my computer is still too slow to achieve better than 14/8 in any reasonable length of time.
Try compiling with gcc -std=c99 -O2 -fopenmp -o matrices.exe matrices.c and running with matrices.exe width height or similar. The output is an integer, the bits of which form the basis for the matrix in question, for instance:
$ matrices.exe 8 14
...
valid i: 1650223

Then, since 1650223 = 0b110010010111000101111, the matrix in question is:
0 0 1 1 1 0 1 0 0 1 0 0 1 1
0 ...
1 ...
0
1
1
1
1

If someone with 8 cores and time on their hands wants to run this for a while, I think some good things could result :)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/*
 * BEGIN WIKIPEDIA CODE
 */
const long long m1  = 0x5555555555555555; //binary: 0101...
const long long m2  = 0x3333333333333333; //binary: 00110011..
const long long m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const long long m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const long long m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const long long m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const long long hff = 0xffffffffffffffff; //binary: all ones
const long long h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...
//This uses fewer arithmetic operations than any other known
//implementation on machines with fast multiplication.
//It uses 12 arithmetic operations, one of which is a multiply.
long long hamming(long long x) {
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
    return (x * h01)>>56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}
/*
 * END WIKIPEDIA CODE
 */

int main ( int argc, char *argv[] ) {
    int height;
    int width;

    sscanf(argv[1], "%d", &height);
    sscanf(argv[2], "%d", &width);

    #pragma omp parallel for
    for (
        /*
         * We know that there are 2^(h+w-1) T-matrices, defined by the entries
         * in the first row and first column. We'll let the long long i
         * represent these entries, with 1s represented by set bits.
         *
         * The first (0) and last (1) matrix we will ignore.
         */
        long long i = 1;
        i < (1 << (height+width-1))-1;
        i++
    ) {
        // Flag for keeping track as we go along.
        int isvalid = 1;

        /*
         * Start by representing the matrix as an array of columns, with each
         * non-zero matrix entry as a bit. This allows us to construct them and
         * check equality very quickly.
         */
        long *cols = malloc(sizeof(long)*width);
        long colmask = (1 << height)-1;
        for (int j = 0; j < width; j++) {
            cols[j] = (i >> j) & colmask;
            if (cols[j] == 0) {
                //check no zero rows
                isvalid = 0;
            } else {
                //check no duplicate rows
                for (int k = 0; k < j; k++) {
                    if (cols[j] == cols[k]) {
                        isvalid = 0;
                    }
                }
            }
        }

        if (isvalid == 1) {
            /*
             * We'll also represent the matrix as an array of rows, in a
             * similar manner.
             */
            long *rows = malloc(sizeof(long)*height);
            long rowmask = (1 << width)-1;
            for (int j = 0; j < height; j++) {
                rows[j] = (i >> j) & rowmask;
            }

            int *sums[(1 << width)];
            for (long j = 0; j < 1<<width; j++) {
                sums[j] = (int*)malloc(sizeof(int)*height);
            }

            for (
                /*
                 * The powerset of columns has size 2^width. Again with the
                 * long; this time each bit represents whether the
                 * corresponding row is a member of the subset. The nice thing
                 * about this is we can xor the permutation with each row,
                 * then take the hamming number of the resulting number to get
                 * the sum.
                 */
                long permutation = 1;
                (isvalid == 1) && (permutation < (1 << width)-1);
                permutation ++
            ) {
                for (int j = 0; j < height; j++) {
                    sums[permutation][j] = hamming( rows[j] & permutation);
                }
                for (int j = permutation-1; (isvalid == 1) && (j > -1); j--) {
                    if (memcmp(sums[j], sums[permutation], sizeof(int)*height) == 0) {
                        isvalid = 0;
                    }
                }
            }

            for (long j = 0; j < 1<<width; j++) {
                free(sums[j]);
            }

            free(rows);

        }

        if (isvalid == 1) {
            printf ("valid i: %ld\n", i);
        }

        free(cols);
    }

    return 0;
}

I get alexander-brett.c: In function ‘main’:
alexander-brett.c:107:21: warning: implicit declaration of function ‘memcmp’ [-Wimplicit-function-declaration]
if (memcmp(sums[j], sums[permutation], sizeof(int)*height) == 0) {
^
alexander-brett.c:122:13: warning: format ‘%ld’ expects argument of type ‘long int’, but argument 2 has type ‘long long int’ [-Wformat=]
printf ("valid i: %ld\n", i);

How long does ./alexander-brett 8 14 take for you?

Hi Lembik, 8 14 got 5 answers in an hour for me on a quad core machine. I managed to compile with those headers on windows, it'd be wierd if memcmp went missing...

http://stackoverflow.com/questions/7132039/implicit-declaration-of-memcmp-is-invalid-in-c99

I tried your code with 7 12 and one of the answers it outputs is valid i: 7481. In python bin(7481) is 0b1110100111001 which isn't long enough. Any idea what is going on?

Huh, that's pretty upsetting... possible it's supposed to start with a 0, ie 0b01110100111001?

It's worse than an out by one problem. Could you maybe try it yourself to see?


text:
Generating Euclidean rhythms
Did you know that the Euclidean algorithm is capable of generating traditional musical rhythms? We'll see how this works by describing a similar, but slightly different algorithm to that in the paper.
Pick a positive integer n, the total number of beats, and a positive integer k, the number of beats which are sounded (notes). We can think of the rhythm as a sequence of n bits, k of which are 1s. The idea of the algorithm is to distribute the 1s as evenly as possible amongst the 0s.
For example, with n = 8 and k = 5, we start with 5 ones and 3 zeroes, each in its own sequence:
[1] [1] [1] [1] [1] [0] [0] [0]

At any point we will have two types of sequences — the ones at the start are the "core" sequences and the ones at the end are the "remainder" sequences. Here the cores are [1]s and the remainders are [0]s. As long as we have more than one remainder sequence, we distribute them amongst the cores:
[1 0] [1 0] [1 0] [1] [1]

Now the core is [1 0] and the remainder is [1], and we distribute again:
[1 0 1] [1 0 1] [1 0]

Now the core is [1 0 1] and the remainder is [1 0]. Since we only have one remainder sequence, we stop and get the string
10110110

This is what it sounds like, repeated 4 times:

Here's another example, with n = 16 and k = 6:
[1] [1] [1] [1] [1] [1] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0]
[1 0] [1 0] [1 0] [1 0] [1 0] [1 0] [0] [0] [0] [0]
[1 0 0] [1 0 0] [1 0 0] [1 0 0] [1 0] [1 0]
[1 0 0 1 0] [1 0 0 1 0] [1 0 0] [1 0 0]
[1 0 0 1 0 1 0 0] [1 0 0 1 0 1 0 0]
1001010010010100

Note how we terminated on the last step with two core sequences and no remainder sequences. Here it is, repeated twice:

Input
You may write a function or a full program reading from STDIN, command line or similar. Input will be two positive integers n and k <= n, which you may assume is in either order.
Output
Your task is to output the generated rhythm as an n character long string. You may pick any two distinct printable ASCII characters (0x20 to 0x7E) to represent notes and rests.
Test cases
The following test cases use x to represent notes and .s to represent rests. Input is given in the order n, then k.
1 1    ->  x
3 2    ->  xx.
5 5    ->  xxxxx
8 2    ->  x...x...
8 5    ->  x.xx.xx.
8 7    ->  xxxxxxx.
10 1   ->  x.........
11 5   ->  x.x.x.x.x..
12 7   ->  x.xx.x.xx.x.
16 6   ->  x..x.x..x..x.x..
34 21  ->  x.xx.x.xx.xx.x.xx.x.xx.xx.x.xx.x.x
42 13  ->  x...x..x..x..x...x..x..x..x...x..x..x..x..
42 18  ->  x..x.x.x..x.x.x..x.x.x..x.x.x..x.x.x..x.x.

Scoring
This is code-golf, so the code in the fewest bytes wins.

CJam, 37 34 30 27 24 bytes
3 bytes saved by user23013.
q~,f>{_(a-W<}{e`:a:e~z}w

This takes the input as k first, n second. It uses 1 and 0 to indicate notes and rests, respectively.
Try it here. Alternatively, here is a test harness which runs all of the given test cases (swapping the input order) and also reformats the output to use x and . for easier comparison with the reference solutions. (The results appearing in the input of the test harness are discarded before running the code. They could be safely removed without affecting the program.)
Explanation
q~                       e# Read and eval the input, dumping k and n on the stack.
  ,                      e# Create a range [0 .. n-1]
   f>                    e# For each of them, check if it's less than k.
                         e# This gives k 1s and n-k 0s.
     {      }{        }w e# While the first block yields a truthy result, execute
                         e# the second block.
      _                  e# Duplicate the array.
       (a-               e# Remove all instances of core sequences.
          W<             e# Remove one remainder sequence if there is one. This
                         e# gives an empty array (falsy) whenever there are less
                         e# than two remainder sequences.
              e`         e# Run-length encode. I.e. this turns an array into a list
                         e# of pairs of run-length and element.
                :a:e~    e# Wrap each RLE pair in an array and RLD it. This
                         e# partitions the array into cores and remainders.
                     z   e# Zip the two parts, interleaving cores and remainders.

This process very deeply nested arrays, but the important part is that all cores (and all remainders) always have the same nested structure, so they are still  equal to each other. CJam automatically prints the stack contents at the end of the program and omits array delimiters entirely, hence this structure does not affect the output either.

2 or 3 bytes shorter: q~\,f>.

@user23013 Oh, that's neat! Thank you. :)

For 3 bytes, I meant input can be in either order.

@user23013 Oh right, I forgot about that.

Haskell, 125 bytes
r=replicate
g z(a:b)(c:d)=g((a++c):z)b d
g z x y=(z,x++y)
f(x,y)|length y>1=f$g[]x y|1<2=concat$x++y
n#k=f(r k "x",r(n-k)".")

Usage example: 42 # 13 -> x...x..x..x..x...x..x..x..x...x..x..x..x...
f takes two parameters: core and remainder list. It either zips both lists (via g) and calls itself again or stops if the remainder is too short. The main function # creates the starting lists and calls f.

Python, 85
f=lambda n,k,a='1',b='0':n-k<2and a*k+b*(n-k)or[f(n-k,k,a+b,b),f(k,n-k,a+b,a)][2*k>n]

The natural recursive solution. The parameters (n,k,a,b) represent a core of k a's followed by a remainder of n-k b's.
This solution is inefficient because both recursive calls to f are evaluated, causing an exponential number of calls.
I tried to compress the conditional invocation of f like
f(max(n-k,k),min(n-k,k),a+b,[a,b][2*k<n])
f(*[n-k,k,k,n-k,b,a][2*k>n::2]+[a+b])

but none turned out shorter.