Skip to main content
Code Golf

Return to Question

Tweeted twitter.com/StackCodeGolf/status/843833843144691712
s/equation/expression/g
Source Link
Martin Ender
Martin Ender
  • 197.2k
  • 67
  • 447
  • 975

Today, we'll be computing the most efficient binary function. More specifically, we'll be computing the function which, when an equationexpression is created from applying the function to the constant input 0 or its own output, can represent all positive integers with the shortest possible expressions, placing higher priority on the smaller integers.

For each integer, starting at 1 and going upwards, choose the shortest expression which we have not yet assigned an output to, and make that integer the output of that equationexpression. Ties in equationexpression length will be broken by smaller left argument, and then by smaller right argument. Here's how it works:

  • Initially, 1 is unassigned. The shortest unassigned equationexpression is f(0, 0), so we'll set that to 1.

  • Now, 2 is unassigned. The shortest unassigned equationsexpressions are f(f(0, 0), 0) = f(1, 0) and f(0, f(0, 0)) = f(0, 1). Ties are broken towards smaller left argument, so f(0, 1) = 2.

  • The shortest unassigned expression remaining is f(f(0, 0), 0) = f(1, 0), so f(1, 0) = 3.

  • Now, we're out of expressions with only 2fs and 30s, so we'll have to add one more of each. Breaking ties by left argument, then right argument, we get f(0, 2) = 4, since f(0, f(0, f(0, 0))) = f(0, f(0, 1)) = f(0, 2).

  • Continuing, we have f(0, 3) = 5, f(1, 1) = 6, f(2, 0) = 7, f(3, 0) = 8, f(0, 4) = 9, ...

Today, we'll be computing the most efficient binary function. More specifically, we'll be computing the function which, when an equation is created from applying the function to the constant input 0, can represent all positive integers with the shortest possible expressions, placing higher priority on the smaller integers.

For each integer, starting at 1 and going upwards, choose the shortest expression which we have not yet assigned an output to, and make that integer the output of that equation. Ties in equation length will be broken by smaller left argument, and then by smaller right argument. Here's how it works:

  • Initially, 1 is unassigned. The shortest unassigned equation is f(0, 0), so we'll set that to 1.

  • Now, 2 is unassigned. The shortest unassigned equations are f(f(0, 0), 0) = f(1, 0) and f(0, f(0, 0)) = f(0, 1). Ties are broken towards smaller left argument, so f(0, 1) = 2.

  • The shortest unassigned expression remaining is f(f(0, 0), 0) = f(1, 0), so f(1, 0) = 3.

  • Now, we're out of expressions with only 2fs and 30s, so we'll have to add one more of each. Breaking ties by left argument, then right argument, we get f(0, 2) = 4, since f(0, f(0, f(0, 0))) = f(0, f(0, 1)) = f(0, 2).

  • Continuing, we have f(0, 3) = 5, f(1, 1) = 6, f(2, 0) = 7, f(3, 0) = 8, f(0, 4) = 9, ...

Today, we'll be computing the most efficient binary function. More specifically, we'll be computing the function which, when an expression is created from applying the function to the constant input 0 or its own output, can represent all positive integers with the shortest possible expressions, placing higher priority on the smaller integers.

For each integer, starting at 1 and going upwards, choose the shortest expression which we have not yet assigned an output to, and make that integer the output of that expression. Ties in expression length will be broken by smaller left argument, and then by smaller right argument. Here's how it works:

  • Initially, 1 is unassigned. The shortest unassigned expression is f(0, 0), so we'll set that to 1.

  • Now, 2 is unassigned. The shortest unassigned expressions are f(f(0, 0), 0) = f(1, 0) and f(0, f(0, 0)) = f(0, 1). Ties are broken towards smaller left argument, so f(0, 1) = 2.

  • The shortest unassigned expression remaining is f(f(0, 0), 0) = f(1, 0), so f(1, 0) = 3.

  • Now, we're out of expressions with only 2fs and 30s, so we'll have to add one more of each. Breaking ties by left argument, then right argument, we get f(0, 2) = 4, since f(0, f(0, f(0, 0))) = f(0, f(0, 1)) = f(0, 2).

  • Continuing, we have f(0, 3) = 5, f(1, 1) = 6, f(2, 0) = 7, f(3, 0) = 8, f(0, 4) = 9, ...

deleted 130 characters in body
Source Link
isaacg
isaacg
  • 42.1k
  • 5
  • 73
  • 213

This function is given as OEIS's A072764, which reads off the table on the up-and-right diagonals.

Your challenge is, given two non-negative integers as input, compute and output the value of this function. This is code golf. Shortest solution, in bytes, wins. Standard loopholes are banned.

This function is given as OEIS's A072764, which reads off the table on the up-and-right diagonals.

Your challenge is, given two non-negative integers as input, compute and output the value of this function. This is code golf. Shortest solution, in bytes, wins. Standard loopholes are banned.

Your challenge is, given two non-negative integers as input, compute and output the value of this function. This is code golf. Shortest solution, in bytes, wins. Standard loopholes are banned.

Source Link
isaacg
isaacg
  • 42.1k
  • 5
  • 73
  • 213

Compute the most efficient binary function

Today, we'll be computing the most efficient binary function. More specifically, we'll be computing the function which, when an equation is created from applying the function to the constant input 0, can represent all positive integers with the shortest possible expressions, placing higher priority on the smaller integers.

This function is built as follows:

For each integer, starting at 1 and going upwards, choose the shortest expression which we have not yet assigned an output to, and make that integer the output of that equation. Ties in equation length will be broken by smaller left argument, and then by smaller right argument. Here's how it works:

  • Initially, 1 is unassigned. The shortest unassigned equation is f(0, 0), so we'll set that to 1.

  • Now, 2 is unassigned. The shortest unassigned equations are f(f(0, 0), 0) = f(1, 0) and f(0, f(0, 0)) = f(0, 1). Ties are broken towards smaller left argument, so f(0, 1) = 2.

  • The shortest unassigned expression remaining is f(f(0, 0), 0) = f(1, 0), so f(1, 0) = 3.

  • Now, we're out of expressions with only 2fs and 30s, so we'll have to add one more of each. Breaking ties by left argument, then right argument, we get f(0, 2) = 4, since f(0, f(0, f(0, 0))) = f(0, f(0, 1)) = f(0, 2).

  • Continuing, we have f(0, 3) = 5, f(1, 1) = 6, f(2, 0) = 7, f(3, 0) = 8, f(0, 4) = 9, ...

Here's a table I filled out for the first few values:

    0  1  2  3  4  5  6  7  8
 /---------------------------
0|  1  2  4  5  9 10 11 12 13
1|  3  6 14 15 37 38 39 40 41
2|  7 16 42 43
3|  8 17 44 45
4| 18 46
5| 19 47
6| 20 48
7| 21 49
8| 22 50

Another way to look at it is that each output has a size, equal to the sum of the sizes of its inputs plus one. The table is filled out in order of increasing size of output, ties broken by minimizing left input then right input.

This function is given as OEIS's A072764, which reads off the table on the up-and-right diagonals.

Your challenge is, given two non-negative integers as input, compute and output the value of this function. This is code golf. Shortest solution, in bytes, wins. Standard loopholes are banned.