text:
Generate a Brainf_ck program that outputs a string of given length
Your friend is trying to break into a vault that has a peculiar locking system: it requires a certain number of gentle knocks in a particular spot. Your friend discovered the number (which is in the range 1...99999) and possesses a gadget that produces the required knocks. However, the gadget is a Brainfuck interpreter! So your friend needs to feed it a Brainfuck program, which, obviously, should be as short as possible (the gadget's I/O is slow).
Your task is to help him! Write a program or a subroutine, in any language, that accepts as input a number N, and outputs a Brainfuck program, which takes no input and outputs a string of printable ASCII characters (excluding the space character - codes in the range 33...126) of length N.
Example: for input 10, the output might be
+++++++++++++++++++++++++++++++++..........

(but I am sure it can be shortened!)
Your score will be the sum of lengths of your outputs for the following values of N (they are random numbers):
55
68
15
28
841
838
522
846
4898
9004
9363
3810
13230
67175
37231
44701

Oh, and you will be transmitting your code (the generator program) to your friend by Twitter. So make sure it's 140 characters or less!

P.S. The Brainfuck language has many variants. Let's assume the tape is infinite in both directions (or "circular and large enough"), and the cells have 32-bit int capacity (finite and able to hold numbers up to 99999). Also, no wrapping: when a cell overflows, the machine self-destructs!

"following values of N (they are random numbers)"
reminded me of http://xkcd.com/221/

Just for reference, the space character (character code 32) is usually included in the printable ASCII range. It doesn't really make a difference for the challenge since you've defined the range explicitly though.

Can we assume cells in brainfuck to be arbitrary width integers? If not, how and when do they wrap?

It would be nice to assume at least being able to contain 67175 + a few.

@anatolyg I realized that later. Sorry.

Python 2, score: 1021
I've just realized that this contest is pretty old but still, since I came up with a better solution than those posted, I posted it as well.
Here's a 102 byte python script that does the job:
n=input()
s='>'
while n:
    s+='>'+'+'*(n%5+1);n/=5
print s+'[->[-<+++++>]<<]<+++++++[>+++++<-]>>[-<.>]'

The idea is to use base 5 encoding for N (best base at least for the current inputs, which do not seem very "random" by the way, looks like they were arbitrarily chosen by OP), and to write a generic Brainfuck algorithm to decode a number of arbitrary length (the number is encoded with each digit increased by one in order to detect the end of conversion). I chose to print character 35 #, character 36 $ is equivalent.
You may run the following bash script to get the score:
i=0
while read p; do
  i=$((i+`echo $p | python convert.py | wc -m`))
done
echo $i

With a more advanced program that replaces encoding with multiplication for small numbers and chooses the best base for encoding each number, I can reach 958 Brainfuck characters, but Python is far too verbose (and I'm a pretty bad/lazy golfer) in order to get the converter into 144 bytes!

This is a great idea! Maybe I'll use it once to improve this answer (wrote a script in Python to get score less than 950, but I don't know any golfing language to make it short enough).

BrainF***, score: 193,313
It's not under 140 characters (it's 147, so close!!), so this can't win, but I thought it was cool.
Prints 43 plus signs, then N periods. Not very optimal.
>++++++[>+++++++<-]>+[->+>+<<]>[->.<]<<+[[-]>[-],[+[-----------[>[-]++++++[<------>-]<--<<[->>++++++++++<<]>>[-<<+>>]<+>]]]<]>>>+++<<<<[>>>>.<<<<-]

If anyone can help shorten this I would love it.

I guess with Brainfuck it would be enough to make a "subroutine" that receives its input on the tape - no need to read from "standard input device".

@anatolyg That makes it much easier - probably about 80 or 90 characters. Should I change it?

J, Total score = 1481
(For my previous entry and explanation check revision history.)
f10=.('>++++++++++<';'')rplc~;@([:(<@('+++++[>+++++++<-]>>+',;@((<'[>++++++++++')#~#)),[<@(']',~'<-','<.>'#~],[,])"0 #-i.@# )10#.inv])

This function generates nested BF loops based on the base10 digits of the input number. Checking all reasonable bases and choosing the smallest BF code would improve the score with a small amount.
BF programs for the test set:
   f10 every 55 68 15 28 841 838 522 846 4898 9004 9363 3810 13230 67175 37231 44701
+++++[>+++++++<-]>>+[>++++++++++[-<<.....>>]<-<.....>]
+++++[>+++++++<-]>>+[>++++++++++[-<<......>>]<-<........>]
+++++[>+++++++<-]>>+[>++++++++++[-<<.>>]<-<.....>]
+++++[>+++++++<-]>>+[>++++++++++[-<<..>>]<-<........>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[-<<<........>>>]<-<<....>>]<-<.>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[-<<<........>>>]<-<<...>>]<-<........>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[-<<<.....>>>]<-<<..>>]<-<..>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[-<<<........>>>]<-<<....>>]<-<......>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[-<<<<....>>>>]<-<<<........>>>]<-<<.........>>]<-<........>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[-<<<<.........>>>>]<-<<<>>>]<-<<>>]<-<....>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[-<<<<.........>>>>]<-<<<...>>>]<-<<......>>]<-<...>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[-<<<<...>>>>]<-<<<........>>>]<-<<.>>]<-<>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[>++++++++++[-<<<<<.>>>>>]<-<<<<...>>>>]<-<<<..>>>]<-<<...>>]<-<>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[>++++++++++[-<<<<<......>>>>>]<-<<<<.......>>>>]<-<<<.>>>]<-<<.......>>]<-<.....>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[>++++++++++[-<<<<<...>>>>>]<-<<<<.......>>>>]<-<<<..>>>]<-<<...>>]<-<.>]
+++++[>+++++++<-]>>+[>++++++++++[>++++++++++[>++++++++++[>++++++++++[-<<<<<....>>>>>]<-<<<<....>>>>]<-<<<.......>>>]<-<<>>]<-<.>]

Computing score on the test set:
   +/#@> f10 each 55 68 15 28 841 838 522 846 4898 9004 9363 3810 13230 67175 37231 44701
1481

Pyth, 1702
Reconstruct numbers using factors of N + x.
+holN+]++">>"*"+"Q"<<"mjk(">>"j">"m*"+"kP+Qd"<[[->[->+>+<<]>>[-<<+>>]<<<]>[-]>[-<<+>>]<<<]>"*"-"d"<<")50"++++++[>++++++<-]>>[<.>-]"

For 2 this outputs ++. now which doesn't print anything in BF.

@randomra Good catch, this happened while updating, I'll fix it, give me a few.

@randomra Should be fixed, made the score slightly higher (of course).

CJam, 52 74 108 bytes, total = 1304 1244 1210
ri5b_,1>{(_3<{\(@5*+}*\+}*W%)\{T+_2>:T5*-_0>"-+"=\z*}%\T+'+*a+W%{"[->+++++<]>"\}*">x[>x<-]<[->>.<<]"'x/'+6**

A test script (slow in the online interpreter):
q~]
{
_[0:T;
5b_,1>{(_3<{\(@5*+}*\+}*W%)\{T+_2>:T5*-_0>"-+"=\z*}%\T+'+*a+W%{"[->+++++<]>"\}*">x[>x<-]<[->>.<<]"'x/'+6**
]s
_[L:RL@0\
"-+><.]"['('){+\_{)}0?@\}{@\+\_{)}0?}{R1$c+:R;}]:`"]a"{{_aa+1$4G#%{:~~1}{;0}?}g}`+a+er:~:~
];R,@=!"Error."N+*o
}%s,

I didn't see the part about self-destruction. But it will never overflow anyway.

How does it work?

@anatolyg The first version simply generate the number in base 5. Later versions added a special case for the first two digits and also used decrement.

@user23013 Oh, sorry, haven't seen the spec changes. (Updated my answer accordingly.)

Befunge-98, N + 41, total = 193281
&>'+\:v
v^-1,\_
' >1-:v
>v^,+'_
,'    :
>ff3++^
>2f*+v
^>/9+:,
>'>,61v
, v*6+<
^/2,:<@
v >+2+,
>'<,']^

I know it's bad, but I felt like writing some Befunge today. The best part of Befunge is that the programs are even less understandible than the actual golf languages, especially when they reuse code :D
Uses a similar algorithm to Martin Büttner's CJam answer:
(N +'s)>+++++++++++++++++++++++++++++++++<[->.<]

CJam, 40 + N, Total: 193265
'+33*'>'+l~*"[<.>-]"

Just to get this started, here is the baseline solution. It generates the following code:
+++++++++++++++++++++++++++++++++>_[<.>-]

where _ is N copies of +.
Run the generator here.

Befunge-93 - 24 + N, total = 193009
&>">>]-<]-<++++>[++++>[+++"v
v  ,,,,,,,,,,,,,,,,,,,,,,, <
>:v
,v_@
"1
.-
"
^<

This uses a prefix of +++[>++++[>++++<-]<-]>> to set the first tape index to '0' with 24 characters.
The Befunge program is very basic and outputs that along with N '.' characters.

Now that I see this I don't know why I was thinking my loop would be any better...


text:
Calculate π with quadratic convergence
Write a function or complete program that takes a positive number n and performs n steps of an iterative algorithm for calculating π that has quadratic convergence (i.e. it approximately doubles the number of accurate digits at every iteration) then returns or prints out 2n correct digits (including the beginning 3). One such algorithm is the Gauss–Legendre algorithm, but you are free to use a different algorithm if you prefer.
Examples:
input 1 → output 3.1
input 2 → output 3.141
input 5 → output 3.1415926535897932384626433832795
Requirements:

Each iteration of the algorithm must perform a constant number of basic operations such as addition, subtraction, multiplication, division, power and root (with integer exponent/degree) - each such operation on "big" integer/decimal numbers is counted as one even if it involves one or more loops internally. To be clear, trigonometric functions and powers involving complex numbers are not basic operations.
The algorithm is expected to have an initialization step which must also have a constant number of operations.
If the algorithm needs 1 or 2 more iterations to get to 2n correct digits, you can perform up to n+2 iterations instead of just n.
If it wasn't clear enough, after the correct 2n digits, your program must not print anything else (such as more correct digits, wrong digits or the complete works of Shakespeare).
Your program must support values of n from 1 to at least 20.
Your program should not take more than an hour for n=20 on a modern computer (not a hard rule, but try to keep it reasonable).
The program must not obtain more than 20 accurate digits after the initialization and first iteration of the algorithm.
The program must be runnable in Linux using freely available software.
The source code must use only ASCII characters.

Scoring:
Straightforward code golf, shortest code wins.
Winner:
The winner is Digital Trauma, I finally finished running his code on n=20 (just kidding). Special prize goes to primo for his very fast python solution and different algorithm :)

Quadratic convergence is error ~ N^(1/2). What you describe is exponential convergence error ~ 2^(-N).

@yo' are you saying that wikipedia is wrong?

@yo' binary digits? What? No, you should compute pi in whatever form you want with 2^n correct decimal digits and output them in decimal representation.

Misleading, at least to say: "quadratic convergence" is ~q^(n^2) according to the 1st section there and ~q^2 according to the 2nd section there.

I don't understand codegolf: surely anyone could just write their own programming language specifically for a single task like this, then write a program of, say, 0 bytes?

@theonlygusti that would be a standard loophole and would get disqualified

@yo' I didn't change the conditions, I only clarified what should have been obvious but apparently wasn't. Also, your answer was not the only one that doesn't meet the requirements.

@yo' exp(I*p).Imag() is just a long-winded way to write sin(p). That this was excluded is evident from the original problem statement. Why not just use acos(-1)?

dc, 99 bytes
Golfed:
2?dsi1+^k1dddsa2v/sb4/stsp[lalb*vlalb+2/dla-d*lp*ltr-stsasblp2*spli1-dsi0<m]dsmxK2/1-klalb+d*4lt*/p

