text:
Index of a multidimensional array
Lower level languages, such as C and C++ actually have no concept of multidimensional arrays. (Other than vectors and dynamic arrays) When you create a multidimensional array with
int foo[5][10];

This is actually just syntactic sugar. What C really does is create a single contiguous array of 5 * 10 elements. This
foo[4][2]

is also syntactic sugar. This really refers to the element at
4 * 10 + 2

or, the 42nd element. In general, the index of element [a][b] in array foo[x][y] is at
a * y + b

The same concept applies to 3d arrays. If we have foo[x][y][z] and we access element [a][b][c] we are really accessing element:
a * y * z + b * z + c

This concept applies to n-dimensional arrays. If we have an array with dimensions D1, D2, D3 ... Dn and we access element S1, S2, S3 ... Sn the formula is
(S1 * D2 * D3 ... * Dn) + (S2 * D3 * D4 ... * Dn) + (S3 * D4 ... * Dn) ... + (Sn-1 * Dn) + Sn

The challenge
You must write a program or function that calculates the index of a multidimensional array according to the formula above. Input will be two arrays. The first array is the dimensions, and the second array is the indices. The length of these two arrays will always be equal and at least 1.
You can safely assume that every number in the arrays will be an non-negative integer. You can also assume that you will not get a 0 in the dimension array, although a 0 might be in the indices. You can also assume that indices will not be larger than the dimensions.
Test IO
Dimensions: [5, 10]
Indices: [4, 2]
Output: 42

Dimensions: [10, 10, 4, 62, 7]
Indices: [1, 2, 3, 4, 5]
Output: 22167

Dimensions: [5, 1, 10]
Indices: [3, 0, 7]
Output: 37

Dimensions: [6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
Indices: [3, 1, 5, 5, 3, 0, 5, 2, 5, 4]
Output: 33570178

So this is 0-based indexing, correct? Can we use 1-based indexing if that's more natural for our language of choice?

@AlexA. Yes, that's acceptable.

Actually, what C 'really does' is create a single contiguous array of five elements of type int[10].

Related.

@Hurkyl Yes, but all of the integers in that array are still contiguous. It's just semantics.

Does someone mind to add the reference output for 1-based indexing? :)

APL, 1 byte
⊥

Test it on TryAPL.

Well, that's it. We have a winner. Everyone else can go home now.

Why... why does this work? o_O

@AlexA. Indexing a multidimensional array is essentially mixed base conversion.

I dont even know anymore

W O W ! T h a t w a s G O O D !

Link to docs, for the curious.

@Dennis You're making it sound easy

Oh, look, a hole in one while golfing!

Most of the time I come here for fun. Then there are times when I accidentally receive profound insights

how do we print that operator ⊥? I just copied and pasted.

@kenn In Dyalog APL (including TryAPL), ngn/APL and possibly others, you can press backtick followed by b.

@kenn As Dennis said, or, if you have an actual APL keyboard layout installed, [APL]+[b], where [APL]  depends on OS and APL flavor. Btw, "b" is for base, and the symbol looks like the base of a pillar.

J, 2 bytes
#.

Where there's an APL, there's a J! Kind of. Takes dimensions as left arg and index as right arg. "Indexing a multidimensional array is essentially mixed base conversion."

JavaScript (ES6), 34 bytes
(d,a)=>a.reduce((r,i,j)=>r*d[j]+i)

Surely reduce must be better than map.

Jelly, 7 6 bytes
Ṇ;żḅ@/

Try it online! or verify all test cases.
How it works
Ṇ;żḅ@/  Main link. Arguments: D (list of dimensions), I (list of indices)

Ṇ       Yield 0, the logical NOT of D.
  ż     Zip D with I.
        If D = [10, 10, 4, 62, 7] and I = [1, 2, 3, 4, 5], this yields
        [[10, 1], [10, 2], [4, 3], [62, 4], [7, 5]].
 ;      Concatenate, yielding [0, [10, 1], [10, 2], [4, 3], [62, 4], [7, 5]].
   ḅ@/  Reduce by swapped base conversion to integer.
        [10, 1] in base    0 is    0 × 10 + 1 = 1.
        [10, 2] in base    1 is    1 × 10 + 2 = 12.
        [ 4, 3] in base   12 is   12 ×  4 + 3 = 51.
        [62, 4] in base   51 is   51 × 62 + 4 = 3166.
        [ 7, 5] in base 3166 is 3166 ×  7 + 5 = 22167.

Python, 43 bytes
f=lambda x,y:x>[]and y.pop()+x.pop()*f(x,y)

Test it on Ideone.

Not only does Dennis solidly thrash all of us, but he does it in every. single. language.

Pyth, 10 bytes
e.b=+*ZNYC

Try it online: Demonstration or Test Suite
Using Horner's method to calculate the index.

MATL, 11 bytes
4L)1hPYpP*s

This uses 0-based indexing, as in the original challenge.
Try it online!
Explanation
The code explicitly does the required multiplications and additions.
4L)    % Take first input array implicitly. Remove its first entry
1h     % Append a 1
PYpP   % Cumulative product from right to left
*      % Take second input array implicitly. Multiply the two arrays element-wise
s      % Sum of resulting array. Implicitly display

MATL, 9 bytes
PiPZ}N$X]

This uses 1-based indexing (now allowed by the challenge), which is the natural choice in MATL.
To compare with the test cases in the challenge, add 1 to each entry in the input index vector, and subtract 1 from the output.
Try it online!
Explanation
The code is based on the builtin X] function, which converts multidimensional indices to a single, linear index (like Matlab or Octave's sub2ind function).
P      % Take dimension vector implicitly. Reverse
iP     % Take vector of indices. Reverse
Z}     % Split vector into its elements
N$X]   % Convert indices to linear index (`sub2ind` function). Implicitly display

Julia, 29 27 bytes
x%y=prod(x)÷cumprod(x)⋅y

Try it online!

Python, 85 bytes
lambda a,b:sum(b[i]*eval('*'.join(str(n)for n in a[i+1:])or'1')for i in range(len(a)))

I'll probably get my butt kicked by the better python golfers out there.

Python 3.5, 69
lambda d,i:sum(eval("*".join(map(str,[z,*d])))for z in i if d.pop(0))

Test here

Nice answer! Much better than mine.

@DrGreenEggsandHamDJ I stole the eval method from your solution :)

Haskell, 34 bytes
a#b=sum$zipWith(*)(0:b)$scanr(*)1a

Usage example: [10,10,4,62,7] # [1,2,3,4,5] -> 22167.
How it works:
      scanr(*)1a  -- build partial products of the first parameter from the right,
                  -- starting with 1, e.g. [173600,17360,1736,434,7,1]
    (0:b)         -- prepend 0 to second parameter, e.g. [0,1,2,3,4,5]
  zipWith(*)      -- multiply both lists elementwise, e.g. [0,17360,3472,1302,28,5]
sum               -- calculate sum

C++, 66 bytes
A quick macro:
#include<stdio.h>
#define F(d,i) int x d;printf("%d",&x i-(int*)x)

Use like:
int main(){
    F([5][1][10], [3][0][7]);
}

This may be a bit of an abuse of the rules. Creates an array with the given size, than checks to see how far the given indexes offset the pointer. Outputs to STDOUT.
This feels so dirty... But I just love the fact that this is valid.

Octave, 58 54 bytes
Thanks to @AlexA. for his suggestion, which removed 4 bytes
@(d,i)reshape(1:prod(d),flip(d))(num2cell(flip(i)){:})

Input and output are 1-based. To compare with the test cases, add 1 ot each entry in the input and subtract 1 from the output.
This is an anonymous function. To call it, assign it to a variable.
Try it here.
Explanation
This works by actually building the multidimensional array (reshape(...)), filled with values 1, 2, ... in linear order (1:prod(d)), and then indexing with the multidimensional index to get the corrresponding value.
The indexing is done by converting the input multidimensional index i into a cell array (num2cell(...)) and then to a comma-separated list ({:}).
The two flip operations are needed to adapt the order of dimensions from C to Octave.

why does reshape have a second pair of parenthesis isnt that non syntactic?

@Agawa001 Do you mean a second pair after reshape? That's non syntactic in Matlab, but accepted in Octave. It works as an index

oh Octave!! that must be better and more ergonomic than matlab , tha,ks for enlightenment.

@Agawa001 It can also lead to some confusion, though

A tip for anonymous functions in example code: I use @(...) ... in the first line of my code, followed by f = ans; in the second. This makes the length of the first line equal to the number of bytes to report.

@bers In that case, why not just skip f and call the function using ans as its name?

What a nice idea! Becomes more difficult when you evaluate multiple examples in a row, but should be perfectly valid for a single one.

Mathematica, 27 bytes
#~FromDigits~MixedRadix@#2&

An unnamed function which takes the list of indices as the first argument and the list of dimensions second. Based on the same observation as Dennis's APL answer that computing the index is really just a mixed-base conversion.

CJam, 7 bytes
0q~z+:b

Try it online!
How it works
0        e# Push 0 on the stack.
 q       e# Read and push all input, e.g., "[[10 10 4 62 7] [1 2 3 4 5]]".
  ~      e# Eval, pushing [[10 10 4 62 7] [1 2 3 4 5]].
   z     e# Zip, pushing [[10 1] [10 2] [4 3] [62 4] [7 5]].
    +    e# Concatenate, pushing [0 [10 1] [10 2] [4 3] [62 4] [7 5]]
     :b  e# Reduce by base conversion.
         e# [10 1] in base    0 is    0 * 10 + 1 = 1.
         e# [10 2] in base    1 is    1 * 10 + 2 = 12.
         e# [ 4 3] in base   12 is   12 *  4 + 3 = 51.
         e# [62 4] in base   51 is   51 * 62 + 4 = 3166.
         e# [ 7 5] in base 3166 is 3166 *  7 + 5 = 22167.

Give us a chance, Dennis! :D

Haskell, 47 bytes
Two equal length solutions:
s(a:b)(x:y)=a*product y:s b y
s _ _=[]
(sum.).s

Called like: ((sum.).s)[4,2][5,10].
Here's an infix version:
(a:b)&(x:y)=a*product y:b&y
_ & _=[]
(sum.).(&)

Octave, 47/43/31 bytes
@(d,i)sub2ind(flip(d),num2cell(flip(i+1)){:})-1
Test it here.
Having said that, as it was asked in a comment, 1-based indexing was said to be OK when this is natural to the language being used. In this case, we can save 4 bytes:
@(d,i)sub2ind(flip(d),num2cell(flip(i)){:})
In analogy, I argue that if the objective of the code is to linearly index an array within that language, the whole flipping around and accounting for MATLAB/Octave's column major order should not be necessary, either. In that case, my solution becomes
@(d,i)sub2ind(d,num2cell(i){:})
Test that one here.

Hello, and welcome to PPCG! Great answer!

