text:
Write a brainfuck compiler
Write a program that takes a brainfuck program and compiles it to executable machine code. You can target x86, x86_64, jvm (java bytecode) or armv6, and use one of the following executable formats: ELF, a.out, class file, exe, com. The executable should work in Linux or Windows (or Java on either).
Neither your program nor the generated executable may run any external program (such as another compiler, assembler or interpreter).
Shortest code wins.

Any reason for downvoting?

Any chance you have any sources for machine code?
This would be my first machine code golfing exercise if you happen to have any resources I could use as an example?

@Eliseod'Annunzio I don't have any particular resources, but generally you can start by looking into assembly language for your platform of choice, and assemble/disassemble some examples. Google is your friend :) A looong time ago I participated in a couple of machine code golfing competitions, I didn't do very well but I remember we were using the com format for DOS, as it had no extra headers and stuff, just code. Maybe other people can give more links and suggestions.

C, 866  783 bytes
Since my code outputs 32 bit ELF executable I can't promise that it will work on everyones setup. It took enough tweaking to get the executable to stop segfaulting on my computer.
For anyone trying to run this:
$ uname --all
Linux 4.4.0-24-generic #43-Ubuntu SMP Wed Jun 8 19:27:37 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux

A Brainfuck program is read from stdin and the compiled ELF is written to stdout.
#define P *(t++)
#define C case
#define B break
char a[30000],b[65535],f,*t=b;*c[100];**d=c;main(g){P=188;t+=4;while((f=getchar())!=-1)switch(f){C'>':P=68;B;C'<':P=76;B;C'+':P=254;P=4;P=36;B;C'-':P=254;P=12;P=36;B;C'.':P=187;t+=4;P=137;P=225;P=186;P=1;t+=3;P=184;P=4;t+=3;P=205;P=128;B;C',':P=187;P=1;t+=3;P=137;P=225;P=186;P=1;t+=3;P=184;P=3;t+=3;P=205;P=128;B;C'[':P=138;P=4;P=36;P=133;P=192;P=15;P=132;t+=4;*d=(int*)t-1;d++;B;C']':P=138;P=4;P=36;P=133;P=192;P=15;P=133;t+=4;d--;g=((char*)(*d+1))-t;*((int*)t-1)=g;**d=-g;B;}P=184;P=1;t+=3;P=187;t+=4;P=205;P=128;*(int*)(b+1)=0x8048054+t-b;long long z[]={282579962709375,0,4295163906,223472812116,0,4297064500,4294967296,577727389698621440,36412867248128,30064779550,140720308490240};write(1,&z,84);write(1,b,t-b);write(1,a,30000);}

Ungolfed
In the ungolfed version of the code, you can get a better idea of what's going on. The character array at the end of the golfed code is an encoding of the ELF and program header in the ungolfed code. This code also show how each Brainfuck instruction is translated into bytecode.
#include <linux/elf.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <stdio.h>
#include <stdint.h>

#define MAX_BIN_LEN 65535
#define MAX_JUMPS 100

unsigned int org = 0x08048000;

unsigned char move_right[] = {0x44};                              /*inc   esp         */

unsigned char move_left[]  = {0x4c};                              /*dec   esp         */

unsigned char inc_cell[]   = {0xfe,0x04,0x24};                    /*inc   [esp]       */

unsigned char dec_cell[]   = {0xfe,0x0c,0x24};                    /*dec   [esp]       */

unsigned char read_char[]  = {0xbb,0x00,0x00,0x00,0x00,           /*mov   ebx,  0     */
                              0x89,0xe1,                          /*mov   ecx,  esp   */
                              0xba,0x01,0x00,0x00,0x00,           /*mov   edx,  1     */
                              0xb8,0x03,0x00,0x00,0x00,           /*mov   eax,  3     */
                              0xcd,0x80};                         /*int   0x80        */

unsigned char print_char[] = {0xbb,0x01,0x00,0x00,0x00,           /*mov   ebx,  1     */
                              0x89,0xe1,                          /*mov   ecx,  esp   */
                              0xba,0x01,0x00,0x00,0x00,           /*mov   edx,  1     */
                              0xb8,0x04,0x00,0x00,0x00,           /*mov   eax,  4     */
                              0xcd,0x80};                         /*int   0x80        */

unsigned char loop_start[] = {0x8a,0x04,0x24,                     /*mov   eax,  [esp] */
                              0x85,0xc0,                          /*test  eax,  eax   */
                              0x0f,0x84,0x00,0x00,0x00,0x00};     /*je    int32_t     */

unsigned char loop_end[]   = {0x8a,0x04,0x24,                     /*mov   eax,  [esp] */
                              0x85,0xc0,                          /*test  eax,  eax   */
                              0x0f,0x85,0x00,0x00,0x00,0x00};     /*jne   int32_t     */

unsigned char call_exit[]  = {0xb8,0x01,0x00,0x00,0x00,           /*mov   eax,  1     */
                              0xbb,0x00,0x00,0x00,0x00,           /*mov   ebx,  0     */
                              0xcd,0x80};                         /*int   0x80        */
unsigned char prelude[]    = {0xbc,0x00,0x00,0x00,0x00};          /*mov   esp, int32_t*/

unsigned char tape[100];

int main(){
    unsigned char text[MAX_BIN_LEN];
    unsigned char *txt_ptr = text;

    int32_t *loop_jmps[MAX_JUMPS];
    int32_t **loop_jmps_ptr = loop_jmps;

    Elf32_Off entry;

    entry = org + sizeof(Elf32_Ehdr) + 1 * sizeof(Elf32_Phdr);

    memcpy(txt_ptr,prelude,sizeof(prelude));
    txt_ptr += sizeof(prelude);
    char input;
    while((input = getchar()) != -1){
        switch(input){
            case '>':
                memcpy(txt_ptr,move_right,sizeof(move_right));
                txt_ptr += sizeof(move_right);
                break;
            case '<':
                memcpy(txt_ptr,move_left,sizeof(move_left));
                txt_ptr += sizeof(move_left);
                break;
            case '+':
                memcpy(txt_ptr,inc_cell,sizeof(inc_cell));
                txt_ptr += sizeof(inc_cell);
                break;
            case '-':
                memcpy(txt_ptr,dec_cell,sizeof(dec_cell));
                txt_ptr += sizeof(dec_cell);
                break;
            case '.':
                memcpy(txt_ptr,print_char,sizeof(print_char));
                txt_ptr += sizeof(print_char);
                break;
            case ',':
                memcpy(txt_ptr,read_char,sizeof(read_char));
                txt_ptr += sizeof(read_char);
                break;
            case '[':
                memcpy(txt_ptr,loop_start,sizeof(loop_start));
                txt_ptr += sizeof(loop_start);
                *loop_jmps_ptr = (int32_t*) txt_ptr - 1;
                loop_jmps_ptr++;
                break;
            case ']':
                memcpy(txt_ptr,loop_end,sizeof(loop_end));
                txt_ptr += sizeof(loop_end);
                loop_jmps_ptr--;
                int32_t offset = ((unsigned char*) (*loop_jmps_ptr + 1)) - txt_ptr;
                *((int32_t*)txt_ptr - 1) = offset;
                **loop_jmps_ptr = -offset;
                break;
        }
    }

    memcpy(txt_ptr,call_exit,sizeof(call_exit));
    txt_ptr += sizeof(call_exit);

    *(int32_t*)(text + 1) = entry + (txt_ptr - text);

    Elf32_Ehdr ehdr = {
        {0x7F,'E','L','F',ELFCLASS32,ELFDATA2LSB,EV_CURRENT,0,0,0,0,0,0,0,0,0},
        ET_EXEC,
        EM_386,
        EV_CURRENT,
        entry,
        sizeof(Elf32_Ehdr),
        0,
        0,
        sizeof(Elf32_Ehdr),
        sizeof(Elf32_Phdr),
        1,
        0,
        0,
        SHN_UNDEF,
    };

    Elf32_Phdr phdr = {
        PT_LOAD,
        0,
        org,
        org,
        sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + (txt_ptr - text),
        sizeof(Elf32_Ehdr) + sizeof(Elf32_Phdr) + (txt_ptr - text),
        PF_R | PF_X | PF_W,
        0x1000,
    };

    int out = open("a.out",O_CREAT|O_TRUNC|O_WRONLY,S_IRWXU);
    write(out,&ehdr,sizeof(Elf32_Ehdr));
    write(out,&phdr,sizeof(Elf32_Phdr));

    write(out,text,txt_ptr-text);
    write(out,tape,sizeof(tape));
    close(out);
}

Self Modifying BrainFuck
In order to save on bytes, the tape for my compiler isn't allocated in a .bss section or anything fancy like that. Instead, the tape is 30,000 null bytes written directly after the compiled byte code of the Brainfuck program. Knowing this, and being aware of what byte code is generated by my compiler means that you can generate or modify byte code at runtime. A simple illustration of this 'feature' is a Brainfuck program that sets its own exit value.
 <<<<<<+

The program goes off the left edge of the tape into the byte code to the point that the exit code is normally set 0. Incrementing this byte causes the exit code to be set to 1 instead of 0 when the program eventually exits. With persistence, this could be used to do system level programming in Brainfuck.

Nice; your code actually has 865 bytes (you don't need a newline at the end of the file). Also, you can merge char variable declarations. I wonder if that long array can be compressed too, as it has many zeros.

@aditsu I've been working on finding some better encoding for the header array. C doesn't come with any built in compression libraries so zipping it seems out of the question. The best I've come up with is encoding it as an array of long long int instead of char. There's definitely room for me to golf out some of my variable declarations. I'll see how much I can get there and update my answer.

I was thinking some form of RLE, but.. whatever works :)

you may replace '577727389698621440' by '4105*pow(2,47)' using implicit declaration of pow, for 4 bytes (this works with gcc, at least) ~

612 bytes

You do inc esp and then inc [esp]. Shouldn't it be either inc esp; inc byte [esp] or add esp, 4; inc [esp]?

@xiver77 The emitted code is correct (opcode 0xfe), but you're right that the mnemonic in the comment should be inc byte [esp].

Python, 1974 chars
import sys
s='\x11\x75\x30\xbc\x08\x4b\x03\x3c'
k=[]
for c in sys.stdin.read():
 if'>'==c:s+='\x84\x01\x01'
 if'<'==c:s+='\x84\x01\xff'
 if'+'==c:s+='\x2a\x1b\x5c\x33\x04\x60\x91\x54'
 if'-'==c:s+='\x2a\x1b\x5c\x33\x04\x64\x91\x54'
 if'['==c:k+=[len(s)];s+='\x2a\x1b\x33\x99\x00\x00'
 if']'==c:a=k[-1];k=k[:-1];d=len(s)-a;s=s[:a+4]+'%c%c'%(d>>8,d&255)+s[a+6:]+'\xa7%c%c'%(-d>>8&255,-d&255)
 if','==c:s+='\x2a\x1b\xb2\x00\x02\xb6\x00\x03\x91\x54'
 if'.'==c:s+='\xb2\x00\x04\x59\x2a\x1b\x33\xb6\x00\x05\xb6\x00\x06'