With whitespace and comments for "readability":
2?dsi               # Push 2. push input n, duplicate and store in i
1+^k                # Set calculation precision to 2^(n+1)
1dddsa              # Push four 1s. Store 1st in a
2v/sb               # Store 1/sqrt(2) in b
4/st                # Store 1/4 in t
sp                  # Store 1 in p
[                   # Start iteration loop macro
lalb*v              # Save sqrt(a*b) on stack
lalb+2/d            # Save a[i+1] = (a[i]+b[i])/2 on stack and duplicate
la-d*lp*ltr-        # Save t-p(a[i]-a[i+1])^2 on the stack
st                  # Store t result from stack
sa                  # Store a result from stack
sb                  # Store b result from stack
lp2*sp              # Store 2p in p
li1-dsi0<m]         # Decrement iteration counter i; recurse into macro if < 0
dsmx                # Duplicate, store and run macro
K2/1-k              # Set display precision to 2^n-1
lalb+d*4lt*/        # Save (a+b)^2/4t on stack
p                   # Print result

dc needs to be told how many digits of precision should be used.  The calculation precision needs to be higher than the final display precision, so the calculation precision is set to be 2^(n+1) digits.  I have verified the accuracy of the output with n=10 against http://www.angio.net/pi/digits/pi1000000.txt.
This slows down dramatically for larger n; n=12 takes 1.5 mins on my VM.  Running a few different samples shows the time complexity is O(e^n) (not surprising).  Extrapolating this to n=20 would have a runtime of 233 days.  Oh well.  Better than heat-death-of-the-universe at least.
This is moderately golfed - the stack is used to eliminate temporary variables during the calculations of each iteration, but there is possibly more use of the stack to shorten this more.
$ dc glpi.dc <<< 1
3.1
$ dc glpi.dc <<< 2
3.141
$ dc glpi.dc <<< 5
3.1415926535897932384626433832795
$ time dc glpi.dc <<< 7
3.1415926535897932384626433832795028841971693993751058209749445923078\
164062862089986280348253421170679821480865132823066470938446

real    0m0.048s
user    0m0.039s
sys 0m0.000s
$

If you don't like dc wrapping output at 70 chars, you can set the environment variable DC_LINE_LENGTH to 0:
$ DC_LINE_LENGTH=0 dc glpi.dc <<< 8
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648
$

Haha, "readability." Doesn't really apply to dc. ;)

It seems to print a lot more than 32 digits for input 5

I added a rule for that, plus another one about running time (but not really strict). I also don't like how your output is split into multiple lines with backslashes, is that a limitation of dc?

I'm afraid the output is wrong for n=6

@aditsu Now I think it really should be fixed.   Previously I was trying too hard to speed it up be keeping the precision lower for earlier iterations. This messed up the accuracy for later iterations.  Now the precision is fixed high at the start (2^(n+1)) digits.  This has the unexpected side-effect of speeding it up (no enough though).  Also saved a char, but I still want to get it under 100.

Great, and you got it under 100 too :) Could you also post the actual golfed 99-char program with no whitespace/comments?

@aditsu golfed version added.

R, 156 bytes
Let's get this party started... with the absolute naivest implementation of the Gauss-Legendre algorithm ever.
for(i in 1:scan()){if(i<2){a=p=Rmpfr::mpfr(1,2e6);t=a/4;b=t^t}else{x=(a+b)/2;b=(a*b)^.5;t=t-p*(a-x)^2;a=x;p=2*p};o=(a+b)^2/(4*t)};cat(Rmpfr::format(o,2^i))

Ungolfed + explanation:
# Generate n approximations of pi, where n is read from stdin
for (i in 1:scan()) {

    # Initial values on the first iteration
    if (i < 2) {
        a <- p <- Rmpfr::mpfr(1, 1e7)
        t <- a/4
        b <- t^t
    } else {
        # Compute new values
        x <- (a + b) / 2
        b <- (a*b)^0.5
        t <- t - p*(a - x)^2

        # Store values for next iteration
        a <- x
        p <- 2*p
    }

    # Approximate pi
    o <- (a + b)^2 / (4*t)
}

# Print the result with 2^n digits
cat(Rmpfr::format(o, 2^i))

The mpfr() function is part of the Rmpfr package. It creates an mpfr object using the first argument as the value and the second argument as the number of bits of precision. We assign a and p to 1, and by defining t based on a (and b based on t), the mpfr type propogates to all four variables, thereby maintaining precision throughout.
As mentioned, this requires the R package Rmpfr, which is an acronym for "R Multiple Precision Floating point Reliable." The package uses GMP in the background. Unfortunately base R does not have the ability to do high-precision arithmetic, hence the package dependency.
Don't have Rmpfr? No sweat. install.packages("Rmpfr") and all of your dreams will come true.
Notice that 2e6 was specified as the precision. That means we have 2,000,000 bits of precision, which is enough to maintain precision for at least n = 20. (Note: n = 20 takes a long time but less than an hour on my computer.)
The approach here is literally just a regurgitation of the formulas on the Wikipedia page, but hey, we have to start somewhere.
Any input is welcome as always!

I had to rewrite a lot of this but I still have to acknowledge that Peter Taylor helped me knock 70 bytes off of my first score. In the words of DigitalTrauma, "boom."

Python 2, 214 bytes
This challenge presented a good excuse for me to learn the Decimal module. The Decimal numbers have definable precision and have square root support. I have set the precision to a conservative estimate of the accuracy depending on the loop count.
Update
I have updated the program to improve accuracy and speed, at the expense of
golfing. By using the decimal sqrt() method and replacing the x**2 usage
with x*x, it is now 200 times faster. This means it can now compute 20
loops giving a million digit result in 6.5 hours. The Decimal
numbers often have an error in the last digit (caused by operations on the limit
of precision), so the program now uses and discards 5 extra digits so only accurate digits are printed.
from decimal import*
d=Decimal
e=input()
getcontext().prec=5+(1<<e)
k=d(1)
j=d(2)
g=j*j
h=k/j
a=k
b=k/j.sqrt()
t=k/g
p=k
for i in[0]*e:f=a;a,b=(a+b)/j,(a*b).sqrt();c=f-a;t-=c*c*p;p+=p
l=a+b
print str(l*l/g/t)[:-5]

Sample run:
$ echo 1 | python min.py
3.1
$ echo 2 | python min.py
3.141
$ echo 3 | python min.py
3.1415926
$ echo 5 | python min.py
3.1415926535897932384626433832795
$ echo 12 | python min.py
3.141592653589793238462643383279502884197169399375105820974944592307816406286208
99862803482534211706798214808651328230664709384460955058223172535940812848111745
02841027019385211055596446229489549303819644288109756659334461284756482337867831
65271201909145648566923460348610454326648213393607260249141273724587006606315588
17488152092096282925409171536436789259036001133053054882046652138414695194151160
94330572703657595919530921861173819326117931051185480744623799627495673518857527
24891227938183011949129833673362440656643086021394946395224737190702179860943702
77053921717629317675238467481846766940513200056812714526356082778577134275778960
91736371787214684409012249534301465495853710507922796892589235420199561121290219
60864034418159813629774771309960518707211349999998372978049951059731732816096318
59502445945534690830264252230825334468503526193118817101000313783875288658753320
83814206171776691473035982534904287554687311595628638823537875937519577818577805
32171226806613001927876611195909216420198938095257201065485863278865936153381827
96823030195203530185296899577362259941389124972177528347913151557485724245415069
59508295331168617278558890750983817546374649393192550604009277016711390098488240
12858361603563707660104710181942955596198946767837449448255379774726847104047534
64620804668425906949129331367702898915210475216205696602405803815019351125338243
00355876402474964732639141992726042699227967823547816360093417216412199245863150
30286182974555706749838505494588586926995690927210797509302955321165344987202755
96023648066549911988183479775356636980742654252786255181841757467289097777279380
00816470600161452491921732172147723501414419735685481613611573525521334757418494
68438523323907394143334547762416862518983569485562099219222184272550254256887671
79049460165346680498862723279178608578438382796797668145410095388378636095068006
42251252051173929848960841284886269456042419652850222106611863067442786220391949
45047123713786960956364371917287467764657573962413890865832645995813390478027590
09946576407895126946839835259570982582262052248940772671947826848260147699090264
01363944374553050682034962524517493996514314298091906592509372216964615157098583
87410597885959772975498930161753928468138268683868942774155991855925245953959431
04997252468084598727364469584865383673622262609912460805124388439045124413654976
27807977156914359977001296160894416948685558484063534220722258284886481584560285
06016842739452267467678895252138522549954666727823986456596116354886230577456498
03559363456817432411251507606947945109659609402522887971089314566913686722874894
05601015033086179286809208747609178249385890097149096759852613655497818931297848
21682998948722658804857564014270477555132379641451523746234364542858444795265867
82105114135473573952311342716610213596953623144295248493718711014576540359027993
44037420073105785390621983874478084784896833214457138687519435064302184531910484
81005370614680674919278191197939952061419663428754440643745123718192179998391015
91956181467514269123974894090718649423196156794520809514655022523160388193014209
37621378559566389377870830390697920773467221825625996615014215030680384477345492
02605414665925201497442850732518666002132434088190710486331734649651453905796268
56100550810665879699816357473638405257145910289706414011097120628043903975951567
71577004203378699360072305587631763594218731251471205329281918261861258673215791
98414848829164470609575270695722091756711672291098169091528017350671274858322287
18352093539657251210835791513698820914442100675103346711031412671113699086585163
98315019701651511685171437657618351556508849099898599823873455283316355076479185
35893226185489632132933089857064204675259070915481416549859461637180270981994309
92448895757128289059232332609729971208443357326548938239119325974636673058360414
28138830320382490375898524374417029132765618093773444030707469211201913020330380
19762110110044929321516084244485963766983895228684783123552658213144957685726243
34418930396864262434107732269780280731891544110104468232527162010526522721116603
96665573092547110557853763466820653109896526918620564769312570586356620185581007
29360659876486117

The ungolfed code:
from decimal import *
d = Decimal

loops = input()
# this is a conservative estimate for precision increase with each loop:
getcontext().prec = 5 + (1<<loops)

# constants:
one = d(1)
two = d(2)
four = two*two
half = one/two

# initialise:
a = one
b = one / two.sqrt()
t = one / four
p = one

for i in [0]*loops :
    temp = a;
    a, b = (a+b)/two, (a*b).sqrt();
    pterm = temp-a;
    t -= pterm*pterm * p;
    p += p

ab = a+b
print str(ab*ab / four / t)[:-5]

Heh half = one/two

It seems that you're not printing the correct number of digits. And I wonder if the slowness is due to the unnecessary use of **.

@aditsu, I have reduced the accuracy to expected digit count (but throwing away perfectly good accuracy from an iteration is making my teeth itch). Good suggestion on the ** effect. I found lots of speed by getting rid of them. I can't meet the 20 loops in 1 hour though. Perhaps with pypy or Cython? Hmmm. I will consider that.

Much better :) For this problem, throwing away good accuracy is less evil than continuing into bad accuracy. The 1 hour limit is based on my cjam/java test code run with java 8. Maybe python doesn't have efficient multiplication/division/sqrt for large numbers (Karatsuba & co)?

@aditsu: I believe integers have karatsuba (and just that) -- but with 32-bit limb size rather than 64-bit limb size. Who knows about Decimal.

Python (2.7) - 131 bytes
from gmpy import*
n=input()
p=a=fsqrt(mpf(8,4<<n));b=0
exec"a=fsqrt(a/2);b=1/(a-a*b+b/a+1);p*=b+a*a*b;a+=1/a;"*n
print`p`[5:2**n+6]

Update: Now using gmpy rather than gmpy2. For whatever reason, in gmpy2 setting the precision on a single value doesn't propagate to other values. The result of any calculation reverts back to the precision of the current context. Precision does propagate in gmpy, which seems more intuitive to me. It's also considerably less verbose.
Using one of the many algorithms devised by Borwein and Borwein, slightly refactored. n=20 takes about 11 seconds on my box. Not the most efficient method, but still not bad.

