text:
Confound my attempts to solve the halting problem
Please note: By its nature, the spec for this challenge is difficult to understand. It probably requires at least a freshman course in computability theory, or equivalent background reading. In addition, the challenge itself is rather hard. Answering it will require writing an entire interpreter for some subset of your language of choice, and not only that but the interpreter will have to be in the form of a something like a quine. If your answer isn't doing all of this, it is almost certain not to meet the spec.
You don't need to solve the halting problem (even partially) in order to solve this challenge. However, you almost certainly do need to write an interpreter (of the language you are using, written in the same language it interprets), though it need not be feature complete. It's this that makes this an interesting challenge.
I promised to award a 500 point bounty to the first answer that meets the spec, and this will be awarded to Jo King's BF answer.
The challenge
A rough, simplified version of Alan Turing's proof of the unsolvability of the halting problem goes something like this:
Suppose I've written a program F that's meant to solve the halting program. That is, F takes the source code of another program as input, and F(G) is supposed to return 1 if G halts, and 0 otherwise.
But if I give you my program F then you can construct another program, H, that runs my program with H as its input. If F(H) returns 0 then H returns 0, but otherwise it deliberately goes into an infinite loop. This leads to a paradox, and we have to conclude that F can't solve the halting problem after all.
Your task is to write the program H, but with a twist: I'm not going to give you my program. Instead, your program will receive my program's source code as an input. That is:

Your program will receive my program as an input, in source code form. (E.g. as a file or as command line input, the details are up to you.)
My program will be written in the same language as your program, and also takes input in the form of a source code string.
If my program returns 0 when given your program as input, your program should halt (and return 0) when given my program as input. (The exact meaning of "returing 0" is up to you.)
if my program doesn't halt, or if it returns anything other than 0 when given your program as input, your program should keep running indefinitely.

The twist is that, just to make it really quite a lot harder, you have to obey the following rules:

You can't use any kind of built-in exec or eval-type function.
You can't use any "cheating" methods to get at your own program's source code. (E.g. you can't say "save this in a file called 'program'" and then have open(program) in your program.)

This means that your program has to be some kind of crazy super-quine that can not only reproduce its own source code in the form of a string, but is also capable of correctly parsing and interpreting the language it's written in.
To make it slightly less insanely hard, you're allowed to use just a (Turing-complete) subset of your chosen language. So if your program is written in Python and will only work if my program only contains ifs and while loops and basic string operations, then that's OK as long as your program only uses those things too. (This means that you don't have to worry about implementing your chosen language's entire standard library!) However, your program does have to actually run - you can't just make up your own language.
This is popularity-contest, so the answer with the most votes wins. However, as mentioned above, it's a serious challenge just to meet the spec at all, so I will award a 500 point bounty to the first answer that does so according to my judgement.
please note: no doubt there are many ways you can "cheat" at this challenge, given the exact wording I've used. However, I'm really hoping for answers that enter into the spirit of the question. The challenge as intended is very difficult but possible, and I'm really hoping to see genuine solutions to it. I won't award the bounty to an answer that feels cheaty in my judgement.

Note: this challenge was originally posted as popularity-contest, but it was closed in 2016 due to not having an "objective winning criterion", and I changed it to code-golf in order to get it reopened. However, I've found that, as of January 2018, popularity-contests are not in fact banned on PPCG (with this being the most recent meta discussion) so closing it in the first place was against site policy. I understand that popcons are not popular these days, but this is an old challenge, and its nature makes it really unsuitable for the code-golf scoring system. If anyone still feels strongly that it shouldn't be allowed then let's have a meta discussion before close votes start getting thrown around. Finally, on the off-chance that someone's spent the last year attempting to golf their solution, rest assured that it will be just as competitive in this challenge, and just as worthy of the bounty, as it would have been in the code-golf version.

By returning, do you mean exit code or stdout? Or are both acceptable?

Both are acceptable.

@Nathaniel I take it it would be illegal to export the received code for F into a file and importing it? ;3

@Nathaniel And also, I cannot use No Comment here unfortunately (function calls are eval calls, functions are strings). :c

@Trimsty indeed. I would say both of those options are taking the exec/eval route.

Your clever inversion of the problem actually reverses the halting problem.  To "win," one basically needs to write a program which solves the halting problem, and then intentionally halts/loops to fail.  If you get to write the program input after seeing the test code, then you can always mentally feed the program to itself, resulting in a input which demonstrates that the halting problem had not been solved by the other.  All those issues aside, what you have declared is a battle of wills, inspiring another consciousness to try to outwit your consciousness, using a language of programs

I like this question a lot but it is hard to understand. If anyone else is having trouble, these two slides (in Java psuedocode) made it much easier for me to understand: http://imgur.com/a/NRmyO

@Harry It's been so long since I posted this challenge that I myself am finding it hard to understand!

You mention the "spirit of the question" and "genuine solutions". What do you mean by that? Are we supposed to write an interpreter for our language ourselves? I can't imagine another way to do it.

@KSFT yes, you are supposed to write an interpreter. I believe there is indeed no other way to do it. (At the time I wrote the challenge, I felt this site could be a place for highly non-trivial challenges aimed at computer scientists, and this was an experiment to see if that would work.)

I've changed the winning criterion, so it's no longer off topic due to lacking an "objective primary winning criterion."

Related.

In CJam, the only way to dynamically construct blocks is through eval: "{"\+"}"+~. Can I do that?

@Challenger5 sorry, no - the rules about eval are really explicit. (And please heed the warnings in the first paragraph. If CJam is Turing complete and has I/O then it is possible to solve this challenge without using an eval block, and you should make sure you understand why before attempting a solution.)

I was thinking about doing an Underload answer, but Underload can't inspect strings whatsoever and furthermore the only way to do control flow (eval) is banned.

Well then it's hardly the right tool for the job, is it? This challenge is as language-agnostic as possible, but if your language can't handle string input then there's not really much you can do.

Thank you @user for posting a bounty, I agree that Esolanging Fruit's answer should be rewarded!

brainfuck, 6013 4877 4376 bytes
Edit: -1136 bytes. Switched to a better way of generating the data for the quine
Edit2: -501 bytes. Revisited my self-interpreter and cut it down a couple of hundred bytes
->++>++++>+>++>+++>>++++>>++++>>+++>>++++>>+++>>++>++>++>++>++>++>++>++>++>++>++++>+++++>+>++>++>++>++>++>++>>+++>+>++>++>++++>+>+++>+>++++>+>+++>+>++>>>+++++>++++>++++>>+++>>++++>>+++>>++>++>++>++>++>++>++>++++>+++++>+>++>++>++>++>++>++>>+++>+>++>++++>+>+++>+>++++>+>+++>+>++>>>+++++>+++>>+++>+>+++++>+++++>++++>>++>+>++>++>++>++>++>++>+++>>++>++>>++++>>+++>++>++>++>++>++>++++>+++++>>++>++>++>+>+++>>++++>>++>++>++>>++>++>++>>++>++>++>>++>++>++>++>++>++>>++>++>++>++>++>++>>++>++>++>>++>++>++>++>>++>++>++>++>++++>+>+++>>+++++>+++>>++>>+++++>>>++>>++>++>++>>+++++>+++++>>>++>++>++++>+>+++>+>+>++++>+>+++>+>+>++++>+>+++>>++++>++++>++++>>+++>>>++++>>+++>>>++++>>+++>+>++++>+++++>>>++>+>+>+++>+>++++>+>+++>+>+>++++>+>+++>+>+>++++>+>+++>>+++++>+++>>++++>>+++>>>++++>>+++>>>++++>>+++>>>++++>+++++>+>+>++>++++>+>+++>+>++>>>++++>>+++>>+++>+>+>++++>++++>+++++>>++>+>+++>+>+++>>>++++>>+++>>++++>++++>+++++>+>++>>+++>>+++>+>+>++++>+>+++>+>+>++++>+>+++>+>+>++++>+>+++>>+++>>>>++++>>+++>>>++++>>+++>+>++++>++++>+++++>+++>+>+++>>>>++++++>++++>>++>++>++>++>++>++>++>++++>+>+++++>+++++>+++++>+++++>+++++>+++++>>+++++>+++>++>+>+++++>++++>>+++>>++++>+>++>+>++>>>>>+++>+>+>+>+++++>++++>>+++>>++++>+>++>+>++>>>>>+++>+>+>+>+++++>++++>>+++>>++++>+>++>+>++>>>>>+++>+>+>+>+++++>++++>>+++>>++++>+>+++++>+>++>++>++>>>>>+++>+>+>+>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>+++++>++++>>+++>>++++>+>++>++>+>++>>>>>+++>+>+>+>+++++>+++++>++++>>+++>>++++>+>+++++>+>++>++>++>++>++>++>++>>>>>+++>+>+>++>++>++>++>++++>+++++>+>+++++>+++++>+++++>+++++>+++++>+++++>>+++>++>+>++>++++>>+++>>++++>+>++>++>+>++>>>>>+++>+>+>+>+++++>+++++>++++>>+++>>++++>+>+++++>+>++>>>>>+++>+>+>+++++>+>++++>++>+++>+>++++>>+++>>++++++>+++>>>>++>+>+>+>+>+++++>++++>+>+++>>++++>+++++>++++>+>+>+++>>++++>+>++>++++>>+++>>>++++>+>+++>+>+>++++>>>++>++++>+>+>++++>+>+++>+>+>+++++>++++>>>+++>+>++++>>>>>++++>>+++>>++>+>+>++++>+>+++>+>+++>+>+++++>++++>>>+++>+>++++>>>>>++++>>+++>>+++++>+>+>++++>+>+++>+>+++>+>++>++>++++>+++++>>>++>+>+>+++>>>++++>>+++>>+++>+>+++>+>++++>+>+++>>+++++>+>+++>>+++++>++++>+>+>+++>>++++>+>++>++>++++>>+++>>>++++>+>+>+++>>++++>+>+>++>++++>+>+>++++>+>+++>>++++>+++++>+>+>++>>>+++>>+++++>+++++>++++>+>+>+++>>++++>++++>>+++>>++>+>+>++++>+>+++>+>+++>>++>++++>+>+>+++>>++++>++++>>+++>>+++++>+>+>++++>+>+++>+>+++>>++>++++>>+++>>+++>+++>+>+>++++>+>+++>>+++++>+++++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>>+++++++>+>+>+>++++>+>+++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>>+++++>+>+>+>++++>+>+++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>>++++++>+>+>+>++++>+>+++>+>+>+>++++>+>+++>+>++++>+>+++>>++++>++++>>+++>>++++>>+++>>>>++++>>+++>>>++>+>+>+>++++>+>+++>+>+>+>++++>+>+++>+>++++>+>+++>>+++++>+++>>++++>>+++>>++++>>+++>>>++++>+>+++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>>++>+>+>+>++++>+>+++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>>>++++>>>+++>>++++>+>+>+>++++>+>+>+++>+>++>>>>++++>>>+++>>+++++>+++>>++++>+++++>+++>+>+>++>++++>+>++++>+++++>>>++>+>+>+++>+>+++>+>++++>+++++>>>++>+>+>+++>+>++++>+>+++>+>+++>>+++++>++++>+>+>+++>>++++>++++>>+++>>++>++>++++>+++++>+++++>>++++>+++++>+>+>++>>>+++>>+++>++>+>+>+++++>++++>++>++>+>+>+++>+>++++>+++++>>>>++++>>>+++>>++>+>+>+>++++>+>+>+++>+>+++>+>++++>+>+++>+>+++>+>++>++>++>++>++>++>++>++>>>++++>++>+>+>+++++>>>+++>>+++>>>++++>++++[<+]>[>[>]>[>]>++++++++++[-<++++++>]<++[<]<[<]<+>>-[[>]>[>]>+++++++[-<++++++>]<+[<]<[<]<+>>-]>]<--[>+<++++++]>++>[>]+++++[->+++<]>[>+++>+++>+++>++++++>++++++>+++>++++>++++[<]>-]>+>->>+>+++>-->>++[<]<<[<]<<[<]>[[[>]>>[>]>>[>]<[->>+<<]<[<]<<[<]<<[<]>-]>[>]>>[>]>>[>]>>[-<<+[<]<+>>[>]>]<<[[->+<]<]>>[>]>[[-<+>]>]<<[<]<<[<]<<[<]>]>>>[>]>>[>]<[[-]<]>>>,[>+++++++[<------>-]+<-[>]>[<+<+>>>>]<<<-[>]>[<+<+>>>>]<<<-[>]>[<+<+>>>>]<<<-[>]>[<-<+++>>>>]<<<--------------[>]>[<++<+>>>>]<<<--[>]>[<-<+++++++>>>>]<<++++[-<------>]+<+[>]>[<++<+>>>>]<<<--[>]>[<-<+>>>>]<<-<[+]<[>]>,]>>>+<<<<-[<]>[-[<<]>[<+[>]>>[<]<<[>>+[<<[<]<<-[>>]<[>>>>[>]>+<<[<]<]<-[>>]<[>>>>[>]>-<<[<]<]<++[->>+<<]>>[>]>]<]<[<]>-<]>-[<<]>[<++[>]>>[<<]>[<<+[<<[<]>[-<<+>>]>--[<<]>[[>]>+<<[<]<]>+[<<]>[[>]>-<<[<]<]>+[>]>]]<<[<]>--<]>-[<<]>[[>]>>.<<<[<]<]>-[<<]>[[>]>>-<<<[<]<]>-[<<]>[[>]>>,<<<[<]<<<[<]<[<]>[[>]>[>]>>>[>]>>+<<<[<]<<<[<]<[<]>-]>[>]>[>]>>[<]<]>-[<<]>[[>]>>+<<<[<]<]>-[<<]>[[>]>>>[>>]>[<<<[<<]<+>>>[>>]>-]>[-]<<+[<[->>+<<]<]<[->>+<<]<[<]<]>-[<<]>[[>]>++[-->[-<<+>>]>]+<<-[++<<]<[->>>[>>]>+<<<[<<]<]<[<]<]<++++++++>>[+<<->>]>]>>[]

Try it online! The input here is a simple cat program (,[.,]) which will print the program itself.
"Return 0" is defined by ending the program on a cell with value 0.
A unholy combination of two programs I've written in the past, a quine and a self-interpreter. First section is the quine part, which takes the data and populates the tape with the the data generation followed by the source code. Next is the self-interpreter, which takes your program and runs it. This is pretty much a unchanged copy of a normal self interpreter, except that instead of taking input directly, it gets input from the beginning of the data section, setting the cell to 0 if there is no more input. Finally, end on the current cell of your program and run []. If the returned value was 0, my program will end on zero. If it is anything else, it will run an infinite loop. If your program runs forever, my program will run forever.
How It Works:
Part 1: Data Generation
->++>++++> ....... >+++++>>>+++>>+++>>>++++>+++

This part makes up the data section of the quine, and is by far the majority of the code at 3270 bytes. The beginning - is a marker for the beginning of the data. Each >+++ represents a character of the code after this section.
Number of Pluses
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
> | < | + | ] | [ | - | , | . |

Part 2: Generate the data section using the data
+[<+]>

[
    Add a right arrow
    >[>]>[>]>(10++++++++++)[-<(6++++++)>]<++[<]<[<]
    <+>>-
    Add the right amount of pluses
    [
        [>]>[>]>(7+++++++)[-<(6++++++)>]<+[<]<[<]<+>>-
    ]
    >
]
Add the beginning minus
<--[>+<++++++]>++

This uses the data from part one to add the characters that are used to generate the data to the code section. It adds a > to the end of the code section and that cell's value many pluses.
Part 3: Generate the rest of the code using the data
Initialises the 8 characters of brainfuck
>[>]+++++[->+++<]>[>+++>+++>+++>++++++>++++++>+++>++++>++++[<]>-]
>+>->>+>+++>-->>++[<]<<[<]<<[<]>

Tape looks like:
data 0 0 code 0 0 characters

Runs through the data destructively and adds the represented symbol to the code section
[
    [
        For each plus in this cell
            Shift the gap in the characters over one
        [>]>>[>]>>[>]<[->>+<<]
        <[<]<<[<]<<[<]>-
    ]
    Navigate to character
    >[>]>>[>]>>[>]>>
    Copy the character to the end of the code section
    [-<<+[<]<+>>[>]>]

    Shift the symbol section over one
    <<[[->+<]<]
    >>[>]>[[-<+>]>]

    Navigate to next byte of data
    <<[<]<<[<]<<[<]>
]

Remove characters
>>[>]>>[>]<[[-]<]

Destroys the data section and adds the rest of the source code to the code section
Part 4: Get inputted program
>>>,
[
    >(7+++++++)[<(6------)>-]+<-
    [>]>
    [plus <+<+>>>>]<<<
    -[>]>
    [comma <+<+>>>>]<<<
    -[>]>
    [minus <+<+>>>>]<<<
    -[>]>
    [dot <-<+++>>>>]<<<
    (14--------------)[>]>
    [left <++<+>>>>]<<<
    --[>]>
    [right <-<+++++++>>>>]<<
    (29++++[-<------>]+<+)
    [>]>
    [start loop <++<+>>>>]<<<
    --[>]>
    [end loop <-<+>>>>]<<
    -<[+]<[>]>,
]

Gets the inputted program. Removes non-brainfuck characters and represents each character with a number:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
] | [ | . | - | , | + | > | < |

Represents the end of the program with 255.
Part 5: Interpreting the input
Initialise simulated tape
>>>+<<<<-

[<]>
[
    -[<<]>
    [end loop
        co 0 0 0 e:  _1 0 0 0 1 ?
        Check if current cell is one
        <+[>]>>[<]<<
        co 0 0 1 e _1: 0 0 !0 1
        or
        co 0 0 1 e _1 0: 0 0 1
        [ If current cell is one navigate to corresponding start loop
            Create counter
            >>+
            [
                co 0 0 de _1 0 c: !0 1
                checks if next instruction is an end loop
                <<[<]<<-
                [>>]<
                c !0 0: 0 de _1 0 c !0 1
                or
                c: 0 0  0 de _1 0 c !0 1
                [>>>>[>]>+<<[<]<] Add one to counter if it is
                checks if start loop
                <-[>>]<
                c !0 0: 0 de _1 0 c !0 1
                or
                c: 0 0  0 de _1 0 c !0 1
                [>>>>[>]>-<<[<]<] Subtract one from counter if it is
                c ? 0: 0 de _1 0 c !0 1
                Adds two to counteract checks and move to the next instruction
                <++[->>+<<]
                >>[>]>
                c 0 0 ode _1 0 c: !0 1
                End on the counter
                    If the counter is 0 then we have reached the corresponding bracket
            ]
            c 0 0 2 de _1 0 0: !0 1 0
            <
        ]
        c 0 0 1?2 de _1 0: 0 0 1 0
        Subtract one from current instruction
            This executes the start loop code next but that does nothing
        <[<]>-<
    ]
    >-[<<]>
    [start loop
        c 0 0 0 de:  _1 0 0 ? 1
        <++[>]>>[<<]>
        c 0 0 2 de _1 0 0 0 1:
        or
        c 0 0 2 de _1 0 0: !0 1
        [ If current cell is 0 navigate to corresponding end loop
            Initialise counter
            <<+
            c 0 0 ode _1 0 c: 0 1
            [ While counter is not 0
                Transfer current instruction over (first instruction is guaranteed to be start loop)
                <<[<]>[-<<+>>]>
                co 0 0 de _1 0 c: 0 1
                Check if start loop
                --[<<]>
                co 0 0: !0 e _1 0 c 0 1
                or
                co 0 0 0 e _1 0 c 0 1
                [[>]>+<<[<]<] Add one to counter if so
                checks if end loop
                >+[<<]>
                co 0 0: !0 e _1 0 c 0 1
                or
                co 0 0 0 e:  _1 0 c 0 1
                [[>]>-<<[<]<] Subtract one from counter if so
                Add one to counteract checks and navigate to counter
                >+[>]>
                co 0 0 de _1 0 c: 0 1
                End on counter
                    If counter is 0 then we have reached the corresponding end loop
            ]
            co 0 1 e _1 0 0: 0 1
        ]
        co 0 0 2?1 e _1 0 0: ? 1
        Subtract two from the current instruction to bring it back up to the right value
        <<[<]>--<
    ]
    3 of these are pretty self explanatory
    Navigate to the current cell and execute the instruction on it
    >-[<<]>
    [output
        [>]>>.<<<[<]<
    ]
    >-[<<]>
    [minus
        [>]>>-<<<[<]<
    ]
    >-[<<]>
    [input
        Reset current cell
        [>]>>, (no more input so this is set to 0)
        co 0 0 0 e:  _1 0 0 0: 1 b 1 a 0 d 1 e 1 f
        Navigate to start of code section
        <<<[<]<<<[<]<[<]>
        d: ata 0 co 0 0 0 e _1 0 0 0 1 b
        or
        0: co 0 0 0 e _1
        Transfer next instruction to current cell
        [[>]>[>]>>>[>]>>+<<<[<]<<<[<]<[<]>-]
        0: ata 0 co 0 0 0 e _1 0 0 d 1 b
        or
        0: co 0 0 0 e _1
        Navigate back to the normal spot
        >[>]>[>]>>[<]<
    ]
    >-[<<]>
    [plus
        [>]>>+<<<[<]<
    ]
    >-[<<]>
    [right
        Simulated tape looks like:
            a b c: d e f
        co 0 0 0 e:  _1 0 0 c 1 b 1 a 0 d 1 e 1 f
        Navigate to value of cell to the right
        [>]>>>[>>]>
        co 0 0 0 e _1 0 0 c 1 b 1 a 0 d: 1 e 1 f
        Transfer it to temporary cell
        [<<<[<<]<+>>>[>>]>-]
        co 0 0 0 e _1 d 0 c 1 b 1 a 0 0: 1 e 1 f
        Pop extra marker if it exists from the right cells and add one to the left
        >[-]<<+
        co 0 0 0 e _1 d 0 c 1 b 1 a 1: 0 0 e 1 f
        Transfer all left cells over 2 cells
        [<[->>+<<]<]<[->>+<<]
        co 0 0 0 e _1 0: 0 d 1 c 1 b 1: a 0 e 1 f
        Navigate back to normal spot
        <[<]<
    ]
    >-[<<]>
    [left
        Simulated tape looks like:
            a b c: d e f
        co 0 0 0: e _1 0 0 c 1 b 1 a 0 d 1 e 1 f
        Add temporary marker
        [>]>++
        co 0 0 0 e _1 0 2: c 1 b 1 a 0 d 1 e 1 f
        Remove temporary marker and transfer all left cells over two
        [-->[-<<+>>]>]
        co 0 0 0 e _1 c 0 b _1 a _1 0 0: d 1 e 1 f
        Add marker to right cells remove marker from left cells and reset left cell's markers
        +<<-[++<<]<
        co 0 0 0 e _1 c: 0 b 1 a 0 0 1 d 1 e 1 f
        Transfer current cell to to right cells
        [->>>[>>]>+<<<[<<]<]
        co 0 0 0 e _1 0: 0 b 1 a 0 c 1 d 1 e 1 f
        Navigate back to normal spot
        <[<]<
    ]
    Add 8 to reverse checks
    <(8++++++++)>>

    Execute next instruction
    [+<<->>]>
]

Interprets the program. The only difference from a normal one is that the input is taken from the beginning of the code section instead of the input.
Part 6: Halt if return is not 0
>>[]

Navigate to the ending cell of your program and run an infinite loop if the return is not 0. If it is 0, exit the loop and end on that same 0.
Test Inputs:
Always returns 0 (halts and returns 0)
(empty program)

Always returns 1 (runs forever)
+

Returns all input added together, mod 256 (returns 211, so it runs forever)
,[[->+<],]>

Returns 0 if the last two characters of a code are an infinite loop ([]) (your program returns 0 when given my program, therefore my program halts)
,[>,]>(9+++++++++)[-<(10++++++++++)>]<[-<-<->>]+<---[[-]>[-]<]<-[[-]>>[-]<<]>+>[-<->]<

Fun Fact for those who are still reading
If the input for this program is the source code of this program, then it will start recursing, repeatedly creating self-interpreters that run this program and then give it the same program again. This gives me some interesting ideas on creating actual recursive programs in brainfuck. Instead of checking the return value and starting an infinite loop as in this question, the return value can be saved and acted upon. A simple example would be a factorial program that goes
If cell1 == 0:
    Get input into cell1
If cell1 == 1 or cell1 == 0:
    Return 1
Else:
    Initialise self-interpreter-quine function
    Pass cell1-1 into cell1 of the function
    Run function
    Multiply cell1 by the return value
    Return cell1

Of course, this is a completely insane way of coding brainfuck, given that running recursing self-interpreters will increase the runtime exponentially.

Yay! BTW if you wanted to golf this, given your return convention I think you could drop supporting .. Although since this is no longer a code-golf question, supporting the whole language may be more impressive.

@ØrjanJohansen, I can probably golf a thousand or so bytes off by switching to a different data generation method alone. Also, the self-interpreter isn't the smallest one I could write, as it supports negative cells.

This looks like it should win the bounty, but I want to take my time to understand it, not being a BF expert myself. Can you ping me if you don't hear back some time next week?

I confirm that this meets the spec, as far as I can tell. A bounty should be winging its way to you shortly. (There is a delay before the system will let me award it.) Thank you for the answer, it is much appreciated.

You may be interested in Muriel.

Lazy K, 5891 bytes
````ssk``s``si``s``si`ks``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`k
s``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk``s``
si`ks``s``si``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s``si``s``si`ks`ki`
`s``si`ks``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si
`ks``s``si`kk``s``si`ks``s``si``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s
``si`ks`ki`kk``s``si`kk`ki``s``si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si
`kk`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk
``s``si`ks`ki`kk``s``si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si``s``si`ks
``s``si`kk`ks``s``si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk`ks``s``si
``s``si`ks``s``si`kk``s``si`ks`ki`kk``s``si`kk``s``si``s``si`ks``s``si`kk`kk``s`
`si`ks``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks
``s``si`kk`kk``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk``s``si`ks
`ki`kk``s``si`kk`kk``s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s`
`si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si
`kk``s``si`ks`ki``s``si``s``si``s``si`ks`ks``s``si`ks``s``si``s``si`ks``s``si``s
``si`ks``s``si``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s``si`ks``s``si``
s``si`ks`ki`ki`kk``s``si`kk`ki``s``si`kk``s``si`kk``s``si`kk`ki``s``si`kk``s``si
`kk`ks``s``si`kk`kk``s``si`kk`kk``s``si``s``si`ks`ki`ki``s``si`kk`kk``s``si``s``
si`ks``s``si`kk`kk``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s`
`si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s
``si`ks``s``si`kk``s``si`ks``s``si`kk``s``si``s``si`ks``s``si`kk`kk``s``si``s``s
i`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk`kk`kk
``s``si``s``si`ks``s``si`kk``s``si`ks``s``si`kk``s``si`ks``s``si`kk``s``si``s``s
i`ks``s``si`kk``s``si`ks``s``si``s``si`ks`ki``s``si`kk``s``si``s``si``s``si`ks``
s``si``s``si``s``si`ks``s``si``s``si`ks`ki`ki``s``si``s``si`ks`ks`ks``s``si``s``
si`ks``s``si`kk`ks`kk``s``si``s``si`ks`ki``s``si``s``si`ks`ki`ki``s``si``s``si`k
s``s``si``s``si`ks``s``si`kk`ks`kk`ki`kk``s``si``s``si`ks``s``si``s``si`ks``s``s
i`kk`ks``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`k
k`kk``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk``s``si`ks``s``si`k
k``s``si``s``si`ks``s``si`kk`ks`kk``s``si``s``si`ks``s``si`kk``s``si`ks`ki`kk``s
``si`kk``s``si``s``si`ks``s``si`kk``s``si`ks`ki`kk``s``si`kk``s``si`kk``s``si``s
``si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks`ki``
s``si`kk``s``si`kk`ki``s``si`kk``s``si`kk``s``si`kk``s``si``s``si`ks`ki``s``si`k
k``s``si``s``si``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks`kk`ki``s``si``s``
si`ks``s``si`kk``s``si`ks`ks``s``si`ks``s``si``s``si`ks`ki``s``si``s``si`ks`ks``
s``si`kk`ki``s``si``s``si`ks`ks``s``si``s``si``s``si`ks`ks`ki``s``si``s``si`ks`k
s``s``si``s``si`ks`ks``s``si`kk`ki``s``si`kk``s``si`kk``s``si``s``si`ks`ki``s``s
i`kk``s``si``s``si`ks``s``si``s``si`ks`ki``s``si``s``si`ks`ks``s``si``s``si``s``
si`ks`ks`ki``s``si``s``si`ks`ks``s``si`kk`ki``s``si``s``si`ks`ks``s``si``s``si`k
s``s``si``s``si`ks`ks`ks``s``si``s``si``s``si`ks`ks`ki``s``si``s``si`ks`ks``s``s
i`kk`ki``s``si`kk``s``si``s``si`ks`ki``s``si`kk``s``si``s``si`ks``s``si``s``si`k
s``s``si``s``si``s``si`ks`ks`ki``s``si``s``si`ks`ks``s``si``s``si`ks`ks``s``si`k
k`ki`ks``s``si``s``si`ks``s``si``s``si`ks`ki``s``si``s``si`ks`ks``s``si``s``si``
s``si`ks`ks`ki``s``si``s``si`ks`ks``s``si`kk`ki``s``si``s``si``s``si`ks`ks``s``s
i``s``si`ks`ks`ki``s``si``s``si`ks`ks``s``si`kk`ki``s``si`kk``s``si``s``si`ks``s
``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``s
i`kk`ks``s``si``s``si`ks``s``si`kk``s``si`ks`ki``s``si``s``si`ks``s``si`kk`kk``s
``si``s``si`ks`ki``s``si`kk``s``si``s``si`ks``s``si`kk`ks`kk``s``si`kk`kk``s``si
`kk`ki``s``si`kk`ki``s``si`kk`ki``s``si`kk`ki``s``si`kk`ki``s``si`kk``s``si``s``
si``s``si`ks`ki``s``si`ks``s``si`kk``s``si``s``si`ks``s``si`kk``s``si`ks``s``si`
`s``si`ks`ki``s``si`kk``s``si``s``si``s``si`ks``s``si``s``si`ks`ki`ki``s``si``s`
`si`ks`ki`ki``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks`kk`ki`kk``s``si``s``
si`ks`ki`ki``s``si`kk``s``si`kk``s``si``s``si``s``si`ks`ki`ki``s``si``s``si`ks`k
i`ki``s``si`kk``s``si`kk``s``si`kk`ki``s``si``s``si`ks``s``si``s``si`ks``s``si`k
k`ks``s``si``s``si`ks``s``si`kk``s``si`ks`ki``s``si``s``si`ks``s``si`kk``s``si`k
s``s``si``s``si`ks`ki``s``si``s``si`ks``s``si``s``si`ks`ki``s``si``s``si`ks``s``
si``s``si`ks`ki``s``si`kk`ks``s``si`kk`ks``s``si`kk`kk``s``si``s``si`ks``s``si``
s``si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks`ki`
`s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si
``s``si`ks``s``si`kk`ks``s``si``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk
`ks``s``si``s``si`ks``s``si`kk``s``si`ks``s``si`kk``s``si``s``si`ks``s``si`kk``s
``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk``s``si`ks``s``si`kk`kk``s``si``s
``si`ks``s``si`kk``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s``si`kk``s``si`ks``s
``si`kk`kk``s``si``s``si`ks``s``si`kk``s``si`ks``s``si`kk`kk``s``si``s``si`ks``s
``si`kk`ks``s``si``s``si`ks``s``si`kk``s``si`ks`ki``s``si``s``si`ks``s``si`kk``s
``si`ks``s``si``s``si`ks`ki``s``si`kk`ks``s``si`ks``s``si``s``si`ks`ki``s``si``s
``si`ks``s``si``s``si`ks`ki``s``si`kk`ks``s``si`kk`ki``s``si``s``si`ks``s``si`kk
``s``si`ks`ki`kk``s``si`kk``s``si``s``si`ks``s``si`kk``s``si`ks`ki`kk``s``si`kk`
`s``si`kk``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks``s``si``s``si`ks``s
``si``s``si`ks`ki``s``si`kk``s``si`kk`ki``s``si`kk``s``si`kk``s``si`kk``s``si``s
``si`ks`ki``s``si`kk`ks``s``si`kk``s``si`kk``s``si``s``si`ks`ki``s``si`kk`ki``s`
`si`kk``s``si``s``si`ks`ki``s``si`kk`kk``s``si`kk``s``si``s``si`ks``s``si`kk``s`
`si`ks``s``si``s``si`ks`ki``s``si`kk`kk`kk``s``si`kk`ki``s``si`kk`ki``s``si`kk`k
i``s``si`kk`ki``s``si`kk`ki``s``si`kk``s``si`kk`kii

Line breaks added for clarity.
This program is written in, and is capable of parsing, only the Unlambda-syntax subset of Lazy K; that is:
program ::= "s" | "k" | "i" | "`" program program.

It expects input to be encoded in the standard format for Lazy K: an input stream is a pair whose first element is a Church numeral, representing the first byte of the stream, and whose second element is the remaining input stream. However, the output is expected to be only a single Church numeral rather than a full output stream.
The parsing part
If we look at the character codes for the relevant bits of Lazy K syntax, we notice something interesting:

s is 115, or 1 mod 6;
k is 107, or 5 mod 6;
i is 105, or 3 mod 6;
` is 96, or 0 mod 6.

If we assume the input program is part of the relevant subset, we can distinguish application using only a parity test, and then distinguish the combinators from each other using remainder mod 3.
Doing these tests effectively in combinatory logic requires a little cleverness, though.

mod 2: the idea is to find terms a, b, and f such that f a = b and f b = a, and then call N f a and examine the result. Traditionally the Church booleans are used for a and b and f is not, but not is annoyingly difficult to encode in SKI. Instead, I did an automated search for terms that would work, and it came up with this:

S I K I     = I (K I)       = K I;
S I K (K I) = K I (K (K I)) = I.

mod 3: similarly, we find distinct terms a, b, c, f with f a = b, f b = c, f c = a. A search yielded:

S (S I I) K I         = I I (K I)                 = K I;
S (S I I) K (K I)     = K I (K I) (K (K I))       = K (K I);
S (S I I) K (K (K I)) = K (K I) (K (K I)) (K ...) = I.

Given these, we can write a fairly conventional recursive-descent parser:
parse : stream -> (term, stream)
parse (c, rest) =
  match (c mod 2)

    0 -> let (f, rest') = parse rest
         let (x, rest'') = parse rest'
         (f x, rest'')

    1 -> ((match (c mod 3)
           0 -> I
           1 -> S
           2 -> K), rest)

The quining part
This is the fun part. One of the most important parts of any quine is figuring out a data format to represent the encoded form of the program. This ends up being the largest source of overhead since it essentially multiplies the program's length.
The representation I went with involves a lambda that substitutes its argument for every application in the encoded term, but leaves combinators unchanged. For example, the SKI-term (S S) (K I) would be encoded as:
λf. f (f S S) (f K I)

In terms of SKI, the encoding looks like this:
encode(S) = (K S)
encode(K) = (K K)
encode(I) = (I I)
encode(f x) = S (S I (encode(f))) (encode(x))

This encoding introduces 3x overhead for combinators and 7x overhead for applications. There are about half many applications as combinators in any Lazy K term, so this encoding has ~5x overhead. There are other encodings which are more efficient than this. For example, @msullivan's quine uses a representation which exploits the fact that top-level terms are applied together to have just 1.5x overhead. However, this approach has several disadvantages. It supports only the S and K combinators, making the body of the quine more verbose. It relies on going outside of the Unlambda subset of the syntax, so I would need to make the parser more complex. Finally, it lacks a very useful feature of my representation: it can be trivially "interpreted" into the term it represents by passing I as the argument, avoiding the need to store both the encoded and decoded form of the quine payload. Nevertheless, the savings from using a more efficient representation like this are so large that it would probably be worth doing.
Finally there is the task of stringifying the encoded quine to obtain the source code and passing it to the parsed input term. For this we need to construct the Church numerals 96, 105, 107, and 115. For golfing purposes I was able to find terms which are much more efficient than the constructions given in the standard library: 96 is reduced from 63 bytes to 45, 105 is reduced from 81 bytes to 49, 107 is reduced from 91 bytes to 65, and 115 is reduced from 89 bytes to 55. I obtained these using alternative representation of numbers which can be easily converted to and from Church numerals. This representation admits much more compact definitions of succ and +, and only slightly less compact definitions of * and ^.
Also, there is the problem of traversing the encoded form of the program to build up the stringified form. For this, we effectively need f x y to be able to distinguish the cases when its arguments are combinators and when its arguments are further applications of f. We accomplish this using a helper function:
helper(x) = x (K I) (K (K (λt. t foo))) (K (λt. t baz)) (λt. t bar) t

This evaluates to t foo, t bar, and t baz when passed S, K, and I as arguments respectively, but you can also pass (λ a b c d e. something else) to distinguish applications. This kind of function is unfortunately relatively cumbersome when encoded in SKI, but I haven't found anything better. We use a difference list to accumulate the stringified representations, since it makes it very cheap to append (just function composition) and doesn't require modification to work with infinite streams.
Further golfing
How to improve this:

Use a better data representation, even though this comes at the cost of easy interpretation.
Find a more efficient way to distinguish the S, K, and I combinators. If a better way exists, it's too large for my search program to find it as-is, so I would need to make it more efficient somehow or make assumptions to reduce the search space.
Find more efficient representations of each of the numbers. 96 in particular feels like it could be improved a lot, although it's probably also too large for the search program.
Better optimize parse, since it has some room for improvement.

The Lazier code used to generate this program can be found here.

This is a great answer! Another user has posted a bounty to reward it, which I'm very happy about.


text:
Pack sequences of non-negative integers
Let N be the set of nonnegative integers, i.e. {0, 1, 2, 3, ...}.
Let c0(N) be the set of all infinite sequences in N that converge to 0, i.e. { (xn) ∈ NN | xn → 0 as n → ∞}.
c0(N) can be equivalently written as the set of all finite sequences of natural numbers, such that there are no trailing zeroes. The infinite sequence of all zeroes (corresponding to a finite sequence of length 0) is an element of c0(N).
Your task is to implement a bijection in your language between N and c0(N), in as few characters as possible. This means every number in N corresponds to a unique item of c0(N), and vice versa. Do this by defining two functions: f, going from N and c0(N); and g, the inverse of f. The length in bytes of these two definitions is your score.
You may use the largest internal integer and list types of your language, even if they aren't bignums or capable of handling infinite length. However, they should theoretically still be able to terminate with the right answer if the language was modified with a suitable bignum or lazy/infinite list type.
Some suggestions for ways to pack are below. Note that these aren't quite solutions yet and could need some tweaking to work; they're mostly to get the blood flowing.

f(1463616) = f(2^6 * 3^3 * 5^0 * 7^1 * 11^2) = [6, 3, 0, 1, 2] - Factorize the number into primes and read off exponents to get the sequence.
f(64971) = f(0b1111110111001011) = [6, 3, 0, 1, 2] - Expand the number in binary and use 0 as a separator to read strings of ones, representing the sequence in unary.

While this is a code-golf and the shortest answer will win, creative and interesting solutions are encouraged and may be subject to a bounty.

You must mean “positive” — it is simpler, by the way. The integer 0 is negative.

@NicolasBarbulesco In maths Zero is not positive or negative. That's why there is a difference between "positive" (excluding zero) and nonnegative (including zero.) Some floating point representations allow for a "postive zero and negative zero" which, while mathematically incorrect, can be convenient in programming for avoiding loss of information in certain cases.

@steveverrill — Not “in maths”. In the maths I learnt (in France), zero is positive and negative. -0 = +0 = 0. ℤ₊ is the set of positive integers, and ℤ₋ is the set of negative integers. To exclude 0, we say strictly positive (ℤ₊*) or strictly negative (ℤ₋*). This is simple, and logical. And this makes many theorems work. In the UK, I have encountered your conception of things, and the convoluted vocabulary it needs.

@NicolasBarbulesco: In none of the four languages I read have I ever seen this definition of positivity. While I agree that the French definition might be simpler (for monotone functions, I prefer increasing and strictly increasing to non-decreasing and increasing as well), it's certainly not commonplace.

GolfScript, 41 bytes
{[2base[0]/{,}/]-1%}:f{:|;-1{).f|=!}do}:g

Function “f”
[
  2base       # Push the digits of the argument in base 2.
  [0]/        # Split the digits around the 0's. This leaves sequences of 1's.
  {,}/        # Compute the lengths of those sequences.
]-1%          # Reverse the array of the lengths.

The binary expansion of any given non-negative integer in its canonical form may have trailing 0's, but not leading 0's.
Thus, reversing the array is necessary and sufficient to comply with the specification.
Function “g”
:|;           # Save the argument in variable “|” and pop it from the stack.
-1            # Push the integer “-1”.
{             #
  )           # Increment the integer.
  .f|=        # Check whether it is the preimage of “|”.
  !           # If it is not,
}do           # repeat the loop.

Function “g” (alternative)
An alternative, straightforward and efficient implementation of g is
{[-1%{0\{1}*}/]2base}:g

The brute-force approach is much slower, but it is four bytes shorter.
[
  -1%         # Reverse the order of the integer sequence.
  {           # For each integer “N”,
    0         # push 0,
    \{1}*     # followed by “N” 1's.
  }/          #
]             # Convert this bit sequence into an array.
2base         # Convert the array into an integer.

Example

1250 is 10011100010 in base 2.
The lengths of the sequences of consecutive 1's are 1,0,3,0,0,1,0.
Thus, the sequence corresponding to 1250 is 0,1,0,0,3,0,1.

Proof of work
10000,(;      # Push an array of all integers from 1 to 9999.
{             # For each integer “N”,
  f-1=0=      # if “f(N)” has a trailing zero,
  {0p}*       # print a message.
}/

leaves nothing on the stack, so f is well-defined.
1000,.        # Push the array of all integers from 0 to 999 and duplicate it.
[             #
  {f g}/      # For each integer “N”, push “g(f(N))”.
]=            # Check if the array of the images matches the original array.

leaves 1 on the stack (using either definition of g).
This means that g is a left inverse of f, so f is injective.
[
  1000,.      # Push the array of all integers from 0 to 999 and duplicate it.
  10%-        # Remove the integers with trailing 0's.
  {           # For each integer “N”,
    10base    # push the array of its digits in base 10,
    .0\+.0\+  # and create copies with one and two leading 0's.
  }/          #
].            # Collect all sequences in an array and duplicate it.
[             #
  {g f}/      # For each sequence “S”, push “f(g(S))”.
]=            # Check if the array of the images matches the original array.

leaves 1 on the stack (using the second definition of g).
This means that g is a right inverse of f, so f is surjective.

Would it save a character to define f inside g, like {:|;-1{).{[2base[0]/{,}/]-1%}:f|=!}do}:g?

Sadly, that won't work. Inside g, the block defining f is pushed on the stack, but it doesn't get executed. You'd need to append ~ to :f to fix this. Also, f won't be defined until g has been executed at least once.

J - 17 char
g=:(f=:_ q:>:)inv

We implement the prime exponent idea with this bijection—that's what the _ q: is doing, getting a list of the exponents of the primes of a number—except we also increment the input number by one before doing so, with >:, so that we don't forget 0, who doesn't have its own prime factorization.
For the definition of g, it's exactly what it looks like: instead of writing it ourselves, we just tell J to take the inverse of f. Arguably this is cheating, or just not interesting, but I think that the ability to do this is what makes J such an interesting language: J can often figure things out for you, allowing you to focus on expressing your solution instead of implementing it.
   i. 20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
   f i. 20  NB. J pads with zeroes on right
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
2 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
1 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
3 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0
2 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0
1 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0
4 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
1 2 0 0 0 0 0 0
0 0 0 0 0 0 0 1
2 0 1 0 0 0 0 0
   g f i. 20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Proving that this is a bijection is straightforward: the injectivity of this f is a well known fact and, if you assume that J's automagical inverse is correct (which it is), then this is trivial.
If you don't want to take it on faith that J knows how to take the inverse of f, we can inspect its automatic inverse for _&q::
   _&q: b. _1
(p:@i.@# */ .^ ])"1 :.(_&q:)

and then check the definition:
(p:@i.@# */ .^ ])"1 :.(_&q:)  NB. the alleged inverse of _&q:
                    :.(_&q:)  NB. defining _&q:inv inv to be _&q:
(               )"1           NB. operate on rows of the argument
       #                      NB. length of argument
    i.@                       NB. nonnegative integers less than
 p:@                          NB. n-th prime for each integer n
               ]              NB. the argument again
            .^                NB. pointwise exponentiation
         */                   NB. product

and then confirm that J's inverse of f gives the decrement of the result of this:
   >: b. _1  NB. inverse of increment is decrement
<:
   f b. _1   NB. ([: f g) is one way of writing f composed with g
[: <: (p:@i.@# */ .^ ])"1 :.(_&q:)

Function inverse as a built-in. I'm speechless.

@Dennis J can also take derivatives.

Jelly, 7 + 3 = 10 or 11 bytes, language postdates question
JÆN*¹P’
‘ÆE

Try it online!
Defines an packing function 1Ŀ and an unpacking function 2Ŀ. These could be defined in two separate programs, but if you define them both in a single program, you need a newline to separate the definitions. Thus I'm not 100% sure how to count it.
Explanation
This packs the sequence into a product of primes, which was one of the suggestions in the question.
Packing
JÆN*¹P’
J         Replace each element of {the input} by its index
 ÆN       Replace each index n by the nth prime number
   *      Raise each element to the power of
    ¹       {the original input}
     P    Take the product of all the elements
      ’   Subtract 1 (so that some sequence maps to 0, making a bijection)

Unpacking
‘ÆE
‘         Add 1 (undo the subtraction earlier)
 ÆE       Output the number of times each prime divides the current value

As can be seen, unpacking is very simple here due to the builtin ÆE, which is why I selected this format. There's no builtin to do the packing, but it has a fairly terse implementation too.
Jelly, 3 + 3 = 6 or 7 bytes, with some help from @Dennis
OK, apparently there is a builtin to do the packing…
ÆẸ’
‘ÆE

Try it online!
The explanation above still works; it's just that all of JÆN*¹P have been replaced by a builtin.

Jelly fact: This challenge is why those built-ins exist in the first place.

Oh, hmm, in that case this answer probably violates a standard loophole (unintentionally). Postdated languages are fair enough, but languages features that were added for a challenge are invalid. (ÆE is useful for other things, though; however, I'm not sure ÆẸ is.)

Considering that you couldn't have possibly known this, there is no problem. Most built-ins of golfing languages were inspired by older challenges.

Right, but I was going along the lines of "if I see lots of challenges where a particular builtin helps, that builtin will likely come in useful in the future". For example, A Pear Tree's checksums were inspired by several specific past challenges, but I had a hunch that they'd come in useful on future challenges too, so they did. I haven't gone back to those past challenges and submitted A Pear Tree answers, though, because that would likely be cheating.

It's not that ÆE isn't used in other challenges; I've used it plenty of times. But every since I saw the OP's answer to this challenge, I knew that if I ever made a language, it would include this built-in. In any case, the loophole exists to prevent people from making up a language to win every challenge. Posting the answer myself woyld have been a bit iffy, but since you discovered a general-purpose built-in that happens to work particularly well for this challenge, it's fine.

Python, 257 265B
from itertools import*
T=lambda i:[list(a)for l in range(i)for a in product(range(i-l+3),repeat=l+1)if a[-1]>0and sum(a)==i-l]
def f(N):
 A,i=[[0]],0
 while len(A)<=N:A+=T(i);i+=1
 return A[N]
def g(t):
 A,i=[[0]],0
 while t not in A:A+=T(i);i+=1
 return A.index(t)

To list every sequence, for each integer i, for each length l

0 :  1
1 :  2
2 :  0 1
3 :  3
4 :  0 2
5 :  1 1
6 :  0 0 1
7 :  4
8 :  0 3
9 :  1 2
10 :  2 1
11 :  0 0 2
12 :  0 1 1
13 :  1 0 1
14 :  0 0 0 1
15 :  5
16 :  0 4
17 :  1 3
18 :  2 2
19 :  3 1
20 :  0 0 3
21 :  0 1 2
22 :  0 2 1
23 :  1 0 2
24 :  1 1 1
25 :  2 0 1
26 :  0 0 0 2
27 :  0 0 1 1
28 :  0 1 0 1
29 :  1 0 0 1
30 :  0 0 0 0 1

so f(256)=[9], and g([4,2,0,3])=2254. NB that this is SLOW for large numbers.

This answer is not quite right: in this question we consider 0 an element of N, so you have to account for the empty sequence and non-trailing zeroes in the sequences. Perhaps map 0 to [] and subtract one from every element except the last in the result of f?

Oh yes I can do - sorry at uni N always meant N+ and we wrote Nu{0} for that so i was on autopilot. it'll actually save me a few digits when i get round to fixing it

MATL, 8+3 = 11 bytes
Function f
QYF

Nice and simple, outputs the exponents of the prime factor decomposition of the input+1, for instance input of 1752922079 gives [5, 3, 1, 4, 0, 2]
Function g
Takes a finite vector of non-negative integers and outputs a single non-negative integer.
n:YqG^pq

Explanation
n       % find the length of the input
:       % make a range that long
Yq      % use the range to find the first n primes
G       % paste the input vector again
^       % take powers element wise
p       % product of elements
q       % decrement by 1 so 0 is included
        % (implicit) convert to string and display

For instance, input [5, 3, 1, 4, 0, 2] first pushes the vector [2, 3, 5, 7, 11, 13], then combines them into [32, 27, 5, 2401, 1, 169] before taking the product, giving 1752922080 and decrementing to give the final answer 1752922079.

The question asks for the functions to be defined, that is, assigned to some variable or name in the function namespace. (Preferably called f and g but some languages cough Jelly cough can't do the usual names.) I don't know how MATL works, but it doesn't look like this answer has done that.

@algorithmshark Oh! Sorry about that... You're right, this answer hasn't done that - and to be honest I don't know if MATL allows it. I suspect not, since matlab functions must be defined in their own, separate, file and I don't know of support for anonymous functions in MATL.

source: Stack Exchange

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

sort: votes


text:
Count the terminal cycles of a directed graph
Task
You must write a program or function in the language of your choice which accurately counts the number of terminal cycles of a simple directed graph.
This particular kind of directed graph is represented as an array of n integers, each with an independently-chosen random value between 1 and n (or 0 and n-1, if your language counts from 0).  The graph can be thought of as arrows pointing from one index (node) to an index which matches the value found at the starting index.
Your function must be capable of accepting large graphs, up to n=1024, or any smaller integer size.
Example
Consider this graph for n=10:
[9, 7, 8, 10, 2, 6, 3, 10, 6, 8]

Index 1 contains a 9, so there's an arrow from index 1 to index 9.  Index 9 contains a 6, so there's an arrow 9 -> 6.  Index 6 contains 6, which is a terminal cycle, pointing back to itself.
Index 2 contains a 7.  Index 7 contains a 3.  Index 3 contains an 8.  Index 8 contains a 10.  Index 10 contains an 8, so that's a second terminal cycle (8 -> 10 -> 8 -> 10, etc.).
Index 4 -> 10, which enters the second terminal cycle.  Likewise, index 5 -> 2 -> 7 -> 3 -> 8, which is also part of the second terminal cycle.
At this point, all indices (nodes) have been checked, all paths have been followed, and two unique terminal cycles are identified.  Therefore, the function should return 2, since that is the number of terminal cycles in this directed graph.
Scoring
Aim for the smallest code, but make sure it counts terminal cycles correctly.  Shortest code after 1 week wins.
Test Cases
Here's are some test cases to check the correctness of your code.  If your language counts array indices starting from 0, you must of course subtract 1 from the value of each array element, to prevent an out-of-bound index.
n=32, 5 cycles:
[8, 28, 14, 8, 2, 1, 13, 15, 30, 17, 9, 8, 18, 19, 30, 3, 8, 25, 23, 12, 6, 7, 19, 24, 17, 7, 21, 20, 29, 15, 32, 32]

n=32, 4 cycles:
[20, 31, 3, 18, 18, 18, 8, 12, 25, 10, 10, 19, 3, 9, 18, 1, 13, 5, 18, 23, 20, 26, 16, 22, 4, 16, 19, 31, 21, 32, 15, 22]

n=32, 3 cycles:
[28, 13, 17, 14, 4, 31, 11, 4, 22, 6, 32, 1, 13, 15, 7, 19, 10, 28, 9, 22, 5, 26, 17, 8, 6, 13, 7, 10, 9, 30, 23, 25]

n=32, 2 cycles:
[25, 23, 22, 6, 24, 3, 1, 21, 6, 18, 20, 4, 8, 5, 16, 10, 15, 32, 26, 25, 27, 14, 13, 12, 9, 9, 29, 8, 13, 31, 32, 1]

n=32, 1 cycle:
[6, 21, 15, 14, 22, 12, 5, 32, 29, 3, 22, 23, 6, 16, 20, 2, 16, 25, 9, 22, 13, 2, 19, 20, 26, 19, 32, 3, 32, 19, 28, 16]

n=32, 1 cycle:
[8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 1, 2, 3, 4, 5, 6, 7]

n=1024, 6 cycles:
[239, 631, 200, 595, 178, 428, 582, 191, 230, 551, 223, 61, 564, 463, 568, 527, 143, 403, 154, 236, 928, 650, 14, 931, 236, 170, 910, 782, 861, 464, 378, 748, 468, 779, 440, 396, 467, 630, 451, 130, 694, 167, 594, 115, 671, 853, 612, 238, 464, 771, 825, 471, 167, 653, 561, 337, 585, 986, 79, 506, 192, 873, 184, 617, 4, 259, 4, 662, 623, 694, 859, 6, 346, 431, 181, 703, 823, 140, 635, 90, 559, 689, 118, 117, 130, 248, 931, 767, 840, 158, 696, 275, 610, 217, 989, 640, 363, 91, 129, 399, 105, 770, 870, 800, 429, 473, 119, 908, 481, 337, 504, 45, 1011, 684, 306, 126, 215, 729, 771, 5, 302, 992, 380, 824, 868, 205, 807, 917, 407, 759, 181, 640, 685, 795, 258, 180, 900, 20, 773, 546, 866, 564, 761, 632, 895, 968, 980, 651, 225, 676, 18, 685, 784, 208, 227, 3, 267, 852, 57, 487, 566, 633, 849, 309, 543, 145, 575, 811, 621, 560, 492, 24, 665, 66, 851, 168, 262, 259, 754, 481, 565, 768, 172, 1012, 241, 3, 370, 985, 389, 82, 779, 744, 829, 836, 249, 975, 909, 840, 226, 867, 499, 192, 909, 972, 735, 252, 785, 545, 486, 186, 1011, 89, 939, 649, 110, 119, 185, 836, 717, 545, 938, 621, 946, 94, 363, 721, 177, 747, 59, 819, 146, 283, 821, 547, 654, 941, 755, 18, 449, 367, 499, 944, 62, 553, 435, 344, 900, 25, 251, 920, 902, 99, 326, 98, 495, 385, 929, 865, 327, 725, 674, 33, 173, 429, 873, 558, 90, 460, 366, 543, 583, 954, 792, 213, 536, 670, 49, 738, 802, 1015, 23, 915, 119, 263, 307, 601, 474, 971, 826, 613, 446, 37, 145, 894, 901, 307, 906, 886, 990, 89, 798, 384, 487, 822, 354, 768, 902, 163, 179, 134, 920, 439, 619, 215, 94, 709, 744, 366, 543, 349, 347, 2, 438, 141, 486, 19, 998, 500, 857, 955, 932, 1, 587, 195, 646, 550, 887, 626, 400, 348, 154, 808, 678, 873, 186, 282, 168, 993, 722, 56, 345, 5, 226, 328, 22, 894, 658, 264, 13, 803, 791, 359, 217, 997, 168, 578, 952, 734, 964, 898, 659, 628, 980, 15, 31, 439, 13, 875, 687, 1004, 1023, 165, 642, 561, 897, 711, 124, 404, 346, 723, 774, 352, 784, 276, 395, 14, 443, 343, 153, 510, 590, 172, 215, 130, 106, 295, 906, 133, 758, 483, 898, 391, 760, 702, 972, 721, 611, 592, 1001, 724, 934, 59, 831, 171, 253, 869, 431, 538, 20, 648, 76, 351, 103, 33, 385, 852, 437, 470, 95, 434, 408, 430, 994, 366, 706, 809, 532, 161, 388, 668, 245, 965, 365, 913, 471, 927, 245, 256, 805, 540, 380, 995, 446, 657, 545, 573, 955, 499, 322, 949, 635, 401, 185, 421, 626, 534, 429, 930, 633, 563, 348, 626, 518, 682, 233, 775, 444, 42, 199, 57, 271, 683, 397, 883, 620, 768, 8, 331, 497, 19, 340, 900, 919, 497, 276, 78, 252, 164, 764, 927, 242, 270, 759, 824, 945, 886, 262, 59, 439, 217, 720, 519, 862, 626, 326, 339, 589, 16, 565, 947, 604, 144, 87, 520, 256, 240, 336, 685, 361, 998, 805, 678, 24, 980, 203, 818, 855, 85, 276, 822, 183, 266, 347, 8, 663, 620, 147, 189, 497, 128, 357, 855, 507, 275, 420, 755, 131, 469, 672, 926, 859, 156, 127, 986, 489, 803, 433, 622, 951, 83, 862, 108, 192, 167, 862, 242, 519, 574, 358, 549, 119, 630, 60, 925, 414, 479, 330, 927, 94, 767, 562, 919, 1011, 999, 908, 113, 932, 632, 403, 309, 838, 341, 179, 708, 847, 472, 907, 537, 516, 992, 944, 615, 778, 801, 413, 653, 690, 393, 452, 394, 596, 545, 591, 136, 109, 942, 546, 57, 626, 61, 587, 862, 829, 988, 965, 781, 849, 843, 815, 60, 928, 784, 388, 341, 491, 565, 83, 110, 164, 38, 1024, 859, 297, 520, 327, 733, 699, 631, 78, 178, 671, 895, 818, 637, 99, 425, 933, 248, 299, 333, 144, 323, 105, 849, 942, 767, 265, 72, 204, 547, 934, 916, 304, 919, 273, 396, 665, 452, 423, 471, 641, 675, 60, 388, 97, 963, 902, 321, 826, 476, 782, 723, 99, 735, 893, 565, 175, 141, 70, 918, 659, 935, 492, 751, 261, 362, 849, 593, 924, 590, 982, 876, 73, 993, 767, 441, 70, 875, 640, 567, 920, 321, 46, 938, 377, 905, 303, 736, 182, 626, 899, 512, 894, 744, 254, 984, 325, 694, 6, 367, 532, 432, 133, 938, 74, 967, 725, 87, 502, 946, 708, 122, 887, 256, 595, 169, 101, 828, 696, 897, 961, 376, 910, 82, 144, 967, 885, 89, 114, 215, 187, 38, 873, 125, 522, 884, 947, 962, 45, 585, 644, 476, 710, 839, 486, 634, 431, 475, 979, 877, 18, 226, 656, 573, 3, 29, 743, 508, 544, 252, 254, 388, 873, 70, 640, 918, 93, 508, 853, 609, 333, 378, 172, 875, 617, 167, 771, 375, 503, 221, 624, 67, 655, 465, 272, 278, 161, 840, 52, 1016, 909, 567, 544, 234, 339, 463, 621, 951, 962, 1019, 383, 523, 279, 780, 838, 984, 999, 29, 897, 564, 762, 753, 393, 205, 31, 150, 490, 156, 796, 586, 676, 773, 465, 489, 1024, 433, 214, 701, 480, 604, 280, 241, 563, 943, 911, 12, 400, 261, 883, 999, 207, 618, 141, 959, 767, 978, 461, 992, 982, 272, 143, 404, 645, 331, 348, 783, 698, 827, 82, 145, 536, 449, 852, 750, 789, 413, 913, 420, 14, 499, 285, 533, 223, 75, 591, 994, 884, 237, 63, 411, 563, 611, 801, 173, 759, 278, 318, 772, 1018, 48, 440, 333, 611, 834, 423, 583, 22, 716, 393, 794, 83, 83, 864, 859, 600, 525, 808, 569, 95, 952, 852, 567, 651, 2, 984, 906, 992, 747, 602, 143, 547, 1008, 940, 245, 633, 378, 193, 771, 965, 648, 437, 873, 591, 664, 271, 777, 274, 742, 68, 429, 825, 144, 55, 272, 279, 6, 400, 485, 66, 311, 663, 441, 23, 988, 726, 48, 624, 302, 617, 120, 653, 810, 641, 142]

Sure, here's a big fat n=1024 test case.  Hopefully I didn't butcher it while packaging it for Stack Exchange.

Clarify: If the language uses zero-based arrays, then the numbers in the array will all be zero-based, or not?

Yes, that's correct.  The numbers in the array will always point to a valid array index.  I used the 'human style' counting method of starting from 1 because that's what my language uses, and I didn't want to screw up my examples.

GolfScript, 25 characters
:I{{I=.}I.+,*]I,>$0=}%.&,

Same approach as Keith Randall's solution but in GolfScript. Note that GolfScript has zero-indexed arrays. Online tester.
:I        # Assign input to variable I
{         # Foreach item in I
  {I=.}   # Code block: take the n-th list item
  I.+,*   # Iterate the code block 2*len(I) times
  ]       # and gather result in an array
  I,>     # Take last len(I) items
  $0=     # Get minimum
}%
.&        # Take unique items
,         # Count

Hard to believe so much is accomplished with so little code.

That's impressively short.

Mathematica 69
Code
This finds the number of graph components.
f@l_ := Length@WeaklyConnectedComponents@Graph@Thread[Range@Length@l -> l]

The first test case:
v = {8, 28, 14, 8, 2, 1, 13, 15, 30, 17, 9, 8, 18, 19, 30, 3, 8, 25, 23, 12, 6, 7, 19, 24, 17, 7, 21, 20, 29, 15, 32, 32}
f[v]

5

Analysis
Make a list of directed edges between indices, (using example 1).
Thread[Range@Length@v -> v

{1 -> 8, 2 -> 28, 3 -> 14, 4 -> 8, 5 -> 2, 6 -> 1, 7 -> 13, 8 -> 15,
   9 -> 30, 10 -> 17, 11 -> 9, 12 -> 8,
  13 -> 18, 14 -> 19, 15 -> 30,
   16 -> 3, 17 -> 8, 18 -> 25, 19 -> 23, 20 -> 12, 21 -> 6, 22 -> 7,
   23 -> 19, 24 -> 24, 25 -> 17, 26 -> 7, 27 -> 21, 28 -> 20, 29 -> 29,
   30 -> 15, 31 -> 32, 32 -> 32}

Graph draws a graph showing the graph components.
ImagePadding and VertexLabels
are used here to show the indices.
Graph[Thread[Range[Length@v] -> v], ImagePadding -> 30, VertexLabels -> "Name"]

WeaklyConnectedComponents returns the list of vertices for each component.
Length returns the number of components.
c = WeaklyConnectedComponents[g]
Length[c]

{{17, 10, 25, 8, 18, 1, 4, 12, 15, 13, 6, 20, 30, 7, 21, 28, 9, 22,
    26, 27, 2, 11, 5}, {14, 3, 19, 16, 23}, {32, 31}, {24}, {29}}
5

Timing of sample list with 1024 elements:
Timing:  0.002015 sec
f[z] // AbsoluteTiming

{0.002015, 6}

Just for fun, here's a picture of the final test case, graphed.  I omitted the vertex labels; there are too many.
Graph[Thread[Range[Length@z] -> z], GraphLayout -> "RadialEmbedding"]

Very concise, despite the 25-character function name.  This may prove hard to beat.  Also, it looks rather like a Choose Your Own Adventure story.

WeaklyConnectedComponents is very verbose.  But it does a lot of work.  (One should never underestimate J and similar languages for conciseness.  )

At some point, I suspect Wolfram will run out of ideas and just start turning Stack Exchange answers into library functions, is order to justify new releases.

Yes, I see what you mean.  There are literally thousands of functions built into Mathematica at present.  What's strange is that they work together so well.

That initial framework of expression-rewriting was a damned good idea.  Now if only they'd implement multiple levels of undo...

One may save 11 bytes with Tr[EdgeCycleMatrix@Graph@Thread[Range@Length@l->l]!] to count the cycles. Also, the Graph@ can be omitted to save 6 more bytes, but I don't remember if this was already the case in 2014.

Python, 132 116 chars
def T(V):
 n=len(V);r=range(n);s={}
 for i in r:
    p=[i]
    for k in r+r:p+=[V[p[-1]]]
    s[min(p[n:])]=1
 return len(s)

For each index, we follows edges for n hops, which guarantees we are in a terminal cycle.  We then follow n more hops and find the minimum index in that cycle.  The total number of terminal cycles is then just the number of different minima we find.

I like this method.  Perhaps there's a way to combine 'i in r' loops?

Sad that you can't #define F for i in r in Python, C(++)-style... :)

In Python:
def c(l):
    if(l==[]):
        return 0
    elif (l[-1]==len(l)):
        return c(l[:-1])+1
    else:
        return c([[x,l[-1]][x==len(l)] for x in l[:-1]])

This is code-golf. Please add the number of bytes in your submission. You might want to remove unnecessary whitespace.

As well as unnecessary parentheses. They are not needed in the if conditions.

c=lambda l:0 if l==[] else c(l[:-1])+1 if l[-1]==len(l) else c([[x,l[-1]][x==len(l)] for x in l[:-1]]) is better: 102 bytes.

J - 61 53 char
This one was a doozy.
#@([:#/.~[:+./ .*"1/~@e.<~.@(],;@:{~)^:_&.>])@:(<@<:)

The <@<: turn the list into a J graph, which looks like a list of boxes, and the box at index i contains all the nodes that node i connects to. J indexes from zero, so we use <: to decrement everything by one before boxing with <.
   (<@<:) 9 7 8 10 2 6 3 10 6 8
+-+-+-+-+-+-+-+-+-+-+
|8|6|7|9|1|5|2|9|5|7|
+-+-+-+-+-+-+-+-+-+-+

The <~.@(],;@:{~)^:_&.>] turns each node into a list of all the nodes that can be reached from it. The <...&.>] is responsible for making this happen to each node, and the ~.@(],;@:{~)^:_ actually comes from a J golf of this 'nodes reachable' task I did a couple of weeks ago.
   (<~.@(],;@:{~)^:_&.>])@:(<@<:) 9 7 8 10 2 6 3 10 6 8
+---+-------+---+---+---------+-+-----+---+-+---+
|8 5|6 2 7 9|7 9|9 7|1 6 2 7 9|5|2 7 9|9 7|5|7 9|
+---+-------+---+---+---------+-+-----+---+-+---+

e. performs an interesting task. If the "reachability" closure of the graph (the version of the graph such that if there are directed edges X→Y and Y→Z we add the edge X→Z.) has N nodes and E edges, then e. on this graph makes a boolean matrix of N rows and E columns, with a True if the corresponding node shares a reachable node with this edge. Confusing, but bear with me.
   ([:e.<~.@(],;@:{~)^:_&.>])@:(<@<:) 9 7 8 10 2 6 3 10 6 8
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1
0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1
0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1
0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1

Next, we have to find the number of terminal cycles, i.e. the number of groups that share Trues amongst their columns. We want to make sort of a multiplication table of the rows ("1/~), and we use a kind of inner product as the multiplication, one that ANDs pairwise and then ORs all the results together (+./ .*). The resulting matrix is a square table with a True in each position that two rows share at least one column between them.
   ([:+./ .*"1/~@e.<~.@(],;@:{~)^:_&.>])@:(<@<:) 9 7 8 10 2 6 3 10 6 8
1 0 0 0 0 1 0 0 1 0
0 1 1 1 1 0 1 1 0 1
0 1 1 1 1 0 1 1 0 1
0 1 1 1 1 0 1 1 0 1
0 1 1 1 1 0 1 1 0 1
1 0 0 0 0 1 0 0 1 0
0 1 1 1 1 0 1 1 0 1
0 1 1 1 1 0 1 1 0 1
1 0 0 0 0 1 0 0 1 0
0 1 1 1 1 0 1 1 0 1

Now all that's left to do is to check how many different kinds of row patterns there are. So we do exactly that: group together rows of the same kind (/.~), report the number in each group (#), and then take the number of groups (#@).
   #@([:#/.~[:+./ .*"1/~@e.<~.@(],;@:{~)^:_&.>])@:(<@<:) 9 7 8 10 2 6 3 10 6 8
2

Usage on other examples:
   tcc =: #@([:#/.~[:+./ .*"1/~@e.<~.@(],;@:{~)^:_&.>])@:(<@<:)  NB. name
   tcc 8 28 14 8 2 1 13 15 30 17 9 8 18 19 30 3 8 25 23 12 6 7 19 24 17 7 21 20 29 15 32 32
5
   tcc 20 31 3 18 18 18 8 12 25 10 10 19 3 9 18 1 13 5 18 23 20 26 16 22 4 16 19 31 21 32 15 22
4
   tcc 6 21 15 14 22 12 5 32 29 3 22 23 6 16 20 2 16 25 9 22 13 2 19 20 26 19 32 3 32 19 28 16
1
   tcc tentwentyfour  NB. the 1024-node example
6

Unfortunately the 1024 element case now takes a really long time to terminate. The previous version <:@#@((#~0={.+/@:*"1])^:a:)@e.@(~.@(],;@:{~)^:_&.>~<)@:(<@<:) (61 char) took a little over a second to do this.

Ah yes, the good old e. function, I should have known.  o_O  I'm getting lightheahed looking at your code.  Well done.

Python (89) (87)
def c(G):
 u=i=0
 for _ in G:
  j=i;i+=1
  while j>=0:G[j],j=~i,G[j]
  u+=j==~i
 return u

The main idea is to start at each node at turn and walk along the path from it, marking each node we visit with a label unique to the node we started at. If we ever hit a marked node, we stop walking, and check if the marking is the one corresponding to our starting node. If it is we must have walked a loop, so we increment the count of cycles by one.
In the code, u is the cycle counter, i is the starting node, j is the current node we're walking. The label corresponding to starting node i is its bit-complement ~i which is always negative. We mark a node by pointing it to that value, overwriting whatever node it actually pointed to (being careful to walk to that node before it's forgotten).
We know we've hit a marked node when we walk to a negative-value "node" immediately afterwards. We check if that negative value is the current label to see whether we've walked a cycle. Since each node we walk is effectively deleted, each cycle will only be walked once.
It saves characters to count up i manually with a dummy loop variable _ then as for i in range(len(G)). Python lists are 0-indexed. If they were instead 1-indexed, we could save two characters by writing j=i=i+1 to have i and j be 1 for the first loop, and
write j>0 in place of j>=0.
Edit:
We can save two characters by iterating i over the elements of the list rather than the indices, since node that are not pointed to by any edge don't matter. We have to iterate over set(G) though to avoid repeating a start node that it pointed to by multiple other nodes.
def c(G):
 u=0
 for i in set(G):
  j=i
  while j>=0:G[j],j=~i,G[j]
  u+=j==~i
 return u

Shortest Python code yet posted, and an interesting 'chalk marking' method.  I like it.

Python (96)
Very, very, very, very based on user2228078's answer, as it works exactly the same, but is more golfed:
c=lambda l:(1+c(l[:-1])if l[-1]==len(l)else c([[x,l[-1]][x==len(l)]for x in l[:-1]]))if l else 0

(Technical question: should a golfing of someone elses answer be community wiki?)

You have my blessing to plagiarize.  Let it be a community effort.

@user2790167 Sure, there ya go ;)

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


text:
May the 4th be with you!
In honor of Star Wars day, write a program to display the following text, scrolling like the Star Wars opening crawl:
It  is  a  period  of  civil war.  Rebel
spaceships,   striking  from   a  hidden
base,  have   won  their  first  victory
against the evil Galactic Empire.

During  the battle,  Rebel spies managed
to  steal  secret  plans to the Empire's
ultimate   weapon,  the  Death Star,  an
armored   space  station   with   enough
power to destroy an entire planet.

Pursued by the Empire's sinister agents,
Princess  Leia  races  home  aboard  her
starship,  custodian of the stolen plans
that  can save  her people  and  restore
freedom to the galaxy...

You may output an animated GIF or have your program display it. The output must show the following:

The text must start from the bottom of the image/display
It must scroll upwards until it reaches the top. It must take at least 30 seconds for a piece of text to reach the top. The animation must continue until all the text reaches the top.
In this distance, the text must get smaller until it is less than 1/3 the size (length and font)
The text must be slanted to follow this angle.
The text must be left and right justified. The text given is already justified for monospaced fonts, however, you may remove the extra spaces (not newlines) and justify it yourself.
The text must be yellow
The background must be black

This video shows the opening crawl.
Good luck, and May the fourth be with you!

What about "May the forth be with you"?

@TheDoctor That's what it was, but I fixed the typo. You seriously think that I should go for the double pun?

Forth would be difficult to do this in.

@TheDoctor "To do in Forth, difficult this would be" - Yoda'd that for you.

One fun thing about this question: before posting, the system warned me that this might be closed as "too subjective".

Since there is an abundance of HTML answers, what about bonus points for those with HTML soltuions that also work in browsers other than webkit based ones?

@rooby That can be handled via votes and bounties.

@Quincunx: I meant for you selecting the winner, not extra stack exchange points.

HTML, 762

It  is  a  period  of  civil war.  Rebel
spaceships,   striking  from   a  hidden
base,  have   won  their  first  victory
against   the   evil   Galactic  Empire.

During  the battle,  Rebel spies managed
to  steal  secret  plans to the Empire's
ultimate   weapon,  the  Death Star,  an
armored   space  station   with   enough
power   to  destroy  an  entire  planet.

Pursued by the Empire's sinister agents,
Princess  Leia  races  home  aboard  her
starship,  custodian of the stolen plans
that  can save  her people  and  restore
freedom to the galaxy...

Kind of choppy (read: extremely choppy :P).
Here's a JSFiddle (with -webkit- vendor prefixes added so it works in Chrome).

I just realized that I was overzealous in my justification. The first two paragraphs don't need extra spaces on the last line.

Also, I don't know about this; the crawl slides to the left, not just up. I don't accept that. The choppiness: okay, but the sliding not just up: not okay.

@Quincunx After a careful rereading of the question, it mentions nothing about sliding (slightly) in another direction. (Although it was so slight I didn't even notice.) I'll keep this answer here, but anyway, I'd be fine if you considered it invalid.

It is so slight to you? It is very apparent to me. Possibly, it is more visible in Chrome. For me, the leftmost edge stays at the same left-ness, even with very small text, so the rightmost moves very noticeably to the left. In that case, I'm fine with it. I wonder what it really looks like....

Is it supposed to work on firefox?

Any chance you can get it to work in firefox?

It works in Firefox when removing the -webkit- strings.

If you just remove the -webkit- prefix you break webkit. You have to have both.

HTML/CSS, 1047
I could golf this a lot more by deleting the -webkit prefixes etc., but this will do for the time being:

It is a period of civil
war. Rebel spaceships, striking from a hidden base, have won their first victory
against the evil Galactic Empire.

During the battle, Rebel spies managed to
steal secret plans to the Empire's ultimate weapon, the DEATH STAR, an armored
space station with enough power to destroy an entire planet.

Pursued by
the Empire's sinister agents, Princess Leia races home aboard her starship,
custodian of the stolen plans that can save her people and restore freedom to
the galaxy...

Live demo

Nice. This is exactly what I had in mind. Except you change the newlines.

Doesn't this break the rule "however, you may remove the extra spaces (not newlines)" @Quincunx?

@Doorknob I assumed that referred to the paragraph breaks?

Does the text get smaller? Not working for me in Chrome.

@PaulDraper works for me (in Chrome)

@m.buettner, weird. Chrome 34 on Ubuntu 12.04. Perhaps I'll file a Chrome bug because of this...

@Doorknob I guess this is okay. This follows the actual crawl, while mine is slightly off. However, I don't want anyone doing each paragraph on one line.

jsfiddle of it: http://jsfiddle.net/73fzU/

Not sure why, but it doesn't work in FireFox 29.0 on Ubuntu 13.10. Not related to @PaulDraper's problem (I'm just seeing a completely black screen, with some occasional flittering and thin yellow streak in the middle of the screen)

I would have upvoted this if it wasn't in code-golfing... :P BTW, Ubuntu 14.04 Chrome v 34.0.1847.132, working.

-1 that isn't a valid HTML file.  If you purposefully wanted to make this only work with a specific browser version then you should include the name and version of the browser in the language specification.

@IQAndreas Waiting long enough, it looks like the text appears in FF but it's tiny.

Works pretty well for me in firefox, however each paragraph doesn't appear until it gets about a third of the way up the page.

HTML+CSS+SVG 1614 1625
I wanted to be visually correct, too. SVG used for masking and animation. HTML+CSS used for transforms. I didn't check if the text gets to exactly 1/3 size.
Recommended viewing in Chrome due to -webkit- prefix. Requires CSS 3D transforms to work; you may need to open chrome://flags and pick 'Override software rendering list'.
Included in bytecount are newlines and blanks.
Update 1: Adding support for Firefox and other browsers that don't need prefixes. Added 11 bytes even after further cleanup. Cleanup was possible because browsers luckily interpret SVG using HTML-crunching parsers as opposed to XML-compilant parsers.
Live

<svg width=760 height=1000>
<g mask=url(#m)>
<g transform=translate(0,0)>
<animateTransform attributeName=transform type=translate dur=50 fill=freeze from=0,700 to=0,-450 />
<foreignObject width=760 height=800>

It is a period of civil war. Rebel
spaceships, striking from a hidden
base, have won their first victory
against the evil Galactic Empire.

During the battle, Rebel spies managed
to steal secret plans to the Empire's
ultimate weapon, the DEATH STAR, an
armored space station with enough
power to destroy an entire planet.

Pursued by the Empire's sinister agents,
Princess Leia races home aboard her
starship, custodian of the stolen plans
that can save her people and restore
freedom to the galaxy...

</foreignObject>
</g>
</g>
<defs>
<linearGradient id=g x1=0 y1=0% x2=0 y2=100%>
<stop offset=0% />
<stop offset=25% />
<stop offset=35% stop-color=#fff />
<stop offset=100% stop-color=#fff />
</linearGradient>
<mask id=m>
<rect width=100% height=100% fill=url(#g) />
</mask>
</defs>
</svg>


text:
Convert a bytes array to base64
Your mission is to write a function/program that converts an array of bytes (i.e: an array of integers from 0 to 255), to base64.
Using built-in base64 encoders is not allowed.
The required base64 implementation is RFC 2045. (using "+", "/", and mandatory padding with "=")
Shortest code (in bytes) wins!
Example:
Input (int array): [99, 97, 102, 195, 169]
Output (string): Y2Fmw6k=

What type of competition is this?

Does built-in base64 encoders cover only binary-to-text encoders or functions manipulating integers as well?

To clarify: Can I use a function that returns 1 2 for the argument 66?

There are 9 standardised or 4 non-standardised versions of base64. Your reference to = for padding narrows it down to 4. Which one do you want? Or do you want a non-standard variant which doesn't have maximum line lengths?

I'm guessing he/she referred to the either the "standard" one specified by RFC 4648 or the version used by MIME-types, RFC 2045. These are different, so clarification would be very useful.

sorry for the lack of precision, I didn't know there were different kinds of base64. The one I'm looking for is the one used in dataURI's (so, yes, RFC 2045)

arg, please don't change requirements when you already have a significant number of answers, and 80% of them will require nontrivial code changes to acommodate the new spec.

RFC 2045 is not what's used in a data URI. When was the last time you saw a data uri with \r\n in it? Also, in addition to wrapping at 76 chars, there is special newline handlng in RFC 2045.

@skibrianski damn, I'm really sorry. According to http://en.wikipedia.org/wiki/Base64, RFC2045 is the one corresponding to "Base64 transfer encoding for MIME". But you're right, URIs don't have \r\n. So... I don't know. Which one is used in URIs / JavaScript btoa() ? RFC 1642?

JavaScript, 177 187 198 characters
function(d){c="";for(a=e=b=0;a<4*d.length/3;f=b>>2*(++a&3)&63,c+=String.fromCharCode(f+71-(f<26?6:f<52?0:f<62?75:f^63?90:87)))a&3^3&&(b=b<<8^d[e++]);for(;a++&3;)c+="=";return c}

For adding linebreaks, \r\n, after each 76th character, add 23 characters to the code:
function(d){c="";for(a=e=b=0;a<4*d.length/3;f=b>>2*(++a&3)&63,c+=String.fromCharCode(f+71-(f<26?6:f<52?0:f<62?75:f^63?90:87))+(75==(a-1)%76?"\r\n":""))a&3^3&&(b=b<<8^d[e++]);for(;a++&3;)c+="=";return c}

Demo code:

var encode = function(d,a,e,b,c,f){c="";for(a=e=b=0;a<4*d.length/3;f=b>>2*(++a&3)&63,c+=String.fromCharCode(f+71-(f<26?6:f<52?0:f<62?75:f^63?90:87))+(75==(a-1)%76?"\r\n":""))a&3^3&&(b=b<<8^d[e++]);for(;a++&3;)c+="=";return c};

//OP test case
console.log(encode([99, 97, 102, 195, 169])); // outputs "Y2Fmw6k=".

//Quote from Hobbes' Leviathan:
console.log(
 encode(
  ("Man is distinguished, not only by his reason, but by this singular passion from " +
   "other animals, which is a lust of the mind, that by a perseverance of delight " +
   "in the continued and indefatigable generation of knowledge, exceeds the short " +
   "vehemence of any carnal pleasure.")
  .split('').map(function(i){return i.charCodeAt(0)})
 )
);

Nice solution! You can shave off some bytes using some ES6 features and removing some duplication: Shortened code with comments

@CraigAyre, thanks for constructive input. ES6 was not finalized and available at the time this challenge was originally posted. As suggested at codegolf.meta, you could post the shortened ES6 version and mark it as non-competing.

No worries, my fault for not double checking the original post date! I'm a fan of your solution so I'm not going to post another, but thanks for the link. The template literal logic that removed the alphabet duplication can be converted to ES5 in the same number of bytes, doesn't save many but every little counts!

@CraigAyre, thanks again for the tip, found another way to compress the base64 symbols even more (which made it even more backwards compatible--should now work in old IE as well).

C, 276 bytes
Quite a bump of this thread but I came up with this question myself a few days ago, then found out about code golfing, then found out about this thread.
Takes the 0-255 int array as first console arg (just a string). Uses K&R C style function parameter declaration and RFC 2045 encoding (except with no 76-character limit).
#define u(_)unsigned _:6;
b(i,j){putchar(j?i>61?43+i%2*4:i+65+6*(i>25)-75*(i>51):61);}i=-3;main(o,c)char**c;{char*s=c[1];for(;(i+=3)<strlen(s);){union{struct{u(a)u(b)u(c)u(d)};char s[3];}a;a.s[2]=s[i];a.s[1]=s[i+1];*a.s=s[i+2];b(a.d);b(a.c);b(a.b,a.s[1]);b(a.a,a.s[1]**a.s);}}

More 'readable' version of the algorithm (it was originally more clear but I started obfusc-golfing it right away so it turned out like this):
#include <stdio.h>
#include <string.h>

void b64_char(int i) {
    putchar(i>61?43+i%2*4:i+65+6*(i>25)-75*(i>51));
}

int i=-3;
int main(int argc, char* argv[]) {
    char* str = argv[1];
    for (;(i+=3)<strlen(str);) {
        union {
            struct {unsigned a:6; unsigned b:6; unsigned c:6; unsigned d:6;};
            char s[3];
        } a;
        a.s[2]=str[i];
        a.s[1]=str[i+1];
        a.s[0]=str[i+2];

        b64_char(a.d);
        b64_char(a.c);
        a.s[1]?b64_char(a.b):putchar(61);
        a.s[0]&&a.s[1]?b64_char(a.a):putchar(61);
    }

    return 0;
}

Defining the Base64 symbol table like that saved me a bunch of bytes.
Basically taking advantage of the consecutiveness of letters in ASCII.
Also, architecture dependent since it only works on little endian machines, and fails non-deterministically when the unpassed parameter for the function b(2) happens to be 0.
This would have been a lot shorter on a big endian machine.
Can anybody shorten this any further?

Suggest i/52*75 instead of75*(i>51)

32-bit x86 assembly, 59 bytes
Byte-code:
66 B8 0D 0A 66 AB 6A 14 5A 4A 74 F4 AD 4E 45 0F C8 6A 04 59 C1 C0 06 24 3F 3C 3E 72 05 C0
E0 02 2C 0E 2C 04 3C 30 7D 08 04 45 3C 5A 76 02 04 06 AA 4D E0 E0 75 D3 B0 3D F3 AA C3
Disassembly:
b64_newline:
    mov     ax, 0a0dh
    stosw
b64encode:
    push    (76 shr 2) + 1
    pop     edx
b64_outer:
    dec     edx
    je      b64_newline
    lodsd
    dec     esi
    inc     ebp
    bswap   eax
    push    4
    pop     ecx
b64_inner:
    rol     eax, 6
    and     al, 3fh
    cmp     al, 3eh
    jb      b64_testchar
    shl     al, 2     ;'+' and '/' differ by only 1 bit
    sub     al, ((3eh shl 2) + 'A' - '+') and 0ffh
b64_testchar:
    sub     al, 4
    cmp     al, '0'
    jnl     b64_store ;l not b because '/' is still < 0 here
    add     al, 'A' + 4
    cmp     al, 'Z'
    jbe     b64_store
    add     al, 'a' - 'Z' - 1
b64_store:
    stosb
    dec     ebp
    loopne  b64_inner
    jne     b64_outer
    mov     al, '='
    rep     stosb
    ret
Call b64encode with esi pointing to input buffer, edi pointing to output buffer.
It could be made even smaller if line-wrapping is not used.

Husk, 118 114 93 82 73 61 bytes
C76ΣtTT'=C4§o↓_ȯa%_3L(mo!ṁ…w"AZ az 09 + /"→B64B256ΣTT0C3+R3 4

Try it online!
Examples

[]:LN "" (LN is a type hint for list of numbers)
[0] "AA=="
[99,97,102,195,169] "Y2Fmw6k="
[108,105,103,104,116,32,119,111,114,107,46] "bGlnaHQgd29yay4="

How it works
C76ΣtTT'=C4§o↓_ȯa%_3L(mo!ṁ…w"AZ az 09 + /"→B64B256ΣTT0C3+R3 4
           §    Main fork combinator.
                                                        +R3 4    Begin first branch of the fork. Prepend 3 4s to deal with leading zeros.
                                                  ΣTT0C3    Chop into 3-byte chunks. Transpose with 0 padding, transpose back, and flatten.
                                           B64B256    Interpret as base 256, then as base 64.
                     (mo!ṁ…w"AZ az 09 + /"→    Map the following: increment (Husk is 1-based) and index into the base 64 alphabet. End first branch of fork.
               ȯa%_3L    Second branch of the fork: padding = abs(length mod -3)
            o↓_    Converge the fork on this function: Drop padding number of characters from the end of the base 64 encoded string.
   ΣtTT'=C4    Chop into 4-character chunks, transpose with '=' padding, transpose back, drop the first chunk, and flatten.
C76    Chop the encoded string into 76-character chunks which will be joined with '\r\n' automatically.

This is my first code-golf submission and I would appreciate any help from the Husk experts here!
Thank you Leo for your help with the 61-byte version!!

Welcome to Code Golf, and nice first answer! We've got a husk tips page here, there are probably some useful tips there.

Excel 2016+, 209 205 Bytes
An anonymous function that take input as a dynamic, spilled or legacy array from range A1# and outputs to the calling cell.
=LET(c,COUNT(A1#),i,CONCAT(MID(CONCAT(CHAR({64;96}+COLUMN(A:Z)),"0123456789+/"),1+BIN2DEC(MID(CONCAT(BASE(A1#,2,8))&REPT("00",MOD(c,3)),SEQUENCE(4*c/3+.7,,,6),6)),1)),j,MOD(LEN(i),4),i&REPT("=",IF(j,4-j)))

Ungolfed
=LET(                                           ' Begin Variable block
    c,COUNT(A1#),                               '   Def c(ount) with count of bytes in array
    i,CONCAT(                                   '   Def i helper var holding the string concatenated from
        MID(                                    '     Repeatedly splitting
            CONCAT(                             '       The Base64 alphabet, made by concating
                CHAR({64;96}+COLUMN(A:Z)),      '          uppercase and lowercase alphas
                "0123456789+/"),                '          numbers and symbols
            1+BIN2DEC(                          '       at index of 1+ decimal value from binary string obtained from
                MID(                            '         splitting
                    CONCAT(                     '           the string concatenated from
                        BASE(A1#,2,8),          '             the binary string array representation of input
                        REPT("00",MOD(c,3))),   '             padded with `0` to lowest even multiple of 6 bits larger than c
                    SEQUENCE(4*c/3+.7,,,6),     '           at every sixth char, for a total of ceil(4/3*count(input)) string
                    6)),                        '           making each substring be a binary string of 6 bits
            1)),                                '       with length 1
    j,MOD(LEN(i),4),                            '   Def j as the helper var holding length of i mod 4
    i&REPT("=",IF(j,4-j)))                      ' Output i and `=` padding to a string length that is a multiple 4

perl, 126 bytes
reads stdin, outputs to stdout
$/=$\;print map{$l=y///c/2%3;[A..Z,a..z,0..9,"+","/"]->[oct"0b".substr$_.0 x4,0,6],$l?"="x(3-$l):""}unpack("B*",<>)=~/.{1,6}/g

ungolfed:
my @x = ('A'..'Z','a'..'z',0..9,'+','/');
my $in = join '', <>;
my $bits = unpack 'B*', $in;
my @six_bit_groups = $bits =~ /.{1,6}/g;
for my $sixbits (@six_bit_groups) {
  next unless defined $sixbits;
  $l=length($sixbits)/2%3;
  my $zero_padded = $sixbits . ( "0" x 4 );
  my $padded_bits = substr( $zero_padded, 0, 6 );
  my $six_bit_int = oct "0b" . $padded_bits;
  print $x[$six_bit_int];
  print "=" x (3 - $l)  if  $l;
}

The question has been clarified to require RFC 2045, so you need to add a bit of code to split the output into 76-char chunks and join with \r\n.

Python, 234 chars
def F(s):
 R=range;A=R(65,91)+R(97,123)+R(48,58)+[43,47];n=len(s);s+=[0,0];r='';i=0
 while i<n:
  if i%57<1:r+='\r\n'
  for j in R(4):r+=chr(A[s[i]*65536+s[i+1]*256+s[i+2]>>18-6*j&63])
  i+=3
 k=-n%3
 if k:r=r[:-k]+'='*k
 return r[2:]

The question has been clarified to require RFC 2045, so you need to add a bit of code to split the output into 76-char chunks and join with \r\n.

@PeterTaylor: fixed.

Perl, 147 bytes
sub b{$f=(3-($#_+1)%3)%3;$_=unpack'B*',pack'C*',@_;@r=map{(A..Z,a..z,0..9,'+','/')[oct"0b$_"]}/.{1,6}/g;$"='';join"\r\n",("@r".'='x$f)=~/.{1,76}/g}

The function takes a list of integers as input and outputs the string, base64 encoded.
Example:
print b(99, 97, 102, 195, 169)

prints
Y2Fmw6kA

Ungolfed:
Version that also visualizes the intermediate steps:
sub b {
    # input array: @_
    # number of elements: $#_ + 1 ($#_ is zero-based index of last element in
    $fillbytes = (3 - ($#_ + 1) % 3) % 3;
      # calculate the number for the needed fill bytes
      print "fillbytes:       $fillbytes\n";
    $byte_string = pack 'C*', @_;
      # the numbers are packed as octets to a binary string
      # (binary string not printed)
    $bit_string = unpack 'B*', $byte_string;
      # the binary string is converted to its bit representation, a string wit
      print "bit string:      \"$bit_string\"\n";
    @six_bit_strings = $bit_string =~ /.{1,6}/g;
      # group in blocks of 6 bit
      print "6-bit strings:   [@six_bit_strings]\n";
    @index_positions = map { oct"0b$_" } @six_bit_strings;
      # convert bit string to number
      print "index positions: [@index_positions]\n";
    @alphabet = (A..Z,a..z,0..9,'+','/');
      # the alphabet for base64
    @output_chars = map { $alphabet[$_] } @index_positions;
      # output characters with wrong last characters that entirely derived fro
      print "output chars:    [@output_chars]\n";
    local $" = ''; #"
    $output_string = "@output_chars";
      # array to string without space between elements ($")
      print "output string:   \"$output_string\"\n";
    $result = $output_string .= '=' x $fillbytes;
      # add padding with trailing '=' characters
      print "result:          \"$result\"\n";
    $formatted_result = join "\r\n", $result =~ /.{1,76}/g;
      # maximum line length is 76 and line ends are "\r\n" according to RFC 2045
      print "formatted result:\n$formatted_result\n";
    return $formatted_result;
}

Output:
fillbytes:       1
bit string:      "0110001101100001011001101100001110101001"
6-bit strings:   [011000 110110 000101 100110 110000 111010 1001]
index positions: [24 54 5 38 48 58 9]
output chars:    [Y 2 F m w 6 J]
output string:   "Y2Fmw6J"
result:          "Y2Fmw6J="
formatted result:
Y2Fmw6J=

Tests:
The test strings come from the example in the question the examples in the Wikipedia article for Base64.
sub b{$f=(3-($#_+1)%3)%3;$_=unpack'B*',pack'C*',@_;@r=map{(A..Z,a..z,0..9,'+','/')[oct"0b$_"]}/.{1,6}/g;$"='';join"\r\n",("@r".'='x$f)=~/.{1,76}/g}

sub test ($) {
   print b(map {ord($_)} $_[0] =~ /./sg), "\n\n";
}

my $str = <<'END_STR';
Man is distinguished, not only by his reason, but by this singular passion from
other animals, which is a lust of the mind, that by a perseverance of delight
in the continued and indefatigable generation of knowledge, exceeds the short
vehemence of any carnal pleasure.
END_STR
chomp $str;

test "\143\141\146\303\251";
test $str;
test "any carnal pleasure.";
test "any carnal pleasure";
test "any carnal pleasur";
test "any carnal pleasu";
test "any carnal pleas";
test "pleasure.";
test "leasure.";
test "easure.";
test "asure.";
test "sure.";

Test output:
TWFuIGlzIGRpc3Rpbmd1aXNoZWQsIG5vdCBvbmx5IGJ5IGhpcyByZWFzb24sIGJ1dCBieSB0aGlz
IHNpbmd1bGFyIHBhc3Npb24gZnJvbQpvdGhlciBhbmltYWxzLCB3aGljaCBpcyBhIGx1c3Qgb2Yg
dGhlIG1pbmQsIHRoYXQgYnkgYSBwZXJzZXZlcmFuY2Ugb2YgZGVsaWdodAppbiB0aGUgY29udGlu
dWVkIGFuZCBpbmRlZmF0aWdhYmxlIGdlbmVyYXRpb24gb2Yga25vd2xlZGdlLCBleGNlZWRzIHRo
ZSBzaG9ydAp2ZWhlbWVuY2Ugb2YgYW55IGNhcm5hbCBwbGVhc3VyZSO=

YW55IGNhcm5hbCBwbGVhc3VyZSO=

YW55IGNhcm5hbCBwbGVhc3VyZB==

YW55IGNhcm5hbCBwbGVhc3Vy

YW55IGNhcm5hbCBwbGVhc3F=

YW55IGNhcm5hbCBwbGVhcD==

cGxlYXN1cmUu

bGVhc3VyZSO=

ZWFzdXJlLC==

YXN1cmUu

c3VyZSO=

The question has been clarified to require RFC 2045, so you need to add a bit of code to split the output into 76-char chunks and join with \r\n.

@PeterTaylor: Thanks, I have updated the answer for RFC 2045.

bravo for this very complete answer. Including mandatory line-breaks (by specifying "RFC 2045" in the OP) was actually an error, you can in fact ignore that part. Sorry :)

GolfScript, 80 (77) bytes
~.,~)3%:P[0]*+[4]3*\+256base 64base{'+/''A[a{:0'{,^}/=}/{;}P*'='P*]4>76/"\r
":n*

The above will fit exactly 76 characters in a line, except for the last line. All lines are terminated by CRLF.
Note that RFC 2045 specifies a variable, maximum line length of 76 characters, so at the cost of pretty output, we can save 3 additional bytes.
~.,~)3%:P[0]*+[4]3*\+256base 64base{'+/''A[a{:0'{,^}/=}/{;}P*'='P*]4>{13]n+}/

The above will print one character per line, except for the last line, which can contain 0, 1 or 2 = chars. GolfScript will also append a final LF, which, according to RFC 2045, must be ignored by decoding software.
Example
$ echo '[99 97 102 195 169]' | golfscript base64.gs | cat -A
Y2Fmw6k=^M$
$ echo [ {0..142} ] | golfscript base64.gs | cat -A
AAECAwQFBgcICQoLDA0ODxAREhMUFRYXGBkaGxwdHh8gISIjJCUmJygpKissLS4vMDEyMzQ1Njc4^M$
OTo7PD0+P0BBQkNERUZHSElKS0xNTk9QUVJTVFVWV1hZWltcXV5fYGFiY2RlZmdoaWprbG1ub3Bx^M$
cnN0dXZ3eHl6e3x9fn+AgYKDhIWGh4iJiouMjY4=^M$
$ echo '[99 97 102 195 169]' | golfscript base64-sneaky.gs | cat -A
Y^M$
2^M$
F^M$
m^M$
w^M$
6^M$
k^M$
=^M$
$

How it works
~          # Interpret the input string.
.,~)3%:P   # Calculate the number of bytes missing to yield a multiple of 3 and save in “P”.
[0]*+      # Append that many zero bytes to the input array.
[4]3*\+    # Prepend 3 bytes to the input array to avoid issues with leading zeros.
256base    # Convert the input array into an integer.
64base     # Convert that integer to base 64.
{          # For each digit:
  '+/'     # Push '+/'.
  'A[a{:0' # Push 'A[a{:0'.
  {        # For each byte in 'A[a{:0':
    ,      # Push the array of all bytes up to that byte.
    ^      # Take the symmetric difference with the array below it.
  }/       # Result: 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
  =        # Retrieve the character corresponding to the digit.
}/         #
{;}P*'='P* # Replace the last “P” characters with a string containing that many “=” chars.
]          # Collect all bytes on the stack into an array.
4>         # Remove the first four, which correspond to the 3 prepended bytes.
76/        # Collect all bytes on the stack into an array and split into 76-byte chunks.
"\r\n":n*  # Join the chunks with separator CRLF and save CRLF as the new line terminator.

PHP, 200 bytes
<?foreach($g=$_GET as$k=>$v)$b[$k/3^0]+=256**(2-$k%3)*$v;for(;$i<62;)$s.=chr($i%26+[65,97,48][$i++/26]);foreach($b as$k=>$v)for($i=4;$i--;$p++)$r.=("$s+/=")[count($g)*4/3<$p?64:($v/64**$i)%64];echo$r;

Try it online!
You could replace the string ("$s+/=") with an array array_merge(range(A,Z),range(a,z),range(0,9),["+","/","="])
Only to compare which byte count can reach with an not allowed built-in
PHP, 45 bytes
<?=base64_encode(join(array_map(chr,$_GET)));

Try it online!

Python - 310, 333
def e(b):
  l=len;c="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";r=p="";d=l(b)%3
  if d>0:d=abs(d-3);p+="="*d;b+=[0]*d
  for i in range(0,l(b)-1,3):
    if l(r)%76==0:r+="\r\n"
    n=(b[i]<<16)+(b[i+1]<<8)+b[i+2];x=(n>>18)&63,(n>>12)&63,(n>>6)&63,n&63;r+=c[x[0]]+c[x[1]]+c[x[2]]+c[x[3]]
  return r[:l(r)-l(p)]+p

Somewhat ungolfed:
def e( b ):
    c = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
    r = p = ""
    d = len( b ) % 3

    if d > 0:
        d = abs( d - 3 )
        p = "=" * d
        b + = [0] * d

    for i in range( 0, len( b ) - 1, 3 ):
        if len( r ) % 76 == 0:
            r += "\r\n"

        n = ( b[i] << 16 ) + ( b[i + 1] << 8 ) + b[i + 2]
        x = ( n >> 18 ) & 63, ( n >> 12 ) & 63, ( n >> 6) & 63, n & 63
        r += c[x[0]] + c[x[1]] + c[x[2]] + c[x[3]]

    return r[:len( r ) - len( p )] + p

Example:
Python's built-in base64 module is only used in this example to ensure the e function has the correct output, the e function itself isn't using it.
from base64 import encodestring as enc

test = [ 99, 97, 102, 195, 169 ]
str  = "".join( chr( x ) for x in test )

control = enc( str ).strip()
output = e( test )

print output            # => Y2Fmw6k=
print control == output # => True

The question has been clarified to require RFC 2045, so you need to add a bit of code to split the output into 76-char chunks and join with \r\n.

@PeterTaylor fixed.

JavaScript (ES6), 220B
f=a=>{for(s=a.map(e=>('0000000'+e.toString(2)).slice(-8)).join(p='');s.length%6;p+='=')s+='00';return s.match(/.{6}/g).map(e=>'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'[parseInt(e,2)]).join('')+p}

If your browser does not support ES6, you can try with this version (262B) :
function f(a){for(s=a.map(function(e){return ('0000000'+e.toString(2)).slice(-8)}).join(p='');s.length%6;p+='=')s+='00';return s.match(/.{6}/g).map(function(e){return 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'[parseInt(e,2)]}).join('')+p}

f([99, 97, 102, 195, 169]) returns "Y2Fmw6k=".

Where's the code to split it into 76-char chunks joined with \r\n?

Jelly, 38 bytes
s3z0Zµḅ⁹b64‘ịØb)FṖ³LN%3¤¡s4z”=Z;€“Æ½‘Ọ

Try it online!
As (almost) every other answer covers the RFC2045 requirement of "at most 76 chars per line with line ending \r\n", I followed it.
How it works
s3z0Zµḅ⁹b64‘ịØb)FṖ³LN%3¤¡s4z”=Z;€“Æ½‘Ọ    Monadic main link. Input: list of bytes

s3z0Z    Slice into 3-item chunks, transpose with 0 padding, transpose back
         Equivalent to "pad to length 3n, then slice into chunks"

µḅ⁹b64‘ịØb)    Convert each chunk to base64
 ḅ⁹b64         Convert base 256 to integer, then to base 64
      ‘ịØb     Increment (Jelly is 1-based) and index into base64 digits

FṖ³LN%3¤¡s4z”=Z    Add correct "=" padding
F                  Flatten the list of strings to single string
 Ṗ      ¡          Repeat "remove last" n times, where
  ³LN%3¤             n = (- input length) % 3
         s4z”=Z    Pad "=" to length 4n, then slice into 4-item chunks

;€“Æ½‘Ọ    Add "\r\n" line separator
;€         Append to each line:
  “Æ½‘       Codepage-encoded list [13,10]
      Ọ    Apply `chr` to numbers; effectively add "\r\n"

Base decompression can be used here, but ṃØbṙ1¤ is a bit too long for a simple operation.

It may be worth asking Dennis to make rotated-base-decompression atom.

Fails for 0,0,0.

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