s+='\xb1'
n=len(s)
sys.stdout.write('\xca\xfe\xba\xbe\x00\x03\x00-\x00+\n\x00\x08\x00\x13\t\x00\x14\x00\x15\n\x00\x16\x00\x17\t\x00\x14\x00\x18\n\x00\x19\x00\x1a\n\x00\x19\x00\x1b\x07\x00\x1c\x07\x00\x1d\x01\x00\x06<init>\x01\x00\x03()V\x01\x00\x04Code\x01\x00\x0fLineNumberTable\x01\x00\x04main\x01\x00\x16([Ljava/lang/String;)V\x01\x00\nExceptions\x07\x00\x1e\x01\x00\nSourceFile\x01\x00\x06B.java\x0c\x00\t\x00\n\x07\x00\x1f\x0c\x00 \x00!\x07\x00"\x0c\x00#\x00$\x0c\x00%\x00&\x07\x00\'\x0c\x00(\x00)\x0c\x00*\x00\n\x01\x00\x01B\x01\x00\x10java/lang/Object\x01\x00\x13java/io/IOException\x01\x00\x10java/lang/System\x01\x00\x02in\x01\x00\x15Ljava/io/InputStream;\x01\x00\x13java/io/InputStream\x01\x00\x04read\x01\x00\x03()I\x01\x00\x03out\x01\x00\x15Ljava/io/PrintStream;\x01\x00\x13java/io/PrintStream\x01\x00\x05write\x01\x00\x04(I)V\x01\x00\x05flush\x00!\x00\x07\x00\x08\x00\x00\x00\x00\x00\x02\x00\x01\x00\t\x00\n\x00\x01\x00\x0b\x00\x00\x00\x1d\x00\x01\x00\x01\x00\x00\x00\x05*\xb7\x00\x01\xb1\x00\x00\x00\x01\x00\x0c\x00\x00\x00\x06\x00\x01\x00\x00\x00\x03\x00\t\x00\r\x00\x0e\x00\x02\x00\x0b\x00\x00'+'%c%c'%((n+60)>>8,(n+60)&255)+'\x00\x04\x00\x03\x00\x00'+'%c%c'%(n>>8,n&255)+s+'\x00\x00\x00\x01\x00\x0c\x00\x00\x00*\x00\n\x00\x00\x00\x05\x00\x06\x00\x06\x00\x08\x00\t\x00\x0b\x00\x0b\x00\x13\x00\r\x00\x1d\x00\x0f\x00&\x00\x11\x00,\x00\x12\x002\x00\x14\x008\x00\x15\x00\x0f\x00\x00\x00\x04\x00\x01\x00\x10\x00\x01\x00\x11\x00\x00\x00\x02\x00\x12')

Below are the translations to java bytecode.  local 0 is a byte array representing the tape, local 1 is the data pointer.
>  iinc 1,+1
<  iinc 1,-1
+  aload_0;iload_1;dup2;baload;iconst_1;iadd;i2b;bastore
-  aload_0;iload_1;dup2;baload;iconst_1;isub;i2b;bastore
[  aload_0;iload_1;baload;ifeq xx xx
]  goto xx xx
,  aload_0;iload_1;getstatic #2;invokevirtual #3;i2b;bastore
.  getstatic #4;dup;aload_0;iload_1;baload;invokevirtual #5;invokevirtual #6

The xx xx are offsets to reach the matching bracket.  #2 is System.in, #3 is read(), #4 is System.out, #5 is write(), and #6 is flush().
The preamble allocates a 30000 byte array and initializes the tape position to 0.
The giant wrapper at the end was generated by compiling a dummy B.java file with code for one of each opcode (to induce generation of the correct constant tables and other junk), then performing delicate surgery on it.
Run it like
python bfc.py < input.b > B.class
java B

Disassemble with
javap -c B

I'm sure it could be golfed some more.  I'm just happy it works...

Use from sys import* and then shave off 2 chars by removing both sys.

You could use base64 to encode that binary data and shave off some bytes

16-bit x86 assembly code, 104 bytes
This code is from 2014, but I just found the task.
;compliant version, non-commands are ignored, but 104 bytes long

[bits 16]
[org 0x100]
; assume bp=091e used
; assume di=fffe
; assume si=0100
; assume dx=cs (see here)
; assume cx=00ff
; assume bx=0000
; assume ax=0000 used (ah)
; assume sp=fffe
start:
        mov al, code_nothing - start
code_start:
        mov ch, 0x7f ; allow bigger programs
        mov bx, cx
        mov di, cx
        rep stosb
        mov bp, find_right + start - code_start ;cache loop head for smaller compiled programs
        jmp code_start_end
find_right:
        pop si
        dec si
        dec si ;point to loop head
        cmp [bx], cl
        jne loop_right_end
loop_right:
        lodsb
        cmp al, 0xD5 ; the "bp" part of "call bp" (because 0xFF is not unique, watch for additional '[')
        jne loop_left
        inc cx
loop_left:
        cmp al, 0xC3 ; ret (watch for ']')
        jne loop_right
        loop loop_right ;all brackets matched when cx==0
        db 0x3c ;cmp al, xx (mask push)
loop_right_end:
        push si
        lodsw ; skip "call" or dummy "dec" instruction, depending on context
        push si
code_sqright:
        ret
code_dec:
        dec byte [bx]
code_start_end:
        db '$' ;end DOS string, also "and al, xx"
code_inc:
        inc byte [bx]
        db '$'
code_right:
        inc bx ;al -> 2
code_nothing:
        db '$'
code_left:
        dec bx
        db '$'
code_sqleft:
        call bp
        db '$'
; create lookup table
real_start:
        inc byte [bx+'<'] ;point to code_left
        dec byte [bx+'>'] ;point to code_right
        mov byte [bx+'['], code_sqleft - start
        mov byte [bx+']'], code_sqright - start
        lea sp, [bx+45+2] ;'+' + 4 (2b='+', 2c=',', 2d='-', 2e='.')
        push (code_dec - start) + (code_dot - start) * 256
        push (code_inc - start) + (code_comma - start) * 256
pre_write:
        mov ah, code_start >> 8
        xchg dx, ax
; write
        mov ah, 9
        int 0x21
; read
code_comma:
        mov dl, 0xff
        db 0x3d ; cmp ax, xxxx (mask mov)
code_dot:
        mov dl, [bx]
        mov ah, 6
        int 0x21
        mov [bx], al
        db '$'
        db 0xff ; parameter for '$', doubles as test for zero
; switch
        xlatb
        jne pre_write
  ; next two lines can also be removed
  ; if the program ends with extra ']'
  ; and then we are at 100 bytes... :-)
the_end:
        mov dl, 0xC3
        int 0x21
        int 0x20

Are you sure it's not an interpreter?

No, it's absolutely a compiler.  "bf.com < hello.bf > out.com", then out.com will be executable.

Ok, can you please explain how to compile it and what OS it works in? I haven't been able to run it yet.

assemble with YASM, run in MS-DOS (via DOSBox is okay).

Ok, I tried it (bf.com < hello.bf > out.com), it took a long time, and generated a 19MB OUT.COM, which freezes when I run it. It seems that your code just outputs random junk.

I found your code on github, it looks like something happened to lines 63-64 when you copied and pasted it (it probably got treated as html). That code also seems to output very large quantities of random junk, but this new junk managed to print "Hello World!" before freezing.

Anyway, even if you fix these problems, your program doesn't really qualify because one of the requirements is: "The executable should work in Linux or Windows (or Java on either)."

The '<' and '>' need to be escaped.  Anyway, 32-bit Windows has a DOS console where will run, and "com" is explicitly one of the allowed formats.

Oh, you should have said that earlier. It behaves much better in (32-bit) windoze - it doesn't add tons of random junk and the generated program terminates nicely (at least the Hello World example). However, I tried the prime example and it doesn't seem to take input, is there something I need to do?


text:
Shortest string expressions stable under deleting quotes
Forgetting quotes can lead to certain problems.
For example, in Scala the two expressions:
"("+("+")+(")+(")+")"
 ("+("+")+(")+(")+")

differ only in starting and ending quotes, but they respectively yield the result:
(+)+()
+()+()+

But this expression in scala almost has the desired property:
def m="+m+"
""+m+""

Your task is to write the shortest expression surrounded with quotes, such that if we remove the outer quotes, the expression still returns the same string.
Key points:

Your language must support "..." as string literals
The program has to contain at least three characters
You are not allowed to define a context outside of the quotes themselves (as I did for m)
You are not allowed to use other delimiters for strings, e.g. no """, no '.
Both expressions should return strings.
Shortest code wins (counting the quotes themselves)

return or output? can we do either? Also, how is "quine" related to this?

This problem isn't even a little quineish.

@boothby But now it's a completely different question.

@Howard I changed only the title to reflect the content of the question.

@Quincunx: Both return or output, but it should be a string. I added a line to describe it. The relation with quines is that solutions somehow encode a part of the program in a string. Ok I agree it's more a far-distant cousin relationship.

And besides, if you manage to write a quine without quotes, then encompassing it with quotes would be an answer (see Befunge answer).

What is a “program” in the sense of your question? Your examples look like you were referring to expressions, i.e. part of a program. After all, a complete stand-alone executable program will hardly “return” anything except perhaps for an exit code. Programs usually print things. But this is not completely clear, and clarification of that point might make things clearer.

Ok I updated. It should be an expression.

@MikaëlMayer when are you going to accept an answer (the shortest valid solution: mine or MvG's)?

yes you're right. I thought that your program did not return a string. Updated.

@MikaëlMayer Next time, use the @ notation, I had no idea you told me that.

Befunge 98 - 3, 4, 6, 17
In these programs, I'll assume you just want to get a string, but you don't care if the program terminates. In other words, you want a code snippet that can be placed in the code somewhere. (Note: in Befunge, whatever is on the stack is a string. It is also a number)
This code snippet must be placed on the first part of the first line.
"g"

When the quotes are removed, g acts like 00g, so it pushes a g. Either way, it pushes a g.
""""

Works in Befunge 93 as well; it always pushes nothing.
This one is more interesting
""z"z"

It will always push z. z is a no-op so although the IP executes the command, it does nothing (I could have used  , but z is more interesting).
This one only has one set of ", and is quine-like:
">:0g\1+:f`1+jb<"

It always pushes the contents of the string, but when the quotes are removed, it does it in a quine-like way. This must be placed on the first part of the first line, but adjustments can be made to put it elsewhere

I updated the question so that it removes the first case: "Both programs should return strings."

@MikaëlMayer No, the first case is not removed. Both programs "g" and g return strings, one is g, and the other is g.

C  (4 chars)
The expression
""""

satisfies the minimal requirement of three characters. It encodes the empty string, no matter even if you omit one level of quotes:
 ""

If you want the resulting string to be at least three characters, here is an expression of length 10 which results in three characters of string, namely three spaces:
""   "   "
 "   "

If you don't like spaces either, here are four printable characters in a length 12 expression:
""/**/"/**/"
 "/**/"/**/

Putting these expressions into a small program:
#include <stdio.h>
#define CASE(s) printf("'%s'\n", s)
int main() {
  CASE("""");
  CASE("");
  CASE(""   "   ");
  CASE("   "   );
  CASE(""/**/"/**/");
  CASE("/**/"/**/);
}

Output:
''
''
'   '
'   '
'/**/'
'/**/'

JavaScript, 28 27 15 12 (6 if result can be non-string (still works with output))
This one's pretty interesting.
"+"*1+"+"+""

The basic explanation is that "string" * 1 is NaN, and +"string" is also NaN. Therefore, it results in the string "NaN+" with or without the outside quotes.
For further explanation, it gets parsed as ("+" * 1) + ("+") + ("") with the outside quotes, and (+ "*1+") + "+" without.
The version that works if the output can be non-string:
"+"*""

Which does work when outputting (as JavaScript is weakly typed):
alert("+"*"") // NaN
alert(+"*")   // NaN

Old version:
"+".replace(/./,NaN)+"+"+""

With the quotes outside, it is parsed as
("+".replace(/./, NaN)) + ("+") + ("")
"NaN" + "+" + ""
"NaN+"