Refactoring
The original algorithm was the following:

Refactoring was done incrementally, but the end result is that

The major simplification happens in pn+1. It's also slightly faster due to having eliminated a division.
The current implementation pushes an back one iteration in the calculation of pn+1, which allows for a different initialization of p0 (2√2), but is otherwise identical.

Sample Usage
$ echo 1 | python pi-borwein.py
3.1

$ echo 2 | python pi-borwein.py
3.141

$ echo 5 | python pi-borwein.py
3.1415926535897932384626433832795

$ echo 10 | python pi-borwein.py
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420198938095257201065485863278

Great, but you're missing a digit for n=7

Also, is it this algorithm?

@aditsu fixed, and yes it is.

Now the last digit is wrong for n=5

@aditsu gmpy takes precision as bits, unfortunately. Should be correct for all values now, with a minor loss of efficiency.

The program with gmpy2 worked great, but now it seems that I can't import gmpy. Too old?

@aditsu it will need to be installed separately.

It doesn't seem to be available (anymore) in my distro. I mean.. there is a gmpy package, but oldest version is 2.0.3 (which is gmpy2). Could you provide some generic installation instructions?

@aditsu pip install gmpy worked for me; gmpy and gmpy2 are separate packages. However, it does rely on the deprecated distutils.

bc and Newton's method, 43 bytes
Newton's method for finding zeros of any function converges quadratically and the algorithm is way simpler than for Gauss-Legendre. It basically boils down to:

So here goes the according snippet:
n=20;x=3;scale=2^n;while(n--)x-=s(x)/c(x);x

A bit more readable:
/* desired number of iterations */
n = 20;

/* starting estimate for pi */
x = 3;

/* set precision to 2^n */
scale = 2^n;

/* perform n iteration steps */
while(n--)
  // f:=sin, f'=cos
  x -= s(x)/c(x)

To test this, run bc -l in a shell and paste the above snippet. Be prepared to wait for a while; n=20 has been running for about 5min now and no end in sight, yet. n=10 takes about 40s.

Not sure if sine and cosine qualify as "basic operations such as addition, subtraction, multiplication, division and power (including roots)". However, if you rolled your own sine/cosine, that would probably be acceptable.

Neat formula, though -- it says that π is a fixed point of f(x) = x - tan(x)

source: Stack Exchange

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

sort: votes


text:
Generate a Rectangle from a Specification
Introduction
This challenge is inspired by Grime, my 2D pattern matching language.
Basically, you are given a "grammar" that describes two-dimensional grids of characters, and your job is to generate a grid according to the grammar.
In addition, the grid should be as small as possible in a certain weak sense.
Input
Your input is a string containing lowercase ASCII characters and the symbols | and -.
For simplicity, the input does not contain repeated lowercase characters.
The string is a specification for a class of rectangular grids of characters, and it is parsed from left to right using a stack as follows.

Given a lowercase character c, push to the stack an m×n grid of the character c, for any m, n ≥ 1.
Given a pipe |, pop two grids A and B from the stack (B was on top), and push the grid AB obtained by concatenating B to the right of A. This requires that A and B have equal height.
Given a hyphen -, pop two grids A and B from the stack (B was on top), and push the grid A/B obtained by concatenating B to the bottom of A. This requires that A and B have equal width.

It is guaranteed that for some choices of m and n made during the parsing process (which may be different for each letter), the input specification correctly describes some rectangle, which is left on the stack at the end.
Output
Your output is a rectangular grid of characters specified by the input.
The grid must be minimal in the sense that removing any row or column would make it invalid.
You can return a newline-separated string (with or without a trailing newline), a 2D array of characters, or an array of strings, whichever is the most convenient format.
Note that you are not required to process the input exactly as described above; the only important thing is that your output is correct.
Example
Consider the specification
par-s||e-

First, we choose to push a 1×2 rectangle of p, and 1×1 rectangles of a and r (the reason for this will be clear later).
Then, we pop the a and r rectangles, and push their vertical concatenation
a
r

Next, we push a 1×2 rectangle of s, pop it and the above rectangle, and push their horizontal concatenation
as
rs

Then we pop that rectangle and the p rectangle, and push their concatenation
pas
prs

Finally, we push a 3×1 rectangle of e, pop it and the above rectangle, and push the vertical concatenation
pas
prs
eee

This is the output of the program, or at least one of the possibilities. Notice that even though
ppas
ppas
pprs
eeee

is also generated by the specification, it is not a valid output, since many of the rows and columns could be removed.
As a more subtle example, consider
co|m|p|il|e|r|-

This specification generates the rectangle
comp
iler

which is a valid output. However, it also generates
commp
iiler

which is valid too, since no single row or column can be removed without invalidating it.
Rules
You can give a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
Extra Test Cases
You can use these to test your program.
Input:
a
Output:
a

Input:
co|mp|l|-ex|i|f|-y|
Example output:
cccoy
mplly
exify

Input:
ja-r|g-o|ni-|ze|d-|
Example output:
jronze
arondd
ggoidd

Input:
un|co|p-yr|i|gh-t-ab|-|le-||-
Example output:
unnnnnnn
coyriggl
ppyrihhe
ppyritte
ppyriabe

Where do n and m come from?

Can be static or has to be some form of input?

@Sieg n and m are chosen non-deterministically. It is guaranteed that suitable values for them exist, but it is your program's job to find them.

You don't actually define what they are.

un|co|p-|yr|i|gh--t-ab|-|le-||- is impossible to be valid. The last - has an arity of 2, while there's only 1 element on the stack.

@Sieg I updated the explanation, hopefully it is clearer now.

@orlp Should be correct now.