Mathematica, 47 bytes
Fold[Last@#2#+First@#2&,First@#,Rest/@{##}]&

(Unicode is U+F3C7, or \[Transpose].) For this, I rewrote the expression as Dn(Dn-1( ⋯ (D3(D2S1 + S2) + S3) ⋯ ) + Sn-1) + Sn. Just Folds the function over both lists.

Actually, 13 bytes
;pX╗lr`╜tπ`M*

Try it online!
This program takes the list of indices as the first input and the list of dimensions as the second input.
Explanation:
;pX╗lr`╜tπ`M*
;pX╗            push dims[1:] to reg0
    lr`   `M    map: for n in range(len(dims)):
       ╜tπ        push product of last n values in reg0
            *   dot product of indices and map result

Racket 76 bytes
(λ(l i(s 0))(if(null? i)s(f(cdr l)(cdr i)(+ s(*(car i)(apply *(cdr l)))))))

Ungolfed:
(define f
  (λ (ll il (sum 0))
    (if (null? il)
        sum
        (f (rest ll)
           (rest il)
           (+ sum
              (* (first il)
                 (apply * (rest ll))))))))

Testing:
(f '(5 10) '(4 2))
(f '(10 10 4 62 7) '(1 2 3 4 5))
(f '(5 1 10) '(3 0 7))

Output:
42
22167
37

Javascript, 119 79 bytes
x=(d,i)=>{a=0;for(m in d){m*=1;a+=i[m];if(m!=i.length-1){a*=d[m+1];}}return a;}

Try it online!

Nice answer! You can save at least 20 bytes by using an arrow function, and leaving out the var.

C#, 73 bytes
d=>i=>{int n=d.Length,x=0,y=1;for(;n>0;){x+=y*i[--n];y*=d[n];}return x;};

Full program with test cases:
using System;

namespace IndexOfAMultidimensionalArray
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<int[],Func<int[],int>>f= d=>i=>{int n=d.Length,x=0,y=1;for(;n>0;){x+=y*i[--n];y*=d[n];}return x;};

            int[] dimensions, indices;
            dimensions =new int[]{5, 10};
            indices=new int[]{4,2};
            Console.WriteLine(f(dimensions)(indices));      //42

            dimensions=new int[]{10, 10, 4, 62, 7};
            indices=new int[]{1, 2, 3, 4, 5};
            Console.WriteLine(f(dimensions)(indices));      //22167

            dimensions=new int[]{5, 1, 10};
            indices=new int[]{3, 0, 7};
            Console.WriteLine(f(dimensions)(indices));      //37

            dimensions=new int[]{6, 6, 6, 6, 6, 6, 6, 6, 6, 6};
            indices=new int[]{3, 1, 5, 5, 3, 0, 5, 2, 5, 4};
            Console.WriteLine(f(dimensions)(indices));      //33570178
        }
    }
}

Perl 6, 39 bytes
->\d,\i{sum i.map:{[×] $_,|d[++$ ..*]}}

A rather naive golf here, just squished a anonymous sub.
Perl 6 has an anonymous state variable $ which is useful for creating a counter in a loop (eg, using post-increment $++ or pre-increment ++$).
I pre-increment this state variable to increment the starting index of the dimension array slice inside a map.
Here's a ungolfed function that creates the sub-lists
sub md-index(@dim, @idx) {
    @idx.map(-> $i { $i, |@dim[++$ .. *] })
}
say md-index([10, 10, 4, 62, 7], [1, 2, 3, 4, 5]);
# OUTPUT: ((1 10 4 62 7) (2 4 62 7) (3 62 7) (4 7) (5))

Then it's just a matter of reducing the sub-lists with the multiplication  (×) operator, and suming the results.
sub md-index(@dim, @idx) {
    @idx.map(-> $i { [×] $i, |@dim[++$ .. *] }).sum
}
say md-index([10, 10, 4, 62, 7], [1, 2, 3, 4, 5]);
# OUTPUT: 22167

Perl, 71 bytes
sub{$s+=$_[1][-$_]*($p*=$_[0][1-$_])for($p=$_[0][$s=0]=1)..@{$_[0]};$s}

Ungolfed:
sub {
    my $s = 0;
    my $p = 1;

    $_[0]->[0] = 1;
    for (1 .. @{$_[1]}) {
        $p *= $_[0]->[1 - $_];
        $s += $_[1]->[-$_] * $p;
    }

    return $s;
}

C++17, 133 115 bytes
-18 bytes for using auto...
template<int d,int ...D>struct M{int f(int s){return s;}int f(int s,auto...S){return(s*...*D)+M<D...>().f(S...);}};

Ungolfed:
template <int d,int ...D> //extract first dimension
struct M{
 int f(int s){return s;} //base case for Sn
 int f(int s, auto... S) { //extract first index
  return (s*...*D)+M<D...>().f(S...);
  //S_i * D_(i+1) * D(i+2) * ... + recursive without first dimension and first index
 }
};

Usage:
M<5,10>().f(4,2)
M<10,10,4,62,7>().f(1,2,3,4,5)

Alternative, only functions, 116 bytes
#define R return
#define A auto
A f(A d){R[](A s){R s;};}A f(A d,A...D){R[=](A s,A...S){R(s*...*D)+f(D...)(S...);};}

Ungolfed:
auto f(auto d){
  return [](auto s){
   return s;
  };
}
auto f(auto d, auto...D){
  return [=](auto s, auto...S){
    return (s*...*D)+f(D...)(S...);
  };
}

Usage:
f(5,10)(4,2)
f(10,10,10)(4,3,2)
f(10,10,4,62,7)(1,2,3,4,5)


text:
Laver table computations and an algorithm that is not known to terminate in ZFC
The Laver tables provide examples of programs which have not been shown to terminate in the standard axiomatic system of mathematics ZFC but which do terminate when one assumes very large cardinal axioms.
Introduction
The classical Laver tables An are the unique finite algebras with underlying set {1,...,2n} and an operation * that satisfies the identity x * (y * z)=(x * y) * (x * z) and where x*1=x+1 for x<2n and where 2n*1=1.
More information about the classical Laver tables can be found in the book Braids and Self-Distributivity by Patrick Dehornoy.
Challenge
What is the shortest code (in bytes) that calculates 1*32 in the classical Laver tables and terminates precisely when it finds an n with 1*32<2n? In other words, the program terminates if and only if it finds an n with 1*32<2n but otherwise it runs forever.
Motivation
A rank-into-rank cardinal (also called an I3-cardinal) is an extremely large level of infinity and if one assumes the existence of a rank-into-rank cardinal, then one is able to prove more theorems than if one does not assume the existence of a rank-into-rank cardinal. If there exists a rank-into-rank cardinal, then there is some classical Laver table An where 1*32<2n. However, there is no known proof that 1*32<2n in ZFC. Furthermore, it is known that the least n where 1*32<2n is greater than Ack(9,Ack(8,Ack(8,254)))(which is an extremely large number since the Ackermann function Ack is a fast growing function). Therefore, any such program will last for an extremely long amount of time.
I want to see how short of a program can be written so that we do not know if the program terminates using the standard axiomatic system ZFC but where we do know that the program eventually terminates in a much stronger axiomatic system, namely ZFC+I3. This question was inspired by Scott Aaronson's recent post in which Aaronson and Adam Yedidia have constructed a Turing machine with under 8000 states such that ZFC cannot prove that the Turing machine does not terminate but is known not to terminate when one assumes large cardinal hypotheses.
How the classical Laver tables are computed
When computing Laver tables it is usually convenient to use the fact that in the algebra An, we have 2n * x=x for all x in An.
The following code calculates the classical Laver table An

# table(n,x,y) returns x*y in An
table:=function(n,x,y)
if x=2^n then return y;
elif y=1 then return x+1;
else return table(n,table(n,x,y-1),x+1); fi; end;

For example, the input table(4,1,2) will return 12.
The code for table(n,x,y) is rather inefficient and it can only compute in the Laver table A4 in a reasonable amount of time. Fortunately, there are much faster algorithms for computing the classical Laver tables than the ones given above.

Welcome to PPCG! Great post!

According to Wikipedia, Ack(9,Ack(8,Ack(8,254))) is a lower bound on n for which the period exceeds 16. For that, we can check 116 rather than 132. I will amend my program accordingly.

John Tromp. Thanks for pointing that out. I now realize that I made that typo and wrote 132<2^n instead of 116<2^n in the question . Nevertheless, the question still makes sense whether one uses 16 or 32 (or even 64), and an answer where one uses 32 would be just as theoretically interesting for me as an answer where one uses 16.

Is this question inspired by http://www.scottaaronson.com/blog/?p=2741 ?

Lembik. Yes. The question was inspired by Scott Aaronson's blog post p=2725.

I've started writing up a Turing machine to do this, and I think I've spotted an out-by-factor-of-two error. Didn't Dougherty prove that Ack(9,Ack(8,Ack(8,254))) is a lower bound for the first table in which the first row has period 32, i.e. where 1*16 < 2^n?

Peter Taylor. Yes. You are correct. I made a typo, and I should have written 116<2^n instead of 132<2^n. Such a Turing machine sounds very interesting. I conjecture that such a Turing machine will be about as easy to describe as a Turing machine for the Ackermann function, so I conjecture that one could use around 20-something states and two symbols to construct a Turing machine that terminates if and only if 1*32<2^n in the n-th classical Laver table for some n.

@Peter Taylor. Also, is there known golfing language for Turing machines? If so, then a Turing machine could be compared with the answers given here already (and such a golfing language should be easy to describe). Let me know when you have constructed such a Turing machine.

If you have a 20-state 2-symbol machine for Ackermann then please give me a link, because I can probably steal some ideas from it. I have 44 states to compute table(n,x,y), and I think it'll take between 25 and 30 states to set up the constants and the outer loop. The only direct TM representation I can find on esolangs.org is http://esolangs.org/wiki/ScripTur and it's not really that golfy.

At googology, a 23 state 2-symbol Turing machine that runs for longer than Graham's number steps before terminating has been constructed. In fact, there they have a 13 state Turing machine that exhibits Ackermann growth.

Should I ask another question asking for a Turing machine that runs as long as 1*16=2^n but halts otherwise (I am new to this site) or are both questions too similar?

Also, if anyone is interested, a Turing machine for computing the classical Laver tables can probably be slightly modified to a Turing machine that computes certain generalized Laver tables simply by adding more symbols to the Turing machine.

If A is a set, then the underlying set of the generalized Laver table (A^(2^n))^+ is the set of non-empty strings over the alphabet A of length at most 2^n and  is given a unique self-distributive operation such that x*y=y whenever |x|=2^n and where y*a=ya whenever |y|<2^n and |a|=1. In other words, the generalized Laver table (A^(2^n))^+ is like the classical Laver table A_n but where we work with non-empty strings of length less than 2^n instead of natural numbers at most 2^n.

http://cheddarmonk.org/papers/laver.pdf is as much as I expect to get done this week, because I'm going to be travelling.

Binary Lambda Calculus, 215 bits (27 bytes)
\io. let
  zero = \f\x. x;
  one = \x. x;
  two = \f\x. f (f x);
  sixteen = (\x. x x x) two;
  pred = \n\f\x. n (\g\h. h (g f)) (\h. x) (\x. x);
  laver = \mx.
    let laver = \b\a. a (\_. mx (b (laver (pred a))) zero) b
    in laver;
  sweet = sixteen;
  dblp1 = \n\f\x. n f (n f (f x)); -- map n to 2*n+1
  go2 = \mx. laver mx sweet mx (\_. mx) (go2 (dblp1 mx));
in go2 one