Without the quotes, it gets parsed as
(+".replace(/./,NaN)+") + ("+")
// +"any string" evaluates to NaN
NaN + "+"
"NaN+"

Shell (3 chars)
"w"
w

Both execute the command w.

Seriously?!?  How many seconds of my life have been wasted typing who?

The question doesn't ask you to execute a command, it asks you to return a string.

@PeterTaylor: The way I read it, it asks for an expression which can be interpreted in two ways with the same meaning either way. So the expression above will do that. It is when you type that expression as the sole argument on an otherwise empty command line that the expression gets interpreted as a command name and executed. You could just as well use that expression as an argument to something else, e.g. to echo.

@boothby: assuming your typing speed is the same as mine, about 0.15 seconds per invocation of w.

I updated the question: "Both programs should return strings."

huh?, 7
"Ouch!"

It works because both "Ouch!" and Ouch! are both invalid files, so the interpreter will return Ouch!

Update: Python (12 chars)
program
""+"+""+"+""
"+"+""+"+"

both giving
'++'

Python (28 chars)
program
"".__str__()+".__str__()+"""
".__str__()+".__str__()+""

both giving
'.__str__()+'

Python (38 chars)
program
"".replace("+","+")+".replace("+","")"
".replace("+","+")+".replace("+","")

both giving
'.replace(,)'

so in python, ","")" evaluates to ",)" ? interesting.

yes that was also new to me, it also allows for a more compact solution (see edit).

JavaScript, 40
"(f=function (){return'(f='+f+')()'})()"

When you remove the quotes, it becomes an immediately invoked function expression, and this function happens to return '(f='+f+')()', which is the entirety of the string. (Absuing Function#toString. ;))

Nice usage of quine. Could you do the same without using secondary quotes?

@Mikaël Probably not, since I can't have double quotes inside double quotes :-P

@MikaëlMayer I made a version (completely different one) without secondary quotes! :D http://codegolf.stackexchange.com/a/18188/3808

Perl - 4 bytes
"$~"

Test program:
print"$~";
print$~;

Ouput:
STDOUT
STDOUT

Also works with many other single-character special variables in Perl. Notably,$0, $;, $/, $: and $^ also have a non-empty string as their default value. (So does $", but "$"" is a syntax error.)

PowerShell, 4 chars
"$?"
$?

Output:
TRUE
TRUE

This uses the automatic variable $?, which is a Boolean containing the execution status of the last run command. The only effect of wrapping it in quotes is that it is converted to a string prior to being printed, which is a transparent operation.

I updated the question: "Both programs should return strings."

GolfScript: 16 chars
OK, since my 3-char solution "1" has been disqualified by a rules change, here's the straightforward solution in GolfScript:
"{`[46 126]+}.~"

With the quotes, this is just a double-quoted string literal.  Without the quotes, it's a quine.  The only slightly trickly part is that, to literally comply with the rule prohibiting alternative string delimiters, I have to encode the string '.~' as an array of ASCII codes [46 126] instead.

I updated the question: "Both programs should return strings."

Scala REPL (10 chars)
"0+"++"+0"
 0+"++"+0

are both returning:
0++0
0++0

Explanation: In the first case ++ treats the left string as a sequence of chars and concatenates the next sequence of chars and rebuilds a string.
In the second case, + converts the first and last 0 to strings.
Note that everything is even a palindrom.
Other interesting solution using blocks (55 chars)
"{val o="*{val o=0;o}+".substring(9,12);val i="*0+";o}"
 {val o="*{val o=0;o}+".substring(9,12);val i="*0+";o}

return both smileys:
 ;o}
 ;o}

Explanation: See the below decomposition
"{val o="*{val o=0;o}+".substring(9,12);val i="*0+";o}"
--multiplied by 0=>"" --------- returns "" -----  result
 {val o="*{val o=0;o}+".substring(9,12);val i="*0+";o}
        -------- o equals ";o}"-------- -i ignored- o

Python (8 characters)
""""""""

and
""""""

both return empty string
Is based on idea of MvG

Tcl, 1, 3
1
"1"

Try it online!
Explanation: In Tcl, "quoting is a tool, not a rule"

TI-BASIC, 6 bytes
""→Str1:"
"→Str1:

Both of these end up storing an empty string to Ans (and to Str1). The second works because storing to a variable also stores to Ans.
I also found another 6-byter:
"":":"
":":

Both of these will return ":".
I have checked every shorter chain matching "[":]{0-3}", and none meet the specifications.

source: Stack Exchange

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

sort: votes


text:
Ascii art hangman
Although there was  a hangman competition before, I don't feel it was beautiful enough. The challenge is to implement a clone of http://inventwithpython.com/chapter9.html but as in the previous competition you can input the list of words in any way you want.  The main difference is therefore just that you have to draw the gallows in ascii as the game goes on.

Hangman wordgame golf already allows for drawing a gallows. That aside, a question should be reasonably self-contained.

The ASCII Gallows Club implemented a better version of hangman than that. It isn't based on it, but may I submit it anyway? We have many improvements over that game, and our gallows look excellent.

@user2509848 Of course!

Python 3
You will need to put the lists in a folder named wordlists, which is placed in the same folder as the source.  You can download the full .zip here: https://github.com/OddLlama/ascii-gallows-club.
This program allows 7 guesses until completion, and allows guessing the full word in one blow, if you think you know it.  It has a debug mode, where you enter 'debug' instead of the number of players, and does not allow you to enter a guess more than once.  It also allows 2-player mode, where one player enters the word, and a second player guesses it.  In this mode, the entered word does not display while being typed.  Other features are score-keeping and displaying special characters (although the lists haven't been updated to represent that):
#!/usr/bin/env python3

import random # for choosing a word
import os # for finding files in wordlists directory
import textwrap # for ASCII art dedentation
import time # for sleeping at the end
import getpass # for 2 player

# grab all the filenames
categories = [f.split('.')[0] for f in os.listdir('wordlists')]

debug_mode = False
def debug(s):
  if debug_mode: print('[DEBUG] ' + s)

def print_ASCII(ascii_str):
  "Print ASCII art."
  print(textwrap.dedent(ascii_str))

def header():
  "Print the header."
  print_ASCII("""
    /=======================\\
    | Welcome to Hangman!!! |
    \\=======================/
  """)

def choose_category():
  "Request the user to input a category."
  for i, cat in enumerate(categories):  # print the categories & numbers
    print('%i. %s' % (i, cat))
  choice = input('Please enter a category name or number: ').lower()
  if choice.isdigit() and 0 <= int(choice) < len(categories):
    choice = categories[int(choice)]
  for i, cat in enumerate(categories):
    if choice == str(i): choice = cat
  while choice not in categories:  # loop until user enters a valid category
    choice = input('Invalid category. Try again: ')
    if choice.isdigit() and 0 <= int(choice) < len(categories):
      choice = categories[int(choice)]
  return choice

def get_word(category):
  "Retrieve a random word from a category."
  with open('wordlists/%s.txt' % category) as f: # use `with` for automatic file closure
  words = f.readlines()
  return random.choice(words).rstrip('\n').strip().lower()

def get_guess(guessed):
  "Get the user to guess a letter."
  guess = input('Guess: ').lower()
  while guess in guessed:
    guess = input('You already guessed that. Try again: ').lower()
  return guess

# draw gallows
def draw_board(bad_guesses, word):

  length = len(bad_guesses)

  # this is also always drawn
  print_ASCII("""
    ______________
    | /          |
    |/           |
    |{0}          {2}{1}{3}
    |            {4}
    |            {5}
    |           {6} {7}
    |
    |
    | {8}
    |________________|""".format('  ' if length == 1 else '', 'O' if length > 0 else '', '__' if len(bad_guesses) > 1 else '',
                                 '__' if len(bad_guesses) > 2 else '', '|' if length > 3 else '', '|' if length > 4 else '',
                                 '/' if length > 5 else '', '\\' if length > 6 else '',
                                 ' '.join(map(lambda s: '[%s]' % s, bad_guesses))).strip('\n'))

def hangman(word):  # main function
  """
  Plays hangman!
  Returns True if the user won, False otherwise.
  """

  debug('The word is %s' % word)

  # the lines showing the word so far
  guess = ['_' if char.isalnum() else char for char in word]

  # already guessed and wrong guesses
  guessed = []
  bad_guesses = []
  while len(bad_guesses) < 7: # main loop
    # print letters so far
    print(' '.join(guess))

    # request input
    letter = get_guess(guessed)
    guessed.append(letter)

    # check if letter is correct or not
    if letter in word or letter == word:
      # update chars guessed so far
      guess = [letter if char == letter else guess_char for char, guess_char in zip(word, guess)]
      if letter == word: guess = list(word)

      # did they win?
      if ''.join(guess) == word:
          print('Congratulations, you guessed the word: %s!' % word)
          return True
    else:
      bad_guesses.append(letter)
      print('%s is not in the word.' % letter)

    # add a little separation
    print()
    draw_board(bad_guesses, word)

  # if program reaches here, user failed
  print('You couldn\'t guess the word. It was %s.' % word)
  return False

if __name__ == '__main__':
  header()
  players = input('How many players? 1 for playing against computer, 2 for playing against another human: ')
  while players not in ['1', '2', 'debug']:
    players = input('Invalid input. Please try again: ')

  # debug mode stuff
  if players == 'debug':
    debug_mode = True
    debug('Debug mode has been turned on.')
  while players not in ['1', '2']:
    players = input('Number of players: ')

  print() # spacing

  if players == '1':
    wins, losses = 0, 0
    if hangman(get_word(choose_category())): wins += 1
    else: losses += 1
    while True:
      print('You have won %i time%s and lost %i time%s.' % (wins, '' if wins == 1 else 's', losses, '' if losses == 1 else 's'))
      again = input('Play again? (y/n): ').lower() == 'y'
      print() # separation
      if again:
          if hangman(get_word(choose_category())): wins += 1
          else: losses += 1
      else:
          break
  else:
    while True:
      word = getpass.getpass('Word maker: enter your word (the input will not be shown): ')
      hangman(word)
      again = input('Play again? (y/n): ').lower() == 'y'
      print() # separation
      if not again: break

print('Goodbye!')
time.sleep(2)

Me, this user, PhiNotPi, and Volatility all worked on this one together :D

Yes. Sorry about forgetting the credits, @DoorknobofSnow.  I guess I should have know better than to plagiarize.

@DoorknobofSnow Maybe we should start a group account for answering these questions?

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


text:
Write an aphorism using valid code
Can you write an aphorism in at most 4 lines of code ?
Code should read as much as possible as an aphorism in plain English and should return the boolean true.
Language: of choice.
Criteria for accepted answer: Most votes in 180 30 days. (8th of July 2014)
Originality: can be an old aphorism but a creative one would be much more appreciated.

What is the max line length ?

@kyle k, 90 characters should should suffice, mostly for estetic, readability reasons, also good aphorisms tend to be short :)

Ruby - !!"[ insert whatever aphorism you want here ]"

@DoorknobofSnow That would be a valid answer but I doubt that would get much of the votes.

Not sure that Shakespeare quotes qualify as aphorisms.

@Blazemonger I think that quote qualifies as an aphorism

Python
import this
love = this
this is love, love is not True or False, love is love
# (True, True, True)

Okay, this returns a tuple of Truths, but that itself evaluates as True anyway.

Forth
2 : b or ! 2 ." b" ;
: that s" the questi" on ;

C:
You'll have to squint a bit to read this one :-)
int x(){ int __,L        ;
     return (__ |__ ||__ |__ ,__,__ ,__ ,__ ,__  ,
             __||  1||__ |  1L/L|__||__|1/__|  1L)
                                ;   }