K, 123 110 bytes
I used a similar approach to cardboard_box's solution.
r:{y,x#,*|y};h:{t:(#x)|#y;r[t-#x;x],'r[t-#y]y};a:{(,x .|2#y),2_ y};*(){(a[{+h[+x;+y]}]x;a[h]x;(,,y),x)"-|"?y}/

This program is a series of helper definitions followed by a tacit function which takes a string as a right argument. Reformatting for readability and assigning the final function as f:
r: {y,x#,*|y};                           / repeat last row x times
h: {t:(#x)|#y;r[t-#x;x],'r[t-#y;y]};     / append horizontal
v: {+h[+x;+y]};                          / append vertical
a: {(,x[y@1;y@0]),2_ y};                 / pop two values, concat

f: *(){:[y="-";a[v;x]; y="|";a[h;x]; (,,y),x]}/;

Use example:
  f "ja-r|g-o|ni-|ze|d-|"
("jronze"
 "aroidd"
 "ggoidd")

Tested using Kona, but it will also work in oK if you replace the : in the definition of f with a $- k5 changed the syntax of "cond".
A key point is recognizing that doing a vertical append is the transpose of the horizontal append of the transpose of both matrices. (See definition v.) I think there's still room to squeeze out a few characters here and there. If anyone is interested in a more detailed explanation I can provide one.
edit:
Updated the program at the top of this entry. Ungolfed version:
r: {y,x#,*|y};                           / repeat row x times
h: {t:(#x)|#y;r[t-#x;x],'r[t-#y;y]};     / append horizontal
v: {+h[+x;+y]};                          / append vertical
a: {(,x .|2#y),2_ y};                    / apply a concat
f: *(){(a[v]x;a[h]x;(,,y),x)"-|"?y}/;

Notable length optimizations include the use of "dot apply" in a, replacing the "cond" with list indexing in f (less efficient, but shorter) and replacing terms of the form a[b;c] into a[b]c where permitted by grouping. Since I'm no longer using "cond" or any primitives which are different between k3 and k5 this version now works in oK without modification.

Congratulations on winning the bounty!

Thanks! It was an interesting problem that yielded pretty well to K. It would have been interesting to see attempts in J or APL for comparison.

Prolog, 539 bytes
:-lib(ic).
:-lib(util).
b(A,B,C):-between(A,B,C).
g(S):-string_list(S,L),p(L,[]).
w(h(L,R):_:_,I,J):-w(L,I,J);L=_:W:_,X is I-W,w(R,X,J).
w(v(U,D):_:_,I,J):-w(U,I,J);U=_:_:H,Y is J-H,w(D,I,Y).
w(f(C):W:H,I,J):-b(1,W,I),b(1,H,J),char_code(S,C),put_char(S).
p([],[S]):-term_variables(S,V),S=_:X:Y,labeling(V),!,b(1,Y,J),(b(1,X,I),w(S,I,J);nl),fail.
p([124|T],[Q,Z|R]):-!,Q=_:WA:H,Z=_:WB:H,W #= WA+WB,p(T,[h(Z,Q):W:H|R]).
p([45|T],[Q,Z|R]):-!,Q=_:W:HA,Z=_:W:HB,H #= HA+HB,p(T,[v(Z,Q):W:H|R]).
p([C|T],R):-!,[H,W] #:: 1..100,p(T,[f(C):W:H|R]).

Explanation
We start with predicate g, which takes a string, convert it as a list of chars and call the p (parse) predicate with an empty stack as a second argument.
Predicate p calls itself recursively with an appropriately modified stack (look for [H|T] destructuring and constructor patterns). When called on the base case, where the input list is empty, p prints the unique element of the stack. If the stack has less or more than one element at this point, it means that we have an empty input string, a bad input string or a bug (with an emtpy string, the predicate fails (Prolog says No), but nothing is printed, which is ok, since we should not print anything for empty strings).
Solving
The stack contains a description of the constructed rectangles, denoted S:W:H, where S is a symbolic representation of the rectangle, W its width and H its height (note, A:B is syntactic sugar for the :(A,B) tuple with a functor named :; it is just shorter to write than having a tuple with prefix notation).
With A and B sub-rectangle specifications, S can be either:

h(A,B) : horizontal concat of A and B
v(A,B) : vertical concat of A and B
f(C) : fill with C, where C is a character code

Widths and heights of grids are constraint-programming variables: during vertical (resp. horizontal) concatenation, the width (resp. height) of the manipulated rectangles are unified, whereas the resulting height  (resp. width) is constrained to be the sum of each subgrid's height (resp. width).
The labeling step at the end of the process instanciates variables while respecting constraints, using the minimal possible values (this is a property of the order by which solutions are tried).
I might have obtained a shorter answer using the same reasonning that is done in other answers, without constraints, but this is too late now.
Note also that because the default domain for variables is set to 1..100, there is a limitation over the possible sizes of grids. The upper-bound could be changed if needed. The performance implications of this are that it could take a lot of time to determine that a particular solution admits no solution. I said "could" because constraints are likely to drastically prune the exponential search. If you find an input string that is hard/costly to reject, please share.
Printing
The printing part is interesting  because there is a kind of ray-casting algorithm over the structure: I iterate over each cell of the resulting grid, from point (1,1) to point (W,H) and call the w predicate to print the content of the grid  in the main tree, at this location (of course, a newline is printed after processing each line).
In w, positions are relative to current grid (the root grid defines absolute coordinates).
When printing a h(A,B) structure at point (X,Y), I unconditionnaly print in both branches:

in grid A at point (X,Y), and
in grid B at point (H,Y), where H is X minus the width of A.

The leaf branches of the grid-tree, f(C), finally either print the character C, if the relative location is inside the grid, or do nothing.
This is how I can print the content of grid to the output stream, from top to bottom, from left to right. No actual arrays are produced.
Tests
t("ja-r|g-o|ni-|ze|d-|").
t("un|co|p-yr|i|gh-t-ab|-|le-||-").
t("co|mp|l|-ex|i|f|-y|").
t("a").

tt :- t(X),nl,g(X).
tt.

Running test:
[eclipse] tt.

jronze
aronze
ggoidd

uuuuuuun
coyriggl
coyrihhl
coyrittl
ppyriabe

cccoy
mmply
exify

a

Yes (0.00s cpu)

+1 No actual arrays are produced. that's how it should be done. Overkill in this case, as the grammar is so simple and there are shortcuts.

@edc65 Yes, it's overkill. But since it is codegolf, I tried to minimize size, and manipulating arrays would have been too verbose.

Haskell, 388 367 352 bytes
data C=L{c::Char}|N{t::Int,w::Int,h::Int,l::C,r::C}
q=replicate
[]#[x]=x
(c:i)#(b:a:s)|c=='-'=i#(N 1(max(w a)$w b)(h a+h b)a b:s)|c=='|'=i#(N 2(w a+w b)(max(h a)$h b)a b:s)
(c:i)#s=i#(N 0 1 1(L c)(L c):s)
p i|t i==0=q(h i)$q(w i)$c$l i|t i==2=zipWith(++)(p(l i){h=h i})$p(r i){h=h i,w=w i-w(l i)}|1<2=p(l i){w=w i}++p(r i){w=w i,h=h i-h(l i)}
f=p.(#[])

Usage: f "par-s||e-" -> ["pas","prs","eee"]
Test run with pretty printing:
> putStr $ unlines $ f "par-s||e-"
pas
prs
eee

> putStr $ unlines $ f "co|m|p|il|e|r|-"
comp
iler

> putStr $ unlines $ f "a"
a

> putStr $ unlines $ f "co|mp|l|-ex|i|f|-y|"
coooy
mplly
exify

> putStr $ unlines $ f "ja-r|g-o|ni-|ze|d-|"
jronze
aroidd
ggoidd

> putStr $ unlines $ f "un|co|p-yr|i|gh-t-ab|-|le-||-"
unnnnnnn
coyriggl
ppyrihhe
ppyritte
ppyriabe

How it works: the function # parses the input string into the tree structure C which is either a leaf L holding the character to print or a node N. N can be a) a side-by-side join (t==2), b) a top-bottom join (t==1) or c) a single letter square (t==0). All nodes have a width and height field and a left and right child. After parsing, p prints the remaining root node by recursively adjusting the size (width x height) of  it's child nodes and joining them.
Edit: output as a list of lines instead of pretty printing

Python 2.7, 259
z=zip
def p(a,b):
 s,l=sorted([a,b],key=len)
 s+=([s[-1]]*(len(l)-len(s)))
 return z(*(z(*a)+z(*b)))
g=lambda s,t=[]:s and(s[0]=='-'and g(s[1:],t[:-2]+[z(*p(z(*t[-2]),z(*t[-1])))])or(s[0]=='|'and g(s[1:],t[:-2]+[p(t[-2],t[-1])])or g(s[1:],t+[[s[0]]])))or t[0]

g is a function which takes a specification and gives a 2D array of characters.  If you want a more user-friendly version, add this line to make it take a specification from stdin and print out the grid:
print'\n'.join(''.join(s)for s in g(raw_input()))

Test Cases
Input:
a
Output:
a
==========
Input:
co|mp|l|-ex|i|f|-y|
Output:
coooy
mplly
exify
==========
Input:
ja-r|g-o|ni-|ze|d-|
Output:
jronze
aroidd
ggoidd
==========
Input:
un|co|p-yr|i|gh-t-ab|-|le-||-
Output:
unnnnnnn
coyriggl
ppyrihhe
ppyritte
ppyriabe

Explanation
The strategy is simple: if a grid G is valid for a specification S, then repeating the rightmost column of G also gives a valid specification for S, and the same is true with repeating the bottom row (the proof of this is by structural induction on S).  Therefore, when we want to concatenate two rectangles, we can simply append the last column/row of the smaller one until they match in size (this is what the function p does).

JavaScript (ES6), 283 295
Edit Now this (heavily golfed) JS solution is at least shorter than the reference (quite golfable) Python solution.
Similar to cardboard_box, just repeating the leftmost column or the topmost row.
F=w=>(
s=[t=1,l='length'],
[for(c of w)(
  b=s[t],a=s[--t],
  c>'z'?
    s[t]=(G=(a,b,m=b[l]-a[l])=>m?m>0?G([a[0],...a],b):G(a,[b[0],...b]):a.map((r,i)=>r+b[i]))(a,b)
  :c<'a'?
    s[t]=a.map(r=>r[m=b[0][l]-r[l],0].repeat(m>0&&m)+r).concat(b.map(r=>r[0].repeat(m<0&&-m)+r))
  :s[t+=2]=[c]
)],
s[t].join('\n'))

Ungolfed This is my first, ungolfed solution.
F=sp=>{
  s=[]
  for(c of sp){
    a=s.pop(b=s.pop())
    if (c > 'z')
    {
      l = a.length
      m = b.length
      for(; l-m ;)
        l < m ? l = a.unshift(a[0]) : m = b.unshift(b[0])
      s.push(a.map((r,i) => r + b[i]))
    }
    else if (c < 'a')
    {
      l = a[0].length
      m = b[0].length
      s.push(
        a.map(r => r[0].repeat(l < m ? m-l : 0) + r)
        .concat(b.map( r => r[0].repeat( l > m ? l-m : 0) + r))
      )
    }
    else
    {
      s.push(a,b,[c])
    }
  }
  return s.pop().join('\n')
}

Test In Firefox/FireBug console
;['par-s||e-','co|m|p|il|e|r|-','co|mp|l|-ex|i|f|-y|',
 'ja-r|g-o|ni-|ze|d-|','un|co|p-yr|i|gh-t-ab|-|le-||-']
.forEach(w=>console.log(F(w)))

Output
pas
prs
eee

comp
iler

cccoy
mmply
exify

jronze
aronze
ggoidd

uuuuuuun
coyriggl
coyrihhl
coyrittl
ppyriabe

Python 3, 251 bytes
Here's the reference answer I promised, golfed a bit further.
T=lambda m:list(map(list,zip(*m)))
E=lambda a,b:a[:1]*(len(b)-len(a))+a
H=lambda a,b:[d+c for c,d in zip(E(a,b),E(b,a))]
s=[]
for k in input():s=k>"z"and[H(*s[:2])]+s[2:]or k<"a"and[T(H(*map(T,s[:2])))]+s[2:]or[[[k]]]+s
for r in s[0]:print("".join(r))

This is a full program that takes the string from STDIN and prints to STDOUT.
The approach is the same as that of cardboard_box: push a 1x1 array for a character, and duplicate rows if needed for concatenation.
$ echo "par-s||e-" | python3 gr.py
pas
prs
eee

Detailed explanation

T transposes a given list of lists. The majority of the work is done by zip(*m) which swaps rows to columns, the rest is just converting the result into a list of lists, since zip returns a generator of tuples.
E(a,b) returns a with its first element repeated enough times to match the length of b. Note that multiplying a list by a negative number gives the empty list, so if b is shorter than a, this returns a.
H(a,b) returns the horizontal concatenation of a and b, the shorter one being lengthened by E if necessary.
s is the stack.
In the for loop, we iterate over the input string, and replace s by a new value: if it's | (greater than z), we pop two values and push their H, if it's - (lower than a), we pop two values, transpose, feed to H, transpose again and push the result, and otherwise push a 1x1 array with the letter.
Finally, we print the first element of s.

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


text:
Self-shortening Prime Tester
Let's get right in to it.
Your challenge is to make a program that does these things depending on its input:

If the input is a number, output "Prime" if the number is a prime number and "Not prime" if the number isn't a prime number. You can assume the number is > 1.

If the input is two numbers, output every single prime number between the first number (inclusive) and the second number (exclusive). You can assume the first number is smaller than the second.

Here comes the real challenge: if there's no input, the program should output a shorter version of itself that does exactly the same things as the original program. The program is not allowed to read from any file or from the web. The new program should also be able to do this. It should work for at least 5 generations. The new program doesn't have to be in the same language as the first.

Scoring:
Your score is equal to the sum of the number of bytes in the first five generations of your submission (the submission itself being generation one). If the new code is hard-coded in to the first program, multiply the score by 1.5. Lowest score wins. (If you find some kind of flaw in the scoring system, please let me know in the comments)

You should specify conditions for the quine part: is the program allowed to read its own source code, etc. See this question from 5 days ago on our meta site: http://meta.codegolf.stackexchange.com/q/4877/15599

I think my edits address the all but one of the previous comments. The one remaining issue: What counts as hard coding?

I think this is a [code-golf] ("shortest code wins" in some metrics), no need to be a [code-challenge].

How about "Prime program generator", "Produce five generations of primes", or "Prime pseudo quine generator"?

CJam, 66 + 65 + 64 + 63 + 62 = 320 325 355  bytes
The following 5 lines are the first 5 generations:
{     `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{    `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{   `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{  `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{ `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~

The last one produces
{`(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~

which still performs the prime tasks correctly.
Test it here.
Explanation
The basic CJam quine is
{"_~"}_~

which can be extended very easily to a generalised quine. For an explanation of this see my answer here.
The basic ideas for this answer are:

Start the quine with a bunch of spaces and remove one of these when quining.
Get an array with all input numbers (0, 1 or 2) and choose some code to run depending on the length (by using it to index into an array).

Here is a breakdown of the code inside the quine:
"Remove a space from the block's string representation:";
`(\1>+
`      "Get the string representation of the block.";
 (\    "Slice off the leading '{' and pull the remaining string back up.";
   1>  "Remove the first character, i.e. a space.";
     + "Prepend the '{' to the string again.";

"Get the array of inputs and choose the code:";
q~](\_,[...]=~
q~             "Read and eval the input.";
  ]            "Wrap everything (including the string for the block) in an array.";
   (\          "Shift off the string and swap it with the rest of the array.";
     _,        "Duplicate the input array and get its length.";
       [...]=  "Use it to index into this array.";
             ~ "If there are no inputs there will now be an array on the top of the
                stack, which ~ will unwrap. Otherwise there will be a block which ~
                will evaluate.";

"If there is no input, push the string needed for the quine and put it in
 an array for ~ to unwrap:";
"_~"a

"If there is one input, test for primality:";
~mp'P"Not p"?"rime"@;
~mp                   "Unwrap the input array and test for primality.";
   'P"Not p"?         "Choose either 'P' or 'Not p' depending on the result.";
             "rime"   "Push the common part of the string.";
                   @; "Pull up the quine string and discard it.";

"If there are two inputs, print an array with all the primes in the range:";
~,>{mp},p;
~          "Unwrap the array leaving N and M on the stack.";
 ,         "Get a range [0 1 .. N-1].";
  >        "Drop the first M elements, giving [M M+1 .. N-1].";
   {mp},   "Filter to keep only the primes.";
        p  "Pretty-print the array.";
         ; "Discard the quine string.";

Could you please add an explanation?

@Loovjo Yes, I will, but not before I'm done golfing. ;)

Could you please put the programs in different code blocks? Kinda confused me when I first read it.

@Loovjo clarified that it's 5 programs and added a full explanation

C, Score: 553 + 552 + 551 + 550 + 549 = 2755,
Original Length: 553, Avg: 551
EDIT: Only 5 generations, not 6!
Looks like Martin beat me both in time and in score (by nearly an order of magnitude!). Ah, well.
The original program is as follows:
char*c="char*c=%c%s%c;k=%d,a;p(c,v,d){for(v=2;v<c;v++)d+=!(c%cv);return!d;}int main(int C,char**V){if(C==1){printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);return 0;}a=atoi(V[1]);if(C==2)printf(p(a,0,0)?%cPrime%c:%cNot prime%c);if(C==3)for(;a<atoi(V[2]);a++)if(p(a,0,0))printf(%c%cd %c,a);}";k=10000,a;p(c,v,d){for(v=2;v<c;v++)d+=!(c%v);return!d;}int main(int C,char**V){if(C==1){printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);return 0;}a=atoi(V[1]);if(C==2)printf(p(a,0,0)?"Prime":"Not prime");if(C==3)for(;a<atoi(V[2]);a++)if(p(a,0,0))printf("%d ",a);}

I'll unravel it a little bit for better understanding, but for it to work properly the new lines are NOT part of the program.
char*c="char*c=%c%s%c;k=%d,a;p(c,v,d){for(v=2;v<c;v++)d+=!(c%cv);return!d;}int main(int C,char**V){if(C==1){printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);return 0;}a=atoi(V[1]);if(C==2)printf(p(a,0,0)?%cPrime%c:%cNot prime%c);if(C==3)for(;a<atoi(V[2]);a++)if(p(a,0,0))printf(%c%cd %c,a);}";
k=10000,a;
p(c,v,d){
    for(v=2;v<c;v++)
        d+=!(c%v);
    return!d;
}
int main(int C,char**V){
    if(C==1){
        printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);
        return 0;
    }
    a=atoi(V[1]);
    if(C==2)
        printf(p(a,0,0)?"Prime":"Not prime");
    if(C==3)
        for(;a<atoi(V[2]);a++)
            if(p(a,0,0))
                printf("%d ",a);
}

The only thing that changes from program to program is the value of k, which loses exactly one digit every iteration. Interestingly, after the 5th generation, k becomes zero and stays there, so you can iterate ad infinitum and always have valid output.

Tcl 253 + 252 + 251 + 250 + 249 = 1255 bytes
eval [set x {     proc q a\ b {incr b;expr $a%$b?\[q $a $b]:$a==$b}
proc 1 a {if [q $a 1] puts\ Prime {puts Not\ Prime}}
proc 2 a\ b {while $b-\$a {if [q $a 1] puts\ $a;incr a}}
proc 0 {} {puts "eval \[set x {[string ra $::x 1 end]}]"}
$argc {*}$argv}]

The code needs to end with a newline.
Explanation:
eval [set x {...}]

Write the code into x, then execute it.
$argc {*}$argv

Execute the command which name is the argument length, passing the arguments along.
proc q a\ b {incr b;expr $a%$b?\[q $a $b]:$a==$b}

Returns 1 when a is prime, 0 else. Uses recursion; the second backslash prevents command substitution from the interpreter and enables the one from expr (which is lazy).
proc 1 a {if [q $a 1] puts\ Prime {puts Not\ Prime}}
proc 2 a\ b {while $b-\$a {if [q $a 1] puts\ $a;incr a}}

Straightforward implementation of the requirements.
proc 0 {} {puts "eval \[set x {[string ra $::x 1 end]}]"}

This is the quine, stripping a space from the beginning each time.

"Your score is equal to the sum of the number of bytes in the first five generations of your submission (the submission itself being generation one)."


text:
Sorted Lexical Partition of a Number
The challenge is really simple: given a number, you split its digits into an array of smaller numbers such that the resulting numbers are non-decreasing. The catch is that you have to split it such that the array length is maximal.
Confused?

You are given a positive integer via STDIN (or closest alternative), command-line argument or function argument in any convenient, unambiguous input format.
You have to partition the number's decimal digits into contiguous, disjoint groups.
The array of numbers represented by these digit groups should be sorted (in the usual, non-decreasing order) without rearranging the groups.
In cases where more than one such partition exists, you have to partition the input into as many numbers as possible. In the case of ties, return one such result.
You can output the array to STDOUT (or closest alternative) or as a function return value. In case of STDOUT (or closest alternative), the array should be printed in any convenient, unambiguous list format.
The split numbers should not have leading zeroes. So for instance 1002003 cannot be printed as either [1, 002, 003] or [1, 2, 3] and the only valid answer for it is [100, 2003].

Test cases:
123456 -> [1, 2, 3, 4, 5, 6]
345823 -> [3, 4, 5, 8, 23]
12345678901234567890 -> [1, 2, 3, 4, 5, 6, 7, 8, 90, 123, 456, 7890]
102 -> [102]
302 -> [302]
324142 -> [3, 24, 142] OR [32, 41, 42]
324142434445 -> [32, 41, 42, 43, 44, 45]
1356531 -> [1, 3, 5, 6, 531]
11121111111 -> [1, 1, 1, 2, 11, 11, 111]
100202003 -> [100, 202003]

Scoring
This is code-golf so shortest code in bytes wins.

Pyth, 34
FNyUz#aYmv:zhdedC,+0N+NlzB)efqSTTY

Try it online here. Notice, this has a time (and space) complexity of O(n). Therefore the test case 12345678901234567890 takes too long in the online compiler. Use the offline one instead (1 minute on my laptop).
This is only my first attempt. There might be some room for improvements.
First some ideas how my algorithm works.

I interpret the input as string and not as a number.
Then I create all possible subsets of [0, 1, 2, ..., len(n-1)]
For each of these subsets (lets take [1, 4, 5]), I split the input string into part using these numbers. [input[0:1], input[1, 4], input[4,5], input[5,len(input)]].
Afterwards I try to convert these numbers into strings. There can be two problems. Pyth (or Python) throws an exception for an empty string, and for a string of numbers starting with 0. Therefore I use a try - catch block (actually infinity loop with an immediate break). If converting was successfully, I add the result to a list Y.
After I handled all subsets, I filter the list Y for results, that are already sorted and print the last one (the last one has the most groups).

Now the detailed explanation:
                            Implicit: z = input() (z is a String!)
                                      Y = empty list
FNyUz                       for each subset N of [0, 1, 2, ..., len(z)-1]:

     #                         start try-catch block (actually an infinite loop,
                               but the Python implementation uses a try catch.

      aY                          append to Y:
                C,+0N+Nlz            zip([0] + N, N + [len(z)])
        m                            map each element d to
          :zhded                     z[d[0]:d[-1]]
         v                           evaluated
                         B        if this didn't throw an exception already, end the infinite loop
                          ) end for loop

 f    Y      filter Y for elements T, for which
  qSTT           sorted(T) == T
e            and print the last one (the subsets generated with yUz are sorted
             by length, so the last one has the most groups)

You can use aY instead of ~Y]

@FryAmTheEggman I always forget about a. Don't know why.

@Jakube Maybe because it's not in the docs?

I had a solution for ~45 chars. I was not aware of the fact that int("01") being an error in Pyth (this doesn't happen in Python).

@orlp Me neither. I thought Pyth (and Python) translates it to an Octal number. Stumbled upon it accidentally.

@orlp Got curious about Python: int("01") works in Python 2/3, but eval("01") (which I use to convert it) fails in Python 3.

@Jakube This is not O(n). It is O(2^n), because of yUz.

int("01") is not an error in Pyth. That would be s"01", not v"01".

@isaacg It is O(n), at least if you interpret the input as number. O(2^len(input)) = O(2^log(number)) = O(number).

@Jakube haha, although seems logical, but generally n is the length of the input.

Mathematica, 134 127 bytes
This is pretty inefficient since it generates a lot more partitions than the valid ones. The 324142434445 test case runs within a few seconds, but I wouldn't try 12345678901234567890.
f/@Last@Select[Needs@"Combinatorica`";f=FromDigits;SetPartitions[d=IntegerDigits@#],0<=##&@@f/@#&&Join@@#==d&&#~FreeQ~{0,__}&]&

This defines an unnamed function which takes an integer and returns a list of integers.
Explanation
The reading order of this code is a bit all over the place, so I'll break down in the order it's intended to be read (and evaluated for the most part):

d=IntegerDigits@# get the decimal digits of the input and assign this list to d.
SetPartitions (which requires Needs@"Combinatorica`";) gives me all partitions of this. However, it returns a lot more than I actually want since it treats the input as a set. This is what makes it inefficient, but I'm using this because the shortest way I know to get all list partitions is much longer. As an example, if the list was {1, 2, 3} the function would return:
{{{1, 2, 3}}, {{1}, {2, 3}}, {{1, 2}, {3}}, {{1, 3}, {2}}, {{1}, {2}, {3}}}

Note that a) the consecutive partitions are all in the right order and b) the partitions are sorted from coarsest to finest.
Select[...,...&] then filters this list by the anonymous function passed in as the second argument.

Join @@ # == d checks that we've actually got a list partition instead of a general set partition.
#~FreeQ~{0, __} checks that no partition starts with a leading zero.
0 <= ## & @@ f /@ # is a bit more obscure. First we map FromDigits onto each list in the partition to recover the numbers represented by the digits. Then we apply 0 <= ## to those numbers, where ## refers to all the numbers. If the partition is {1, 23, 45} then this expands to 0 <= 1 <= 23 <= 45, so it checks that the array is sorted.

Last@ then gives me the last partition left after filtering - this works because SetPartitions already sorted the partitions, such that the finest ones are at the end.
Finally, f/@ recovers the numbers from the digit lists.

Python 3, 134 bytes
def f(s,n=0,L=[],R=[],i=0):
 while s[i:]:i+=1;m=int(s[:i]);R=max([f(s[i:],m,L+[m]),R][m<n or"1">s[i:]>"":],key=len)
 return[L,R][s>""]

It's a little messy, but oh well. The program just generates all valid partitions recursively. The interesting part is that to disallow leading zeroes, all that was necessary was an additional or "1">s[i:]>"" condition.
Takes input like f("12345678901234567890") and returns a list of ints.

Pyth, 62 61 60
JlzKkef&qJsml`dTqTSTolNmmibTcjKsC,z+m>Ndt>+*J]0jk2_JKNU^2-J1

Explanation
The algorithm works by generating all binary numbers between 0 (inclusive) and 2^(n-1) (exclusive), where n is the length of the input.
The binary digits of each are then mapped to a separator (N) for 1 and nothing for 0.
These characters are then inserted between each input character, and the result is split by N, yielding a list.
The values in the lists are then parsed to integers, and the lists are sorted by length. Then all that is left is to filter out non-sorted ones and ones that have been split at leading zeroes, after which the longest list is picked.
Jlz                                                   set J to len(input)
Kk                                                    set K to ""
e                                                     take the last of:
 f&                                                    only take lists where:
   qJsml`dT                                             sum of string lengths of items
                                                        is equal to length of input and
           qTST                                         list is in order
               olN                                       sort by length
                  m                                       map k over...
                   mibT                                    convert items to int (base-10)
                       c                        N           split by N
                        jK                                   join by ""
                          s                                   sum to combine tuples
                           C,z                                 zip input with
                              +                K                append [""] for equal lengths
                               m>Nd                              replace 1 with N, 0 with ""
                                   t                              take all but first
                                    >        _J                    take len(input) last values
                                     +                              pad front of binary with
                                      *J]0                           [0] times input's length
                                          jk2                        current k in binary
                                                 U^2-J1  range 0..2^(len(input)-1)-1

Pyth, 25 bytes
ef&&Fmnhd\0T.A<V=NsMTtN./

Try it online!
How it works:
ef&&Fmnhd\0T.A<V=NsMTtN./  Q = eval(input())
                         ./  all partitions of Q
 f                       ./  filter all partitions of Q where:
  &                            both:
   &Fmnhd\0T                     neither substring starts with "0"
                               and:
            .A<V=NsMTtN          all entries are less than their proceeding ones
e                            returns the last amongst the filtered partitions

J, 109 bytes
Very long but at least takes up O(n * (2n)!) memory and O(n * log(n) * (2n)!) time where n is the length of the input. (So don't try to run it with more than 5 digits.)
f=.3 :0
>({~(i.>./)@:(((-:/:~)@(#$])*#)@>))<@".(' 0';' _1')rplc"1~(#~y-:"1' '-."#:~])(i.!2*#y)A.y,' '#~#y
)

The function takes the input as a string.
Examples:
   f every '5423';'103';'1023'
  5 423
103   0
 10  23

Method:

Add the same number of spaces to the input as it's length.
Permute it in every possible way.
Check if the spaceless string is the same as the input (i.e. it's a partition of it).
Replace ' 0's to ' _1's to invalidate leading zero solutions.
Evaluate each string.
Find the longest list which is also sorted. This is the return value.

Haskell, 161 bytes
(#)=map
f[x]=[[[x]]]
f(h:t)=([h]:)#f t++(\(a:b)->(h:a):b)#f t
g l=snd$maximum[(length x,x::[Int])|x<-[read#y|y<-f l,all((/='0').head)y],and$zipWith(>=)=<<tail$x]

Test run:
*Main> mapM_ (print . g) ["123456","345823","12345678901234567890","102","302","324142","324142434445","1356531","11121111111","100202003"]
[1,2,3,4,5,6]
[3,4,5,8,23]
[1,2,3,4,5,6,7,8,90,123,456,7890]
[102]
[302]
[32,41,42]
[32,41,42,43,44,45]
[1,3,5,6,531]
[1,1,1,2,11,11,111]
[100,202003]

How it works: the helper function f splits the input list into every possible list of sublists. g first discards those with a sublist beginning with 0 and then those without the proper order. Pair every remaining list with it's length, take the maximum and discard the length part again.

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


text:
Drawing an Image Based on a Trace of its Hue
Introduction
Local genius Calvin's Hobbies recently challenged us to trace the hue of an image.
It is recommended to read his challenge beforehand, but to highlight the main points:

The trace of hue in an image can be found by starting at one pixel, finding its hue angle(hue = atan2(sqrt(3) * (G - B), 2 * R - G - B)), and moving one pixel's width in that direction. If this process is repeated, and a black pixel is left at each pixel passed, we produce a trace of the image.

Here is a simple example of the trace:

We start at pixel 250, 250, with RGB color 36, 226, 132. We observe that the hue of this color is 150. Thus, we begin drawing a black line 150 degrees counterclockwise from the positive x-axis. We run into the square to the left, with RGB color 100, 220, 7 and hue 94. This results in an almost vertical line to the next square. We continue the pattern into every square, and observe the change in slope at each new color. The length of this trace was 300 pixels. If you're wondering why the image is so ugly, it's because I randomly generated 25 colors in 100x100 squares and used my answer to trace it. On a much more complex and beautiful image, we may get a trace like this one:

Calvin created this wonderful code snippet on the original post that draws a trace over an image, starting at the point provided by the mouse cursor. This is a very useful testing tool!

Load an image: <input type='file' onchange='load(this)'>

Max length <input id='length' type='text' value='300'>

<canvas id='c' width='100' height='100'>Your browser doesn't support the HTML5 canvas tag.</canvas>

 Snippet tested in Google Chrome

Answers to that challenge may also serve as appropriate testing tools for this challenge.

Note: I do not take any credit for Calvin's work, and have received explicit permission to use his ideas in this challenge.
The Challenge
In that challenge, we found the trace. Now, I'm asking you to find the image. You will be given a start point, an end point, and a length, and your program must output an image whose trace beginning at the start point arrives at the end point in approximately length pixels. Moreover, because there are so many options, your program's algorithm must be inherently random in some regard--thus the same input should (more often than not) produce a different output image.
Input
You will receive seven positive integers as input: w, h, x1, y1, x2, y2, len where:

x1, x2 < w <= 1920

y1, y2 < h <= 1080

len < 2000

These guidelines are minimum requirements. Your program may accept higher values.
You may receive input through stdin, a file, or as arguments to a function. You will ONLY receive these 5 integers as input.
Output
As output, produce an image of width w and height h with a continuous hue trace from x1,y1 to x2, y2 in approximately len pixel-width steps.

Output should be random.
Output may be in any format--whether it be .bmp, .png, PPM, or an image shown on-screen at runtime makes no difference.
You may assume it is possible to move from x1, y1 to x2, y2 in under len pixels.
Output should NOT show the path of the trace from x1, y1 to x2, y2--though an image showing this path in your answer is appreciated.

Rules

This is a popularity-contest! Try to make your output beautiful or interesting. More interesting hue traces than straight lines are also recommended.
This is not code-golf. As such, readable code is appreciated. Still, try to keep size below ~2KB. This rule will not be strictly enforced.
Values are approximate. If your code's trace reaches its destination within ~5-10% of len pixels, this is acceptable. Along this same vein, do not worry about slightly incorrect hue angle values. Some error is reasonable.
This is graphical-output. Please include output images of your solution in your answer.
Standard Loopholes apply.

Questions, comments, concerns? Let me know!

I think you should explain a bit more about how the direction of the black line in the image is generated (perhaps with a simpler image?). Explain that the line starts out going left because the hue of light blue is 180°, and curves down because as the blue gets darker the hue angle increases. You are also welcome to repost and even edit the snippet from my question.

This might work better as a [tag:code-golf], though then you'd need to be more specific on what constitutes "randomness". However a pop-con may let people show off some neater ways to make these images. I also think it'd be "purer" to give the image dimensions as part of the input, though this is really a matter of opinion.

@Calvin'sHobbies Thanks for the feedback! I will definitely try to think of a way to concisely explain the hue. Let me work on it a bit, and I'll see if I can put together an explanation. On making it code-golf, I have one pretty serious problem with that. If you were to take atan((y1-y2)/(x1-x2)) you could quite easily find a "random" color whose hue is this angle. You could then draw a solid line of this color between the points on a white background, divert a bit to account for length, and boom. I really want to promote creativity with this question, and I don't think code-golf does that.

@Calvin'sHobbies I think you're right about width and height. I'll make it take 7 arguments.

All the code is on bitbucket(it is completely unoptimised). The hue path tracing logic is my own so might differ slightly from that in the original question. Instead of trying to work out a function to generate a line and then an image from that, it makes multiple sets of random changes to a starting image and then picks the set where the end of the path is closest to the target end, then repeats.

I think it looks kinda artistic sometimes. The current randomisation method just draws randomly coloured rectangles, if you run the program yourself you can watch it iterating. With 60 generations (and 70 children per generation) it basically always gets within a pixel of the target. I tried swapping individual pixels but that was too slow. Plain rectangles was the best (simple) way of changing the image that I tried which still created interesting output. I might see how well circles work later.

Thank you! This is an awesome answer! I like the idea of iteratively testing random rectangles. Do you have an estimate of how close this usually gets to the exact pixel? (Also, if you could put what input you gave it for the output shown, that'd be great!)

Inputs were (800, 650), (500,50), (60,310) ,700. I didn't seed the rng in that commit though so you probably aren't able to recreate it (although I have in a newer commit). See edit for how close it gets.


text:
Finding Symmetries in Squares
Write a program or function that takes in a list of positive integers. Each of these integers represents the side length of a square on a 2D plane. Each square can be moved to any integer coordinates in the plane, but it can't rotate and it can't overlap other squares.
Using a different printable ASCII character for each square (excluding space which is used for emptiness) your program/function needs to print any single arrangement of the squares that has a horizontal or vertical line of reflectional symmetry. If no such arrangement exists then nothing should be printed.
The squares are different characters just so they can be told apart. Only the shape made by the union of all the squares needs to be symmetrical. You can assume the list will not contain more than 94 elements (as there are 94 characters).
For example, if the input was [2, 1, 2, 2, 2], a possible output is:
DD--
DD--
Z
FFPP
FFPP

This shape has a horizontal line of reflectional symmetry; its top and bottom halves are mirror images. Here are some other possibilities: (Note that the squares don't need to touch and any characters can be used as long as no two squares are made of the same character.)
  55
  55
  %%
  %%
@
  HH
  HH
  ((
  ((
       G

     11 33
     11 33

    22   44
    22   44
The line of symmetry could also be the boundary between characters, e.g. for [2, 4]:
!!!!
!!!!  ++
!!!!  ++
!!!!

Some sets of squares are impossible to arrange symmetrically, e.g. [1, 2, 3]:
AAA BB C
AAA BB         (these can't be vertically or horizontally symmetric => no output)
AAA

And remember that the overall shape may be symmetric even if the square boundaries aren't. e.g. a valid output for [2, 1, 1, 1, 1, 4] is:
AA----
AA----
BC----
DE----

Similarly, a valid output for [1, 1, 2, 3, 5] is:
44444
44444
44444
44444
44444
33301
33322
33322

Notes

The input list will always have from 1 to 94 elements.
Take input in any reasonable way: stdin, command line, text file, function arg. It can be slightly formatted to suit your needs, e.g. {1, 2, 3, 4} or [1 2 3 4].
Output to stdout or similar. Any amounts of leading/trailing spaces or newlines are fine as long as the resulting shape has the line of symmetry.
A diagonal line of symmetry does not count (else this would be super easy). Also, it has to be reflectional symmetry, not rotational or transitional.
I'm honestly not sure how computationally difficult this task is. You may post partial answers that solve some subset of the problem (especially if you want to show off a particularly clever algorithm). These are not eligible to win.

For example, you might assume that the input always has at least one symmetrical arrangement (so lists like [1, 2, 3] are never input).
Or, for example, you may only consider arrangements where the square boundaries, as well as the overall shape, are symmetrical. In this case, [1, 1, 2, 3, 5] would have no output.
If you want to go crazy, you could extend the idea to rectangles or even polyominoes.

Scoring
Your score is the size of your program in bytes. The lowest score wins. Tiebreaker goes the the answer posted first.

Bonus points for solving [2, 4, 6, 7, 8, 9, 11, 15, 16, 17, 18, 19, 24, 25, 27, 29, 33, 35, 37, 42, 50, 112], although since the question gives a lot more freedom there's probably other solutions.

Python 2, 460 452 437 bytes
exec"""def f(L):
 if[]==L:
  X{2}[map(" ".__lt__,q)for q in G]);Z{2}zip(*X));C=Z==Z[::-1]or X==X[::-1]
  if C:print"\\n".join(map("".join,G))
  return C
 x=L[-1];T=S-x+1;R=range(x)
 for n in range(T*T):
  i=n%T;j=n/T
  if all({1}=" "{0}):
{0}:{1}chr(32+len(L))
   r=f(L[:-1])
{0}:{1}" "
   if r:return r""".format("   for a,b in[(a,b)for a in R for b in R]","G[i+a][j+b]=","=filter(sum,")
L=input()
S=sum(L)
G=[S*[" "]for _ in[0]*S]
f(L)

Only mildly golfed for now, but here's something to get things started. I tried using exec for lines 10 and 12, but for some reason it didn't let me.
Input the list L via STDIN, e.g. [2, 1, 2, 2, 2]. The program simply tries every possibility of placing squares in a sum(L) x sum(L) grid.
Sample output (blank lines removed for compactness):
[2, 1, 2, 2, 2]

%%
%%
$$
$$
"
##
##
!!
!!

[2, 4]

""""
""""
""""
""""
 !!
 !!

[2, 1, 1, 1]

$!!
#!!
 "

[1, 1, 2, 3, 5]

%%%%%
%%%%%
%%%%%
%%%%%
%%%%%
$$$##
$$$##
$$$"!

[1, 4, 1, 8]

$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
# """" !
  """"
  """"
  """"

[8, 1, 4, 1]

$   !!!!!!!!
    !!!!!!!!
####!!!!!!!!
####!!!!!!!!
####!!!!!!!!
####!!!!!!!!
    !!!!!!!!
"   !!!!!!!!

(The algorithm starts placing from the last square first, prioritising left then up)

Slightly less confusing version (452 bytes):
def f(L):
 if[]==L:
  X=filter(sum,[map(" ".__lt__,q)for q in G]);Z=filter(sum,zip(*X));C=Z==Z[::-1]or X==X[::-1]
  if C:print"\n".join(map("".join,G))
  return C
 x=L[-1];T=S-x+1;R=range(x);V=[(a,b)for a in R for b in R]
 for n in range(T*T):
  i=n%T;j=n/T
  if all(G[i+a][j+b]<"!"for a,b in V):
   for a,b in V:G[i+a][j+b]=chr(32+len(L))
   r=f(L[:-1])
   for a,b in V:G[i+a][j+b]=" "
   if r:return r
L=input()
S=sum(L)
G=[S*[" "]for _ in[0]*S]
f(L)

@Calvin'sHobbies I just realised I forgot to strip empty rows and columns (which would have meant that the configuration had to be symmetric with respect to the board as well). [1, 1, 2, 3, 5] now runs fine.

Ah. I thought the brute force was just taking forever.

@Calvin'sHobbies It does for larger boards, but putting additional constraints just makes it worse :P

I think you can save some chars using the indentation trick.


text:
The Urinal Protocol
Background
The so-called "Urinal Protocol", describing the order in which individual urinals are picked in a men's bathroom, has been discussed in multiple places. One version is given in this xkcd blog post. This question concerns a slight variation:

Arrangement: n urinals in a line.
Protocol: each new person selects one of the urinals most distant from those already in use.

Note that this places no restrictions on which urinal is picked by the first person.
Update: The sequence of the number of different ways in which n people can select n urinals starts with 1, 2, 4, 8, 20... Note that this not the same as OEIS A095236, which describes slightly stricter restrictions than in this question.
Task
Given an integer n between 0 and 10, output (in any order) all the possible orderings in which n people can occupy n urinals. Each ordering should be printed as the final arrangement: a sequence of digits representing the people (1-9 for the first 9 people, 0 for the tenth), starting from the leftmost urinal, with optional non-alphanumeric separators between (but not before or after) the digits. For example, the following outputs are both valid:
>> 3
132
213
312
231

>> 4
1|3|4|2
1|4|3|2
3|1|4|2
4|1|3|2
2|3|1|4
2|4|1|3
2|3|4|1
2|4|3|1

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. Results should be printed to STDOUT (or closest alternative).
Scoring
Shortest code wins. Standard terms & conditions apply.

Hm. For 5 urinals I get this. It should be 16 rows instead. Would anyone please elaborate which of those solutions are wrong? This is currently implementing: Choose any one of the urinals with maximum distance to anybody else.

So much for sandboxing :-( Spec is as described in the task, not the sequence definition. I'll update as soon as I get to a computer.

@knedlsepp Rows 3, 4, 17, 18 are incorrect. In these, you place person #3 in a span of length 1, where there is a span of length 2 available. I've suddenly managed to confuse myself. It would appear the OP is intentionally derived from the link, and thus the link should be followed?

Updated spec to note that the task is not the same as A095236.

Is it allowed to output the format in [1, 3, 2], where each such solution is seperated by newlines? (so not only a seperator of ", ", but also a start of "[" and end of "]")

No, it's just separators between digits that are allowed (partly for aesthetics, partly to make it easier to print arrays in some languages). I'll clarify that in the instructions.

@BrainSteel: Thanks for clarifying! Somehow I also think the 'real' series should be used. But in this case it's quite an odd constraint. As for my personal taste as #3, I wouldn't feel a need to avoid situations 3,4,17,18.

Is the difference between this sequence and A095236 that if you have a choice between being N urinals away from both your neighbors or being N urinals away from one neighbor and N+1 urinals away from the other, you don't have to pick the second option?

@user2357112: yes, that's it. Had I noticed this originally, I would have probably phrased the task accordingly. However, given that I'd already posted the question it seemed best to go with the definition that I'd used. Also, as knedlsepp notes, it's not an obvious constraint.

At a glance I thought output 3,1,2 meant "first the 3rd, then the 1st, then the 2nd urinal". For n=3, this works for all 4 example output lines. Maybe it's good to add an example for larger n, to prevent people (like myself) from making dumb comments.

@freekvd: sorry about that. I've replaced one of the examples with n=4.

Pyth, 53 51
MhSm^-dG2HjbmjdmehxkbQusmm+dkfqgTdeSmgbdQUQGUtQm]dQ

This is an iterative approach. Given a possible partially filled in ordered sets of locations, we find all the optimal further locations, then generate the corresponding location list, and repeat.
Results are generated in the form [<first person's location>, <second person's location> ...], then this is transformed into the desired format. MhSm^-dG2H defines a helper function which finds the minimum distances from a given stall to an occupied stall (squared). Amusingly, the separator is free.
Example run.
Explanation:
First, the helper function g, which finds the minimum squared distance between G and any value in H.
MhSm^-dG2H
M             def g(G,H): return
 hS           min(                         )
   m     H        map(lambda d:        , H)
    ^-dG2                      (d-G)**2

Next, we find the maximum over urinal locations of the minimum squared distance between that urinal and any occupied urinal:
(Q is the input.)
eSmgbdQ
eS          max(                                   )
  m   Q         map(lambda b:      , range(len(Q)))
   gbd                       g(b,d)

d in this case is the list of occupied urinals, while b iterates over urinal locations.
Next, we find all urinal locations whose minimum squared distance from the nearest occupied urinal is equal to the maximum value found above.
fqgTdeSmgbdQUQ
f           UQ    filter(lambda T:                             , range(len(Q)))
 qgTd                             g(T,d) ==
     eSmgbdQ                                <value found above>

Next, we will generate the urinal location lists created by adding the urinal locations found above to d. We will do this for each previous list of urinal locations, thus extending the lists from length N to N+1. G is the list of legal lists of occupied urinal locations of a given length.
smm+dkfqgTdeSmgbdQUQG
sm                  G    sum(map(lambda d:                               ,G)
  m+dk                                   map(lambda k:d+[k],            )
      fqgTdeSmgbdQUQ                                        <above list>

Next, we will apply the above expression repeatedly, to generate the complete list of lists of occupied urinal locations. u, the reduce function, does exactly this, as many times as there are elements in its second argument.
usmm+dkfqgTdeSmgbdQUQGUtQm]dQ
usmm+dkfqgTdeSmgbdQUQG           reduce(lambda G,H: <the above expression)
                      UtQ        repeat Q-1 times
                         m]dQ    starting with [[0], [1], ... [Q-1]].

Convert from the above representation, which goes [<1st location>, <2nd location>, ... ], to the desired output form, [<person in slot 1>, <person in slot 2>, ... ]. Then, the output form is joined into the output string and printed. Printing is implicit.
jbmjdmehxkbQ
jbm             '\n'.join(map(λ k:                                    ,<above>)
   jdm     Q                      ' '.join(map(λ b:                ,Q)
        xkb                                        b.index(k)
      eh                                                     +1 %10

Damnit, I should stop writing recursive solutions in Pyth. I always get beat out :P

kajsdlkas^23asdjkla1lasdkj~JZasSSA - almost half the size.

@Optimizer I'll add an explanation when I'm less busy.

Pyth, 75 71 67
DcGHFk_UQJf!s:GeS,0-TkhS,h+TklGUQIJRsmcX>G0dhHhHJ)R]Gjbmjdmebkcm0Q0

Recursive combinatorial solution.
It's a fairly direct translation from this Python solution:
N = int(input())

def gen(l, p):
    for d in reversed(range(N)):
        s = []
        for i in range(N):
            if not sum(l[max(0,i-d):min(i+d+1, len(l))]):
                s.append(i)

        if s:
            r = []
            for possib in s:
                j = l[:]
                j[possib] = p+1
                r += gen(j, p+1)

            return r

    return [l]

print("\n".join(" ".join(str(x % 10) for x in sol) for sol in gen([0] * N, 0)))

How does that work? In more detail than "recursive combinatorial solution".

@tbodt Added the Python code which I wrote before translating to Pyth.

C, 929 878 bytes
This one's a monster, guys. Sorry.
typedef unsigned long U;typedef unsigned char C;U f(int*u,n){C c[8],a[8];*(U*)(&c)=-1;int i,b=0,l=-9,s=-2,f=0,d;for (i=0; i<n; i++) {if (!u[i]&&s<0)s=i,l=0;if(!u[i])l++;if(u[i]&&s>=0){if(!s)l=2*l-1;d=(l-1)/2;if(b<d)*(U*)(a)=0,*(U*)(c)=-1,*c=s,*a=l,f=1,b=d;else if(b==d)c[f]=s,a[f++]=l;s=-1;}}if(s>=0&&l){l=2*l-1;d=(l-1)/2;if(b<d)*(U*)(c)=-1,*c=s,*a=l,f=1,b=d;else if(b==d)c[f]=s,a[f++]=l;}d=f;for(i=0;i<d;i++){if((c[i]+1)&&c[i]){if(c[i]+a[i]==n)c[i]=n-1;else{if(!(a[i]%2))c[f++]=b+c[i]+1;c[i]+=b;}}}return*(U*)c;}void P(int*u,n,i,c,m){for(i=0;i<n;i++){if(!u[i])c++;if(u[i]>m)m=u[i];}if(!c){for(i=0;i<n;i++)printf("%d",u[i]==10?0:u[i]);printf("\n");}else{int s[8][n];for(i=0;i<8;i++)for(c=0;c<n;c++)s[i][c]=u[c];U t=f(u,n);C*H=&t;for(i=0;i<8;i++)if((C)(H[i]+1))s[i][H[i]]=m+1,P(s[i],n,0,0,0);}}void L(n){int u[n],i,j;for(i=0;i<n;i++){for(j=0;j<n;j++)u[j]=j==i?1:0;P(u,n,0,0,0);}}

Defines 3 functions, f(int*,int),P(int*,int,int,int,int), and L(int). Call L(n), and it outputs to STDOUT.
Output for n=5:
14352
15342
31452
31542
41352
51342
41532
51432
24153
25143
34152
35142
23415
23514
24513
25413
24315
25314
24351
25341

Update: I removed separators and fixed up the code. The old code not only failed for n=7+, but failed to output anything at all for n=10 (oops!). I've more thoroughly tested this bunch. It now supports input of up to n=13 (though the "%d" should be changed to "%x"so it prints in hexadecimal). The size of input depends on sizeof(long) and it is assumed to be 8 in practice.
Here's some explanation of how it works, and why such an odd restriction exists:
These were used a lot, so we define them to save a couple bytes:
typedef unsigned long U; typedef unsigned char C;
Here is f:
U f(int*u,n){
    C c[8],a[8];
    *(U*)(&c)=-1;
    int i,b=0,l=-9,s=-2,f=0,d;
    for (i=0; i<n; i++) {
        if (!u[i]&&s<0)
            s=i,l=0;
        if(!u[i])
            l++;
        if(u[i]&&s>=0){
            if(!s)
                l=2*l-1;
            d=(l-1)/2;
            if(b<d)
                *(U*)(a)=0,
                *(U*)(c)=-1,
                *c=s,
                *a=l,
                f=1,
                b=d;
            else if(b==d)
                c[f]=s,a[f++]=l;
            s=-1;
        }
    }
    if(s>=0&&l){
        l=2*l-1;
        d=(l-1)/2;
        if(b<d)
            *(U*)(c)=-1,
            *c=s,
            *a=l,
            f=1,
            b=d;
        else if(b==d)
            c[f]=s,a[f++]=l;
    }
    d=f;
    for(i=0;i<d;i++){
        if((c[i]+1)&&c[i]){
            if(c[i]+a[i]==n)
                c[i]=n-1;
            else{
                if(!(a[i]%2))
                    c[f++]=b+c[i]+1;
                c[i]+=b;
            }
        }
    }
    return*(U*)c;
}

f takes an array of integers of size n, and n itself. The only clever bit here is that it returns an unsigned long, which is converted into a char[8] by the calling function. Each character in the array is thus set either to 0xFF or to an index pointing to a valid urinal for the next person. For n<10, we never need more than 5 bytes to hold every valid urinal the next person can use.
Here is P:
void P(int*u,n,i,c,m){
    for(i=0;i<n;i++){
        if(!u[i])c++;
        if(u[i]>m)m=u[i];
    }
    if(!c){
        for(i=0;i<n;i++)
            printf("%d",u[i]==10?0:u[i]);
        printf("\n");
    }
    else{
        int s[8][n];
        for(i=0;i<8;i++)
            for(c=0;c<n;c++)
                s[i][c]=u[c];
        U t=f(u,n);
        C*H=&t;
        for(i=0;i<8;i++)
            if((C)(H[i]+1))
                s[i][H[i]]=m+1,P(s[i],n,0,0,0);
    }
}

P takes an array u of size n wherein exactly one element is set to 1, and the rest are 0. It then finds and prints every permutation possible recursively.
Here is L:
void L(n){
    int u[n],i,j;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            u[j]=j==i?1:0;
        P(u,n,0,0,0);
    }
}

L simply calls P n times with different starting positions each time.
For the interested, this (less golfed) f will generate the sequence in A095236.
U f(int*u,n) {
    C c[8];
    *(U*)(&c) = -1;
    int i,b=0,l=-10,s=-2,f=0,d;
    for (i=0; i<n; i++) {
        if (!u[i]&&s<0) {
            s=i,l=0;
        }
        if(!u[i]){
            l++;
        }
        if (u[i]&&s>=0) {
            if (!s) {
                l=2*l-1;
            }
            if (b<l) {
                *(U*)(&c)=-1;
                c[0]=s;
                f=1;
                b=l;
            }
            else if (b==l)
                c[f++]=s;
            s=-1;
        }
    }
    if (s>=0&&l) {
        l=2*l-1;
        if (b<l) {
            *(U*)(&c)=-1;
            c[0]=s;
            f=1;
            b=l;
        }
        else if (b==l)
            c[f++]=s;
    }
    d=f;
    for (i=0; i<d; i++) {
        if ((c[i]+1)&&c[i]) {
            if (c[i]+b==n) {
                c[i]=n-1;
            }
            else{
                if (!(b%2)) {
                    c[f++]=(b-1)/2+c[i]+1;
                }
                c[i]+=(b-1)/2;
            }
        }
    }
    return *(U*)c;
}

"1 4 ..." at the start seems to be against the spec: if the first number is 1, the next one should be 5.

@anatolyg No. Here's a step-by-step explanation of how "1 4" can happen: https://gist.github.com/orlp/a5706ba664b70209b48a

Remember, the separators are optional. You can save 1 byte(!) by removing the space after the %d :-)

@UriZarfaty Thanks! Actually, there are a ton of bytes to be saved here. I'm currently writing a better solution up and an explanation.

@yo' I think you're confusing the output a little bit. An output of 14352 means person #1 chose the left-most urinal. Person #2 chose the right-most one, which then forced #3 into the middle. It's not the number of the urinal picked next that should be output.

@BrainSteel Ah ok, got it now, thanks!

Python 2, 208
n=input()
r=range(n)
l=[0]*n
def f(a,d=-1):
 if a>n:print''.join(l);return
 for i in r:
  t=min([n]+[abs(i-j)for j in r if l[j]])
  if t==d:p+=[i]
  if t>d:p=[i];d=t
 for i in p:l[i]=`a%10`;f(a+1);l[i]=0
f(1)

Recursive approach.

JavaScript (ES6) 153 160 169
Edit Using Math.min to find (of course) the max distance: streamlined code and 16 bytes saved.
Recursive search, can work with n > 10, just remove % 10 (and be prepared to wait while the console unrolls all its output).
I use a single array to store the slot in use (positive numbers) or the current distance from the nearest slot (negative numbers so < and > are swapped in code).
F=n=>{(R=(m,d,t,x=Math.min(...d=m?
  d.map((v,i)=>(c=i<t?i-t:t-i)?v<c?c:v:m%10)
  :Array(n).fill(-n)))=>
x<0?d.map((v,i)=>v>x||R(-~m,d,i)):console.log(d+[]))()}

Ungolfed
F=n=>{
  var R=(m, // current 'man', undefined at first step
   d, // slot array
   t // current position to fill
  ) =>
  {
    if (m) // if not at first step
    {
      d[t] = m % 10; // mark slot in use, (10 stored as 0 )
      d = d.map((v,i) => { // update distances in d[]
        var c = i<t ? i-t : t-i; // distance from the current position (negated)
        return v < c ? c : v; // change if less than current distance
      });
    }
    else
    {
      d = Array(n).fill(-n) // fill distance array with max at first step
      // negative means slot free, value is the distance from nearest used slot
      // >= 0 means slot in use by man number 1..n
    }
    var x = Math.min(...d);
    if ( x < 0 ) // if there is still any free slot
    {
      d.forEach((v,i) => { // check distance for each slot
        if (v <= x) // if slot is at max distance, call recursive search
          R(-~m, [...d], i) // ~- is like '+1', but works on undefined too
      });
    }
    else
    {
      console.log(d+[]); // no free slot, output current solution
    }
  }

  R() // first step call
}

Test In Firefox/FireBug console
F(5)

1,4,3,5,2
1,5,3,4,2
3,1,4,5,2
3,1,5,4,2
4,1,3,5,2
5,1,3,4,2
4,1,5,3,2
5,1,4,3,2
2,4,1,5,3
2,5,1,4,3
3,4,1,5,2
3,5,1,4,2
2,3,4,1,5
2,3,5,1,4
2,4,3,1,5
2,5,3,1,4
2,4,5,1,3
2,5,4,1,3
2,4,3,5,1
2,5,3,4,1

Mathematica, 123 104
f[n_,s_:{}]:=If[Length@s<n,f[n,s~Join~{#}]&/@MaximalBy[Range@n,Min@Abs[#-s]&];,Print@@Ordering@s~Mod~10]

@MartinBüttner n~f~s~Join~{#} will become Join[f[n,s],{#}].

Oh right, I thought it was right associative.

MATLAB, 164
function o=t(n),o=mod(r(zeros(1,n)),10);function o=r(s),o=[];d=bwdist(s);m=max(d);J=find(d==m);if~d,o=s;J=[];end,n=max(s)+1;for j=J,o=[o;r(s+n*(1:numel(s)==j))];end

Perl, 174
Not very short, but fun. I'm not counting use feature 'say'; towards the byte total.
$n=pop;@u="_"x$n." "x$n."_"x$n;for$p(1..$n){@u=map{my@r;for$x(reverse 0..$n){
s/(?<=\D{$x}) (?=\D{$x})/push@r,$_;substr $r[-1],pos,1,$p%10/eg and last;
}@r}@u}y/_//d&&say for@u

De-golfed:
$n = pop; # Get number of urinals from commandline
@state = ( "_" x $n . " " x $n . "_" x $n );

for my $person (1 .. $n) {
  # Replace each state with its list of possible next states.
  @state = map {
    my @results;
    for my $distance (reverse 0 .. $n) {
      # If there are any spots with at least $distance empty on
      # both sides, then add an entry to @results with the current
      # $person number in that spot, for each spot. Note that this
      # is only used for its side-effect on @results; the modified $_
      # is never used.
      s{
        (?<=\D{$distance})
        [ ]
        (?=\D{$distance})
      }{
        push @results, $_;
        substr $results[-1], pos(), 1, $person % 10;
      }xeg
      # If we found any spots, move on, otherwise try
      # with $distance one lower.
      and last;
    }
    # New state is the array we built up.
    @results;
  } @state;
}

# After adding all the people, remove underscores and print the results
for my $result (@state) {
  $result =~ tr/_//d;
  say $result;
}

Bash, 744 674 bytes
This is still way too long :). I use a string to represent the row of urinals and a flooding algorithm to find the most distant urinals in each phase of recursion. The ungolfed code is almost self-explanatory. The number of urinals is read from keyboard.
Code (golfed):
read l;u=----------;u=-${u::$l}-
s(){ u=${u:0:$1}$2${u:$((1+$1))};}
m(){ local u=$1;a=();while :;do [ 0 -ne `expr index - ${u:1:$l}` ]||break;t=$u;y=$u;for i in `seq $l`;do [ ${y:$i:1} = - ]||{ s $(($i-1)) X;s $(($i+1)) X;};done;done;while :;do k=`expr index $t -`;[ 0 != $k ]||break;t=${t:0:$(($k-1))}X${t:$k};if [ 1 -ne $k ]&&[ $(($l+2)) -ne $k ];then a+=($(($k-1)));fi;done;}
e(){ local u f b v;u=$1;f=$2;if [ 1 -eq $l ];then echo 1;return;fi;if [ 1 = $f ];then for i in `seq $l`;do v=$u;s $i 1;e $u 2;u=$v;done;else m $u;b=(${a[@]});if [ 0 -eq ${#b} ];then echo ${u:1:$l};else for i in ${b[@]};do v=$u;s $i $(($f%10));e $u $(($f+1));u=$v;a=(${b[@]});done;fi;fi;}
e $u 1

Use:
$ source ./script.sh
input number of urinals from keyboard

And ungolfed it goes:
read l  # read number of urinals
u=----------
u=-${u:0:$l}- #row is two positions longer (it will be helpful when finding the most distant urinals)

# So, for the end, with 6 men, u might look like this:
# -143652-

# subu no fellow_no => set urinal [number] occupied by [fellow_no]
# this is just convenience for resetting a character inside a string
subu(){ u=${u:0:$1}$2${u:$((1+$1))};}

# this will be iterated in longest to find the remotest places:
# -1---3---2- => spreadstep => X1X-X3X-X2X => spreadstep => X1XXX3XXX2X
# see longest() to get more explanation.
spreadstep()
{
    y=$u
    for i in `seq 1 $l`
    do
    if [ "${y:$i:1}" != "-" ]
    then
        subu $(($i-1)) X
        subu $(($i+1)) X
    fi
    done
}

# Find the urinals with the longest distance. It uses spreadstep() - see above.
# -1---3---2- => spreadstep => X1X-X3X-X2X => spreadstep => X1XXX3XXX2X
# ---> last state with free ones was X1X-X3X-X2X ,
#                                     123456789
# free urinals are no. 3 and no. 7 => save them to arr
longest()
{
    local u=$1
    arr=()
    while true
    do
        if [ 0 -eq `expr index - ${u:1:$l}` ]
        then
            break
        fi
        save=$u
        spreadstep
    done

    while true
    do
        index=`expr index $save -`
        if [ 0 == $index ]
        then
            break
        fi

        save=${save:0:$(($index-1))}X${save:$index}
        if [ 1 -ne $index ] && [ $(($l+2)) -ne $index ]
        then
            arr+=($(($index-1)))
        fi
    done
}

# main function, recursively called
# the first fellow may take any of the urinals.
# the next fellows - only those with the longest distance.
placements_with_start()
{
    local u=$1
    local fellow=$2
    if [ 1 -eq $l ] # special case - there is no 2nd fellow, so below code would work incorrect
    then
        echo "1"
        return
    fi
    if [ 1 == $fellow ]       # may take any of urinals
    then
        for i in `seq 1 $l`
        do
            local _u=$u
            subu $i 1                     # take the urinal
            placements_with_start $u 2    # let the 2nd fellow choose :)
            u=$_u
        done
    else
        longest $u   # find the ones he can take
        local _arr=(${arr[@]})
        if [ 0 -eq ${#_arr} ]
        then
            echo ${u:1:$l}    # no more free urinals - everyone took one - print the result
        else
            for i in ${_arr[@]}
            do
                local _u=$u
                subu $i $(($fellow % 10))                # take urinal
                placements_with_start $u $(($fellow+1))  # find locations for for next fellow
                u=$_u
                arr=(${_arr[@]})
            done
        fi
    fi
}

placements_with_start $u 1

C, 248 bytes
This code uses a recursive algoritm to generate the desired outcome.
void q(char*f,int l,int d,char*o){char*c=f;while(f<c+l){if(!*f){sprintf(o+4*d,"%03i,",f-c);*f=1;q(c,l,d+1,o);*f=0;}f++;}if(d+1==l){o[4*d+3]=0;printf("%s\n",o);}}int main(int i,char**v){int k=atoi(v[1]);char*c=calloc(k,5),*o=c+k;q(c,k,0,o);free(c);}

Expanded:
void printperms(char* memory,int length,int offset,char*output)
{
    char*temp_char=memory;
    while(memory<temp_char+length)
    {
        if(!*memory)
        {
            sprintf(output+4*offset,"%03i,",memory-temp_char);
            *memory=1;
            printperms(temp_char,length,offset+1,output);
            *memory=0;
        }
        memory++;
    }
    if(offset+1==length)
    {
        output[4*offset+3]=0;
        printf("%s\n",output);
    }
}

int main(int i,char**v)
{
    int argument=atoi(v[1]);
    char*t=calloc(argument,5),*output=t+argument;
    printperms(t,argument,0,output);
    free(t);
}