compiles to (using software at https://github.com/tromp/AIT)
000101000110100000010101010100011010000000010110000101111110011110010111
110111100000010101111100000011001110111100011000100000101100100010110101
00000011100111010100011001011101100000010111101100101111011001110100010

This solution is mostly due to https://github.com/int-e

I'm not sure how you got your score but by default submissions should be scored according to the number of bytes in the code. I count 375 bytes for this submission. You should also include the language name and optionally a link to an interpreter for the language.

You should probably include the exact code of length 234 bits in your post.

The encoding can be found on Wikipedia. There's also a link to this interpreter (not tested). These should be checked, though, and the binary encoding should also be in the post.

For compiled languages, we score the code written by the user--not the number of bytes in the generated binary.

@AlexA. That's not necessary... any form of the code that can be understood by a compiler or interpreter is fine.

CJam (36 32 bytes)
1{2*31TW$,(+a{0X$j@(@jj}2j)W$=}g

In practice, this errors out quite quickly because it overflows the call stack, but on a theoretical unlimited machine it is correct, and I understand that to be the assumption of this question.

The code for table(n,x,y) is rather inefficient and it can only compute in the Laver table A4 in a reasonable amount of time.

is not actually correct if we cache computed values to avoid recomputing them. That's the approach I've taken, using the j (memoisation) operator. It tests A6 in milliseconds and overflows the stack testing A7 - and I've actually deoptimised table in the interests of golfing.
Dissection
If we assume that n is understood from the context, instead of
f(x,y) =
    x==2^n ? y :
    y==1 ? x+1 :
    f(f(x,y-1),x+1)

we can remove the first special case, giving
f(x,y) =
    y==1 ? x+1 :
    f(f(x,y-1),x+1)

and it still works because
f(2^n, 1) = 2^n + 1 = 1

and for any other y,
f(2^n, y) = f(f(2^n, y-1), 1) = f(2^n, y-1) + 1

so by induction we get f(2^n, y) = y.
For CJam it turns out to be more convenient to reverse the order of the parameters. And rather than using the range 1 .. 2^n I'm using the range 0 .. 2^n - 1 by decrementing each value, so the recursive function I'm implementing is
g(y,x) =
    y==0 ? x+1
         : g(x+1, g(y-1, x))

1           e# Initial value of 2^n
{           e# do-while loop
  2*        e#   Double 2^n (i.e. increment n)
  31T       e#   table(n,1,32) is g(31,0) so push 31 0
  W$,(+a    e#   Set up a lookup table for g(0,x) = x+1 % 2^n
  {         e#   Memoisation function body: stack is 2^n ... y x
    0X$j    e#     Compute g(0,x) = x+1 % 2^n
            e#     Stack is 2^n ... y x (x+1%2^n)
    @(      e#     Bring y to top, decrement (guaranteed not to underflow)
            e#     Stack is 2^n ... x (x+1%2^n) (y-1%2^n)
    @jj     e#     Rotate and apply memoised function twice: g(x+1,g(y-1,x))
  }
  2j        e#   Memoise two-parameter function
            e#   Stack: 2^n g(31,0)
  )W$=      e#   Test whether g(31,0)+1 is 2^n
}g          e# Loop while true

Pyth, 33 bytes
.N?qT^2NY?tY:N:NTtYhThT<:T1 32^2T

Try it online! (Obviously the testing part is not included here.)

What loop? Also, what does fi in the code mean?

Javascript, 53 bytes
for(M=0;!g(1,31);M-=~M)g=(x,y)=>y?g(g(x,y-1),x):x+1&M

Define g(x,y)=x*(y+1) on \$F_{2^n}\$, aka. \$2^n\$ is written as 0

source: Stack Exchange

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

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

sort: votes


text:
Write a brain-flak classic interpreter!
Brain-Flak (a cross between Brainf**k and Flak-Overstow) is a stack-based esoteric language. Since this challenge was posted, the language has evolved and updated, but this first revision of the language is known as "brain-flak classic".
You must write a program or function that takes a string of Brain-Flak classic code, and evaluates it. It will also take a (possible empty) list of integers. There are the inputs to the Brain-Flak classic program.
The Language
Brain-Flak has two stacks, known as 'left' and 'right'. The active stack starts at left. If an empty stack is popped or peeked, it will return 0. There are no variables. When the program starts, each input is pushed on to the active stack in order (so that the last input is on top of the stack).
The only valid characters in a Brain-Flak program are ()[]{}<>, and they must always be balanced. If there are invalid characters, or the brackets are unmatched, you get undefined behaviour. Anything is valid.
There are two types of functions: Nilads and Monads. A nilad is a function that takes 0 arguments. Here are all of the nilads:

() +1.
[] -1.
{} Pop the active stack.
<> Toggle the active stack.

These are concatenated together when they are evaluated. So if we had a '3' on top of the active stack, this snippet:
()(){}

would evaluate to 1 + 1 + active.pop() which would evaluate to 5. <> evaluates to 0.
The monads take one argument, a chunk of Brain-Flak code. Here are all of the monads:

(n) Push 'n' on the active stack.
[n] Print 'n' as an int and a newline.
{foo} While active.peek() != 0, do foo. Evaluates to 0¹.
<foo> Execute foo, but evaluate it as 0.

These functions will also return the value inside of them, so
(()()())

Will push 3 and
[()()()]

Will print 3 but
[(()()())]

Will print and push 3.
When the program is done executing, each value left on the active stack is printed as an integer, with a newline between. Values on the other stack are ignored.
Rules:

Your program must support numbers in the (-128, 127) range, and a stack size of at least 255. If you support larger, great.

Underflow/overflow is undefined.

Sample IO:
The empty program:
Input: None
Output: None
Addition. Source:
({}{})

Input:
2, 3

Output:
5

Subtraction. Source:
({}<>){({}[])<>({}[])<>}<>

Input:
2, 3

Output:
-1

Multiplication. Source:
({}<>)<>({}[]){({}[])<>(({}))<>}<>{({}<>{})<>}<>

Input:
7, 8

Output:
56

Fibonacci. Source:
<>((()))<>{({}[])<>({}<>)<>(({})<>({}<>))<>}<>

Input:
5

Output:
13
8
5
3
2
1
1

Truth machine
{[({})]}

Standard loopholes apply, and the shortest answer in bytes wins.

¹: This was actually a mistake on my part. {...} should evaluate to the sum of all of it's runs, which is IMO one of the coolest features of brain-flak. However, for the purposes of this challenge, assume that {...} evaluates as 0.

Is there a rule concerning the minimum integer value the program needs to handle?

What does the monad {...} evaluate to?

In what order are the subtraction arguments? I'm getting the negation of what I expect.

@Neil Sorry about that. The monad {...} evaluates to 0. Also, the arguments are pushed in order, so 2 is pushed, then 3 is pushed, so when the program starts, the second input (3) is on top of the stack. I'll clarify both of those in the post.

Are there any rules for over/underflow? If my numbers go from (-128, 127) is (127)()[{}] undefined?

@AndrewPiliser Yes, that is undefined. So is (-128)[]

Brainflak syntax highlighter :D

Can you add a test case with nested loops?

Difference between {foo} and  is not clear. Can you give an example for this?

@DLosc I know this is almost a year later, but yes that is the correct truth machine. I don't know how I missed that.

Can valid syntax be assumed?

@user230118  If there are invalid characters, or the brackets are unmatched, you get undefined behaviour. Anything is valid. So yes, you may assume valid syntax.

What exactly is Flak-Overstow? I can't find it on esolangs or Google or GitHub, the closest thing I can find is this.

@mdxf Hahaha, I suppose that one needs some explanation. It's a spoonerism of Stack Overflow that I came up with. I explained it in more detail here.

Pip -n, 151 148 101 98 bytes
YRVg;VqR^"{}()<>[]";,8R J,8<>2AL,8("POy|i o0Syl1v0W@y{ }1yPU$+[ ]&@y0 1P$+[ ]"R0" (V{"R1"i}) "^s)y

Takes the list of inputs as command-line arguments and the Brain-Flak code from (a line of) stdin. Try it online!
Edit: Saved a whole lot of bytes over my original approach by switching to a translate-and-eval strategy.
Ungolfed and commented
This version also includes some debug output showing the Pip code that results from the translation, as well as the stack contents after execution.
;;; Setup ;;;

; y is the active stack, l is the off-stack
; y is initialized from command-line arguments
y:RVg   (reversed to put the last input at the top)
; l is preset to empty list by default

; p is the program (read from stdin)
p:q

; Translate from braces to numbers 0-7 (we do this so that the
; later replacement step won't try to replace the braces in the
; Pip code)
p R: ^"()[]{}<>" 0,8

;;; Replace nilads with the appropriate code ;;;

; () => o (variable preset to 1)
p R: 01 "o"

; [] => v (variable preset to -1)
p R: 23 "v"

; {} => POy|i
; Pop y; return that value OR i (variable preset to 0)
p R: 45 "POy|i"

; <> => (V{Syli})
; Eval the code Syl to swap stacks y and l, then return i (i.e. 0)
p R: 67 "(V{Syli})"

;;; Replace monads with the appropriate code ;;;

; ( ) => yPU$+[ ]&@y
; Sum ($+) the inside and push (PU) the sum onto y; return
; the just-pushed value, which is the first element of y (@y)
; y will always be truthy (nonempty), since we just pushed a value onto it
p R: 0 "yPU$+["
p R: 1 "]&@y"

; [ ] => P$+[ ]
; Sum ($+) the inside, print (P) the sum, and return it
p R: 2 "P$+["
p R: 3 "]"

; { } => (V{W@y{ }i})
; Eval the code W@y{ }, which wraps the inside in curly braces
; and runs it while (W) the first element of y (@y) is truthy
; (i.e. not zero, and not nil from an empty stack)
; Then return i (i.e. 0)
p R: 4 "(V{W@y{"
p R: 5 "}i})"

; < > => (V{ i})
; Eval the inside, then return i (i.e. 0)
p R: 6 "(V{"
p R: 7 "i})"

; Debug: print the resulting translated code and a blank line
Pp.n

;;; Run the code ;;;

; Eval the translated code
(Vp)

; Output the active stack, newline-separated
PyJn

; Debug: print the active stack and the off-stack
P"Active stack: ".RPy
"Off-stack: ".RPl

Is pip newer than this challenge?

@DJMcMayhem Nope! Nor am I using any features newer than the challenge.

Brain-Flak Classic, 1271 1247 1239 bytes
<>(()){<>((([][][][][])<(((({}){})(({})({}))[])({}(({})({}({})({}{}(<>)))))[])>{()<{}>}{})<{{}}{}>())}{}<>(<(({()(((<>))<>)}{}{<({}(([][][])((({})({}))[]{})){})>((){[]<({}{})((){[]<({}{}<>((({})({})){}{}){})(<>)>}{}){{}{}<>(<({}{}())>)(<>)}>}{}){(<{}{}{}((<>))<>>)}{}}<>)<{({}[]<({}<>)<>{(<{}>)<>{<>({}[])}{}<>({}<>)(<>)}{}>)}{}<>>)>)<>{(({}[])(){(<{}>)<><(({})[])>[][][][]{()()()()(<{}>)}{}<>}{}<>)<>}<>{}{(({})<({()<<>({}<>)>}{})>([]))((){[](<(({}()()(<>))()()()){(<{}>)<>}>)}{}<>){{}((){[]<({}())((){[]<({}())((){[]<({}())((){[]<({}())((){[]<({}())((){[]<({}())((){[](<{}<>{({}<>)<>}{}(({}))({<{}({}<>)<>>{}(<<>({}[]<>)>)}<><{({}<>)<>}>{})>)}{}){{}{}(<([])>)}>}{}){{}<>{({}<>)<>}{}((({})())<{({}[]<({}<>)<>>)}>{}){({}[]<><({}<><({()<({}[]<({}<>)<>>)>}{}<>)><>)<>({()<({}[]<({}<>)<>>)>}{}<>)>)}<>(<{({}<>)<>}>)}>}{}){{}{}(<(())>)}>}{}){(<{}{}>)<>{({}<>)<>}{}(({}))({<{}({}<>)<>>({})(<<>({}<>)>)}<><{({}<>)<>}>){{}([][][])<>(((<{}>)<>))}}>}{}){{}(<([{}])>)}>}{}){{}((<{}>))}>}{}){{}(({})(<()>)<<>{({}<>)<>}{}({}()<>)<>>)<>(<({}<>)>)<>{({}<>)<>}}{}(<({}<({}<>)<>>{})<>({}<>)>)<>(<({}())>)}{}({}<{({}[]<({}<>)<>>)}{}>){((({}[]<>){(<{}({}<>)>)}{}())<{({}()<({}<>)<>(({})[])>{[][](<{}>)}{})}{}>()){{}(<>)}}{}}{}{({}[]<[{}]>)}{}{({}[]<{}>)}{}

Try it online!
+4 bytes from fixing a bug with the condition in the {...} monad, and -36 bytes from various golfs.
1238 bytes of code, +1 byte for the -a flag (which can be combined with the language flag).
This now evaluates {...} as zero per the challenge specification.  Note that Brain-Flak itself has evaluated {...} as the sum of all runs since the May 7, 2016 bugfix two days before this challenge was posted.
The following code interprets Brain-Flak Classic correctly, with {...} as the sum of all runs.  The only difference between the two interpreters is the placement of one {} nilad.
<>(()){<>((([][][][][])<(((({}){})(({})({}))[])({}(({})({}({})({}{}(<>)))))[])>{()<{}>}{})<{{}}{}>())}{}<>(<(({()(((<>))<>)}{}{<({}(([][][])((({})({}))[]{})){})>((){[]<({}{})((){[]<({}{}<>((({})({})){}{}){})(<>)>}{}){{}{}<>(<({}{}())>)(<>)}>}{}){(<{}{}{}((<>))<>>)}{}}<>)<{({}[]<({}<>)<>{(<{}>)<>{<>({}[])}{}<>({}<>)(<>)}{}>)}{}<>>)>)<>{(({}[])(){(<{}>)<><(({})[])>[][][][]{()()()()(<{}>)}{}<>}{}<>)<>}<>{}{(({})<({()<<>({}<>)>}{})>([]))((){[](<(({}()()(<>))()()()){(<{}>)<>}>)}{}<>){{}((){[]<({}())((){[]<({}())((){[]<({}())((){[]<({}())((){[]<({}())((){[]<({}())((){[](<{}<>{({}<>)<>}{}(({}))({<{}({}<>)<>>{}(<<>({}[]<>)>)}<><{({}<>)<>}>{})>)}{}){{}{}(<([])>)}>}{}){{}<>{({}<>)<>}{}((({})())<{({}[]<({}<>)<>>)}>{}){({}[]<><({}<><({()<({}[]<({}<>)<>>)>}{}<>)><>)<>({()<({}[]<({}<>)<>>)>}{}<>)>)}<>(<{({}<>)<>}>)}>}{}){{}{}(<(())>)}>}{}){(<{}>)<>{({}<>)<>}{}(({}))({<{}({}<>)<>>({})(<<>({}<>)>)}<><{({}<>)<>}>{}){{}([][][])<>(((<{}>)<>))}}>}{}){{}(<([{}])>)}>}{}){{}((<{}>))}>}{}){{}(({})(<()>)<<>{({}<>)<>}{}({}()<>)<>>)<>(<({}<>)>)<>{({}<>)<>}}{}(<({}<({}<>)<>>{})<>({}<>)>)<>(<({}())>)}{}({}<{({}[]<({}<>)<>>)}{}>){((({}[]<>){(<{}({}<>)>)}{}())<{({}()<({}<>)<>(({})[])>{[][](<{}>)}{})}{}>()){{}(<>)}}{}}{}{({}[]<[{}]>)}{}{({}[]<{}>)}{}

Try it online!
Input (to either interpreter) is the Brain-Flak Classic program to interpret, then a newline, then a space-separated list of integers.  No validation is performed on the input.  The newline is required, even if the program or input is blank.
The first step is to parse all of the input, starting with the brackets:
# Move to right stack, and push 1 to allow loop to start
<>(())
{
   # While keeping -5 on third stack:
   <>((([][][][][])<

       # Pop bracket or newline k from left stack, and push 0, k-10, k-40, k-60, k-91, k-123 on right stack
       (((({}){})(({})({}))[])({}(({})({}({})({}{}(<>)))))[])

   # Search this list for a zero, and push the number of nonzero entries popped minus 5
   # (thus replacing the 0 if it was destroyed)
   >{()<{}>}{})

   # Remove rest of list, and push the same number plus 1
   # Result is -4 for {, -3 for [, -2 for <, -1 for (, 0 for newline, or 1 for everything else (assumed closing bracket)
   <{{}}{}>())

# Repeat until newline found
}{}<>

Then the integers are parsed.  This wouldn't normally be required, but the input was taken as ASCII.  This does have a silver lining, though: text input allows us to determine the stack height, which simplifies things when we don't have access to the stack height nilad.
Integers are parsed into two numbers on the second stack: one for the absolute value, and one for the sign.  These are then moved back to the first stack.
The interpreted stacks are stored below the code on the first stack in the following order: current stack height, current stack, other stack height, other stack.  The 0 for the other stack height does not need to be pushed at this point, since it will be an implicit zero the first time it is read.
(<((

    # If stack nonempty, register first stack entry.
    {()(((<>))<>)}{}

    # For each byte k of input:
    {

        # Push -3, -13, and k-32
        <({}(([][][])((({})({}))[]{})){})>

        # Evaluate to 1 if space
        # If not space (32):
        ((){[]<

            # If not minus (45):
            ({}{})((){[]<

                # Replace top of right stack (n) with 10*n + (k-48)
                ({}{}<>((({})({})){}{}){})(<>)

            # Else (i.e., if minus):
            >}{}){

                # Remove excess "else" entry and -3
                {}{}

                # Set sign to negative (and destroy magnitude that shouldn't even be there yet)
                <>(<({}{}())>)(<>)}

        # Else (i.e., if space):
        >}{}){

            # Remove working data for byte, and push two more 0s onto right stack
            (<{}{}{}((<>))<>>)

    # Push number of integers found
    }{}}<>)

    # For each integer:
    <{({}[]<

        # Move magnitude back to left stack
        ({}<>)<>

        # If sign is negative, negate
        {(<{}>)<>{<>({}[])}{}<>({}<>)(<>)}{}

    >)}{}

    # Push stack height onto stack
    <>>)

# Push 0
>)

The representation of the code is now moved back to the left stack.  To make things easier later, we subtract 4 from the opening brackets of nilads, so that each operation has a unique integer from -1 to -8.
# For each bracket in the code:
<>{

    # Push k-1 and evaluate to k
    (({}[])()

    # If not closing bracket:
    {

        # Check next bracket (previously checked, since we started at the end here)
        (<{}>)<><(({})[])>

        # Subtract 4 if next bracket is closing bracket
        # Inverting this condition would save 8 bytes here, but cost 12 bytes later.
        [][][][]{()()()()(<{}>)}{}

    <>}{}

    # Push result onto left stack
    <>)

<>}<>{}

The main part of the program is actually interpreting the instructions.  At the start of each iteration of the main loop, the current instruction is at the top of the left stack, everything after it is below it on the same stack, and everything before it is on the right stack.  I tend to visualize this as having a book open to a certain page.
{

    (

        # Get current instruction
        ({})

        # Move all code to left stack, and track the current position in code
        <({()<<>({}<>)>}{})>

        # Push -1, signifying that the code will move forward to just before a matching }.
        # In most cases, this will become 0 (do nothing special) before it is acted upon
        ([])

    # Push instruction minus 1
    )

    # If opening bracket:
    ((){[](<

        # Push instruction+1 and instruction+4
        (({}()()(<>))()()())

        # If instruction+4 is nonzero (not loop monad), replace the earlier -1 with 0 to cancel forward seek
        # This would be clearer as {(<{}>)<>(<{}>)<>}, but that would be unnecessarily verbose
        {(<{}>)<>}

    # Else (i.e., if closing bracket):
    >)}{}<>){

# If closing bracket, parse command
# Post-condition for all: if not moving to {, pop two and push evaluation, 0.
# (For nilads, can assume second from top is 0.)
# If moving to {, pop one, push -3, 0, 0.

        # Seven nested if/else statements, corresponding to eight possible instruction.
        # The "else" statements end with 0 already on the stack, so no need to push a 0 except in the innermost if.
        # Each one beyond the first increments the instruction by 1 to compare the result with 0
        # Each instruction will pop the instruction, leaving only its evaluation (with a 0 on top).
        {}((){[]<
        ({}())((){[]<
        ({}())((){[]<
        ({}())((){[]<
        ({}())((){[]<
        ({}())((){[]<
        ({}())((){[](<

            # -7: pop
            # Pop instruction to reveal existing 0 evaluation
            {}

            # Move code out of the way to access stack
            <>{({}<>)<>}{}

            # Duplicate stack height (only useful if stack height is zero)
            (({}))

            (

                # If stack height nonzero
                {

                    # Save stack height on second stack
                    <{}({}<>)<>>

                    # Pop stack
                    {}

                    # Move stack height back and subtract 1
                    (<<>({}[]<>)>)

                }

                # Move code back to normal position
                <><{({}<>)<>}>{}

            # Evaluate as popped entry (0 if nothing popped)
            )

        # (else)
        >)}{}){

            # -6: -1 nilad
            # Just evaluate as -1
            {}{}(<([])>)

        # (else)
        }>}{}){

            # -5: swap nilad
            # Move code out of the way to access stack
            {}<>{({}<>)<>}{}

            # Number of integers to move: stack height + 1 (namely, the stack height and every entry in the stack)
            ((({})())

            # Move to second stack
            <{({}[]<({}<>)<>>)}>{}

            # Do (stack height + 1) times again
            ){({}[]<><

                # Get stack element
                ({}<><

                    # Move alternate (interpreted) stack to second (real) stack, and push length on top of it
                    ({()<({}[]<({}<>)<>>)>}{}<>)

                # Push current stack element below alternate stack
                ><>)

                # Move alternate stack back above newly pushed element
                <>({()<({}[]<({}<>)<>>)>}{}<>)

            >)}

            # Move code back to normal position
            <>(<{({}<>)<>}>)

        # (else)
        }>}{}){

            # -4: 1
            # Just evaluate to 1
            {}{}(<(())>)

        # (else)
        }>}{}){

            # -3: loop
            # Create zero on stack while keeping existing evaluation
            # This becomes (<{}{}>) in the version that meets the challenge spec
            (<{}>)

            # Move code out of the way to access stack
            <>{({}<>)<>}{}

            # Duplicate stack height
            (({}))

            (

                # If stack height nonzero
                {

                    # Save stack height on second stack
                    <{}({}<>)<>>

                    # Peek at top of stack
                    ({})

                    # Move stack height back
                    (<<>({}<>)>)

                }

                # Move code back to normal position
                <><{({}<>)<>}>

            # Look at peeked entry
            # Remove the {} in the version meeting the challenge spec
            {})

            # If peeked entry is nonzero
            {

                # Replace -3 instruction on third stack
                {}([][][])

                # Replace loop indicator to 0 (to be incremented later to 1)
                <>(((<{}>)

                # Create dummy third stack entry to pop
                <>))

            }

        # (else)
        }>}{}){

            # -2: print
            # Just print evaluation without modifying it
            {}(<([{}])>)

        # (else)
        }>}{}){

            # -1: evaluate as zero
            # Just change evaluation to 0
            {}((<{}>))

        # else
        }>}{}){

            # 0: push
            # Get current evaluation (without modifying it)
            {}(({})

                # Create zero on stack as barrier
                (<()>)

                # Move code out of the way to access stack
                <<>{({}<>)<>}{}

                # Increment stack height and save on other stack
                ({}()<>)<>

            # Push evaluation
            >)

            # Move stack height back (and push zero)
            <>(<({}<>)>)

            # Move code back to normal position
            <>{({}<>)<>}

        }{}

        # Update third stack by adding evaluation to previous entry's evaluation
        # Previous entry's instruction is saved temporarily on left stack
        (<({}<({}<>)<>>{})<>({}<>)>)

        # Increment loop indicator
        # If instruction was loop monad and top of stack was nonzero, this increments 0 to 1 (search backward)
        # Otherwise, this increments -1 to 0 (do nothing)
        <>(<({}())>)

    }{}

    # While holding onto loop indicator
    ({}<

        # Go to immediately after executed symbol
        {({}[]<({}<>)<>>)}{}

    >)

    # If looping behavior:
    {

        # Switch stack and check if searching forward
        ((({}[]<>)

        # If so:
        {

            # Move just-executed { back to left stack, and move with it
            (<{}({}<>)>)

        }{}

        # Either way, we are currently looking at the just-executed bracket.
        # In addition, the position we wish to move to is on the current stack.

        # Push unmodified loop indicator as initial value in search
        ())

        # While value is nonzero:
        <{

            # Add 1
            ({}()

                # Move current instruction to other stack
                <({}<>)<>

                # Check whether next instruction is closing bracket
                (({})[])>

                # If opening bracket, subtract 2 from value
                {[][](<{}>)}{}

            )

        }{}>

        # If searching backward, move back to left stack
        ()){{}(<>)}

    }{}

}

After exiting the main loop, all of the code is on the right stack.  The only things on the left stack are a zero and the two interpreted stacks.  Producing the correct output is a simple matter.
# Pop the zero
{}

# Output current stack
{({}[]<[{}]>)}{}

# Discard other stack to avoid implicit printing
{({}[]<{}>)}{}

:O what the... Ok, bountying immediately. Nice job! :D

Let me get this straight... you created an interpreter for the language that is to be interpreted. YoDawg

OK, why does it only have a 2 digit upvote number?

Good job on correctly implementing the accumulator in {...}, which is the correct behavior for modern brain-flak and (I think) brain-flak classic, however I wrote in the challenge that {...} evaluates as 0. You could probably golf a significant number of bytes of by removing that functionality, although it would be nice to keep the original around because it's technically more correct in general (just wrong for this challenge)

@DJMcMayhem Fixed.  Just don't make me port the entire interpreter to that hypothetical version of Brain-Flak.

APL, 255 257 bytes
b←{S←(⌽⍺)⍬
e←{0=⍴⍵:0
v+∇⊃_ v←∇{r←⊂2↓⍵
'()'≡n←2↑⍵:r,1
'[]'≡n:r,¯1
'{}'≡n:r,{i←⊃⊃⊃S⋄S[1]↓⍨←1⋄i}⍬
'<>'≡n:r,0⊣S⌽⍨←1
r←⊂⍵↓⍨i←0⍳⍨(+\c=⍵)-+\')]>}'['([<{'⍳c←⊃⍵]=⍵
i←1↓¯1↓c←i↑⍵
'('=c←⊃c:r,S[1],⍨←⍺⍺i
'['=c:r,+⎕←⍺⍺i
'{'=c:r,{0≠⊃⊃⊃S:∇e i⋄0}⍬
'<'=c:r,0⊣⍺⍺i}⍵}
⎕←⍪⊃S⊣e⍵}

This takes the program as its right argument, and the program input as its left argument, i.e:
      2 3 b '({}{})'
5
      2 3 b '({}<>){({}[])<>({}[])<>}<>'
¯1
      7 8 b '({}<>)<>({}[]){({}[])<>(({}))<>}<>{({}<>{})<>}<>'
56
      5 b '<>((()))<>{({}[])<>({}<>)<>(({})<>({}<>))<>}<>'
13
 8
 5
 3
 2
 1
 1

Ungolfed version: here.

APL (Dyalog Classic), 146 bytes
↑⍕¨s⊣{⍎⍕1 ¯1'(s↓⍨←1)⊢⊃s' '0⊣s t←t s' 's,⍨←+/∇¨a' '⎕←+/∇¨a' '∇{×⊃s:∇⍺⍺¨a⋄0}0' '0⊣+/∇¨a'[(⊃⍵)+4×⍬≢a←1↓⍵]}¨⍎∊(')',⍨'(',¨⍕¨⍳4)[0,4,⍨'([{<'⍳⍞]⊣s←⌽⎕⊣t←⍬

Try it online!
one Classic interpreting another :)

Python 3, 429 bytes
import re
S='s+=[v];v=0';T='v+=s.pop()';i=0
d={'()':'v+=1','(':S,')':'a+=[v];'+T,'[]':'v-=1','[':S,']':'print(v);'+T,'<>':'a.reverse()','<':S,'>':T,'{}':'v+=0if a[-1]==""else a.pop()','{':S+';while a[-1]:','}':T}
def r(m):global i;t=m.group();i-=(t=='}');s=' '*i;i+=(t=='{');return''.join(s+r+'\n'for r in d[t].split(';'))
def g(c,*a):
 a,s,v=['']+list(a),[],0;exec(re.sub(r'[<({[]?[]})>]?',r,c));
 while a[-1]!="":print(a.pop())

Used like g('[{}{}]', 2, 3)
It uses re.sub to "compile" the brain-flak source to python and then executes the python. (for debuging, replace exec with print to get a listing of the python code)
Properly indenting nested while loops eats up a lot of bytes in the code.

Perl 5.6, 419 414 bytes
I've golfed it a bit but there's probably scope for improvement. Newlines and tabs added here for the sake of a bit of readability:
use Text::Balanced extract_bracketed;
$s=shift;
@a=reverse@ARGV;
sub p
{
    my($c)=@_;
    my$s=0;
    while(my$n=extract_bracketed($c)){
        $s+='()'eq$n||'{}'eq$n&&shift@a;
        $s-='[]'eq$n;
        @t=@a,@a=@i,@i=@t if'<>'eq$n;
        my$m=chop($n);
        $n=substr($n,1);
        if($n){
            p($n)while'}'eq$m&&$a[0];
            p($n)if'}'ne$m;
            $s+=$v,unshift@a,$v if')'eq$m;
            $s+=$v,print"n=$n m=$m v=$v\n"if']'eq$m;
        }
    }
    $v=$s;
}
p($s);
foreach(@a){
    print"$_\n";
}

Python, 616 bytes
Instructions:

Run with python
Input list in [1,2,...] format, then press enter
Paste/write program, then press enter again
Done

Basically, what this program does is recursively "compile" the Brain-flak code into nested lists, and recursively interpret that list. There probably is a way to combine the two...
I'll try and rework the logic later.
y="([{<)]}>"
w,z,g=print,len,input
def c(s):
 if z(s)<1:return[]
 t,i,o=[],1,0
 t.append(y.index(s[0]))
 while z(t)>0:
  x=y.index(s[i])
  if x<4:t.append(x)
  else:o=t.pop()
  i+=1
 r=[[o,c(s[1:i-1])]]
 r.extend(c(s[i:]))
 return r
p=lambda t:t.pop()if z(t)>0 else 0
k=lambda t:t[z(t)-1]if z(t)>0 else 0
r,l=[],eval(g())
a=l
def i(u):
 v=0
 global a
 for t,n in u:
  if t<1:
   if n:o=i(n);v+=o;a.append(o)
   else:v+=1
  if t==1:
   if n:o=i(n);v+=o;w(o)
   else:v-=1
  if t==2:
   if n:
    while k(a)!=0:i(n)
   else:v+=p(a)
  if t>2:
   if n:i(n)
   elif a==l:a=r
   else:a=l
 return v
i(c(g()))
for n in a:w(n)

Python 2, 361, 348 bytes
c,s=input();s=s,[]
a=s[0]
def w():global a,s;s=s[::-1];a=s[0];return 0
def p(c):a.append(c);return c
def n(c):print c;return c
z=lambda c:0
def l(f):
 global a
 while a and a[-1]:f()
 return 0
for x,y in zip("() ( [] {} <> [ < { } ] >".split(),"+1 +p( -1 +(len(a)and(a.pop())) +w() +n( +z( +l(lambda: ) ) )".split()):c=c.replace(x,y)
exec c
print a

Try it online!
-13 bytes saved thanks to @Mr. Xcoder!

Python 3, 290 bytes
def f(s,*a):
 for t in '],) },) >,) [,+3 (,+2 2),1 3),-1 {),+(lAorA).pop() <),<l.reverse()) 2,LlA.appendK 3,LprintK {,+cL <,+L0)( L,(lambda*n: K,(*n)or+nA)( A,[0]'.split():s=s.replace(*t.split(','))
 l=[[*a],[]];c=lambda g:[0,*l[0]][-1]and g()+c(g);exec(s,locals());[*map(print,l[0][::-1])]

Try it online!

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


text:
How many steps does it take from n to 1 by subtracting the greatest divisor?
Inspired by this question over at Mathematics.

The Problem

Let n be a natural number ≥ 2. Take the biggest divisor of n – which is different from n itself – and subtract it from n. Repeat until you get 1.

The Question
How many steps does it take to reach 1 for a given number n ≥ 2.
Detailed Example

Let n = 30.

The greatest divisor of:
1.   30 is 15  -->  30 - 15 = 15
2.   15 is  5  -->  15 -  5 = 10
3.   10 is  5  -->  10 -  5 =  5
4.    5 is  1  -->   5 -  1 =  4
5.    4 is  2  -->   4 -  2 =  2
6.    2 is  1  -->   2 -  1 =  1

It takes 6 steps to reach 1.
Input

Input is an integer n, where n ≥ 2.
Your program should support input up to the language's maximum integer value.

Output

Simply output the number of steps, like 6.
Leading/trailing whitespaces or newlines are fine.

Examples
f(5)        --> 3
f(30)       --> 6
f(31)       --> 7
f(32)       --> 5
f(100)      --> 8
f(200)      --> 9
f(2016^155) --> 2015

Requirements

You can get input from STDIN, command line arguments, as function parameters or from the closest equivalent.
You can write a program or a function. If it is an anonymous function, please include an example of how to invoke it.
This is code-golf so shortest answer in bytes wins.
Standard loopholes are disallowed.

This series can be found on OEIS as well: A064097

A quasi-logarithm defined inductively by a(1) = 0 and a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if m,n > 1.

clarify the input requirement in languages with native arbitrary precision integers?

@Sparr I would say, you should at least support up to 2^32 - 1. The rest is up to you and your system. Hope, this is what you meant with your question.

I like how the title sums it all up

Jelly, 9 bytes
ÆṪÐĿÆFL€S

Try it online! or verify all test cases.
Background
The definition of sequence A064097 implies that
$$\small{a(p)-a(p-1)=1}\text{ for all primes }p\text{ and }a(km)=a(k)+a(m)\text{ for all }k,m\in \mathbb{N}$$
By Euler's product formula
$$\small{\varphi(n)=n\prod_{p|n}\left(1-{1\over p}\right)=n\prod_{p|n}{{p-1}\over p}}$$
where \$\varphi\$ denotes Euler's totient function and \$p\$ varies only over prime numbers.
Combining both, we deduce the property
$$\small{a(\varphi(n))=a\left(n\prod_{p|n}{{p-1}\over p}\right)=a(n)+\sum_{p|n}\left(a(p-1)-a(p)\right)=a(n)-\sum_{p|n}{1=a(n)-\omega(n)}}$$
where \$\omega\$ denotes the number of distinct prime factors of \$n\$.
Applying the resulting formula \$k + 1\$ times, where \$k\$ is large enough so that \$\varphi^{k+1}(n)=1\$, we get
$$\small{
\begin{aligned}
0=a\left(\varphi^{k+1}(n)\right)=a\left(\varphi^k(n)\right)-\omega\left(\varphi^k(n)\right)&=a\left(\varphi^{k-1}(n)\right)-\omega\left(\varphi^{k-1}(n)\right)-\omega\left(\varphi^k(n)\right) \\
&= \cdots = a(n)-\sum_{j=0}^k\omega\left(\varphi^j(n)\right)
\end{aligned}
}$$
From this property, we obtain the formula
$$\small{a(n)=\sum_{j=0}^k\omega\left(\varphi^j(n)\right)=\sum_{j=0}^{+\infty}\omega\left(\varphi^j(n)\right)}$$
where the last equality holds because \$\omega(1)=0\$.
How it works
ÆṪÐĿÆFL€S  Main link. Argument: n

  ÐĿ       Repeatedly apply the link to the left until the results are no longer
           unique, and return the list of unique results.
ÆṪ           Apply Euler's totient function.
           Since φ(1) = 1, This computes φ-towers until 1 is reached.
    ÆF     Break each resulting integer into [prime, exponent] pairs.
      L€   Compute the length of each list.
           This counts the number of distinct prime factors.
        S  Add the results.

Now that is a super clever approach !

With the latest version of Jelly, this is 7 bytes, meaning it's still in (joint) first

05AB1E, 13 11 bytes
Code:
[DÒ¦P-¼D#]¾

Explanation:
[        ]   # An infinite loop and...
       D#        break out of the loop when the value is equal to 1.
 D           # Duplicate top of the stack (or in the beginning: duplicate input).
  Ò          # Get the prime factors, in the form [2, 3, 5]
   ¦         # Remove the first prime factor (the smallest one), in order to get
               the largest product.
    P        # Take the product, [3, 5] -> 15, [] -> 1.
     -       # Substract from the current value.
      ¼      # Add one to the counting variable.
          ¾  # Push the counting variable and implicitly print that value.

Uses CP-1252 encoding. Try it online!.

Remove the first prime factor (the smallest one), in order to get                the largest product How clever! :-)

I see, you are the language developer

@SargeBorsch Yes, that is correct :)

[¼Ñü-¤ÄD#]¾ - I was close to shaving off a byte with pairwise, oh well...

-1 byte: [Ð#Ò¦P-¼]¾. Ð is better than DD.

Down to 9: [Ð#Ò¦P-]N. You don't need the counter variable.

Pyth, 11 bytes
fq1=-Q/QhPQ

Test suite
A straightforward repeat-until-true loop.
Explanation:
fq1=-Q/QhPQ
               Implicit: Q = eval(input())
f              Apply the following function until it is truthy,
               incrementing T each time starting at 1:
         PQ    Take the prime factorization of Q
        h      Take its first element, the smallest factor of Q
      /Q       Divide Q by that, giving Q's largest factor
    -Q         Subtract the result from Q
   =           Assign Q to that value
 q1            Check if Q is now 1.

that's a really nice trick with filter.

I don't understand why this outputs the number of times the function ran. Is this an undocumented feature of f?

@corsiKa f without a second argument iterates over all positive integers starting from 1 and returns the first value that gives true on the inner statement. This value happens to be unused in this program, so it returns the number of times that it ran. Not undocumented, just unorthodox :) If it helps, you can think of this as a for loop like: for(int i=1; some_condition_unrelated_to_i; i++) { change_stuff_that_affects_condition_but_not_i;}

@corsiKa It's documented in the character reference on the right side of the online interpreter. With only one argument (f <l:T> <none>), f is First input where A(_) is truthy over [1, 2, 3, 4...].

Ah I understand it now. It uses that input but never uses the input in the calculation. That explains @Maltysen comment of "that's a really nice trick" because you only care about the iteration count not using that count anywhere in your filter. I love those ah-ha moments!: )

Python 2, 50 49 bytes
f=lambda n,k=1:2/n or n%(n-k)and f(n,k+1)or-~f(k)

This isn't going to finish that last test case any time soon...
Alternatively, here's a 48-byte which returns True instead of 1 for n=2:
f=lambda n,k=1:n<3or n%(n-k)and f(n,k+1)or-~f(k)

Retina, 12

14 bytes saved thanks to @MartinBüttner

(1+)(?=\1+$)

This assumes input given in unary and output given in decimal.  If this is not acceptable then we can do this for 6 bytes more:
Retina, 18

8 bytes saved thanks to @MartinBüttner

.+
$*
(1+)(?=\1+$)

Try it online - 1st line added to run all testcases in one go.
Sadly this uses unary for the calculations, so input of 2016155 is not practical.

The first stage (2 lines) simply converts the decimal input to unary as a string of 1s
The second stage (1 line) calculates the largest factor of n using regex matching groups and lookbehinds to and effectively subtracts it from n.  This regex will match as many times as is necessary to reduce the number as far as possible.  The number of regex matches will be the number of steps, and is output by this stage.

I don't think you need the \b.

You can save a lot more like this though and technically you don't need the first stage either.

@MartinBüttner Fantastic! Very elegant - thanks!

Jelly, 10 bytes
ÆfḊPạµÐĿi2

Try it online! or verify most test cases. The last test cases finishes quickly locally.
How it works
ÆfḊPạµÐĿi2  Main link. Argument: n (integer)

Æf          Factorize n, yielding a list of primes, [] for 1, or [0] for 0.
  Ḋ         Dequeue; remove the first (smallest) element.
   P        Take the product.
            This yields the largest proper divisor if n > 1, 1 if n < 2.
    ạ       Yield the abs. value of the difference of the divisor (or 1) and n.
     µ      Convert the chain to the left into a link.
      ÐĿ    Repeatedly execute the link until the results are no longer unique.
            Collect all intermediate results in a list.
            For each starting value of n, the last results are 2 -> 1 -> 0 (-> 1).
        i2  Compute the 1-based index of 2.

Pyth - 15 14 13 bytes
Special casing 1 is really killing me.
tl.u-N/Nh+PN2

Try it online here.
tl                One minus the length of
 .u               Cumulative fixed point operator implicitly on input
  -N              N -
   /N             N /
    h             Smallest prime factor
     +PN2         Prime factorization of lambda var, with two added to work with 1

One thing I always forget.... brute force is often the golfiest approach

What do you mean with special casing 1?

@Adnan the prime factorization of 1 is [], which causes an error when I take the first element. I have to special case it to make it return 1 again so the .u fixed-point ends. I found a better way than .x try-except which is what saved me those 2 bytes.

It only needs to accept numbers >= 2 (>1).

@SolomonUcko you're misunderstanding, the .u fixed-point will eventually reach 1 for all input, at which point it will have to be special cased.

Oh, thanks, I see. By the way could you add an explanation to your post?

Please explain "cumulative fixed point operator".

@SolomonUcko the normal u fixed point operator will apply the first argument to the second argument until it stops changing. .u returns all the intermediate steps along the way, so by taking its length, we can see how many steps it took.

@Maltysen, thanks for explaining, but I was thinking maybe put it in the explanation?

Julia, 56 50 45 39 bytes
f(n)=n>1&&f(n-n÷first(factor(n))[1])+1

This is a recursive function that accepts an integer and returns an integer.
Ungolfed:
function f(n)
    if n < 2
        # No decrementing necessary
        return 0
    else
        # As Dennis showed in his Jelly answer, we don't need to
        # divide by the smallest prime factor; any prime factor
        # will do. Since `factor` returns a `Dict` which isn't
        # sorted, `first` doesn't always get the smallest, and
        # that's okay.
        return f(n - n ÷ first(factor(n))[1]) + 1
    end
end

Try it online! (includes all test cases)
Saved 6 bytes thanks to Martin Büttner and 11 thanks to Dennis!

JavaScript (ES6), *44 38
Edit 6 bytes saved thanks @l4m2
(* 4 striked is still 4)
Recursive function
f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

Less golfed
f=(n, d=n-1)=>{
  if (n>1)
    if(n % d != 0)
      return f(n, d-1) // same number, try a smaller divisor
    else
      return f(n-d)+1  // reduce number, increment step, repeat
  else
    return 0
}

Test

f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0

console.log=x=>O.textContent+=x+'\n';

[5,30,31,32,100,200].forEach(x=>console.log(x+' -> '+f(x)))

Nice, but I think you should spend the two bytes needed to make f(1) == 0.

@Neil thinking again: no. "Let n be a natural number ≥ 2 ..."

I need new glasses.

Why not f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0?

@l4m2 right, why not? Thanks

Regex  (ECMAScript or better), 12 bytes
(x+)(?=\1+$)

Takes its input in unary, as a sequence of x characters whose length represents the number. Returns its output as the number of matches.
This of course has already been done in Digital Trauma's Retina answer, but here it is demonstrated to work on a much wider variety of regex engines.
Try it online! - ECMAScript
Try it online! - Perl
Try it online! - Java
Try it online! - PCRE
Try it online! - Boost
Try it online! - Python
Try it online! - Ruby
Try it online! - .NET
(x+)(?=\2+$)   # \2 = largest proper divisor of tail; tail -= \2;
               # return \2 as a match

Try it online!
Regex  (.NET), 15 bytes
((x+)(?=\2+$))*

Try it online!
Returns its output as the capture count of group \1.
                   # tail = input number; no need to anchor, as all inputs return a result
(
    (x+)(?=\2+$)   # \2 = largest proper divisor of tail; tail -= \2
)*                 # Loop the above as many times as possible, minimum zero, and push each
                   # match onto the \1 capture stack

Regex (Perl / Java / PCRE2 v10.34 or later), 26 bytes
((?=(\2?+(x*))x(x\3)+$)x)*

Returns its output as the length of the match.
Try it online! - Perl
Try it online! - Java
Attempt This Online! - PCRE2 v10.40+
We can't just do a direct port of the .NET version, because we need to subtract at least 1 from tail on each iteration (as a regex loop terminates after a zero-width match), and with most inputs, the iteration count exceeds the cumulative result of subtracting the largest divisor before the last iteration has finished. So instead, we let \2 be the sum of the subtracted divisors minus the iteration count:
                    # tail = input number; no need to anchor, as all inputs return a result
(
    (?=
        (\2?+(x*))  # \3 = {conjectured largest proper divisor of tail-\2} - 1;
                    # \2 = {\2, or 0 if \2 is unset} + \3; tail -= \2; note that the
                    # subtraction of 1 from this divisor compensates for the "tail -= 1"
                    # on each iteration (below)
        x(x\3)+$    # assert tail - 1 is divisible by \3 + 1
    )
    x               # head += 1; tail -=1
)*                  # Loop the above as many times as possible, minimum zero

(The PCRE version requirement is because PCRE2 v10.33 and earlier automatically makes any group containing a nested backreference atomic, thus \3 always captures the entire remaining tail, making the regex always return 0.)
Regex (.NET), 28 bytes
(?=((x+)(?=\2+$))*)(?<-1>x)*

Try it online!
A simple port of the 15 byte .NET version, that returns its output as the length of the match instead.
Regex (Perl / Java / PCRE2 v10.34 or later / .NET), 29 bytes
Obsoleted by the 29 byte regex below, which supports a superset of regex engines.
Regex (Perl / Java / PCRE / Pythonregex / Ruby / .NET), 33 29 bytes
((?=.*(?=\3$|^)(x+)(\2+$))x)*

Try it online! - Perl
Try it online! - Java
Try it online! - PCRE1
Try it online! - PCRE2 v10.33
Attempt This Online! - PCRE2 v10.40+
Try it online! - Python import regex
Try it online! - Ruby
Try it online! - .NET
For regex engines that lack nested backreferences but support forward-declared backreferences, we switch to a different approach. In this version, each iteration, while inside a lookahead, stores the new value of tail in the capture group \3, so that the next iteration can then recall that value rather directly. Since this directly sets \3 instead of building it up incrementally, there's no need to emulate a nested backreference.
                     # tail = N = input number;
                     # no need to anchor, as all inputs return a result
(
    (?=
        .*(?=\3$|^)  # tail = \3, or N if \3 is unset
        (x+)(\2+$)   # \2 = largest proper divisor of tail; \3 = tail - \2
    )
    x                # Increment the return value
)*                   # Loop the above as many times as possible, minimum zero

Regex (Perl / PCRE / Pythonregex), 63 bytes
(?=(xx+?)\1*(?=\1$)((?R)))(?=(x+)\3*(?=\3$)((?R)))\2\4|x\B(?R)|

This implements the recursive definition of the function:
\$a(1) = 0\$
\$a(p) = 1 + a(p-1)\$ if \$p\$ is prime
\$a(nm) = a(n) + a(m)\$ if \$m,n > 1\$
Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2 v10.33
Attempt This Online! - PCRE2 v10.40+
Try it online! - Python import regex
                # tail = input number; no need to anchor, as all inputs return a result
    (?=
        (xx+?)\1*(?=\1$)  # Assert tail isn't prime;
                          # tail = \1 = smallest prime factor of tail
        ((?R))            # \2 = recursive result of f(tail)
    )
    (?=
        (x+)\3*(?=\3$)    # tail = \3 = largest proper divisor of tail
        ((?R))            # \4 = recursive result of f(tail)
    )
    \2\4                  # return \2 + \4 as the match
|       # or if tail is prime:
    x                     # tail -= 1; return result += 1
    \B                    # Assert tail > 0
    (?R)                  # return 1 + recursive result of f(tail)
|       # or if tail == 1:
                          # return 0 at the match

Note that (?0) could have been used as a synonym for (?R).
Regex (Perl / PCRE / Boost / Pythonregex), 65 bytes
((?=(xx+?)\2*(?=\2$)((?1)))(?=(x+)\4*(?=\4$)((?1)))\3\5|x\B(?1)|)

The intent of the 63 byte version was to create a version that works under Boost, but as it turned out Boost has a bug (which I've reported) in which it ignores top-level alternatives in a top-level recursive call (i.e. (?R)), trying only the first top-level alternative. The workaround is to nest the entire regex in a capture group, so that Boost sees the other alternatives. Either (?R) or (?1) would work, but the latter is used for slightly better efficiency.
Try it online! - Perl
Try it online! - PCRE2
Try it online! - Boost
Try it online! - Python import regex
Regex (Ruby), 76 71 bytes
(?=(xx+?)\1*(?=\1$)(\g<0>))(?=(x+)\3*(?=\3$)(\g<0>))\k<2+0>\4|x\B\g<0>|

Try it online!
This is a port to Ruby's style of recursion; (?R) is replaced with \g<0>. Also, the backreference \2 needs to be replaced with \k<2+0> to get its value at the current level of recursion, rather than its global value which may have been overwritten at deeper levels of recursion.

That’s awesome. :)

Mathematica, 36 bytes
f@1=0;f@n_:=f[n-Divisors[n][[-2]]]+1

An unnamed function takes the same bytes:
If[#<2,0,#0[#-Divisors[#][[-2]]]+1]&

This is a very straightforward implementation of the definition as a recursive function.

PowerShell v2+, 81 bytes
param($a)for(;$a-gt1){for($i=$a-1;$i-gt0;$i--){if(!($a%$i)){$j++;$a-=$i;$i=0}}}$j

Brutest of brute force.
Takes input $a, enters a for loop until $a is less than or equal to 1. Each loop we go through another for loop that counts down from $a until we find a divisor (!($a%$i). At worst, we'll find $i=1 as a divisor. When we do, increment our counter $j, subtract our divisor $a-=$i and set $i=0 to break out of the inner loop. Eventually, we'll reach a condition where the outer loop is false (i.e., $a has reached 1), so output $j and exit.
Caution: This will take a long time on larger numbers, especially primes. Input of 100,000,000 takes ~35 seconds on my Core i5 laptop. Edit -- just tested with [int]::MaxValue (2^32-1), and it took ~27 minutes. Not too bad, I suppose.

Octave, 59 58 55 bytes
function r=f(x)r=0;while(x-=x/factor(x)(1));r++;end;end

Updated thanks to Stewie Griffin, saving 1 byte
Further update, saving three more bytes by using result of factorization in while-check.

Sample runs:
octave:41> f(5)
ans =  3
octave:42> f(30)
ans =  6
octave:43> f(31)
ans =  7
octave:44> f(32)
ans =  5
octave:45> f(100)
ans =  8
octave:46> f(200)
ans =  9

is the last end necessary in octave ?

It is. I noticed it was not in matlab from your answers, but Octave expects it (as I learned from trying yours in Octave).

Haskell, 59 bytes
f 1=0;f n=1+(f$n-(last$filter(\x->n`mod`x==0)[1..n`div`2]))

Usage:
Prelude> f 30
Prelude> 6

It may be a little inefficient for big numbers because of generating the list.

List comprehension and <1 instead of ==0 saves a few bytes: f 1=0;f n=1+f(n-last[a|a<-[1..ndiv2],mod n a<1])

You can save a character by rewriting (f$...) to f(...).

Python 3, 75, 70, 67 bytes.
g=lambda x,y=0:y*(x<2)or[g(x-z,y+1)for z in range(1,x)if x%z<1][-1]

This is a pretty straight forward recursive solution. It takes a VERY long time for the high number test cases.

Same bytecount: f=lambda n,k=0:k*(n<2)or f(n-max(d*(n%d<1)for d in range(1,n)),k+1)

Matlab, 58 bytes
function p=l(a),p=0;if(a-1),p=1+l(a-a/min(factor(a)));end

Japt, 12 bytes
@!(UµUk Å×}a

Test it online!
How it works
@   !(Uµ Uk Å  ×   }a
XYZ{!(U-=Uk s1 r*1 }a
                       // Implicit: U = input integer
XYZ{               }a  // Return the smallest non-negative integer X which returns
                       // a truthy value when run through this function:
         Uk            //   Take the prime factorization of U.
            s1         //   Slice off the first item.
                       //   Now we have all but the smallest prime factor of U.
               r*1     //   Reduce the result by multiplication, starting at 1.
                       //   This takes the product of the array, which is the
                       //   largest divisor of U.
      U-=              //   Subtract the result from U.
    !(                 //   Return !U (which is basically U == 0).
                       //   Since we started at 0, U == 1 after 1 less iteration than
                       //   the desired result. U == 0 works because the smallest
                       //   divisor of 1 is 1, so the next term after 1 is 0.
                       // Implicit: output result of last expression

This technique was inspired by the 05AB1E answer. A previous version used  ²¤ (push a 2, slice off the first two items) in place of Å because it's one byte shorter than s1  (note trailing space); I only realized after the fact that because this appends a 2 to the end of the array and slices from the beginning, it in fact fails on any odd composite number, though it works on all given test cases.

Vyxal s, 6 bytes
⁽∆ṫ↔v†

Try it Online!
Port of Jelly.
⁽∆ṫ↔v†
⁽  ↔    # Repeatedly apply until the result does not change, collecting intermediate results:
 ∆ṫ     #  Euler's totient
    v†  # For each, get the number of distinct prime factors
        # s flag sums

I found a way to do this in 6 bytes.

Vyxal l, 6 5 bytes
≬K¯÷ẋ

Try it Online!
This is the same as the 6 byte answer below except the length is taken by the l flag rather than a L element.
Vyxal, 7 6 bytes
≬K¯÷ẋL

Try it Online!
≬    # 3-element lambda:
  K  # Push a list of the divisors, from 1 to the number itself in increasing order
  ¯  # Deltas - returns a list of the consecutive differences in the list.
     # The resulting list has a length of 1 less than the one fed to it.
  ÷  # Unwrap the list onto the stack. For a non-empty list, this is effectively
     # equivalent to t (Tail - get the last item). But for an empty list, the
     # result is effectively whatever was already on the stack, i.e. the the
     # number whose list of divisors was taken, i.e., 1, the only one that yields
     # an empty deltas list. This makes 1, instead of 0, the fixed point.
ẋ    # Repeat the lambda on the number at the top of the stack (which is initially
     # the input) until the result no longer changes, returning a list of the
     # results. The last result will be 1, our fixed point.
L    # Length

This is very slow for most numbers of more than 60 decimal digits or so, since it has to generate a full list of divisors (even if it only uses the largest two). Prime factorization is still fast enough at that level, but unless the number has only one distinct prime factor, the list of divisors will be orders of magnitude longer.

@Steffan Nice work. And now I've beaten yours by 1 byte again :-)

><>, 32 bytes
<\?=2:-$@:$/:
1-$:@@:@%?!\
;/ln

Expects the input number, n, on the stack.
This program builds the complete sequence on the stack. As the only number that can lead to 1 is 2, building the sequence stops when 2 is reached. This also causes the size of the stack to equal the number of steps, rather than the number of steps +1.

C99, 62 61 bytes
1 byte golfed off by @Alchymist.
f(a,c,b)long*c,a,b;{for(*c=0,b=a;a^1;a%--b||(++*c,b=a-=b));}

Call as f(x,&y), where x is the input and y is the output.

If you test a%--b then you can avoid the b-- at the end.  A whole one byte saving.

Haskell, 67 bytes
Here's the code:
a&b|b<2=0|a==b=1+2&(b-1)|mod b a<1=1+2&(b-div b a)|1<2=(a+1)&b
(2&)

And here's one reason why Haskell is awesome:
f = (2&)

(-->) :: Eq a => a -> a -> Bool
(-->) = (==)

h=[f(5)        --> 3
  ,f(30)       --> 6
  ,f(31)       --> 7
  ,f(32)       --> 5
  ,f(100)      --> 8
  ,f(200)      --> 9
  ,f(2016^155) --> 2015
  ]

Yes, in Haskell you can define --> to be equivalent to ==.

Matlab, 107 bytes
a=input('');b=factor(a-isprime(a));c=log2(a);while(max(b)>1),b=max(factor(max(b)-1));c=c+1;end,disp(fix(c))

Non-competing, this is not the iterative translation of my last submission, just another direct algerbraic method, it sums up all binary-logs of all prime factors, kinda ambiguous to illustrate.
I will golf this more when i have time.

Ruby, 43 bytes
f=->x{x<2?0:1+f[(1..x).find{|i|x%(x-i)<1}]}

Find the smallest number i such that x divides x-i and recurse until we reach 1.

MATL, 17 16 bytes
`tttYfl)/-tq]vnq

Try it Online
Explanation
        % Implicitly grab input
`       % Do while loop
    ttt % Make three copies of top stack element
    Yf  % Compute all prime factors
    l)  % Grab the smallest one
    /   % Divide by this to get the biggest divisor
    -   % Subtract the biggest divisor
    t   % Duplicate the result
    q   % Subtract one (causes loop to terminate when the value is 1). This
        % is functionally equivalent to doing 1> (since the input will always be positive)
        % with fewer bytes
]       % End do...while loop
v       % Vertically concatenate stack contents (consumes entire stack)
n       % Determine length of the result
q       % Subtract 1 from the length
        % Implicitly display result

Julia, 39 36 bytes
\(n,k=2)=n%k>0?n>1&&n\-~k:\(n-n/k)+1

Try it online!

Clojure, 116 104 bytes
(fn[n](loop[m n t 1](let[s(- m(last(filter #(=(rem m %)0)(range 1 m))))](if(< s 2)t(recur s (inc t))))))

-12 bytes by filtering a range to find multiples, then using last one to get the greatest one
Naïve solution that basically just solves the problem as it's described by the OP. Unfortunately, finding the greatest divisor alone takes up like half the bytes used. At least I should have lots of room to golf from here.
Pregolfed and test:
(defn great-divider [n]
  ; Filter a range to find multiples, then take the last one to get the largest
  (last
     (filter #(= (rem n %) 0)
             (range 1 n))))

(defn sub-great-divide [n]
  (loop [m n
         step 1]
    (let [g-d (great-divider m) ; Find greatest divisor of m
          diff (- m g-d)] ; Find the difference
      (println m " is " g-d " --> " m " - " g-d " = " diff)
      (if (< diff 2)
        step
        (recur diff (inc step))))))

(sub-great-divide 30)

30  is  15  -->  30  -  15  =  15
15  is  5  -->  15  -  5  =  10
10  is  5  -->  10  -  5  =  5
5  is  1  -->  5  -  1  =  4
4  is  2  -->  4  -  2  =  2
2  is  1  -->  2  -  1  =  1
6

@insertusernamehere No, unfortunately, because those are all valid identifiers. I've removed all the possible whitespace. If I want to golf it further, I'll need to rework the algorithm.

Perl 6, 35 bytes
{+({$_ -first $_%%*,[R,] ^$_}...1)}

Try it online!
How it works
{                                 }   # A bare block lambda.
                    [R,] ^$_          # Construct range from arg minus 1, down to 0.
        first $_%%*,                  # Get first element that is a divisor of the arg.
    $_ -                              # Subtract it from the arg.
   {                        }...1     # Do this iteratively, until 1 is reached.
 +(                              )    # Return the number of values generated this way.

Stax, 9 7 bytes
Åiw^Å♫┌

Run and debug it
These two operations are identical.

Take the biggest divisor of n – which is different from n itself – and subtract it from n.
Let d be the smallest prime divisor of n.  Calculate n * (d - 1) / d.

I like #2 better, so let's count how many times we can do that one instead.  So at each step, we decrement the smallest prime factor.
Let's work an example starting with 30.
Step    n   Factors             Operation
0       30  [2, 3, 5]           Replace 2 with 1
1       15  [1, 3, 5] = [3, 5]  Replace 3 with 2
2       10  [2, 5]              Replace 2 with 1
3       5   [1, 5] = [5]        Replace 5 with 4
4       4   [4] = [2, 2]        Replace 2 with 1
5       2   [1, 2] = [2]        Replace 2 with 1
6       1   [1] = []            End of the line

From the example we can see a recursive definition for steps(x) that solves the problem.  Presented here in python-ish pseudo-code.
def steps(n):
    pf = primeFactors(n)
    return sum(steps(d - 1) for d in pf) + 1

The stax program, unpacked into ascii looks like this.
Z       push a zero under the input
|fF     for each prime factor of the input, run the rest of the program
  v     decrement the prime factor
  G     run the *whole* program from the beginning
  +^    add to the running total, then increment

Run this one

Looks like we have a new winner. A short question: Is there a meta agreement that characters count as bytes on Stax? I would say these are 7 characters and 13 bytes.

You can read about the character encoding stax uses here.  If you doubt the byte count, you can download the program using the down arrow button, and count the bytes yourself.  It will show you that the program is 7 bytes.  To verify, you can re-upload the program and run it to verify the behavior is the same.

Jelly, 8 bytes
ÆḌṀạƊƬL’

Try it online!
A different approach that takes advantage of Jelly's newer features.
How it works
ÆḌṀạƊƬL’ - Main link. Takes n on the left
    Ɗ    - Group the previous 3 links as a monad f(n):
ÆḌ       -   Proper divisors of n
  Ṁ      -   The largest
   ạ     -   Absolute different with n
     Ƭ   - Repeatedly run f(n) on n, updating n with the result, until
             reaching a fixed point (1), collecting intermediate steps
      L  - Take the length
       ’ - Decrement to account for the 1

C (clang), 45 bytes
g;l(f){for(g=f;f%--g;);return f<3?:1+l(f-g);}

inspired by this answer to a similar question.
Try it online!

-5 by replacing return  with an assignment

BQN, 24 bytes
{1:0;1+-⊢´↕⊸(⊣/˜0=|)}

Anonymous function that takes a number and returns the number of steps. Try it at BQN online!
The algorithm works for any number in theory. In practice, since it constructs a range from 0 to N-1, it runs out of memory for large inputs. For inputs above \$2^{32}-1\$, BQN refuses to even make an array that big; but fortunately, the OP has commented that those inputs do not need to be handled.
Explanation
{1:0;1+-⊢´↕⊸(⊣/˜0=|)}
{                       }  Anonymous block function
 1:                        If the argument is 1:
   0                         Return 0
    ;                      Otherwise:
                            Apply the following tacit function to the argument:
             ↕⊸(      )        Use range(argument) as the left arg to this binary function:
                     |         Mod (i.e. take  mod each number in range())
                   0=          Compare each with 0
                ⊣/˜            Keep only the ones that compared equal to 0 (perfect divisors)
          ⊢´                Get the last element of the list of divisors
        -                  Subtract it from the argument
                           Call this function on that value recursively
     1+                     Add 1 to the result

Pyth, 17 16 bytes
L?tbhy-b*F+1tPb0

Try it online! (The y.v at the end is for function calling)

Original 17 bytes:
L?tb+1y-b*F+1tPb0

Try it online! (The y.v at the end is for function calling)
(I actually answered that question with this Pyth program.)

I didn't actually bother going through your program, but if you're using the recursive definition in the OP, u is probably shorter than actual recursion.

Perl, 57 + 1 (-p flag) = 58 bytes
$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{

Usage:
> echo 31 | perl -pe '$n=$_;$n-=$n/(grep!($n%$_),2..$n/2,$n)[0],$\++while$n>1}{'

Ungolfed:
while (<>) {
# code above added by -p
    # $_ has input value
    # $\ has undef (or 0)
    my $n = $_;
    while ($n > 1) {
        my $d = 1;
        for (2 .. ($n / 2)) {
            if ($n % $_ == 0) {
                $d = $n / $_;
                last;
            }
        }
        $n -= $d;
        $\++;
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}

JavaScript (ES6), 70 54 bytes
f=(n,i=2)=>ni?f(i)+f(n/i):1+f(n-1)

Implementation of the provided recursive formula, but now updated to use recursion to find the divisor too.

Java (JDK 10), 60 bytes
n->{int c=0,d;for(;n>1;c++,n-=d)for(d=n;n%--d>0;);return c;}

Try it online!

You don't need the parenthesis around n->

Pyke, 11 bytes (noncompeting)
D3Phf-oRr;o

This uses a new behaviour where if there is an exception raised after a goto, it restores the state from before the goto (except variable definitions) and continues. In this case it is equivalent to the following python code:
# Implicit input and variable setup
inp = input()
o = 0
# End implicit
try:
    while 1:
        inp -= factors(inp)[0] # If factors is called on the value 1, it returns an empty
                               # list which when the first element tries to be accessed
                               # raises an exception
        o += 1 # Using `o` returns the current value of `o` and increments it
except:
    print o # This in effect gets the number of times the loop went

This is all possible using Pyke without a while loop construction - yay goto!
Try it here!

Clojure, 98 96 bytes
#(loop[n % i -1](if n(recur(first(for[j(range(dec n)0 -1):when(=(mod n j)0)](- n j)))(inc i))i))

uses for :when to find the largest divisor, loops until no such value larger than one is found.

x86, 24 23 bytes
Straightforward implementation of problem. Input in ecx, output in edi.
I wonder if there's a way to test if n > 1 in less than 3 bytes...
-1 by using cdq to zero edx. This requires the input to be a positive signed number (<=2^31-1), which I think is reasonable.
.section .text
.globl main
main:
        mov     $100, %ecx      # n = 100

start:
        xor     %edi, %edi      # result = 0
loop1:
        mov     %ecx, %ebx      # d = n
loop2:
        dec     %ebx            # --d
        mov     %ecx, %eax
        cdq
        div     %ebx            # n % d
        test    %edx, %edx
        jnz     loop2           # do while (n % d)

        inc     %edi            # ++result
        sub     %ebx, %ecx      # n -= d
        cmp     $1, %ecx
        ja      loop1           # do while (n > 1)

        ret

Hexdump:
00000039  31 ff 89 cb 4b 89 c8 99  f7 f3 85 d2 75 f6 47 29  |1...K.......u.G)|
00000049  d9 83 f9 01 77 ec c3                              |....w..|

Japt v1.4.5, 8 bytes
Had to switch to Japt v1.4.5 and sacrifice a byte to get around a bug with the â method in v1.4.6+. @µk Å×}f would work for the same bytes count in those versions, but that's just a golfed version of ETH's solution.
@Uµâ¬Ì}f

Try it

Husk, 9 bytes
LU¡Ṡ-ȯ→hḊ

Try it online!

Haskell, 42 bytes
f 1=0
f n=1+f(n-maximum(gcd n<$>[1..n-1]))

Try it online!

Batch, 139 136 bytes (Uses LF line delimiters)
@set/an=%1-1
:]
@for /l %%n in (1 1 %n%)do @((cmd/c"set/a1/((n+1)%%%%n)")||set[=%%n)>x 2>y
@set/at+=1,n-=[
@if %n% NEQ 0 goto]
@echo %t%

n should be supplied as the first command line argument %1.
n is limited to 32-bit integers.

If passing arbitrary command line arguments is allowed, the code above can be shortened by another 6 bytes
124 (code) + 6 (extra argument length) = 130 bytes
%2n=%1-1
:]
@for /l %%n in (1 1 %n%)do @((cmd/c"%21/((n+1)%%%%n)")||%2[=%%n)>x 2>y
%2t+=1,n-=[
@if %n% NEQ 0 goto]
@echo %t%

Run it like
code.bat <n> @set/a

Brachylog, 15 bytes
;.{fkt;?-ṅ}ⁱ⁾1∧

Try it online!
Explanation
;.{       }ⁱ⁾1∧     Iterate <Output> times until you get 1
   f                  Get the factors of the input, ordered
    kt                Take the penultimate one
      ;?-             Subtract the input
         ṅ            Negate

Excel VBA, 121 110 107 bytes
Sub a
o=[A1]
For i=o-1To 1Step-1
If o=WorksheetFunction.Lcm(o,i)Then[A1]=o-i:[B1]=[B1]+1:a
Next
End
End Sub

This presumes you start with a new, blank sheet (what you get when you open a new file). Input is in cell A1. Output is in cell B1. VBA will add spaces automatically then that code is pasted in. It is equivalent to this formatted and commented version:
Sub a()
  o = [A1]                                    'Store the starting value to save bytes later
  For i = o - 1 To 1 Step -1                  'Start at 1 less than the starting value and count down
    If o = WorksheetFunction.Lcm(o, i) Then   'If the LCM is the starting value then the current value is a divisor
      [A1] = o - i                            'Subtract the current value from the starting value and set it as the new starting value
      [B1] = [B1] + 1                         'Increase the count by 1
      a                                       'Recurse
    End If
  Next
  End   'You only get here if the for loop was skipped meaning o=1 (since "For i=0 to 1 Step -1" will just skip) so we can end all code now
End Sub

The maximum integer value in VBA is 32767 and the program above output 21 given that input as shown in the GIF below (with an added 1 second pause between each calculation).

You can drop the () in the sub definition, and drop a byte by rearranging the if statement to read as If o=WorksheetFunction.Lcm(o, i)Then ...

dc, 39 bytes
0[1+rd[d3R1-d_4R%0<t]dstxr-d_3R1<l]dslx

Try it online!
Takes input as number on top of stack, and leaves result as top of stack

APL, 21 bytes
{1=⍵:0⋄1+∇⍵-⍵⌈.∨⍳⍵-1}

You have an extra space at the start of your code which can be removed

PARI/GP, 61 bytes
Try it online!
f(1)=0;
f(n)=if(n==1,0,f(n-divisors(n)[#(divisors(n))-1])+1);

PowerShell, 75 bytes
param($i)$a=0;while($i-gt1){$i=$i-(($i-1)..1|%{($_)[$i%$_-ne0]})[0];$a++}$a

Try it online!