You might notice a potential division-by-zero error on line 3, but this is never executed because the expression evaluates as true before the calculation is performed.

Forest gump! +1

Could you please translate, for those of us without the necessary squinting skills?

@Bob Do you want a breakdown of the C code, or a clearer rendering of the ASCII art?

Oh, the C code is easy enough (__ is an identifier, couple bitwise and logical ORs and comma operators, which are all insignificant because it's all logical ORed with a 1 evaluating to true). It's the ASCII art that's a little difficult to read.

@Bob OK, here's something similar. (Not valid C code, but easier to read, I hope.)

Thanks! It's obvious in retrospect :\ (I was trying to read it one line at a time)

It's difficult to avoid string literals, comments and tricks fo this kind, but I tried to keep them to a mininum. Also, the first line makes no sense. Well, I had fun doing it
F#
(fun () -> (fun (_) -> // fun fun? wtf
try not <| failwith("me") ; (*but*) with |Failure((*co*)me(*s*)) -> true)("learning"))()
// "Try not to fail with me, but with failure comes true learning

I could also do some declaration abusing, but I ended up not finding a way to return true:
let the,bodies,hit_the=floor(0.0),(),()

or
let the_games=bigint() //pun intended

I really need to stop with the puns.

C
No string literals or comments:
Better(to,re);main(silent){and();}be(thought,a,fool){}
than(to,open,your,mouth);and(){}remove(all,doubt);

Split over two lines, but one would work fine as well.
When compiled using gcc on Linux (x86-64), this produces an executable which exits with success (exit code 0), the same as the true Unix utility; this being how I choose to interpret the requirement of returning boolean true in a non-scripting language.
Note: notwithstanding the abuse of the "implicit int" rule, the principal trick behind this program is that while a C program that falls off the end of main without a return statement will usually result in a non zero exit code, by calling another function we can set the EAX register which is then used as the exit code of the program. This is of course totally undefined behaviour and utterly non portable.

Python
war=peace=freedom=slavery=ignorance=strength=0
war is peace|freedom is slavery|ignorance is strength

Power=a=means=it=an=end=0
Power is not (a, means, it is (an, end))

JavaScript
You=true;function BigBrother(){};BigBrother.isWatching=function(y){return y};
BigBrother.isWatching(You)

C#:
short life = 0;
return (life is short);

"Life is short" (Hippocrates)

Too bad there is no literal specifiers for shorts!  It would be neat to do var life = 0s;

Ruby
class String
  def before(b) self < b end
end

A bit lengthy, but gets us a few aphorisms:
"age".before("beauty")
"business".before("pleasure")
"pearls".before("swine")

And (stretching slightly):
dont = []; y = 1
dont.count + y or ('chickens'.before('they hatch'))

Scala
Some apply Double forall _; None isEmpty

CoffeeScript
2 * @wrong isnt @right

=> true

C++
bool life = true;
bool fair = false;

assert(life != fair);

Python
love=[True];all,fair,war=love*3
all is fair in love and war

An aphorism about http verbs, in
Ruby
puts do
something idempotent but are considered to be unsafe
because if the value at the beginning of a chain of calls is one possibly the value at the
end != 1

C
if ((ifs && ands) == (pots && pans))
    work_for_tinkers_hands = FALSE;

Javascript
function be(who) {
   if (who == 'thine own self') {
      return true;
   }
}

An approximation of "To thine own self be true."
I'm kind of fudging with the requirements, since it only returns true in one particular case ... but I'm hoping you'll let it slide because the return value is actually part of the aphorism.

I got a wonderful error while attempting this:
It's very much inspired by Darren Stone's answer.

TypeError: Cannot use 'in' operator to search for 'tis nobler' in mind to suffer the The Slings and Arrows of outrageous fortune

Javascript
[2].be || ! [2].be ; this.is, "the question"

It returns an implicit true.
Slightly less terse, with a question mark:
[2].be || ! [2].be? is = this: !"the question"

C
main(int I,char **think) {char *a="there"; for (;--I;) a['m'];}

You can remove the types in declarations. Also something has to be done to a's declaration... It gets in the way when you read

I left them because my compiler gave me errors without them, so I wanted to be very adherent :P

C
int main(int fear, int* computers){ int

    i; do { !fear; computers[i]; fear; "the lack of them";

} while();return true;}

I do not fear computers, I fear the lack of them.
-Isaac Asimov

PHP
$all = array('not well', 'not well', 'not well', 'well');
$end = array_pop($all);
$all = ($end == 'well') ? $end : 'not well';
return true;

"All's well that ends well."

A bit lazy, but my take.
Python:
life = short = True; art = long = True; life=art
life is short and art is long

JavaScript:
The = word = 'Yoga'
has = been = 'vulgarized'
and = does = not=  mean = anything =Date.now() ,!''
//Swami Rama

Q
any bird:`int$"hehand"=2^`int$"hebush"
and
(./) 2_iscomp:any 3,'s:"a",'"crowd"

PHP
An apple a day...
$aphorism = function(){
    for($day=1;$day<=365;$day++) $apple++;
    return ($apple==365) ? true : 'doctor';
};

Common Lisp
(Do ((as)) ('(I say no)t) as I do)
(time (and 'tide (wait-for 'no-man))) ;requires sbcl

Lua
-- all search is in vain
function search() end
-- only the void is true
function void() return function() return true end, true end
-- and what remains is to
for ever in void() do repeat search("light") until true end
return true

JavaScript
return (Do || !Do) || (there == !try);

return 2 * be || !(2 * be);

Upvote for the Yoda one, but I am thinking there should be a ban on "To be or not to be".

R
the_whole <- c(-1,-1)
the_part <- -1
the_whole > sum(the_part,the_part)

-Socrates

Simply-Basic 84
Label 1;a random number between 0 and 1~should be stored in~A
If A is equal to 1 Then Display A End;Stop&Else,Go to label 1
:End; Otherwise destroy quantum transmitters internationally.
Since quantum transmitters are gone, power lost. KA-POW, yes?

Prolog
waste(not).

want(X) :-
    waste(X).

Python
be = that = the = question = 1
2 - be or not 2 - be
that is the & question

Ruby
Not the most elegant solution, but very easy to read
def you_know_meaning(x) true end

!!!("aphorism" != "aphorism" unless you_know_meaning "aphorism")

=> true

JAVA
public static boolean think(){return true;}public static boolean so()
{return true;}public static boolean be(){return true;}static{boolean i=true;
    System.out.println((i==think())?so():i==be());
}

I think so i be --Descartes

C++
int main() {
  int right,might;
  might==right;
}

Might is right.

Haskell
Be original!
do otherwise

It returns True.

Rebol
Rebol []
between: :if thought: expression: true lies: func ['a 'b] [a != b]

between thought and expression [lies a lifetime]

Some explanation
The above code translates to:
if thought and expression [lies word-arg1 word-arg2]

The if statement is true so the lies function is called which returns true as along as the two arguments provided are different.

Perl
sub between (&@) { $_[1] if $_[0]->() } sub lies { $_[0] ne $_[1] }
my ($thought, $expression) = (1,1);

between {$thought and $expression} lies a => 'lifetime';

NB. Above works fine with (or without) strict and warnings pragmas.

Javascript
get: with(this) 1;
I think this makes sense.
Edit: was notified it didn't return true, well now it does.

Doesn't return true

Is my use of the literal string true cheating?
This is an AutoHotkey script:
Be("true") to yourself

Be(msg) {
    MsgBox % msg
}

Ruby vs Friedrich Nietzsche
=> class Lie
=>   def self.is_a_condition_of?(life);true;end
=> end
=> Lie.is_a_condition_of?("life") # => true

You're admitting also that self is a condition of life :) +1

Rebol
love: true
war:  false

if true? any [love is blind and war is hell] [make love not war]

Not one of my favourite songs, still a great album.
PHP
$_GET['this'] or die(!0);

Reads as: Get this or die! (No!)
Get This
Slipknot
1999

T-SQL
I made several attempts at this challenge before arriving at an answer that expresses truth through the code itself. After a few attempts at turning favorite quotes into pithy code translations, I realized the way to go was to set aside quotation entirely and let the language of choice simply speak the wisdom it is capable of speaking.
Since SQL is verbose, I have chosen to break this 4-line program into more lines for ease of reading without horizontal scrolling. The properly "golfed" version may be found on this SQLFiddle.
DECLARE @mindInTurmoil BIT = 'True'
Samsara: SELECT 'equanimity' AS Attitude, 0 AS Ego INTO #Self
    WHERE @mindInTurmoil = 'True'
IF (SELECT TOP 1 Attitude FROM #Self ORDER BY Ego) = 'equanimity'
    SET @mindInTurmoil = 'False' ELSE GOTO Samsara
SELECT CASE @mindInTurmoil
    WHEN 'True' THEN 'False' WHEN 'False' THEN 'True' END AS Liberation

Returns:
Liberation
----------
True

Java (probably others too)
boolean hasExceptions(Rule rule) { return rule != this; }

"There are always exceptions, except to this rule." - by me.

JavaScript
function healthy_community(diversity){
    return (diversity === true) ? true : false;
}
healthy_community(true);

why not just return diversity ?

well if you pass 'kinda sorta' it will return false. it must be absolutely true in type and value.

Groovy
short Short;
short life = Short;
assert life.is(Short);

Java
for (Person person : people) {
    if (!HouseTypeEnum.GLASS_HOUSE.equals(person.getResidence().getHouseType()))
        throw new StonesException();
}

Two problems: This doesn't compile because we don't have a Person class or a HouseTypeEnum or a StonesException or (etc). Also "should return the boolean true." This code doesn't return any value.

Mathematica
 mo[thing__] := MemberQ[{thing}, money | problems | True]
 mo[money~mo~problems]

Javascript
with = javascript = we = can = create = any = aphorism = returning = true;

Yes, but is it creative? ;)

C
This quote is a line from My Fair Lady. See here https://www.youtube.com/watch?v=uVmU3iANbgk
#include <stdio.h>
/*the rain */int /*Spain falls*/ main/*ly*/(){return puts("on the plane")>0?1:0;}

TI-BASIC
2_be or not(2_be)


text:
Count the Zeros
For a given n, count the total number of zeros in the decimal representation of the positive integers less than or equal to n. For instance, there are 11 zeros in the decimal representations of the numbers less than or equal to 100, in the numbers 10, 20, 30, 40, 50, 60, 70, 80, 90, and twice in the number 100. Expect n to be as large as 10^10000.
Your task is to write a program to count zeros.  Most efficient algorithm wins (Big O complexity)
EDIT: post your code and your answer for n = 9223372036854775807.

How are you going to measure the speed of the submissions?

Most efficient algorithm.

@Xinbi most efficient isn't particularly well defined. Do you mean in Big O complexity? Benchmark? If we measure straight time, it's unfair if I have an 8 core processor and parallelise this.

I did mean Big O complexity. I'm not interested in the CPU power of the machine it's running on. I'm interested in the algorithm that solves the problem.

@Xinbi In that case, you're very likely to get ties. Do you have a tie breaking condition?

I got an O(1) solution. Do I win now? xD

I agree with @Cruncher's approach to game a Big-O challenge with a massive lookup table.  It's foolish to not freely spend a free resource if it helps your answer.  RAM, code space, and setup time, in this problem specification, are all free.  A pure lookup approach may be practically impossible but a hybrid solution of lookup/computation could be the best in practical implementation.

You might limit program size to get the actual computation, without too much lookup. In that case, be specific about the bound.

Relevant Euler problem... I solved it years ago, my code works for all other digits except zero, so it needs some refactoring.

At the moment, you have at least three different answers: 16577013436077779652, 16577013372932555467 and my own 16577013372932555466 which is off by one from that before. Can we establish that for e.g. n = 30270501, the correct answer is 20398096 as per this simple approach? Or does anyone have reason to doubt even that simple approach?

@MvG I think yours is correct.

Some thoughts up front:
f[i]: number of zeros in [10^i, 2*10^i)
g[i]: number of zeros in [10*10^i, 11*10^i)
h[i]: number of zeros in [0, 10^i)

i   f       g     h
1  1*     10*     *
2  1**    10**    **
3  1***   10***   ***
4  1****  10****  ****

f[i] = 9*f[i - 1] + g[i - 1]
g[i] = f[i] + 10^i
h[i] = h[i - 1] + 9*f[i - 1]

Now the code:
def zeros(n):
    s = str(n)
    f = [0]
    g = [1]
    h = [0]
    for i in range(1, len(s) + 1):
        f.append(9*f[-1] + g[-1])
        g.append(f[-1] + 10**i)
        h.append(h[-1] + 9*f[-2])
    k = len(s) - 1
    a = h[k]                  # all numbers with fewer digits
    a += (int(s[0]) - 1)*f[k] # same number of digits but first digit less
    s = s[1:]
    while s:
        if s[0] == '0':
            a += int(s) + 1
        else:
            a += int(s[0])*f[len(s) - 1] + 10**(len(s) - 1)
        s = s[1:]
    return a

For n = 9223372036854775807 the result is 16577013372932555466. This is different from the currently accepted answer by @user14325, but I have more trust in it since starting at n=1000, @user14325 disagrees from the naive implementation suggested by @user2509848 in which I have a lot of trust due to its simplicity.
Complexity of my code is O(log n), at least if you assume uniform cost for arithmetic operations. Taking bit cost into account, it will probably be O(log(n)3log log(n)) or something like that, depending on how Python does its big integers and the exponentiation on them. If you care about the constants, then there is a lot of room for optimizations. Converting between numbers and strings all the time is hardly efficient. But as long as you only care for asymptotic behavior, I'll leave it at
that.

I agree with your assessment.  My O(Log(n)) solution came up with the same answer as yours.  (I didn't look close enough at the resulting digits)

Python O(1):
Since the challenge has been specified to be using Big O. I concluded that the best way to do it(since the upper bound is limited by a constant) is to just to create a giant look-up array.
However, this program would be too big to post here, so I made a program that generates it:
def zeroesUpToN(n):
    zeros = 0
    for i in range(n):
        s = str(i+1)
        zeros += s.count('0')
    return zeros

s = "print(["
for i in range(10^10000):
    s += str(zeroesUpToN(i+1)) + ",";
s = s[:-1] + "][int(input())])"

print(s)

So, this will ALWAYS take a long time to run(I mean the resulting program, not the generating program. The generating program would take even longer). But, how long it takes to run will not depend on n. Therefore, by definition it is an O(1) solution.
Here is an actual program that works for smaller outputs(up to 200):
print([0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,11,12,13,14,15,16,17,18,19,20,21,21,21,21,21,21,21,21,21,21,22,22,22,22,22,22,22,22,22,22,23,23,23,23,23,23,23,23,23,23,24,24,24,24,24,24,24,24,24,24,25,25,25,25,25,25,25,25,25,25,26,26,26,26,26,26,26,26,26,26,27,27,27,27,27,27,27,27,27,27,28,28,28,28,28,28,28,28,28,28,29,29,29,29,29,29,29,29,29,29,31][int(input())])

The real one is obviously much bigger.
P.S This is the problem with Big O problems.
EDIT: Oops, I forgot to give credit to @user2509848 whom I actually stole the code for generating each N.

Unfortunately, I don't think there's a computer out there that can hold an array of ten tremilliatrecendotrigintillion integers.

@Xinbi I don't believe a computer being able to run it was in the requirements. This program provably works, even if I can't run it.

Post the algorithm that comes up with the array, and I'll call it a win. :-)

@Xinbi I did. However it just produces source code. The program that this produces would absolutely solve your program to the requirements, in O(1).

I'd contend that your solution is actually O(n+1), since the generation is part of the solution.

No. The generation is there, simply because I cannot write the program here. It's vastly too big. It doesn't mean that the program doesn't conceptually exist. (FYI, O(n+1) is nonsense. It's just O(n))

@Xinbi actually. I would argue that the generating code is O(1) as well. It takes NO input, therefore there is no n. So it's O(1) by default. It will take the same amount of time every time you run it. for(i=0;i<1000000;i++){print("hi")} Is O(1) for the same reason. Unless you accept the number as an input.

What if there were no upper constraint for N in problem definition. This constraint is artificial. Would you generate an O(1) program which solves given task for arbitrary N ?

@SergeyS If there was no upper bound constraint, then an O(1) solution would be impossible for this problem. The O(1) is entirely a product of the bound. It's a bit of a rule abuse. Oh well.

@SergeyS Thanks for pointing out the error in my answer. Deleting.

Java:
public class ZeroCount {
    static final int max = 65498;

    public static void main(String[] args) {
        int res = 0;
        for (int i = 10; i <= max; i*=10) {
            res += max/i + max/(10*i) * (i-1);
            res -= (max % (10*i) < i) ? (i-1) - (max % i) / (i/10) : 0;
        }
        System.out.println(res);
    }
}

Should be O(log(n))
Edit:
For n=9223372036854775807
I decided to use Python instead of Java since 9223372036854775807 is Long.MAX_VALUE in Java and I didn't want to use BigInt
def zeros(n):
    res = 0
    i = 10
    while i <= n:
        res += (n // i) + n // (10 * i) * (i - 1)
        res -= (i - 1) - (n % i) if n % (10 * i) < i else 0
        i *= 10
    return res

print(zeros(9223372036854775807))

> 16577013372932555466

Won't this skip 101?

Most efficient algorithm wins (Big O complexity).

It does. Why didn't I thought of it?

I updated my code and it should be right and faster now.

It gives the wrong answer, why it is accepted?

@swish agreed.  I didn't look close enough at the resulting answer (my brain couldn't handle that many digits at once. :-)

@swish I fixed the mistake. The basic algorithm is still the same but now it works. Furthermore I replaced the floating point divisions (/) by integer divisions (//). I think there won't be a simpler algorithm with O(log n).

Python 3
n = int(input())
zeros = 0
for i in range(n):
  s = str(i+1)
  zeros += s.count('0')

print(zeros)

Fast up to 10,000,000.  It gets slower when I bring it to 100,000,000.

I borrowed your code for generating my solution btw

@Cruncher Big deal since I don't know Big O (whatever that is).

http://en.wikipedia.org/wiki/Big_O_notation if you're interested it all. It's very academic. It's a way of formally measuring the complexity of algorithms. Not always a good metric in practice though (as evidenced by my perfect solution.) O(1) is the smallest complexity. It means constant time.

@Cruncher Oh, so my solution is correct, yours just takes forever to run always (a joke solution)?

In all cases, your solution is faster. But since mine is ALWAYS slow, even for small n's, the runtime does not depend on n, so we call it a constant time(O(1)) algorithm.

@Cruncher Very interesting, you should make it an if-else statement for the size of the number, I won't mind being beaten - I've never won yet, and I won't win either way.

Theoretically. My solution has lower complexity than yours. And by the winning condition of this question is better than yours. Even though its always slower. My answer was to point out the flaws in the question

Your code is a very good reference to compare other computations against, because it is so very simple. It simply has to be correct, even if it is slow.

@MvG This is why I used his solution to generate mine xD

Haskell - O(n) for 10^n input
import Data.Char
import Data.List

p n = (10^n-10)`div`9 -- number of padded zeroes below 10^n
t n = n*10^(n-1) -- number of zeroes below 10^n with padded
digsToInt = foldl1 (\x y -> x*10+y)

-- number of zeroes below n
f :: Integer -> Integer
f n = h ds (len - 1) - p len
  where
  ds = map (fromIntegral . digitToInt) $ show n
  len = genericLength ds
h [x] _ = 0
h (x:ys) n | x == 0 = 1 + digsToInt ys + h ys (n-1)
           | otherwise = t (n+1) - (10-x) * t n + h ys (n-1)

Answer for 9223372036854775807 is 16577013372932555466.

Comparing your answer to mine, it seems like one of us is off by one. Did you perhaps include the number 0 in the count? Do you get the correct result of 11 for input 100?

@MvG It indeed counts the first 0 as I didn't read the problem carefully, now it's fine.

@swish now it's the correct value. Yay!

Python O(log10 n)
def zerosA(n):
  '''finds the number of zeros from [1, 10**n]'''
  if n < 1: return 0
  return 10*zerosA(n-1) + 10**(n-1) - 9*(n-1)

def zerosB(n):
  '''finds the number of zeros from (10**n, 2*10**n]'''
  if n < 1: return 0
  return 10**n + n*10**(n-1) - 1

def zerosC(n):
  '''finds the number of zeros from (2*10**n, 3*10**n]'''
  if n < 1: return 0
  return n*10**(n-1)

def count_zeros(n):
  p = z = 0
  while n >= 10:
    n, r = divmod(n, 10)
    if r > 0:
      z += zerosB(p) + zerosC(p)*(r-1) + `n`.count('0')*r*10**p
    p += 1
  z += zerosA(p) + zerosC(p)*(n-1)
  return z

if __name__ == "__main__":
  print count_zeros(9223372036854775807)

Output:
 16577013372932555466

For the number 12345, for example, this works in the following manner:
[12341, 12345] ⇒ 0
[12301, 12340] ⇒ 13
[12001, 12300] ⇒ 159
[10001, 12000] ⇒ 1599
[1, 10000] ⇒ 2893
For a total sum of 4664. No more than log10 n iterations are needed to reach the final answer.

C# O(log n):
using System;

namespace Zeroes
{
    class program
    {
        static void Main(string[] a)
        {
            int n = int.Parse(a[0]);
            int result = 0;
            for (int i = 1; i < Math.Log(n); i++)
                result += n/(int)Math.Pow(10, i);
            Console.Write(result);
        }
    }
}

Only works for integers, of course, but the logic's sound. I have a feeling there's a better algorithm to be found, though. Nope, there's a bug in this.


text:
1+2+3+4+...+n = -1/12?
Today, Numberphile posted this video where it's stated that 1+2+3+4+...+n = -1/12.
While this isn't really new (several ways to prove that have been found, you can look here for further informations), this leads us to our question!
Your goal is to write a function that returns -0.083333 (feel free to stop at -0.083 if you wish), which is -1/12.
Be original, since this is a popularity-contest!
Most upvoted answer in 2 weeks wins this.

I don't understand, does this mean that infinity is -1/12?

No, but there are several mathematic methods to calculate this value as the result of that sum. Read the link I gave for more informations about that, this would be off-topic here I guess! :)

These wikipedia articles seem relevant: http://en.wikipedia.org/wiki/Ramanujan_summation#Sum_of_divergent_series http://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%C2%B7_%C2%B7_%C2%B7#Summability

The Riemann Zeta function is defined as ζ(s) = Sum(n-s) where you sum from n=1 to n=infinity.  Hence ζ(-1) = Sum(n) = 1 + 2 + 3 + 4 + ... to infinity.
Now scipy defines zetac to be sum(k**(-x), k=2..inf) (that is the zeta function with the first term removed).
Hence in python
>>> import scipy.special
>>> print 1+scipy.special.zetac(-1)
-0.0833333333333

essentially calculates the infinite sum 1+2+3+4+... to give -1/12.

J
This is quite short, but I hope you think it's sweet:
(%&13@<:^:_)0

I'm relying on the fact that a negative twelfth is -0.1111111... in base thirteen. This function takes its argument, decrements it, and divides by 13 (a right-shift in base 13). It does this until the value converges to -1/12. To see how the base 13 stuff fits in, you might want to imagine the 13 being changed to a 10. The function would then converge at decimal -0.111111... = -1/9.

PowerShell (and probably a polyglot)
I know this isn't code-golf, but since no other parameters are really defined for the challenge except:

Your goal is to write a function that returns -0.083333 (feel free to stop at -0.083 if you wish), which is -1/12.

I have a really hard time justifying doing anything other than:
-1/12

This outputs:
-0.0833333333333333


text:
I know you, but you don't know me
You're tasked with writing two programs. Program A must print out nothing on all inputs except when program B is input, in which case it should print 1. Program B must print out 1 on all inputs except when program A is input, in which case it should print nothing.
Scoring:

+1 For each character from both programs.
Lowest score wins.

Is this quine-ish enough to tag it as [tag:quine]? It certainly seems so to me.

As the first two answers posted indicate, "being" another program is not terribly well defined in this descriptions. And, I'm with @Quincunx that this has something very much like the quine-nature.

@Quincunx I've added the quine tag.

when you say it takes a program as input, do you mean it takes that program's source code as input or that program's output?

@Markasoftware The source code as input.

@Quincunx A quine is a computer program which takes no input and produces a copy of its own source code as its only output.  Neither program A nor B do that.

@BrianRogers However, to solve this problem, you have to use the same concept behind a quine.

@Quincunx true, but nobody is doing that so far, unless you also call a quine any program that reads its source code from disk and prints it out :p

@aditsu I much dislike those answers. I think I'll post a very suboptimal answer that does not do that. I personally feel that reading source code through files is cheating; programs should work anywhere!

Ugh, my suboptimal answer is very difficult to debug. My head hurts like crazy

@Quincunx, I hear what you're saying about programs here that read their peers' code from disk. It's a shortcut, for sure. But consider a very real advantage: with such an approach, when you change code in A, you do not need to change B. The "purist" approach I think you're describing leaves both programs co-dependent on each other, doesn't it?  i.e. if you make any to change A then you must also change B. Referencing is not as clever, but it is robust. :)

GTB, 25
Executed from a TI-84 calculator
Program A
`_@_eq;"$w;&

Program B
`_@_eq;"$#w;&

Explanation
`_ Input a string
@_eq;" Check if it equals the source code (# is automatically stripped along with lowercase letters)
$w;& If so, display 1 (otherwise nothing) [for B it's $#w;& - if not, display 1 (otherwise nothing)]

Bash - 32 characters
Script A - 16 characters
cmp -s b&&echo 1

Script B - 16 characters
cmp -s a||echo 1

Usage
$> echo "foo" | ./a
$> cat b | ./a
1
$> echo "foo" ./b
foo ./b
$> cat a | ./b

Ruby, 54
A
$><<1if$<.read==IO.read(?B)

B
$><<1if$<.read!=IO.read(?A)

examples:
bash-3.2$ ruby A < A
bash-3.2$ ruby A < B
1bash-3.2$ ruby B < A
bash-3.2$ ruby B < B
1bash-3.2$

J (62)
Since you didn't forbid this...
Store the programs as A and B respectively.
Program A (30):
exit echo#~(1!:1<'B')-:1!:1[3

Program B (32):
exit echo#~-.(1!:1<'A')-:1!:1[3

How it works (Program B, A is similar):

1!:1[3: read stdin
1!:1<'A': read file A
-:: see if they are equal
-.: negate the result
#~: replicate the result by itself (so, 1 results in one 1 and 0 results in zero 0s, i.e. nothing)
echo: output
exit: exit (the J interpreter does not exit by default when it reaches the end of the file)

$ jconsole A <B
1
$ jconsole A <foo
$ jconsole B <A
$ jconsole B <foo
1
$

Can you give a short explanation of what this does?

@ike: did so _______

Haskell - WITHOUT loading source - 478 644 characters
This assumes getContents ALWAYS ends with a newline and so drops the final character without checking because I don't feel like escaping it

A
main=interact$($'1').replicate.(1-).fromEnum.(/=map r(d++shows d[toEnum 10]))where r n|n=='-'='*'|n=='*'='-'|True=n;d="main=interact$($'1').replicate.(1-).fromEnum.(/=map r(d++shows d[toEnum 10]))where r n|n=='-'='*'|n=='*'='-'|True=n;d="

B
main=interact$($'1').replicate.(1*).fromEnum.(/=map r(d++shows d[toEnum 10]))where r n|n=='*'='-'|n=='-'='*'|True=n;d="main=interact$($'1').replicate.(1*).fromEnum.(/=map r(d++shows d[toEnum 10]))where r n|n=='*'='-'|n=='-'='*'|True=n;d="

It works like a standard quine, but swapping - for * to get the other program (avoiding those characters elsewhere).
The following test prints as expected (replacing main=interact$ with a= and b=)
main=do
  putStrLn "START"
  putStrLn$a "FOO"
  putStrLn$a "main=interact$($'1').replicate.(1*).fromEnum.(/=map r(d++shows d[toEnum 10]))where r n|n=='*'='-'|n=='-'='*'|True=n;d=\"main=interact$($'1').replicate.(1*).fromEnum.(/=map r(d++shows d[toEnum 10]))where r n|n=='*'='-'|n=='-'='*'|True=n;d=\"\n"
  putStrLn$b "FOO"
  putStrLn$b "main=interact$($'1').replicate.(1-).fromEnum.(/=map r(d++shows d[toEnum 10]))where r n|n=='-'='*'|n=='*'='-'|True=n;d=\"main=interact$($'1').replicate.(1-).fromEnum.(/=map r(d++shows d[toEnum 10]))where r n|n=='-'='*'|n=='*'='-'|True=n;d=\"\n"
  putStrLn "END"

-
START

1
1

END

Also if there's a preferred way to format monolithic single line functions that would be handy, http://meta.stackexchange.com/questions/22186/how-do-i-format-my-code-blocks doesn't appear to cover it

Ruby, 166 chars, no reading source
A:
(gets(p)==<<2.tr('&|','|&')*2+'2')&&p(1)
(gets(p)==<<2.tr('&|','|&')*2+'2')&&p(1)
2

B:
(gets(p)==<<2.tr('|&','&|')*2+'2')||p(1)
(gets(p)==<<2.tr('|&','&|')*2+'2')||p(1)
2

Make sure your text editor doesn't save with a trailing newline.
Usage (example):
 $ ruby know_a.rb know_b.rb
1
 $ ruby know_a.rb know_a.rb
 $ ruby know_b.rb know_a.rb
 $ ruby know_b.rb know_b.rb
1

Each program constructs the source of the other program using a HEREdoc and string transforms, then compares the result to the input.

This was easy enough to write, but now some part of my brain that doesn't understand recursion is insisting it can be optimized but has no idea how.

What is p? And where does the heredoc end?

p is a built-in ruby method that prints the arguments passed to it, then returns those arguments, making it useful for golfed output. When called with no arguments it returns nil. The argument to gets is a delimiter, so passing p results in a nil delimiter which means it reads STDIN until it gets to EOF. The heredoc expression is <<2, so it ends at (and does not include), the 2 at the end of the file.

The use of 2 as the heredoc delimiter is a traditional bit of obfuscation. It can be almost any string.

Is the content of the heredoc evaluated somehow?

Nope, it's just a string (that happens to be identical to the first line of code). <<2 returns the middle line, which we then call tr on to switch the '&' and '|' characters, then concatenate to itself via *2, then concatenate '2' to. We compare the resulting string to the result of gets(p), which is the input file.

How can you call tr and all the other stuff if they are just part of your heredoc string? The way I see it, both your programs are: unbalanced (, compare gets(p) (whole input, I suppose) with static heredoc string, the end.

The Ruby parser is extremely forgiving. It treats <<2.tr the same as (<<2).tr, which is to say that 2 is the heredoc delimiter string and everything after it (on the same line) is more code. The heredoc string doesn't start until the next line.

Oh God, that's horrible... and kinda cool. I'll see if I can figure out the &| vs |& stuff.

Ok I think I got it, very clever! Too bad you can't add the number 2 directly.

Python 2.7 - 82
File A (literally named just a):
if raw_input()==open('b').read():print 1

File B (literally named just b):
if raw_input()!=open('a').read():print 1

Total abuse there without the .py - does that even work?

I'm sure @LegoStormtroopr would be running in the same manner as my Ruby examples posted here, a few minutes earlier. ;-)

@Timtech It does if you run them from the command line as python a.

I meant is it possible to even generate a file without an extension?

Of course it is? If you are on a Posix machine touch a will create an empty file if you have permissions. For extra cruel fun you can even do touch \~ which creates a file named with a single tilde (~) - then watch as someone foolhardedly tries to remove it ;)

Python 3 - 102 characters
Prints 1 if the input is the same as program 2, otherwise nothing:
if input()==open('a.py').read():print('1')

Prints 1 if input is not the same as program 1, otherwise nothing:
if input()==open('a.py').read():print('1')

Can't the whitespace be removed? Also you can shorten the scripts from t.py and tt.py to a.py and b.py.

@Timtech Sure, good idea.  Also, I wasn't counting white-space - that is just there for readability.  The new-lines cannot be removed though.

Yes, I am aware of Python's newline sensitivity.

Only one of the newlines can really be removed, that after the colon. The others would need semicolons added, so there is no advantage to removing those newlines.

@AJMansfield Yes, I know, but I didn't count newlines anyway.

@user2509848, if you cannot remove newlines or whitespaces then it is conventional to include those characters in your byte count.  You will find these conventions used in nearly everyone's counts and there are discussions about this on meta. Each of your programs above can be reduced to 4 lines so that requires an additional 3 newlines each to separate the lines.  I would suggest +6 chars.  But I would really suggest eliminating those variable assignments.

@user2509848 I just fixed what he was talking about; the new programs don't need any newlines at all.

@AJMansfield Thanks.  Your edit was rejected, but I got the code and changed it anyway.

Haskell - 138
Not really a good answer, but wanted to make both programs use the same source.
Could save some chars by renaming the file, but it's not going to make this a winning solution so I don't think it's worth it.
import System.Environment
import Control.Monad
main=do{i<-getContents;p<-getProgName;f<-readFile "ab.hs";when((f==i)/=(p=="B"))(print 1)}

Compile this source as both A and B.
Test:
% ghc -o A ab.hs
[1 of 1] Compiling Main             ( ab.hs, ab.o )
Linking A ...
% cp A B
% ./A < ab.hs
1
% ./B < ab.hs
% ./A < ab.hi
% ./B < ab.hi
1

why compile twice into A, and then copy A to B?

That was a mistake by my part when copypasting the code. Thanks for pointing that out. Will fix.

Node.js - 142 characters
Script | (otherwise known as Script A) - 80 characters

f=require('fs').readFileSync;f('/dev/stdin','hex')==f('&','hex')&&console.log(1)

Script & (otherwise known as Script B) - 62 characters

eval(require('fs').readFileSync('|','utf8').replace(/&/g,'|'))

Usage
# \| is Script A
# \& is Script B

$> echo "foo" | node \|
$> cat \& | node \|
1
$> echo "foo" | node \&
1
$> cat \| | node \&

Description
Script B reads the contents of Script A and evals it after swapping the file names and the and operator to an or.
I named the files & and | so I can perform a single replace in Script B.

bash/grep — 59 chars
51 chars if we only count the actual program string.
$ a='grep -cx "$b" | grep -x 1'
$ b='grep -vcx "$a" | grep -x 1'
$ echo 'foo' | eval $a
$ echo $b | eval $a
1
$ echo 'foo' | eval $b
1
$ echo $a | eval $b

R (62 chars)
i=identical
A=function(x)if(i(x,B))1
B=function(x)if(!i(x,A))1

produces:
> A(123)
> A(A)
> A(B)
[1] 1
> B(123)
[1] 1
> B(A)
> B(B)
[1] 1

Meta comment: R fairs relatively bad on code golf as there is no shortcut to function...


text:
Reciprocal Fibonacci constant
Seeing as there have been an awful lot of normal Fibonacci challenges, I decided that it might be interesting to calculate the Reciprocal Fibonacci constant - namely, the sum of the reciprocals of the Fibonacci sequence.
The challenge is to calculate the Reciprocal Fibonacci constant with the number of Fibonacci series to use digit given as input, i.e. an input of 10 means to calculate based on the reciprocals of the first 10 Fibonacci numbers.  In the likely case of a tie, shortest code wins.
The winner will be chosen in three weeks via standard code-golf rules.

This is equal (if I've understood it right) to 1/φ (reciprocal of golden ratio). If you want us to actually use the Fibonacci numbers in the calculation, you should specify. If not, there's certainly languages where φ is a builtin. (not APL for a change)

@marinus Changed.

@marinus, it's not equal to 1/phi. It does have a closed form, but it's quite tricky. Mathematica probably has a built-in, but I doubt many other languages do.

@OP, "highest accuracy possible" is a useless winning criterion. Anyone who has a language which supports arbitrary decimal precision, or who can be bothered to write the support for it, can make an implementation with a precision parameter and then engage in an edit war to increase that parameter. It would make more sense to ask for a function which takes the precision as a parameter. Judging on speed is also tricky, because it depends on many factors (CPU model, RAM available, system load, ...).

@PeterTaylor Is this better?

That's one way to improve it. You could probably remove the last rule now, because any approach which doesn't require adding the inverses of the numbers themselves is going to be very interesting.

What is the winning criteria?

@Quincunx Sorry, it was removed during question modification.

@Quincunx Fixed now.

For comparison, the answer I would have submitted to an earlier version of the question which asked for the constant per se: import java.math.*;public class C{public static void main(String[]_){MathContext C=new MathContext(110);BigDecimal I=BigDecimal.ONE,a=I,b=I,s=I,S,x,y;int n=11;while(n-->1){b=I.subtract(a);s=a.subtract(b);a=a.pow(2).add(I).divide(s,C);}S=I.divide(b.negate(),C);while(++n<20){x=b.divide(a,C).pow(n);y=x.divide(a,C);S=S.add(I.divide(I.subtract(x),C).add(y.divide(I.subtract(y),C)).multiply(y.pow(n)));}System.out.println(S.multiply(s,C));}}

@PeterTaylor Thank you for helping me.  I seem to keep making different blunders.  Fortunately, they have been more and more minor (it seems).

K (19)
(or 17 if you skip defining it as a function)
f:{+/*+%x(|+\)\|!2}

Tested on Kona.
Basically, it generates the first x values of the fibonacci sequence into an array (without using builtins), divides 1 by each value of the entire array, transposes and sums it up.
(thanks to @tmartin for the better sum method)

A slight variation on yours for 17 chars -- {+/*+%x(|+\)\|!2}

@tmartin Thanks, yes, that was a less convoluted sum method :)

Perl - 35 bytes
print!map$\-=1/($%+=$.=$%-$.),0..<>

Sample usage:
$ echo 10 | perl inv-fib-sum.pl
3.34170499581934

Further Analysis
It's interesting to note that the sum

is convergent. Supposing we wanted to calculate a few thousand digits or so, the naïve approach is almost sufficient. The convergence is quite slow at first, but speeds up rapidly, so that 1000 digits only takes about 4800 terms. A sample Python implementation might be:
a=[1,1]
for i in range(4800):a=[a[0]+a[1]]+a
z=10**1000
print sum(map(lambda i:z/i,a))

which after a second or so outputs:
33598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142832933

(The last four digits don't quite converge, but we'll ignore that for now.)
Let's try to speed up the convergence a bit. A standard trick is to use Euler's Transform. After expansion and simplification, this produces a nicer result:

It should be fairly apparent why this converges more quickly; each term has 3 terms in the denominator rather than just one. Calculating 1000 digits takes only 1600 (one third as many) terms:
a=[1,1]
for i in range(1601):a=[a[0]+a[1]]+a
z=10**1000
print sum(map(lambda i:(-1)**i*z/(a[i]*a[i+1]*a[i+2]),range(1601)))

Output:
3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142834500

(Here again, the last 4 digits don't converge.)
We're not quite done yet. If we combine adjacent terms, we end up with the following:

Factoring out each term from the remainder of the summation gives the nested expression:

Now we're getting somewhere. Notice that the numerators of follow OEIS A206351 (with the exception of the first term, which is doubled):

and the denominators follow OEIS A081016 (shifted by one term):

Each of these have very simple recurrence relations, namely:

and

respectively. Putting it all together, we find that we need only 800 iterations for 1000 digits:
b,c=[16,3,1],[273,40,3]
for i in range(800):b,c=[7*b[0]-b[1]-4]+b,[7*c[0]-c[1]-1]+c
s=z=10**1000
for x,y in zip(b,c):s=(z+s)*x/y
print s

which outputs:
3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142835294

(Here, finally, the last 4 digits converge correctly.)
But that's still not quite everything. If we observe the intermediate values for s, we find that it converges to a different value entirely before converging on the actual convergence point. The reason for this is the following:

Solving for a stable s, we find that:

Because this is a simple root, we can use Newton's Method to get us most of the way there, and then jump in at a much later point in the iteration. Only about 400 digits of precision are necessary (as the b and c values aren't any larger than that anyway), which can be achieved with just 7 iterations, while saving 320 iterations of the main loop:
b,c=[16,3,1],[273,40,3]
for i in range(480):b,c=[7*b[0]-b[1]-4]+b,[7*c[0]-c[1]-1]+c
z=10**1000;s=z/17
for i in range(7):s-=(s*s+s*z-z*z/16)/(2*s+z)
for x,y in zip(b,c):s=(z+s)*x/y
print s

Output is identical to the previous, runtime is about 0.02s on my system using PyPy v2.1. Even though it needs one tenth the number of iterations as the original, it's significantly faster than 10x due to multiplying and dividing by much smaller terms. I don't think much more can be tweaked out of it, although I'd be happy to be shown wrong.

Mathematica (32 characters without built-in Fibonacci)
Tr[1/⌈(.5+√5/2)^Range@#/√5-.5⌉]&

Here I used the rounding formula for Fibonacci numbers

where φ is the golden ratio.

Kona (25 21)
{+/%(x(|+\)\1 1)[;1]}

Probably could be made smaller by experts, but I am still learning the language.
  f 10
3.341705
  f 3
2.8333
  f 25
3.359872
  f 400
3.359886

The last one didn't actually take any more time than the others.

I am learning some languages by completing challenges in them.  Nice to see that I am not the only one.

Save yourself two characters by just calling the function as a lambda rather than a named function. Then save a further two by using % as the reciprocal function rather than doing 1.% -- {+/%(x(|+\)\1 1)[;1]} for 21 chars

@tmartin: Odd...I thought I tried doing reciprocal and was getting 0 because of integer division, but it is currently working for me. I'm updating the answer, thanks a lot!

Are you sure you're computing the right sum? I get 2.833333333 for n=4, for example, instead of 3. One of us is wrong!

@Tobia: A difference between 0 and 1 indexing. f 0 results in 1.0, f 1 -> 2.0 and so on.

Well, it does say "an input of 10 means to calculate based on the reciprocals of the first 10 Fibonacci numbers"…

APL, 21 chars/bytes*
{+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵}

Example
      {+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵} 10
3.330469041
      ⍪{+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵}¨⍳10
1
2
2.5
2.833333333
3.033333333
3.158333333
3.23525641
3.282875458
3.312287223
3.330469041
      {+/÷{↑+\∘⌽⍣⍵⊢0 1}¨⍳⍵} 100
3.359885666

⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
*: APL can be written in its own (legacy) single-byte charset that maps APL symbols to the upper 128 byte values. Therefore, for the purpose of scoring, a program of N chars that only uses ASCII characters and APL symbols can be considered to be N bytes long.

Mathematica 30  24
With 6 characters saved thanks to ybeltukov.
 Tr[1/Fibonacci@Range@#]&

Before adding the terms:
1/Fibonacci@Range@#&[20]

With addition included:
 Tr[1/Fibonacci@Range@#]&[20]

Fibonacci is Listable :) It can be reduced to Tr[1/Fibonacci@Range@#]&

K, 22
...
{+/%x#x{x,+/-2#x}/1 1}

Javascript, 33
Input: n = 10
s=f=t=1;for(;n--;)t+=1/(s+=f=s-f)

Based in my first post in Perl, here is the result directly from the Google Chrome Console.

Perl 6, 27 bytes
{sum 1 X/(1,&[+]...*)[^$_]}

Try it online!
Alternatively
{sum 1 xx$_ Z/(1,&[+]...*)}

Try it online!

Python (55 51)

i,r=p=1,1
while i<n+1:r+=1./p[-1];p=p[1],sum(p);i+=1
r

i,r,a,b=[1]*4
while i<n+1:r+=1./b;a,b=b,b+a;i+=1
r

In interactive mode:
n=10
3.341704995819338

n=100

3.3598856429940778

3.359885666243178

n=400

3.3598855578800064

3.359885666243178

BC - 116
define f(n){if(n < 2){return n;}else{return f(n-1)+f(n-2);}}
define r(n){for(i=1;i<n;++i){m=m+(1/f(i));};return m;}

call r(n) with n to solve. The precision can be set arbitrarily, so this is the most accurate solution.

Forth, 64
: r 1 1 rot 1e 0 do 2dup - nip tuck + dup s>f 1/f f+ swap loop ;

usage:
10 r f. 3.34170499581934  ok
100 r f. 3.35988566624318  ok
1000 r f. 3.35988566624318  ok

GTB, 35
Runs on a TI-84 calculator
1→Y:0→X`N4;N,1,N~1/X:Y→Z:X+Y→Y:Z→X&

Store 1 in Y and 0 in X
Take N as input
Initialize a For loop
Display X
Store Y in Z and X+Y in Y
Store Z in X
End the For loop

I assume it works, but can you provide an explanation?

I've added one.

PERL, 62 43

$s=$t=1;$t+=1/($a=$f+$s),$f=$s,$s=$a,for 0..<>;say $t

Edit:
After some more time looking at my code I was able to save 19 chars:
$s=1;$t+=1/($s+=$f=$s-$f)for 0..<>;say $t+2

input: 10
  > 3.35294128575734

RPL (HP 49G/G+/50g), 50 bytes
« 0. 1. DUP2 5. ROLL
  START SWAP OVER + ROT OVER INV + UNROT
  NEXT DROP2
»

Examples:
10 -> 3.33046904076
11 -> 3.34170499582
30 -> 3.35988372158
55 -> 3.35988566622
In theory, the sum of the first 55 digits would give 12 correct digits. The last digit should be '4' instead of '2'. This should be fixed by adding up the terms backwards, but the code would be slightly longer.
If the constant were to be computed to 1000 decimal places using the definition  the sum should be carried out to at least the first 4790 terms, which would take too much time on the HP 50g, if possible at all. For this task a more efficient method is required, like the one used in the following RPL program (464 bytes, checksum # 207Eh) whose argument is the desired number of decimal places:
%%HP: T(3)A(R)F(.);
\<< PUSH RAD -105 CF -3 CF R\->I DUP 1 + 2 INV SWAP 100 LN * 5 LN + OVER ASINH / \v/ * CEIL DUP 2 MOD + DUP 0 ROT
[[ 1 1 ]
 [ 1 0 ]] SWAP DUP2 ^ 3 GETI UNROT GET 4 ROLLD 4 ROLLD DUP + ^ 1 GETI UNROT GET 1 + 0 1 8 ROLL 2 /
  START PICK3 + DUP PICK3 * NEG 6 PICK SQ + / 4 PICK SQ * EXPAND ROT PICK3 - ROT OVER - ROT 6 ROLL 6 ROLL 6 ROLL + LASTARG * LASTARG 5 ROLLD 5 ROLLD / + ROT PICK3 - ROT OVER - 6 ROLL 6 ROLL 6 ROLL
  NEXT ROT + INV 5 ROLL + EXPAND 4 ROLLD 3 DROPN FXND PICK3 ALOG OVER - PICK3 * SWAP IQUOT + \->STR DUP HEAD -51 FC? { "." } { "," } IFTE + SWAP TAIL + 1 ROT 2 + SUB POP
\>>

'RFC' STO

1000 RFC -->
3.3598856662431775531720113029189271796889051337319684864955538153251303189966833836154162164567900872970453429288539133041367890171008836795913517330771190785803335503325077531875998504871797778970060395645092153758927752656733540240331694417992939346109926262579646476518686594497102165589843608814726932495910794738736733785233268774997627277579468536769185419814676687429987673820969139012177220244052081510942649349513745416672789553444707777758478025963407690748474155579104200675015203410705335285129792635242062267537568055761955669720848843854407983324292851368070827522662579751188646464096737461572387236295562053612203024635409252678424224347036310363201466298040249015578724456176000319551987905969942029178866949174808096746523682654086938399069873211752166957063859411814553647364268782462926166650100098903804823359519893146150108288726392887669917149304053057745574321561167298985617729731395370735291966884327898022165047585028091806291002444277017460241040417786069190065037142835294
(22 min 23 sec, on the real HP 50g)

For one thousand digits the first 50 terms of the series plus another 50 terms of a continued fraction are evaluated, two at a time in only 25 iterations (48 terms of each would have sufficed, though). An equivalent DECIMAL BASIC program takes just 10 milliseconds on my computer (Intel(R) Core(TM) Duo CPU E4700 @ 2.6 GHz).

Japt -mx, 6 bytes
1/MgUÄ

Try it

JAEL, 9 7 bytes
Changing the diacritics from one character to another gave me 1 byte
Still working on SBCS encoding.
#`&@uȦ

Explanation (generated automatically):
./jael -u explain '#`&@uȦ'

ORIGINAL CODE:
#`&@uȦ

EXPANDING EXPLANATION:
Ȧ => .a!

EXPANDED CODE:
#`&@u.a!

COMPLETED CODE:
#`&@u.a!,

#       ,               repeat (p1) times:
 `                              stack 1
  &                             push number of iterations of this loop
   @                            push nth fibonacci number
    u                           push p2 / p1
     .                          push the value under the tape head
      a                         push p1 + p2
       !                        write p1 to the tapehead
         ␄              print machine state

Yes, you're right. I miscounted it.

I know the language is optimised for characters, but this site scores by bytes, so it's misleading to include the character count

You can get 8 bytes if you don't compress u.. On the topic of an SBCS, you might have trouble because your docs list over 600 commands or combinations of commands, and a SBCS language can only have 256 single byte commands. On the other hand, there's a large number of useless one to one translations...

Yes @JoKing, you are right. I started the whole idea a while ago and didn't consider that it would affect the byte size. Now I'm writing my undergraduate thesis on top of JAEL and it's too late to reconsider some decisions (I'm presenting it by the end of november). About the command list: yes, it was automatically generated and I didn't give it enough attention. As this is my first project on this area, I'll gather experience and try to learn from the bad decisions. Thank you for sharing your thoughts!

C# (.NET Core), 66 bytes
a=>{double r=1,x=1,y=1,i=0;for(;++i<a;y+=x,x=y-x)r+=1/y;return r;}

Try it online!
Can't use floats because of imprecision.
Example where input = 8:

double: 3.28287545787546 (rounds to 3.282875)
float:  3.282876 (off by 0.000001)

Ungolfed:
a => {
    double r = 1,                       // initialize r (sum of reciprocals) - start at 1 to save one byte in for loop
            x = 1, y = 1,                   // initialize x (2nd largest Fibonacci) and y (largest Fibonacci)
            i = 0;                          // initialize i (loop counter)
    for(; ++i < a; y += x, x = y - x)   // from 1 to a, while incrementing the Fibonacci numbers
        r += 1 / y;                         // increment the reciprocal Fibonacci
    return r;                           // return the reciprocal Fibonacci
}

cQuents, 13 11 bytes
;/b$
=1:Z+Y

Try it online!
Explanation
;          The sum of the first n terms of the sequence
 /         which are 1 divided by
  b$       the nth term in the sequence on the second line

=1:Z+Y     Fibonacci with starting indexes 1,1

Jelly, 5 bytes
RÆḞİS

Try it online!
How it works
RÆḞİS    Main link (monad). Input: integer
R        Range
 ÆḞ      nth Fibonacci number
   İ     Reciprocal
    S    Sum

J-uby, 24 bytes
:+|:sum+(:++[0,1]|:/&1r)

Returns a fraction. If a floating point number is necessary, change 1r to 1.0 for +1 byte.
Attempt This Online!
Explanation
J-uby's + operator, when called with a function and initial array like fn + arr, returns a function that, when called with an integer n (like (fn + arr).(n)), applies fn to the last arr.size items in arr n times, making it very handy for Fibonacci and similar sequences.
:+ | :sum + (:+ + [0,1] | :/ & 1r)
:+ |                                # Range 1..input, then
     :sum + (                    )  # sum of...
             :+ + [0,1] |           #   nth fibonacci number, then
                          :/ & 1r   #   reciprocal

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


text:
Crazy chemical equations
You should get string of chemical equation (no spaces, only letters (upper-case and lower-case), numbers, brackets and math signs) from user and print the answer if equation is balanced or not (any pair of positive/negative answers: Yes/No, true/false, 1/0). To make code shorter you can assume that input strings can contain only these elements: Al, Ar, B, Be, C, Cl, Cr, Cu, Fe, H, He, K, N, O, S. And one more thing: there could be - signs. It's all about math: + means addition, - means subtraction.
Examples:
Input:
C6H5COOH-O2=7CO2+3H2O

Output:
No

Input:
2Fe(CN)6+2SO2+202=Fe2(SO4)2+6C2N2

Output:
Yes

Input:
2SO2=2SO4-2O2

Output:
Yes

The shortest code wins.

Are you looking for a function? Or a program that takes text input and gives text output? If the later, should it take and process multiple lines? Or just one equation per run?

Related: Balance chemical equations

@MtnViewMark It is supposed to be a program. It should take one equation per run.

Your second and third examples are wrong. I think you meant to type 2O2 instead of 202 (two hundred and two).

@squeamishossifrage Oh, yeah. Sure. Thank you. Question is updated.

Mathematica 152
f=Times@@@Tr@CoefficientRules@ToExpression@(r=StringReplace)[r[
#<>")",{"="->"-(",x:_?LetterQ|")"~~y_?DigitQ:>x<>"^"<>y}],x_?UpperCaseQ:>" "<>x]⋃{}=={0}&

Result:
f@"C6H5COOH-O2=7CO2+3H2O"
f@"2Fe(CN)6+2SO2+2O2=Fe2(SO4)2+6C2N2"
f@"2SO2=2SO4-2O2"

False
True
True

I treat the chemical formula as a polynomial, e.g.

Then I just count the coefficients.

How does that work? In your example, the coefficients of each "variable" doesn't simplify to zero.

@MtnViewMark More precisely, I count powers with Tr@CoefficientRules and then multiply they by coefficients with Times@@@. For O: 2*2+2*2=4*2, for C: 2*6 = 6*2, etc.

Haskell, 400 351 308 characters
import Data.List
import Text.Parsec
(&)=fmap
r=return
s=string
l f b=(>>=(&b).f)
x=(=<<).replicate
m=sort&chainl1(l x(concat&many1(l(flip x)n i))n)((s"+">>r(++))<|>(s"-">>r(\\)))
i=between(s"(")(s")")m<|>(:[])&(l(:)(many lower)upper)
n=option 1$read&many1 digit
main=getContents>>=parseTest(l(==)(s"=">>m)m)

This just might have all the golf squeezed out of it. I don't know if there is another 100 51 8 characters to be saved!
& echo 'C6H5COOH-O2=7CO2+3H2O' | runhaskell Chemical.hs
False

& echo '2Fe(CN)6+2SO2+2O2=Fe2(SO4)2+6C2N2' | runhaskell Chemical.hs
True

& echo '2SO2=2SO4-2O2' | runhaskell Chemical.hs
True

Here's the ungolf'd version, in case anyone want to follow along. It is a simple Parsec based parser:
import Control.Applicative ((<$>), (<*>))
import Data.List
import Text.Parsec
import Text.Parsec.String (Parser)

type Atom = String

{- golf'd as x -}
multiple :: Int -> [Atom] -> [Atom]
multiple n = concat . replicate n

{- golf'd as m -}
chemicals :: Parser [Atom]
chemicals = sort <$> chainl1 molecules op
  where
    op :: Eq a => Parser ([a] -> [a] -> [a])
    op = (char '+' >> return (++))
     <|> (char '-' >> return (\\))

    molecules :: Parser [Atom]
    molecules = multiple <$> number <*> terms

    terms :: Parser [Atom]
    terms = concat <$> many1 term

    term :: Parser [Atom]
    term = flip multiple <$> item <*> number

{- gofl'd as i -}
item :: Parser [Atom]
item = between (char '(') (char ')') chemicals
   <|> (:[]) <$> atom
  where
    atom :: Parser Atom
    atom = (:) <$> upper <*> many lower

{- gofl'd as n -}
number :: Parser Int
number = option 1 $ read <$> many1 digit

{- gofl'd as main -}
main :: IO ()
main = getContents >>= parseTest chemEquality
  where
    chemEquality :: Parser Bool
    chemEquality = (==) <$> chemicals <*> (char '=' >> chemicals)

Python 2.7, 316 276 chars
import re
r=re.sub
x='(^|[=+-])'
y=r'\1+\2'
z='(\w)([A-Z(])'
t=r('=','==',r(z,y,r(z,y,r('([A-Za-z)])(\d)',r'\1*\2',r('([=+-]|$)',r')\1',r(x+'(\d+)',r'\1\2*(',r(x+'([A-Z])',r'\1(\2',raw_input())))))))
E=re.findall('[A-Za-z]+',t)
print all(eval(t,{f:f==e for f in E})for e in E)

It does a lot of regex-rewriting to convert the input equation into something evalable.  Then it checks the equation for each element individually.
For instance, the example equations rewrite to (the t variable):
(C*6+H*5+C+O+O+H)-(O*2)==7*(C+O*2)+3*(H*2+O)
2*(Fe+(C+N)*6)+2*(S+O*2)+2*(O*2)==(Fe*2+(S+O*4)*2)+6*(C*2+N*2)
2*(S+O*2)==2*(S+O*4)-2*(O*2)

I'm sure there's more golf to be had on the regex part.