text:
Quickly express a number with only 0-9 and the four operations, plus one more extra
Explanation
Befunge is a two-dimensional program that uses stacks.
That means, to do 5 + 6, you write 56+, meaning:
56+
5    push 5 into stack
 6   push 6 into stack
  +  pop the first two items in the stack and add them up, and push the result into stack

(to those of you who do not know stacks, "push" just means add and "pop" just means take off)

However, we cannot push the number 56 directly into the stack.
To do so, we must write 78* instead, which multiplies 7 and 8 and pushes the product into the stack.
Details
For each number from 1 to n, find a string consisting of only these characters: 0123456789+-*/: (I would not use % modulo.)
The goal is to find the shortest string that can represent the number, using the format described above.
For example, if the input is 123, then the output would be 67*9:*+. The output should be evaluated from left to right.
If there are more than one acceptable outputs (e.g. 99*67*+ is also acceptable), any one can be printed (no bonus for printing all of them).
Further Explanation
If you still do not understand how 67*9:*+ evaluates to 123, here is a detailed explanation.
stack    |operation|explanation
          67*9:*+
[6]       6         push 6 to stack
[6,7]      7        push 7 to stack
[42]        *       pop two from stack and multiply, then put result to stack
[42,9]       9      push 9 to stack
[42,9,9]      :     duplicate the top of stack
[42,81]        *    pop two from stack and multiply, then put result to stack
[123]           +   pop two from stack and add, then put result to stack

TL;DR
The program needs to find the shortest string that can represent the input (number), using the format specified above.
SCORING

We have already done it in the shortest amount of code. This time, size does not matter.
Your language of choice has to have a free compiler/interpreter for my operating system (Windows 7 Enterprise).
Bonus if you include the link to the compiler/interpreter (I am too lazy).
If possible, please include a timer for my convenience. The output from the timer is valid.
The score will be the largest n in 1 minute.
That means, the program needs to print the required representation from 1 onward.
No hard-coding, except 0 to 9.

(more) SPECIFICS

The program is invalid if it outputs a string longer than needed for any number.
1/0=ERROR
5/2=2, (-5)/2=-2, (-5)/(-2)=2, 5/(-2)=-2

Disambiguation
The - is second-top minus top, meaning that 92- returns 7.
Likewise, the / is second-top divide top, meaning that 92/ returns 4.
Sample program
Lua
Uses depth-first search.
local function div(a,b)
    if b == 0 then
        return "error"
    end
    local result = a/b
    if result > 0 then
        return math.floor(result)
    else
        return math.ceil(result)
    end
end

local function eval(expr)
    local stack = {}
    for i=1,#expr do
        local c = expr:sub(i,i)
        if c:match('[0-9]') then
            table.insert(stack, tonumber(c))
        elseif c == ':' then
            local a = table.remove(stack)
            if a then
                table.insert(stack,a)
                table.insert(stack,a)
            else
                return -1
            end
        else
            local a = table.remove(stack)
            local b = table.remove(stack)
            if a and b then
                if c == '+' then
                    table.insert(stack, a+b)
                elseif c == '-' then
                    table.insert(stack, b-a)
                elseif c == '*' then
                    table.insert(stack, a*b)
                elseif c == '/' then
                    local test = div(b,a)
                    if test == "error" then
                        return -1
                    else
                        table.insert(stack, test)
                    end
                end
            else
                return -1
            end
        end
    end
    return table.remove(stack) or -1
end

local samples, temp = {""}, {}

while true do
    temp = {}
    for i=1,#samples do
        local s = samples[i]
        if eval(s) ~= -1 or s == "" then for n in ("9876543210+-*/:"):gmatch(".") do
            table.insert(temp, s..n)
        end end
    end
    for i=1,#temp do
        local test = eval(temp[i])
        if input == test then
            print(temp[i])
            return
        end
    end
    samples = temp
end

Wait, if we can't push 56 directly into the stack, how can we push 78 into the stack?

We can't push 56 fifty-six directly into the stack, but we can push 7 seven and 8 eight separately into the stack.

But we can also do the same with 56 can't we? It's just two numbers, like in 78. Are you saying we can only push numbers into the stack when multiplying?

I'm just saying we cannot push 56 fifty-six directly into the stack by writing 56.

@R.Kap: When you do something like 56 in Befunge, you're pushing the digits, so you end up with a stack of [5, 6]. To get the number 56, you have to push 7, then 8 onto the stack, and then multiply them to get the number 56 on the stack.

Okay, so you can only push single digit numbers into the stack. Got it.

: makes things a lot trickier, so I'd recommend supplying a good list of test cases, e.g. 86387

@Sp3000 Could you supply the numbers while I generate the testcases?

@KennyLau Why do you think I won't need division? I can make 265620 by 99999*9/2 (where 9^3 is duplicated)  in 9 operations. Can you do it in less?

@feersum Okay. You won't need division with negative numbers then. Division by zero results in infinity. Don't know why you would need this.

Alright. 5/2=2, (-5)/2=-2, (-5)/(-2)=2, 5/(-2)=-2.

Initial test case ideas: 1, 11, 26, 27, 100, 2431, 3727, 86387, 265729, 1921600, 57168721, 4747561509943. All should be doable in at most 11 instructions (assuming - and / mean second op top).

@R.Kap / is integer division. The result is rounded to the nearest integer that is closer to 0. OK, there is a typo in one of hte digits.

largest integer in 5 seconds is a bad metric. the computational time for larger numbers will not increase monotonically, so many solutions can get stuck at the same hard-to-calculate number, despite some of them being much faster or slower on nearby numbers.

I don't understand why we are arguing about specific behaviors of operators. Why not just use the actual Befunge specs?

@Sparr What metric should I use?

@Sp3000 What is the answer for 3727?

@KennyLau I don't know what the optimal solution is, but it's at most 9 chars: 79*2-:*6+

@KennyLau maybe first what you have now, then tiebreak with the time to calculate the next lower number?

@Sp3000 I still have not been fruitful in producing the program. Maybe it would be nice of you to provide the solutions to, well, all of your testcases.

@Sparr next lower number as in n+1?

Is a program allowed to run in a loop, spitting out representations of ever increasing numbers?

No it is not...

@KennyLau That makes no sense and will force a lot of repeated computation. The only way to make sure that your representation is the shortest is to enumerate them.

@orlp Then what counts as part of calculating that number?

@KennyLau What about the largest number that a program can produce in 1 minute, but forcing the program to calculate each number from 1 onwards?

@orlp That sounds good.

I think this is a lot trickier than you expect.

I like @orlp's metric, although it does change the nature of the challenge a bit, in terms of data management.

@DanielJour we've had a few contests recently that did things like this. finding a solution isn't hard. I love algorithm complexity challenges, from a purely math perspective. I am sad that language differences will come into play with this sort of thing, but there's little helping that.

One would never actually need to this number-golfing, though, as it is shorter to write '! (for 33) instead of 3a*, which is the output which these programs would give.

@ppperry At least my solution can easily be extended to handle this

C++, exploding all memory on a computer near you
Generates the shortest string where the calculation nowhere causes an overflow of a signed 32-bit integer (so all intermediate results are in the range [-2147483648, 2147483647]
On my system this generates a solution for all numbers up to and including 483432 in 30 seconds while using 1.8G memory. Even higher numbers will quickly explode the memory usage. The highest number I can handle on my system is 5113906. The calculation takes almost 9 minutes and 24GB. When it finishes it internally has a solution for 398499338 values, about 9% of all 32 bit integers (positive and negative)
Needs a C++11 compiler. On linux compile with:
g++ -Wall -O3 -march=native -std=gnu++11 -s befour.cpp -o befour

Add -DINT64 as an option to use a 64-bit integer range instead of 32-bit for intermediate results (this will use about 50% more time and memory). This needs a builtin 128 bit type. You may need to change the gcc type __int128. No result in at least the range [1..483432] changes by allowing larger intermediate results.
Add -DOVERFLOW as an option to not use a bigger integer type to check for overflow. This has the effect of allowing overflow and value wrapping.
If your system has tcmalloc (https://github.com/gperftools/gperftools) you can link with that resulting in a program that is generally a little faster and uses slightly less memory. On some UNIX systems you can use a preload, e.g.
LD_PRELOAD=/usr/lib/libtcmalloc_minimal.so.4 befour 5

Basic usage: generate and print all numbers up to target:
befour target

Options:

-a Also print all numbers that were generated while working out target
-c Also print all numbers that were generated starting with a "carry" (dup)
-f Find and print the first number beyond target that was not generated
-s Stop if target is generated even if not all numbers before were generated
-S Like -s and -f in an automatic loop. As soon as target is generated find the first number not yet generated and make that the new target
-E Don't immediately exit when the goal is reached. First finish all strings of the current length
-O Don't output the strings for all numbers up to target. just the string for target
-o Allowed instructions (defaults to +-*/:
-b num Lowest literal that can be pushed (defaults to 0)
-B num Highest literal that can be pushed (defaults to 9)
-r num The lowest allowed intermediate result. Used to avoid underflow. (defaults to INT32_MIN, -2147483648
-R num The highest allowed intermediate result. Used to avoid overflow. (defaults to INT32_MAX, 2147483647
-m memory (linux only) exit when approximately this much extra memory has been allocated

Some interesting option combinations:
Generate all numbers up to target and calculate the smallest number that needs a longer generator than all these numbers:
befour -fE target

Generate only target (-s), print only target (-O)
befour -sO target

Find the highest number that can be generated on your system given time and/or memory constraints (This will run your system out of memory if you leave it running. Subtract 1 from the last "looking for" output you see as the last safe value):
befour -S 1

Generate solutions without ever using negative intermediate results (30932 is the first value that needs negative intermediate results for the shortest string):
befour -r0 target

Generate solutions without ever pushing 0 (this doesn't seem to lead to any suboptimal solutions):
befour -b1 target

Generate solutions including a..f (10..15):
befour -B15 target

Generate solutions without using dup : (add -r0 since negative intermediate values are never interesting for this case)
befour -r0 -o "+-*/" target

Find the first value that can not be generated for a given string length using just +, -, * and /:
befour -ES -r0 -o "+-*/" 1

This will in fact generate the first few terms of https://oeis.org/A181898, but will start to diverge at 14771 because we use truncating division so that number can be done with a length 13 string instead of length 15 as the OEIS series expects:
14771: 13: 99*9*9*4+9*4/

instead of
14771: 15: 19+5*6*7*9+7*8+

Since without truncation division seems pointless the OEIS series can be better generated by using
befour -ES -r0 -o"+-*" 1

Assuming division remains useless this gave me 3 extra terms before I went out of memory:
10, 19, 92, 417, 851, 4237, 14771, 73237, 298609, 1346341, 6176426, 25622578

Another version of this program storing part of the data in external files adds 135153107 and 675854293 after which all 32-bit integers have been generated.
befour.cpp
/*
  Compile using something like:
g++ -Wall -O3 -march=native -std=gnu++11 -s  befour.cpp -o befour
*/
#include <iostream>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
#include <limits>
#include <climits>
#include <cstdint>
#include <cstdlib>
#include <chrono>
#include <unordered_map>

using namespace std;

#ifdef __GNUC__
# define HOT        __attribute__((__hot__))
# define COLD       __attribute__((__cold__))
# define NOINLINE   __attribute__((__noinline__))
# define LIKELY(x)  __builtin_expect(!!(x),1)
# define UNLIKELY(x)    __builtin_expect(!!(x),0)
#else // __GNUC__
# define HOT
# define COLD
# define NOINLINE
# define LIKELY(x)  (x)
# define UNLIKELY(x)    (x)
#endif // __GNUC__

#ifdef INT64
using Int  = int64_t;       // Supported value type
# ifndef OVERFLOW
using Int2 = __int128;      // Do calculations in this type. Check overflow
# endif // OVERFLOW
#else // INT64
using Int  = int32_t;       // Supported value type
# ifndef OVERFLOW
using Int2 = int64_t;       // Do calculations in this type. Check overflow
# endif // OVERFLOW
#endif // INT64
#ifdef OVERFLOW
using Int2 = Int;
#endif // OVERFLOW

// Supported value range
Int2 MIN = numeric_limits<Int>::lowest();
Int2 MAX = numeric_limits<Int>::max();
Int HALF_MIN, HALF_MAX;

// The initial values we can push
Int ATOM_MIN = 0;
Int ATOM_MAX = 9;

bool all    = false;    // Output all reached values
bool all_carry  = false;    // Output all values reachable using carry
bool early_exit = true;     // Exit before finishing level if goal reached
bool find_hole  = false;    // Look for first unconstructed > target
bool output = true;     // Output [1..target] instead of just target
bool single = false;    // Only go for target instead of [1..target]
bool explore    = false;    // Don't stop, increase N until out of memory
bool do_dup = false;    // Use operator :
bool do_multiply= false;    // Use operator *
bool do_add = false;    // Use operator +
bool do_subtract= false;    // Use operator -
bool do_divide  = false;    // Use operator /
char const* operators = "+-*/:"; // Use these operators
size_t max_mem  = SIZE_MAX; // Stop if target memory reached

size_t const MEM_CHECK = 1000000;

chrono::steady_clock::time_point start;

NOINLINE size_t get_memory(bool set_base_mem = false) {
static size_t base_mem = 0;
size_t const PAGE_SIZE = 4096;

// Linux specific. Won't hurt on other systems, just gets no result
size_t mem = 0;
std::ifstream statm;
statm.open("/proc/self/statm");
statm >> mem;
mem *= PAGE_SIZE;
if (set_base_mem) base_mem = mem;
else mem -= base_mem;
return mem;
}

// Handle commandline options.
// Simplified getopt for systems that don't have it in their library (Windows..)
class GetOpt {
  private:
string const options;
char const* const* argv;
int nextchar = 0;
int optind = 1;
char ch = '?';
char const* optarg = nullptr;

  public:
int ind() const { return optind; }
char const* arg() const { return optarg; }
char option() const { return ch; }

GetOpt(string const options_, char const* const* argv_) :
options(options_), argv(argv_) {}
char next() {
while (1) {
    if (nextchar == 0) {
    if (!argv[optind] ||
        argv[optind][0] != '-' ||
        argv[optind][1] == 0) return ch = 0;
    if (argv[optind][1] == '-' && argv[optind][2] == 0) {
        ++optind;
        return ch = 0;
    }
    nextchar = 1;
    }
    ch = argv[optind][nextchar++];
    if (ch == 0) {
    ++optind;
    nextchar = 0;
    continue;
    }
    auto pos = options.find(ch);
    if (pos == string::npos) ch = '?';
    else if (options[pos+1] == ':') {
    if (argv[optind][nextchar]) {
        optarg = &argv[optind][nextchar];
    } else {
        optarg = argv[++optind];
        if (!optarg) return ch = options[0] == ':' ? ':' : '?';
    }
    ++optind;
    nextchar = 0;
    }
    return ch;
}
}
};

using ms = chrono::milliseconds;

Int missing, N;
size_t cached, cached_next;

uint8_t const CARRY_MASK = '\x80';
uint8_t const LITERAL    = 0;
struct How {
// Describes how to construct a number
Int left;
Int right;
uint8_t ops, op;

How(uint8_t ops_, uint8_t op_, Int carry_=0, Int left_=0, Int right_=0) :
left(left_),
right(right_),
ops(ops_),
op(carry_ ? CARRY_MASK | op_ : op_)
{}
How() = default;
How(How&&) = default;
How& operator=(How&&) = default;
static How const* predict(Int carry, Int value, int& ops);
static void print_predicted(ostream& out, Int carry, Int value, How const* Value = nullptr);
void print(ostream& out, Int carry = 0, bool length = false) const;
};

ostream& operator<<(ostream& out, How const& how) {
how.print(out, 0, true);
return out;
}

using NumSet  = vector<Int>;
using NumSets = vector<NumSet>;

struct Known: public unordered_map<Int, How>
{
void store(NumSet& L, Int accu, uint8_t ops, uint8_t op,
       Int left=0, Int carry_right=0, Int right=0) {
++cached;
emplace(accu, How(ops, op, carry_right, left, right));
// operator[](accu) = How(ops, op, carry_right, left, right);
L.emplace_back(accu);
}
void maybe_store(Known const& known0, NumSet& L,
         Int accu, uint8_t ops, uint8_t op,
         Int carry_left, Int left, Int carry_right, Int right) {
if (count(accu)) return;
if (carry_left) {
    auto found = known0.find(accu);
    // If we can do as good or better without carry use that
    if (found != known0.end() && found->second.ops <= ops) return;
}
store(L, accu, ops, op, left, carry_right, right);
if (carry_left) return;
if (single) {
    if (UNLIKELY(accu == N)) known0.maybe_explore();
} else if (1 <= accu && accu <= N) --missing;
}
NOINLINE void maybe_explore() const COLD {
--missing;
if (explore && early_exit) do_explore();
}
NOINLINE void do_explore() const COLD {
auto i = N;
while (i < MAX && count(++i));
auto end = chrono::steady_clock::now();
auto elapsed = chrono::duration_cast<ms>(end-start).count();

cerr << "Found " << N << " at " << elapsed / 1000. << " s";
auto mem = get_memory();
if (mem) cerr << " (" << mem / 1000 / 1000.  << " MB)";
if (i < MAX || !count(i)) {
    cerr << ", now looking for " << i << endl;
    N = i;
    ++missing;
} else
    cerr << ", every value has now been generated" << endl;
}
};

struct KnowHow {
// Describes all numbers we know how to construct
NumSets num_sets;
Known known;

KnowHow() = default;
~KnowHow() = default;
KnowHow(KnowHow const&) = delete;
KnowHow& operator=(KnowHow const&) = delete;
};
// Describes all numbers we know how to construct for a given carry
// Key 0 is special: the numbers we can construct without carry (the solutions)
unordered_map<Int, KnowHow> known_how;

// Try to predict if a subtree is a delayed How and avoid descending
// into it (since it may not exist yet)
How const* How::predict(Int carry, Int value, int& ops) {
How* Value;
if (carry) {
if (value == carry) {
    Value = nullptr;
    ops = 0;
} else {
    Value = &known_how.at(carry).known.at(value);
    ops = Value->ops;
}
} else {
if (ATOM_MIN <= value && value <= ATOM_MAX) {
    Value = nullptr;
    ops = 0;
} else {
    Value = &known_how.at(0).known.at(value);
    ops = Value->ops;
}
}
return Value;
}

void How::print_predicted(ostream& out, Int carry, Int value, How const* Value) {
if (Value) Value->print(out, carry);
else if (carry) out << ":";
else if (value > 9) out << static_cast<char>(value-10+'a');
else out << value;
}

void How::print(ostream& out, Int carry_left, bool length) const {
if (length) out << 2*ops+1 << ": ";

Int carry_right = 0;
auto op_ = op;

switch(op_) {
case LITERAL:
  How::print_predicted(out, 0, left);
  break;
case '*' | CARRY_MASK:
case '/' | CARRY_MASK:
case '+' | CARRY_MASK:
case '-' | CARRY_MASK:
  carry_right = left;
  op_ &= ~CARRY_MASK;
  // Intentional drop through
case '*':
case '/':
case '+':
case '-':
  {
      int left_ops, right_ops;
      auto Left  = How::predict(carry_left,  left,  left_ops);
      // Int right = 0;
      auto Right = How::predict(carry_right, right, right_ops);

      // Sanity check: tree = left_tree + root + right_tree
      if (ops != left_ops + right_ops +1) {
      char buffer[80];
      snprintf(buffer, sizeof(buffer),
           "Broken number %d %c %d, length %d != %d + %d + 1",
           static_cast<int>(left), op_, static_cast<int>(right),
           ops, left_ops, right_ops);
      throw(logic_error(buffer));
      }

      How::print_predicted(out, carry_left,  left,  Left);
      How::print_predicted(out, carry_right, right, Right);
  }
  // Intentional drop through
case ':':
  out << op_;
  break;
default:
  throw(logic_error("Unknown op " + string{static_cast<char>(op_)}));
  break;
}
}

// carryX indicates Xv was reached using carry. If not we also know [L, known] is known_how[0]
// carryY indicates Y was reached using carry (carryY == Xv if so)
void combine(NumSet& L, Known& known, Known const& known0, int ops, Int carryX, Int2 Xv, Int carryY, NumSet const&Y) HOT;
void combine(NumSet& L, Known& known, Known const& known0, int ops, Int carryX, Int2 Xv, Int carryY, NumSet const&Y) {
for (Int Yv: Y) {
// Yv == 0 can never lead to an optimal calculation
if (Yv == 0) continue;

Int2 accu;

if (do_multiply) {
    accu = Xv * Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '*', carryX, Xv, carryY, Yv);
}

if (do_add) {
    accu = Xv + Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '+', carryX, Xv, carryY, Yv);
}

if (do_subtract) {
    accu = Xv - Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '-', carryX, Xv, carryY, Yv);
}

if (do_divide) {
    accu = Xv / Yv;
    if (accu <= MAX && accu >= MIN)
    known.maybe_store(known0, L, accu, ops, '/', carryX, Xv, carryY, Yv);
}
}
}

// value was constructed using a carry if and only if value != 0
NumSet const& level(KnowHow& known_how0, Int value, int ops) HOT;
NumSet const& level(KnowHow& known_how0, Int value, int ops) {
auto& from_value = known_how[value];
if (from_value.num_sets.size() <= static_cast<size_t>(ops)) {
auto& known = from_value.known;
if (from_value.num_sets.size() != static_cast<size_t>(ops)) {
    if (value == 0 || ops != 1)
    throw(logic_error("Unexpected level skip"));
    // This was because of delayed carry creation.
    // The delay is over. Create the base case
    from_value.num_sets.resize(ops+1);
    known.store(from_value.num_sets[0], value, 0, ':', value);
} else
    from_value.num_sets.resize(ops+1);
auto& L = from_value.num_sets[ops];
if (ops == 0) {
    if (value) {
    known.store(L, value, ops, ':', value);
    } else {
    for (auto i = ATOM_MIN; i <= ATOM_MAX; ++i) {
        if (single) {
        if (i == N) --missing;
        } else {
        if (0 < i && i <= N) --missing;
        }
        known.store(L, i, 0, LITERAL, i);
    }
    }
} else {
    auto& known0 = known_how0.known;
    // for (auto k=ops-1; k>=0; --k) {
    for (auto k=0; k<ops; ++k) {
    auto const& X = from_value.num_sets[ops-1-k];
    auto const& Y = known_how0.num_sets[k];

    for (Int Xv: X) {
        // Plain combine must come before carry combine so a plain
        // solution will prune a same length carry solution
        combine(L, known, known0, ops, value, Xv, 0, Y);
        if (!missing && early_exit) goto DONE;
        if (do_dup && (Xv > ATOM_MAX || Xv < ATOM_MIN)) {
        // Dup Xv, construct something using k operators, combine
        if (k == 0 && Xv != 0) {
            // Delay creation of carry known_how[Xv] for 1 level
            // This is purely a memory and speed optimization

            // Subtraction gives 0 which is never optimal
            // Division    gives 1 which is never optimal

            // Multiplication gives Xv ** 2
            // Could be == Xv if Xv== 0 or Xv == 1, but will be
            // pruned by atom - atom or atom / atom
            Int2 accu = Xv;
            accu *= accu;
            if (accu <= MAX && accu >= MIN) {
            known.maybe_store(known0, L, accu, ops, '*',
                      value, Xv, Xv, Xv);
            }

            // Addition gives Xv * 2 (!= Xv)
            if (HALF_MIN <= Xv && Xv <= HALF_MAX)
            known.maybe_store(known0, L, 2*Xv, ops, '+',
                      value, Xv, Xv, Xv);
        } else {
            auto& Z = level(known_how0, Xv, k);
            combine(L, known, known0, ops, value, Xv, Xv, Z);
        }
        if (!missing && early_exit) goto DONE;
        }
        if (max_mem != SIZE_MAX && cached > cached_next) {
        cached_next = cached + MEM_CHECK;
        if (get_memory() >= max_mem) goto DONE;
        }
    }
    }
}
// L.shrink_to_fit();
}
  DONE:
return from_value.num_sets[ops];
}

void my_main(int argc, char const* const* argv) {
GetOpt options("acfm:sSEOo:b:B:r:R:", argv);
while (options.next())
switch (options.option()) {
    case 'a': all    = true;  break;
    case 'b': {
    auto tmp = atoll(options.arg());
    ATOM_MIN = static_cast<Int>(tmp);
    if (static_cast<long long int>(ATOM_MIN) != tmp)
        throw(range_error("ATOM_MIN is out of range"));
    break;
    }
    case 'B': {
    auto tmp = atoll(options.arg());
    ATOM_MAX = static_cast<Int>(tmp);
    if (static_cast<long long int>(ATOM_MAX) != tmp)
        throw(range_error("ATOM_MAX is out of range"));
    break;
    }
    case 'c': all_carry  = true;  break;
    case 'f': find_hole  = true;  break;
    case 'm': max_mem = atoll(options.arg()); break;
    case 'S': explore    = true;  // intended drop through to single
    case 's': single     = true;  break;
    case 'o': operators  = options.arg(); break;
    case 'E': early_exit = false; break;
    case 'r': {
    auto tmp = atoll(options.arg());
    MIN = static_cast<Int>(tmp);
    if (static_cast<long long int>(MIN) != tmp)
        throw(range_error("MIN is out of range"));
    break;
    }
    case 'R': {
    auto tmp = atoll(options.arg());
    MAX = static_cast<Int>(tmp);
    if (static_cast<long long int>(MAX) != tmp)
        throw(range_error("MAX is out of range"));
    break;
    }
    case 'O': output     = false; break;
    default:
      cerr << "usage: " << argv[0] << " [-a] [-c] [-f] [-D] [-E] [-O] [-s] [-b atom_min] [-B atom_max] [r range_min] [-R range_max] [-m max_mem] [max]" << endl;
      exit(EXIT_FAILURE);
}

// Avoid silly option combinations
if (MIN > MAX) throw(logic_error("MIN above MAX"));
if (ATOM_MIN > ATOM_MAX) throw(logic_error("ATOM_MIN above ATOM_MAX"));
if (ATOM_MIN < 0)  throw(range_error("Cannot represent negative atoms"));
if (ATOM_MAX > 35) throw(range_error("Cannot represent atoms > 35"));
if (ATOM_MIN < MIN) throw(range_error("ATOM_MIN is out of range"));
if (ATOM_MAX > MAX) throw(range_error("ATOM_MAX is out of range"));

HALF_MIN = MIN / 2;
HALF_MAX = MAX / 2;

for (auto ops=operators; *ops; ++ops)
switch(*ops) {
    case '*': do_multiply = true; break;
    case '/': do_divide   = true; break;
    case '+': do_add      = true; break;
    case '-': do_subtract = true; break;
    case ':': do_dup      = true; break;
    default:
      throw(logic_error("Unknown operator"));
}
long long int const NN =
options.ind() < argc ? atoll(argv[options.ind()]) : 1;
if (NN < MIN || NN > MAX)
throw(range_error("Target number is out of range"));
N = NN;
if (N < 1) {
single = true;
output = false;
}
cerr << "N=" << N << ", using " << sizeof(Int) * CHAR_BIT << " bits without overflow" << endl;

missing = single ? 1 : N;
cached = cached_next = 0;
auto& known_how0 = known_how[0];
auto& known = known_how0.known;
auto mem = get_memory(true);
if (!mem && max_mem != SIZE_MAX)
throw(runtime_error("Cannot get memory usage on this system"));

// Start calculation
start = chrono::steady_clock::now();

// Fill in initial values [0..9]
level(known_how0, 0, 0);

// Grow number of allowed operations until all requested numbers are reached
// for (auto ops=1; ops <=5; ++ops) {
for (auto ops=1;;++ops) {
if (missing == 0) {
    if (!explore) break;
    known_how0.known.do_explore();
    if (missing == 0) break;
}
if (max_mem != SIZE_MAX && get_memory() >= max_mem) break;
auto end = chrono::steady_clock::now();
auto elapsed = chrono::duration_cast<ms>(end-start).count();
cerr << "Reaching for " << 2*ops+1 << " instructions at " << elapsed/1000. << " s";
if (mem) cerr << " (" << get_memory() / 1000 / 1000.  << " MB)";
cerr << endl;

auto old_cached = cached;
level(known_how0, 0, ops);
if (cached == old_cached) {
    cerr << "Oops, all possible numbers have been generated and we still weren't finished"  << endl;
    break;
}
}

// We are done generating all numbers.
auto end = chrono::steady_clock::now();

// Report the result
// length = 2*ops + 1
Int limit = known_how0.num_sets.size()*2-1;
cerr << "Some numbers needed " << limit << " instructions" << endl;

auto elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
stringstream out;
out << "Calculation: " << elapsed/1000.  << " s\n";
for (auto i = output ? 1 : N; i <= N; ++i) {
if (single || missing) {
    auto got = known.find(i);
    if (got != known.end())
    cout << i << ": " << got->second << "\n";
    else
    cout << i << " not generated\n";
} else
    cout << i << ": " << known.at(i) << "\n";
}
if (output) {
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "Printing:    " << elapsed/1000. << " s\n";
}

if (find_hole) {
Int hole;
for (auto i = single ? 1 : N+1; 1; ++i) {
    if (!known_how0.known.count(i) || i == 0) {
    hole = i;
    break;
    }
}
out << "First missing value " << hole << "\n";
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "Missing:     " << elapsed/1000. << " s\n";
}

if (all) {
for (auto const& entry: known_how0.known) {
    cout << entry.first << ": " << entry.second << "\n";
}
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "All:         " << elapsed/1000. << " s\n";
}

if (all_carry) {
for (auto const& carry: known_how) {
    auto carry_left = carry.first;
    if (carry_left == 0) continue;
    cout << "Carry " << carry_left << "\n";
    for (auto const& how: carry.second.known) {
    cout << "    " << how.first << ": ";
    how.second.print(cout, carry_left, true);
    cout << "\n";
    }
}
end = chrono::steady_clock::now();
elapsed = chrono::duration_cast<ms>(end-start).count();
start = end;
out << "All carry:   " << elapsed/1000. << " s\n";
}

mem = get_memory();
if (mem) cerr << "used about " << mem / 1000 / 1000.  << " MB\n";

cerr << out.str();
cerr << "Cached " << cached << " results = " << known.size() << " plain + " << cached - known.size() << " carry" << endl;
}

int main(int argc, char const* const* argv) {
try {
my_main(argc, argv);
} catch(exception& e) {
cerr << "Error: " << e.what() << endl;
quick_exit(EXIT_FAILURE);
}
// Cleaning up the datastructures can take ages
quick_exit(EXIT_SUCCESS);
}

Some test cases:

1: 1: 1
11: 3: 29+
26: 5: 29*8+
27: 3: 39*
100: 5: 19+:*
2431: 9: 56*9*9*1+
3727: 9: 69*7+:*6+
86387: 11: 67*:*1-7*7*
265729: 11: 39*:*:*2/9+
265620: 13: 99*::*6/*7+3*
1921600: 9: 77*:*:*3/
21523360: 9: 99*:*:*2/
57168721: 11: 99*6+:*8-:*
30932: 11: 159*-:4*:*+

Nice work, this is impressively fast given the difficulty of the problem! Bit of trouble though: for 38950002 your program gives 89*7+:::**1-*, which is pretty good, but you can do 299*-::*:*+ for shorter. I think this confirms the doubts I had about negative numbers...

@Sp3000: Bummer, I had only considered positive numbers. It's not hard to extend the program to also handle negative numbers but I expect it will take a severe memory and speed hit

@Sp3000 Updated for negative temporaries. The reachable range indeed went down quite a bit

int main(int argc, char const* const* argv) I don't know C better than the average Joe but what's this? a const pointer to a const pointer to a char? Shouldn't it be char const *argv[] or so (or char const **argv if you're that hardcore)?

@cat It's a pointer to (an array of) constant pointers to (an array of) constant char. To make the top level pointer constant I would have to add yet another const directly in front of argv too (which would work since I don't change argv either). Basically I promise not to change the arguments or the pointers to the arguments.

JavaScript Node Brute Force
Program file bfCodes.js
function bfCodes( n)
{   var odo = [0], valid = true, valCount=1;

    const vDUP = 10, vADD = 11, vSUB = 12, vMUL=13, vDIV = 14, vMAX = vDIV;
    const vCHARS = "0123456789:+-*/";

    function inc(sd) // increment significant digit, lsd = 0
    {   if(sd >= odo.length) { odo.push(0); console.log("length: " + (sd+1)); ++valCount; return;}
        var v = ++odo[sd]; // increment and read the base 15 odometer digit
        if( v == vDUP)
            if( valCount) {++valCount; return}
            else { odo[ sd] = vMAX; --valCount; valid = false; return;}

        if( v == vADD)
        {    if( (--valCount) < 1) { valid = false; odo[ sd] = vMAX; return;};
        }
        if( v > vMAX) { odo[sd] = 0; ++valCount; valid = true; inc(sd+1); return;}
    }

    function bfDecode( odo)
    {   var a,b,stack = [];
        for(var i = odo.length; i--;)
        {   var v = odo[ i];
            if( v < 10) { stack.push( v); continue;};
            switch(v) {
            case vDUP: stack.push( stack[stack.length-1]); continue;
            case vADD: b=stack.pop(); stack.push( stack.pop()+b); continue;
            case vMUL: b=stack.pop(); stack.push(stack.pop()*b); continue;
            case vDIV: b=stack.pop(); if(!b) return undefined; a = stack.pop();
                stack.push( (a < 0 ? b < 0 : b > 0) ? (a/b)>>0 : -(-a/b >>0)); continue;
            }
        }
        return stack[0];
    }
    var codes = [], value;
    for( var got = 0; got < n;)
    {   inc(0);
        if(!valid) continue;
        if(!(value = bfDecode( odo))) continue;
        if( value <= 0 || value > n || codes[ value]) continue;
        ++got;
        for(var i = odo.length, s=""; i--;)  s+=vCHARS[ odo[i]];
        codes[ value] = s;
    }
    return codes;
}

function main( args) // node, script, number
{   n = parseInt( args[2]);
    if(isNaN(n)){ console.log("\nTry:  node bfCodes number\nfor script saved as bfCodes.js"); return;}
    console.log("\ngenerating befunge code for numbers up to " + n);
    var start = Date.now();
    var codes = bfCodes(n);
    var end = Date.now();
    console.log("befunge codes:");
    for( var i = 1; i <=n; ++i) console.log( i + ": " + codes[i]);
    console.log(end-start + " msec");
}
main( process.argv);

Running under Windows

Download and install Nodejs, a stand alone implementation of Chromes V8 JavaScript engine.
Save the program file above in a working directory using file name "bfCodes.js" (Windows filenames are case insensitive).
Right click in the working directory and create a shortcut to the command shell program (DOS box for oldies) with target cmd.exe
Edit the shortcut's properties and set the working folder to the name of your working directory (click in the location bar and copy).
Open cmd.exe using the shortcut and check the DOS prompt starts with the working directory
Enter "node bfCodes" without quotes and enter - runing node the first time can take longer than running it again.
Enter "node bfCodes 16" to show codes up to 16. Do not use a large number!

Optimization
The algorithm cycles through all combinations of befunge characters starting with a code string of length 1. Think of it as spinning a base 15 odometer from the least significant digit. Higher order digits click over with increasing slowness. bfCodes does not evaluate generated code that would make the stack length zero or negative or leave more than one number on the stack in an attempt to optimize speed of execution.
The Brute Force Problem
For a code set of 15 characters, the time it takes to run through all combinations of a given length is give by

Tlen = 15 * Tlen-1

which is to say that if your program runs fifteen times faster than mine, you will only be able to check  one additional character code strings in the same time. To check two more characters in the same time a program would need to run 225 times faster. Time taken with a brute force approach rises exponentially as the length of code strings increases. And the magnitude of a number does necessarily indicate the number of befunge bytes needed to generate it.
Some figures.
Approximate times to generate a lists of codes on a Windows 7 32 bit notepad for integers up to

9:   1 msec
10: 16 msec
32: 156 msec
81: 312 msec
93: 18.5 seconds
132: 28 seconds

To generate befunge for 3727 (which is 66 squared plus 6) by itself took 1 hour 47 minutes and generated 578*+:*6+
Optimal code generation
Generating befunge for numbers without checking for shortest lengths is relatively simple. Using a recursive algorithm which used integer square roots and remainders, encodings for numbers up to 132 took about 3 msec instead of 28 seconds. They were not optimal. Because of the way it worked this particular algorithm produced638:*-:*+ for 3727 in about 1 msec (instead of an hour or so) which happened to be optimal.
The issue with providing a non brute force method is proving it is optimal in every case. Good luck!

You should be able to lower your exponent by a lot by observing that your string must represent a valid evaluation tree with +-*/ at the inner nodes and 0-9 and : at the leaves (and : cannot be leftmost). So generate and evaluate all valid tree of size 2*n+1 at step n (n starts from 0) and convert them to a strings when needed

3727 is 61 squared plus 6, not 66 :)

JavaScript
Whant can be done with a JS snippet? In my machine, Firefox 64 bit, 416 in 60 seconds

function go() {
    B.disabled=true
    O.textContent = '...wait...'
    setTimeout(run, 100)
}

function run()
{
 var o=[0],
 t0=performance.now(),
 te=t0+T.value*1000,
 k=[],t=[...'0123456789'],i=0,n=0,e,v,j,l,x,h
 MainLoop:
 for(;;)
 {
   for(;!k[n] && (e=t[i++]);)
   {
     if(performance.now()>te)break MainLoop

     for(v=[],j=0;x=e[j++];l=x)
       1/x?h=v.push(+x):(b=v.pop(),x>'9'?h=v.push(b,b):(a=v.pop(),h=v.push(x<'+'?a*b:x<'-'?a+b:x<'/'?a-b:a/b|0)))
     if(!k[v])
     {
       k[v]=e
       //if(!e[10])
       {
         if (l==':')
           t.push(e+'+',e+'*')
         else if (h>1)
         {
           if (l == '1') t.push(e+'+',e+'-')
           else if (l != '0') t.push(e+'+',e+'-',e+'*',e+'/')
         }
         if (h<4)
         {
           if (l<'0'|l>'9') t.push(e+':');
           [...'0123456789'].forEach(x => t.push(e+x))
         }
       }
     }
   }
   o.push([n,k[n]])
    ++n;
 }
 o[0]='Run time sec '+(performance.now()-t0)/1000+'\nTried '+t.length+'\nRange 0..'+(n-1)+'\nTop '+k.pop()+' '+k.length
 O.textContent=o.join`\n`
    B.disabled=false
}
Time limit sec:<input id=T type=number value=60><button id=B onclick='go()'>GO</button>
<pre id=O></pre>


text:
Convert to Roman Numeral!
Your task is to convert a given positive integer from Arabic numeral to Roman numeral.
Things get difficult when you count to 4000.
The romans did this by adding a line above a symbol to multiply that symbol by 1 000. However, overlines aren't exactly displayable in ASCII. Also, there are double overlines to multiply a symbol by 1 000 000, and then triple overline to multiply a symbol by 1 000 000 000, etc...
Therefore, I decided to use parentheses to replace overlines.
The symbols can be individually placed in parentheses. For example, both (VI) and (V)(I) are valid representations of 6 000. (V)M is also a valid representation of 6000.
(I) is a valid way to represent 1 000.
Testcases
Input: 1
Output: I
Input: 2
Output: II
Input: 3
Output: III
Input: 4
Output: IV
Input: 15
Output: XV
Input: 40
Output: XL
Input: 60
Output: LX
Input: 67
Output: LXVII
Input: 400
Output: CD
Input: 666
Output: DCLXVI
Input: 3000
Output: MMM
Input: 3999
Output: MMMCMXCIX
Input: 4000
Output: M(V)
Input: 4999
Output: M(V)CMXCIX
Input: 6000
Output: (VI)
Input: 6000000
Output: ((VI))
Input: 6006000
Output: ((VI)VI)
Input: 6666666666
Output: (((VI)DCLXVI)DCLXVI)DCLXVI

Scoring
This is code-golf. Shortest code in bytes win.

The justification for why this isn't a duplicate clutters the spec. It would be better without it IMO.

Where would I add the justification?

Leave it out. If someone questions whether or not it is a duplicate, have the discussion in comments or in chat.

@Mego Done. :-)

Is (IV) an acceptable representation of 4000?

Yes, clarified.

@Neil For that case, you can output which one you want, 'cause (IV) and MMMM are the same length in bytes.

@ErikKonstantopoulos Not really. MMMM is not accepted.

Possible duplicate of Roman numeral converter function

@mbomb007 That's the opposite direction.

Mathematica, 67 bytes
Fold["("<>#<>")"<>#2&,RomanNumeral[#~IntegerDigits~1000]/."N"->""]&

Avoids all trouble with M by converting the input to base 1000 and converting each digit separately with RomanNumeral. Then we fold them up by inserting (...) from the left.
Unfortunately, Mathematica represents zeros as N so we need to get rid of those.

darn mathematica with its builtins for everything >:(

@OldBunny2800 I'd be surprised if this wasn't beaten by any of the golfing languages anyway though.

@OldBunny2800 And it costs real money to get it. That's bad.

@MartinBüttner I thought simply RomanNumeral can do it?

@KennyLau It outputs MMMM for 4000, it only starts working to spec at 5000 (and then you get the same problem for 4000000 etc.). Even then, it uses overbars instead of parentheses. If you're fine with that, you should say so in the challenge specification.

JavaScript (ES6), 136 bytes
f=n=>n<4e3?"M1000CM900D500CD400C100XC90L50XL40X10IX9V5IV4I1".replace(/(\D+)(\d+)/g,(_,r,d)=>r.repeat(n/d,n%=d)):`(${f(n/1e3)})`+f(n%1e3)

For numbers under 4000, repeats each Roman "letter" as many times as possible, using the list of Roman "letters" and their decimal values. Otherwise recursively builds up the answer from the division and modulo with 1000. Fortunately repeat truncates so I don't have to do it myself.

Common Lisp, 108
(defun p(n)(if(> n 0)(if(< n 4000)(format()"~@R"n)(format()"(~A)~@[~A~]"(p(floor n 1000))(p(mod n 1000))))))

Ungolfed
(defun p(n)
  (if (> n 0)
      (if (< n 4000)

          ;; Built-in Roman formatter (between 1 and 3999)
          (format () "~@R" n)

          ;; Divide N by 1000, as 1000*Q + R.
          ;; First print (p Q) in parentheses (recursively)
          ;; Then, if it is not NIL, the remainder R.
          (format () "(~A)~@[~A~]"
                  (p (floor n 1000))
                  (p (mod n 1000))))))

Tests
Two tests give different outputs than the ones from the question:
(loop for (in out) in '((1 "I")
                        (2 "II")
                        (3 "III")
                        (4 "IV")
                        (15 "XV")
                        (40 "XL")
                        (60 "LX")
                        (67 "LXVII")
                        (400 "CD")
                        (666 "DCLXVI")
                        (3000 "MMM")
                        (3999 "MMMCMXCIX")
                        (4000 "M(V)")
                        (4999 "M(V)CMXCIX")
                        (6000 "(VI)")
                        (6000000 "((VI))")
                        (6006000 "((VI)VI)")
                        (6666666666 "(((VI)DCLXVI)DCLXVI)DCLXVI"))
   for computed = (p in)
   unless (string= out computed)
   collect (list in out computed))

=> ((4000 "M(V)" "(IV)")
    (4999 "M(V)CMXCIX" "(IV)CMXCIX"))

Ruby, 137 134 130 129 bytes
Recursive function that returns the string. I'm trying to golf down the numeral encodings a bit more if possible, but I'm not sure how.
Whoops, it's practically a direct port of @Neil's ES6 answer now.
f=->x{(x<t=1e3)?"CM900D500CD400C100XC90L50XL40X10IX9V5IV4I1".gsub(/(\D+)(\d+)/){s=x/v=eval($2);x%=v;$1*s}:"(#{f[x/t]})#{f[x%t]}"}

Attempt This Online!

An anonymous user has suggested a golf: {v=$2.to_i;s=x/v;x%=v;$1*s} to {s=x/(v=eval$2);x%=v;$1*s} (saves 1 byte).

Ruby, 185 161 144 bytes
r=->i{i>(t=1e3)? "(#{r[i/t]})"+r[i%t]:(s=?I*i;"IVXXLCCDM".scan(/(.)(.)(.)/){|x,y,z|{x*5=>y,x*4=>x+y,y*2=>z,y+x+y=>x+z}.map{|x,y|s.gsub!x,y}};s)}

Over a year after the original post, I think I learned something about golfing.
Thank you Value Ink for your valuable comments.

gsub can take a string as the first argument, removing the need for substitutions into a regex pattern since s.gsub! x,y does it automatically. Other than that, you can probably just forgo the assignment of your a array since you only use it once, and put it directly into the each_slice call.

"IVXXLCCDM".scan(/(.)(.)(.)/){|x,b,c|... works too

Also r[x] is functionally equivalent to r.(x) whenever stabby lambdas are involved

@ValueInk thank you. That r[x] trick is going to be useful for all my futer recursive golf in ruby!

Hi sorry to ask so late, but is there a way instead of doing (III), to do MMM?

@DialFrost Replacing i>(t=1e3) with i>=4*(t=1e3) would do that.

R, 134
m=1000;x=scan();while(x[1]>=m)x=c(floor(x[1]/m),x[1]%%m,x[-1]);cat(rep("(",length(x)),sep="");cat(as.character(as.roman(x)),sep=")")

It's pretty much not the best option, but I think the idea should go pretty similar to this.

TCL 134 bytes
proc f r {
set map {M 1000+ CM 900+ D 500+ CD 400+ C 100+ XC 90+ L 50+ XL 40+ X 10+ IX 9+ V 5+ IV 4+ I 1+}
expr [string map $map $r]0}

Try it here: https://rextester.com/BJC92885

Python, 188 194
-6 bytes from getting rid of some whitespace
This challenge brought me back to when I was first learning to program...
def f(x,s=zip("M CM D CD C XC L XL X IX V IV I".split(),[1e3,900,500,400,100,90,50,40,10,9,5,4,1])):
 r=""if x<4e3else"("+f(x/1e3)+")";x%=1e3
 for a,b in s:
    while x>=b:r+=a;x-=b
 return r

It might not be the shortest solution, but I had fun golfing this problem.
Try it out!

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:
Form tiles in a rectangular ring
Given the input tilesX and tilesY create a method that would make a rectangular ring from the tiles.
The function must order the tiles in a ring like this:

tilesX and tilesY are always positive integer values, cannot be 0
tilesX and tilesY are not always equal, expect values like: 2x5, 6x3 etc.
Checking for invalid input is not necessary
You can use any way to display the tiles, including 2d arrays, ASCII art or printed text.
There's no strict way how the input is passed as long as it's two integers.
Cannot be a line, drawing a rectangle size of tilesX and tilesY pixels is not valid
The shortest code wins

Could you give examples of input/output ?

Can we use a full program as well as a function?

@FliiFe Input is two integers ( cannot be negative or null ), output is a printed image like in the image attached.

Can the output be a 2D array?

@muddyfish I would very much prefer the solution to be mathematical and not a part of some API.

@Doorknob sure, that's totally valid

You can use any way to display the tiles You should clarify this. Can it be ASCII art? Any characters?

@LuisMendo yes, you can use ASCII art or any characters if you want to display it in the output window/console. I'll update the question.

Sorry for the bombardment, but some clarifying questions, part 1: 1) Is the expected output an image (e.g. JPG/PNG/displayed to screen) or ASCII-art? You seem to mention both in the comments, 2) Is the "4x4" or similar text part of the output? 3) Any rules on spacing between the tiles?

@Sp3000 no rule how to display the image, it can be text ( but I thought Mathematica golfers might want to output an image and not text ). No rule on how to pass the input, so long as the input are two integers. No rule for spacing the tiles. Each tile can be viewed as a pixel.

In that case I'd recommend giving example outputs for ASCII art as well so people know what's allowed (allowing both image and ASCII output's a bit weird, but your choice I guess). I'd also suggest removing mentions of "square" if the width/height are taken as input, since that might confuse people.

Clarifications part two: 4) In the case of ASCII output, any rules on what characters are allowed to represent the tiles and the blank space in between?

I also suggest that you allow either a function or a program, as usual on this site.

@Sp3000 absolutely any characters can be used to represent the tile. There's no space between the tiles in case of ASCII/text output, the tiles must be neighboring to each other.

@CreativeMagic If the output is an array, can we use the language's default displaying of arrays, even if that means spaces between the numbers? (see my answer for example)

@LuisMendo it's allowed, but it's simply my own preference to have the logic of placing the tiles in the method, other than that it's pretty free.

Related. Related.

@CreativeMagic When you say "cannot be a line... drawing a rectangle size is not valid", do you mean that it cannot be a thin line? That is, if the "line" becomes a frame one tile thick (see my answer) is it valid?

@LuisMendo your answer is valid, I just wanted to prevent a hack that would use drawing API's of some languages for example drawRect( 0, 0, tilesX, tilesY )

Dyalog APL, 8 bytes
×/¨1<⊂|⍳

This monadic function train takes height and width as right arguments and returns a 2D array of 0's (border) and 1's (interior). Test it on TryAPL.
How it works
×/¨1<⊂|⍳  Right argument: h w

       ⍳  Generate all index pairs (1-based) of a h×w array.
     ⊂    Enclose (h w), so it depth matches the one of the index array.
      |   For each pair (i j) compute the remainders of the division by (h w).
   1<     Compare all remainders with 1.
×/¨       Reduce each pair of Booleans by multiplication.

MATL, 10 bytes
2$lO6Lt4$(

This outputs an array containing zeros and ones.
Try it online!
2$l    % Implicit inputs M, N. Generate M×N array of ones
O      % Push number 0
6Lt    % Push [2 -1] twice, corresponding to index "2:end-1"
4$(    % Fill the center of the array with value 0. Implicit display

For graphical output, add 1YG at the end to display the array as an image  (13 bytes) :
2$Ol6Lt4$(1YG

Try it at MATL Online! For example,
>> matl 2$Ol6Lt4$(1YG
> 5
> 7

produces

@Sp3000 You're right... I couldn't resist :-) Anyway, the OP has clarified that an array or ASCII art with any characters is valid output

@LuisMendo great work, but it has to have two values passes to the method

@CreativeMagic Sorry. Corrected now. Maybe rephrase the challenge? "Square ring" may be confusing

@LuisMendo not trying to make an excuse, but English is not my first language, if you can give me a better title, I'd be happy to hear it.

@CreativeMagic Maybe "rectangular ring" instead of "square ring"?

@LuisMendo thanks, I've edited ^.^ Sorry for the confusion.

@CreativeMagic No problem!

@LuisMendo Should inputs of 1 and 1 return a value of 1 or 0?

@Suever According to the first image in the OP, the output is 1 in that case

According to my interpretation the graphical output would be invalid as the tiles should not form a solid line.

@Neil The OP says Cannot be a line. I took that as "it cannot be a line without the appropriate thickness, corresponding to one tile". I'll ask them

So yes, one-tile thick line is valid

@CreativeMagic Thanks for the accept, but there's a shorter answer now

MATLAB, 32 31 bytes
@(x)conv2(ones(x),eye(3),'s')>2

This creates an anonymous function which can then be run as ans([4 5]) within the workspace.
Input is [height, width] and output is a matrix with 1 in the center and 0 for the boundary.
The way that this works is a matrix of ones the size of the input is created. It is then convolved with a 3 x 3 identify matrix with ones on the diagonal. We use the same input to conv2 (shortened to 's' here) to keep the result the same size as the input.
We then want to convert the output to a binary value with 0 around the boundary and 1 inside. We use the inequality >2 because all edge pixels will have a result < 3 and all non-boundary elements will have a result equal to 3.
For graphical output:
@(x)imagesc(conv2(ones(x),eye(3),'s')>8)
ans([6,9])

MATL, 10 bytes
2$l3XyZ+3=

Input arguments are height and width as integers. The output is a matrix of size height x width where the boundary tiles are 0 and the inner values are 1.
Try it Online!
Explanation
Same logic as my other answer with fewer bytes.
        % Grab two input parameters implicitly
2$l     % Create a matrix of ones that has the dimensions specified as inputs
3       % Number literal 3
Xy      % Create a 3x3 identity matrix
Z+      % Perform 2D convolution (preserving size)
3=      % Create a logical matrix where values == 3 are 1 and 0 otherwise (boundary)
        % Implicitly display output.

HTML/JS/CSS, 198 194 bytes
Graphical output version. The byte count doesn't include f= nor the three <input> elements which are used for demonstration purposes only. Saved 3 bytes thanks to @IsmaelMiguel.

f=(n,m)=>{with(d.style)width=n*25+'px',height=m*25+'px'}
<input id=w placeholder=width><input id=h placeholder=height><input type=button value=Go! onclick=f(w.value,h.value)>

Can't f=(n,m)=>{d.style.width=n*25+'px';d.style.height=m*25+'px';} be simplified to f=(n,m)=>with(d.style)width=n*25+'px',height=m*25+'px';?

@IsmaelMiguel The with does save me 3 bytes but I still need the {}s. On the other hand the ; is unnecessary so I removed that too.

Jelly, 10 bytes
p%€,>1P€G

Returns a grid of 0's (border) and 1's (interior). Try it online!
How it works
p%€,>1P€sG  Main link. Arguments: h (height), w (width)

p           Cartesian product; return all pairs in [1, ..., h] × [1, ..., w].
   ,        Yield the pair [h, w].
 %€         For each pair [i, j] in the product, compute [i % h, j % w].
    >1      Compare all resulting moduli with 1.
      P€    Compute the product of each pair of Booleans.
        s   Split the resulting flat list into rows of length w.
         G  Display the results in a 2D grid.

This answer is great, but it has to visually be a rectangular ring. While it's fine to use arrays, strings etc., it has to look like a ring on the screen when you run it.

OK. When I read that 2D arrays were allowed, I didn't expect their visual representation to matter. I've edited my answer.

@Dennis "[I]t has to look like a ring on the screen when you run it". That means spaces should be used?

Julia, 46 34 bytes
f(n,m)=[n>i>1<j<m for i=1:n,j=1:m]

This is a function that accepts two integers and returns a 2-dimensional boolean array.
We construct an n × m matrix using an array comprehension with a double for loop. For each index from 1 to n and 1 to m, i.e. each element of the matrix, we set the value to true if n > i > 1 and 1 < j < m. This is true everywhere but the boundaries, so the resulting array will have trues in the middle and falses around the border.
Examples:
julia> f(n,m)=[n>i>1<j<m for i=1:n,j=1:m]
f (generic function with 1 method)

julia> f(4,4)
4x4 Array{Bool,2}:
 false  false  false  false
 false   true   true  false
 false   true   true  false
 false  false  false  false

julia> f(1,1)
1x1 Array{Bool,2}:
 false

julia> f(2,5)
2x5 Array{Bool,2}:
 false  false  false  false  false
 false  false  false  false  false

Saved 12 bytes thanks to Dennis!

J, 12 bytes
*/&(<:*@|i.)

Try it online!
Coming back to this, almost 3 years later.  An idea inspired by Dennis answer, though not a translation.

i. Create 0 based index lists from each arg
<: | remainders when divided by the arg minus 1
*@ signup the results.  Now, eg, if an arg was 4, we'll have a list like 0 1 1 0
*/ Create a multiplication table of those lists.

Original Answer, 16 bytes
0(<2#<<0 _1)}$&1

Use shape $ to create a rectangle of all ones the size of the inputs, and then use the complementary form of Amend } to turn the interior to zeros.
Try it online!

Pyke, 16 15 bytes
jQ]Uajt%!RQt%!|

Try it here!
Explanation:
                - Q = eval_input()
j               - j = eval_input()
jQ]             - [Q,j]
   U            - create a 3d array sized Q by j with coords
    a           - for each coord (2d for)
     jt%!       -   not (coord_1 % j-1)
              | -  ^ or V
          Qt%!  -   not (coord_2 % Q-1)

For prettified output, use this code.
Or 13 bytes with a zeroed out mask round the edge (middle chars non-zero)
jQ]Uajt%RQt%&

Try it here!

CJam, 20 bytes
l~S*a*{3a.f|W%z}4*N*

Input should be in the form height width, output is an ASCII grid using spaces for the centre and # for the boundary.
Test it here.
Explanation
l~       e# Read and evaluate input, dumping h and w on the stack.
S*       e# Create a string of w spaces.
a*       e# Create an array of h copies of that string.
{        e# Repeat this block 4 times...
  3a.f|  e#   For each character in the first row, take its bitwise OR with 3, turning
         e#   spaces into # and leaving # unchanged.
  W%z    e#   Reverse and transpose the grid, rotating it by 90 degrees.
}4*
N*       e# Join the lines of the result with linefeeds.

JavaScript (ES6), 80 82 85
Edit 3 bytes saved thx @Neil
Edit 2 bytes saved using reduce for once
Anonymous function returning a multi line string
(w,h)=>[...Array(h)].reduce(o=>o+(w>1?'O'+' O'[!--h|!o].repeat(w-2):'')+`O
`,'')

Test

f=(w,h)=>[...Array(h)].reduce(o=>o+(w>1?'O'+' O'[!--h|!o].repeat(w-2):'')+`O
`,'')

function test(){
  var [w,h] = I.value.match(/\d+/g)
  w=+w,h=+h // convert to numeric
  O.textContent=f(w,h)
}

test()
<input value='5 4' id=I><button onclick='test()'>Test</button>

Surely !--h|!o is already an integer? Otherwise, I like the use of !o.

Ruby, 63 bytes
Anonymous function, prints to STDOUT. Border is #.
->x,y{h=?#;puts t=h*x,y>1?[[h+(x<2?'':' '*(x-2)+h)]*(y-2),t]:p}

Sorry, you must output a ring, so no backticks allowed inside.

And there goes the one byte I had been hoping to save by filling the inside with a small less-noticeable character...

Perl 5, 45 + 1 (-p) = 46 bytes
$_=join$/,(1x$_)x<>;1while s/
.+\K1(?=.+
)/ /

following 45 bytes doesn't handle tileY=1
$_=1x<>.$/;say$_.s/(?!^.|.$)./ /gr x(<>-2).$_

Try it online

JavaScript (ES6), 97 bytes
(n,m)=>Array(n).fill(' '.repeat(m).replace(/^ | $/g,0)).join`
`.replace(/^.+|.+$/g,'0'.repeat(m))

Creates a ring of 0s. Probably a terrible approach but I wanted to avoid edge cases.

JavaScript (ES6), 77 bytes
h=>w=>[...Array(i=h)].map(_=>(a=Array(w).fill(h-i--&&i?0:1),a[0]=a[w-1]=1,a))

I don't like the array of array output (even if it's allowed). What I see in console is f(4)(4) -> Array [ Array[4], Array[4], Array[4], Array[4] ]

Retina, 45 43 bytes
\d+
$*
S_`1(?=.* (1+))|.
T`1`#`^.+|.+$|.?¶.

Input should be in the form height width, output is an ASCII grid using 1 for the centre and # for the boundary.
Try it online!
Explanation
\d+
$*

Convert each number N to a string of N ones (i.e. convert the input to unary).
S_`1(?=.* (1+))|.

Match each 1 in height and replace it with width, while also matching everything else and removing it. We do this by abusing a split stage. This creates a w x h grid.
T`1`#`^.+|.+$|.?¶.

Finally we replace every 1 with a # that is either found in the first line, the last line or at the beginning or end of a line.

Actually, 23 bytes
;'#*;))¬' *'#;)@+(+nXX(

Try it online!
This approach is very similar to my approach in this related challenge.
Explanation:
;'#*;))¬' *'#;)@+(+nXX(
                         (implicit) push all input to stack
;'#*                     push a string containing X #s
    ;))                  dupe, and push both to bottom of stack
       ¬' *              push a string containing (X-2) spaces
           '#;)@+(+      add a # to the front and the back of the string
                   nXX   make (Y-2) copies
                      (  bring one of the "#"*X strings back to the top
                         (implicit) pop and print each stack item, separated by newlines

If Seriously v3 isn't called Wait, Really? I'll be quite disappointed.

@AlexA. Did you seriously just?

TSQL, 107 105 97 bytes
DECLARE @ INT=3,@y INT=5

PRINT REPLICATE(1,@)+ISNULL('
'+REPLICATE('1'+ISNULL(SPACE(@-2),'')+'1
',@y-2)+REPLICATE(1,@),'')

generating first line
adding hollow lines + line breaks
adding last line(when needed)

QBasic, 69 bytes
INPUT x,y
FOR i=1TO y
FOR j=1TO x
?i MOD y<2OR j MOD x<2;
NEXT
?
NEXT

Takes dimensions as width,height. The boolean value from the is-it-on-the-border test is simply printed: -1 for true and 0 for false. A sample run looks like:
? 5,3
-1 -1 -1 -1 -1
-1  0  0  0 -1
-1 -1 -1 -1 -1

Bonus: Graphical version, 88 bytes
INPUT x,y
SCREEN 9
FOR i=1TO y
FOR j=1TO x
PSET(j*3,i*3),i MOD y<2OR j MOD x<2
NEXT
NEXT

I believe this counts as "not a line." When the MOD expression is false (0), PSET plots a black pixel; when it's true (-1), PSET apparently plots a white pixel. Here's 17,31, shown at 2x size:

Perl 5, 76 + 1 (-a) = 77 bytes
print(1x($a=$F[0]),$/,((1,$"x($a-2),1 x($a>1),$/)x($F[1]-2),1x$a)x($F[1]>1))

Try it online!

Unicorn, 26 23 bytes
P3G$PG@PS@S$L2B$T1B@T1N

Because who doesn't like unicorns?!
Explanation ("list program" output):
P3  Paint current square with 3
G$P Get: sets $ from input P
G@P Get: sets @ from input P
S@  Subtract 1 from @
S$  Subtract 1 from $
L2  ~Loop 2 times
B$  ~Brush $ more square
T1  ~Turn 1 right angle clockwise
B@  ~Brush @ more square
T1  ~Turn 1 right angle clockwise
N   ~Next (loop)

Output for tilesX = 3, tilesY = 5:

Note: This version only works for tilesX up to 6 and tilesY up to 5. The question does not mention what range we need to support though, so I'm assuming this is OK. Otherwise, a small addition to the program produces this alternative, which supports a slightly larger range:
Unicorn, 30 27 bytes
x0y9P3G$PG@PS@S$L2B$T1B@T1N

By adding x0y9, which starts the box at (0,9), the program works for tilesX up to 9 and tilesY up to 9 (because input only goes up to 9).

05AB1E, 6 bytes
«¾6ÅÈΛ

Input as a pair of integers, where the first is the height and the second is the width.
Outputs with 0 as characters.
Try it online.
Explanation:
     Λ  # Use the Canvas builtin with the following three options:
        # (after which the resulting shape is output implicitly immediately afterwards)
«       # - line lengths: use the (implicit) input-integer, merged with itself: [h,w,h,w]
  6ÅÈ   # - the directions: push a list of even integers <= 6: [0,2,4,6]
 ¾      # - what to draw: push the counter variable, which is 0 by default

The Canvas builtin uses three arguments to draw a shape:

Character/string to draw: character 0, which could alternatively be 1/2 by replacing the ¾ with X/Y respectively.
Length of the lines we'll draw: the input-list twice. Since there is more than one input-length, these are leading for the Canvas builtin, so we'll need the additional merge « at the start, otherwise it would only draw the top and left borders, instead of the entire box.
The direction to draw in: [0,2,4,6]. The digits in the range \$[0,7]\$ each represent a certain direction:

7   0   1
  ↖ ↑ ↗
6 ← X → 2
  ↙ ↓ ↘
5   4   3

So the [0,2,4,6] in this case translate to the directions \$[↑,→,↓,←]\$.
Here a step-by-step explanation of the output (we'll use input-lengths [3,5] as example here):
Step 1: Draw 3 0 characters in direction 0↑:
0
0
0

Step 2: Draw 5-1 0 characters in direction 2→:
00000
0
0

Step 3: Draw 3-1 0 characters in direction 4↓:
00000
0   0
0   0

Step 4: Draw 5-1 0 characters in direction 6←:
00000
0   0
00000

See this 05AB1E tip of mine for an in-depth explanation of the Canvas builtin.

Charcoal, 4 bytes
ＢＮＮ*

First input is the width, second input is the height.
Try it online (verbose) or try it online (pure).
Explanation:
ＢＮＮ*
Box(InputNumber(),InputNumber(),"*")

Builtin: draw a box using the two input as width/height respectively and character * as border. (The * can be replaced with other ASCII characters that are available in the Charcoal codepage.)

Python 3, 71 67 63 bytes
lambda n,m:[[n>i+1>1<j+1<m for i in range(n)]for j in range(m)]

Returns a 2 dimensional array. Try it online!
Port of Alex A.'s answer.
-4 thx to @Steffan

63

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


text:
Seeking Leapers
I recently got a really weird irregular chess board. It's squares are all over the place and not even all connected. At least they're still laid out on a regular grid. I want to adapt the chess rules to be able to play on the board, but to start with, I need a piece that can actually go anywhere on the board, and it seems a leaper is my best bet for that.
Leapers are the fairy chess generalisation of knights. Leapers are parameterised by two integers m and n and can move m squares in one direction and then another n squares in either perpendicular direction. For the standard knight, we have (m, n) = (2, 1). The entire move is considered a single jump such that none of the squares on the way to the target need to be empty or even exist.
The Challenge
You're given a "chess board" in the form of a list of positive 2D integer coordinates which represent the squares that are part of the board. Your task is to find a leaper which, given enough moves, can reach any square on the board.
Let's look at some examples. The standard chessboard uses a regular grid of 8x8 squares (note that we don't distinguish between white and black squares for this challenge):
########
########
########
########
########
########
########
########

The standard knight can reach all of those, so (2, 1) would be a valid output. However, (1, 1) for example wouldn't be valid, since such a piece can only reach half of the squares no matter where it starts. (1, 0) on the other hand would also be a valid output, since all the squares are orthogonally connected.
Now if we have an irregular board like:
#   #
 # # #
  # # #
 # #
    #

Then possible solutions are (1, 1) and (3, 1). We can also have a board with completely disconnected regions like:
#### ####
#### ####
#### ####
#### ####

The standard knight (2, 1) can still reach all of the squares here, which is in fact the only solution.
And finally, the following simple board cannot be completely reached by any leaper at all:
#
 ##

Note that the input format will not be as an ASCII representation but a list of coordinates instead. E.g. the second example above could be given as:
[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]]

Rules
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.
The input coordinates can be taken in any convenient list format (flat list, list of pairs, list of complex integers, string with consistent separators, etc.).
The output should be the two integers m and n that identify the leaper if a solution exists (as two separate integers, a list, a string with non-numeric delimiter, etc.). If no solution exists, you may output any consistent value which cannot possibly be a valid leaper. This includes the pair of integers (0, 0) in your normal format, as well as anything that isn't a pair of non-negative integers.
Your program needs to handle any of the test cases within a minute. This is a somewhat fuzzy restriction, but use common sense: if it takes 2 minutes on your machine, I think we can assume that it might run within 1 on someone else's, but if it takes 20 that's less likely. It shouldn't be hard to solve each test case in a matter of seconds, so this rule only acts to rule out naive brute force.
Standard code-golf rules apply.
Test Cases
Each test case is of the form board => all valid leapers. Remember that you only need to output one of those. If the list of leapers is empty, make sure to return something that isn't a valid leaper.
Examples above:
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [6, 8], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7], [7, 8], [8, 1], [8, 2], [8, 3], [8, 4], [8, 5], [8, 6], [8, 7], [8, 8]] => [[0, 1], [1, 2], [1, 4], [2, 3], [3, 4]]
[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]] => [[1, 1], [1, 3]]
[[1, 1], [2, 2], [3, 2]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => [[1, 2]]

Square boards:
[[1, 1], [1, 2], [2, 1], [2, 2]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [2, 3]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7]] => [[0, 1], [1, 2], [2, 3]]

Miscellaneous:
[[1, 1], [2, 1]] => [[0, 1]]
[[1, 1], [1, 2]] => [[0, 1]]
[[1, 1], [12, 35]] => [[11, 34]]
[[1, 1], [1, 2], [2, 1], [2, 2], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 5], [3, 6], [4, 1], [4, 2], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [1, 4]]
[[2, 2], [2, 4], [2, 6], [2, 8], [4, 2], [4, 4], [4, 6], [4, 8], [6, 2], [6, 4], [6, 6], [6, 8], [8, 2], [8, 4], [8, 6], [8, 8]] => [[0, 2], [2, 4]]

Random boards:
[[1, 5], [1, 9], [2, 6], [2, 8], [2, 10], [2, 12], [3, 5], [3, 7], [3, 9], [3, 11], [3, 13], [4, 2], [4, 4], [4, 6], [4, 8], [4, 14], [5, 1], [5, 3], [5, 5], [5, 7], [6, 2], [6, 4], [7, 1], [8, 2]] => [[1, 1], [1, 3]]
[[1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 6], [3, 7], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 3], [5, 4], [5, 6]] => [[0, 1], [1, 2]]
[[1, 8], [2, 6], [2, 10], [3, 3], [3, 4], [3, 8], [4, 1], [4, 11], [5, 3], [5, 9], [6, 12], [8, 11], [10, 10], [11, 12], [12, 6], [12, 8], [13, 6], [13, 8], [13, 10], [13, 11], [14, 5], [14, 7], [14, 8], [14, 13], [14, 14], [15, 7], [15, 9], [15, 11], [15, 12], [16, 6], [16, 7], [16, 9], [16, 13], [16, 14], [17, 10], [17, 12], [18, 8], [18, 12], [20, 9], [21, 11], [22, 13], [23, 10], [23, 11], [23, 15], [24, 12]] => [[1, 2]]
[[1, 17], [1, 21], [3, 11], [3, 15], [3, 19], [3, 23], [5, 13], [5, 21], [7, 11], [7, 15], [7, 19], [9, 1], [9, 13], [9, 17], [11, 3], [11, 7], [11, 15], [11, 19], [13, 5], [13, 9], [13, 13], [13, 17], [13, 21], [15, 11], [15, 15], [15, 19], [17, 13], [17, 17]] => [[2, 2], [2, 6], [2, 10]]
[[1, 3], [2, 4], [2, 5], [3, 6], [4, 1], [5, 3], [5, 6], [5, 7], [6, 12], [6, 14], [6, 21], [7, 9], [7, 19], [8, 9], [8, 15], [8, 17], [8, 18], [8, 24], [9, 12], [9, 19], [10, 12], [10, 14], [10, 17], [10, 21], [11, 22], [12, 15], [12, 17], [12, 24], [13, 16], [14, 20], [14, 21], [14, 26], [15, 13], [15, 19], [16, 18], [16, 23], [17, 16], [17, 24]] => [[2, 3]]
[[1, 11], [3, 13], [4, 10], [6, 14], [8, 12], [9, 9], [9, 15], [12, 8], [13, 5], [13, 19], [13, 21], [14, 8], [15, 1], [15, 17], [16, 4], [16, 14], [16, 18], [16, 20], [17, 21], [18, 2], [18, 16], [18, 18], [19, 9], [19, 13], [19, 15], [20, 12], [21, 1], [21, 17], [22, 4], [22, 10], [23, 7]] => [[1, 3]]
[[1, 39], [6, 37], [8, 32], [10, 27], [11, 31], [11, 35], [12, 22], [16, 21], [16, 29], [16, 33], [18, 34], [21, 3], [21, 9], [21, 19], [23, 8], [23, 14], [23, 22], [23, 24], [23, 36], [24, 6], [25, 13], [25, 17], [26, 1], [26, 11], [28, 6], [28, 20], [28, 26], [28, 30], [28, 34], [30, 11], [30, 15], [30, 21], [32, 6], [33, 28], [33, 32], [35, 13], [35, 23]] => [[2, 5]]

As a special case, note that for a board consisting of only one cell, any leaper works, but your output must correspond to an actual leaper, so [0, 0] is not valid output.

Quick question. How is a knight (2,1)? Correct me if I'm wrong, but I'm pretty sure knights can move 3 squares in any one direction, and then 1 square in any direction perpendicular to the previous one, so it should instead be (3,1).

@R.Kap You're wrong. ;) https://en.wikipedia.org/wiki/Knight_(chess)#Movement

@DLosc Ok, wow. I guess I was. Thanks for that!

May we output all valid leapers in a list? If we do, can we output equivalent leapers like [[1, 0], [0, 1]]?

@FryAmTheEggman Just (any) one of them, please.

Pyth, 41 35
hfqQu@+G+VM*s_BM*F_BMTGQ]hQ)maVhQdt

Exits on error if there are no valid leapers, giving the empty string if STDERR is ignored.
Try it here or run a Test Suite
Saved 6 bytes thanks to isaacg! Basically just finds all leaper candidates by selecting each valid leaper from the first tile to each other tile. Then for each of these, it makes all eight configurations of [x, y] offsets that the leaper could take. It then finds all moves starting from the first tile that follow after the move, and discards those that are not in the input. It keeps doing this until the result doesn't change. If this final list is the same as the input then the leaper was valid.
The standard chess board took the longest when I was testing, it took about 3 seconds on my not very impressive computer.


text:
A Numpad's Knight Numbers
For the non-zero digits on a standard numpad
789
456
123

consider placing a chess knight at any digit and moving it around with any number of normal L-shaped jumps, tracing out a positive decimal integer. What positive integers can be expressed in such a way?
One of them is 38, since the knight could start on the 3 and move left and up to the 8. 381 and 383 are also possible.
3 itself is possible if no jumps are taken (which is allowed). 5 is as well, but no other digits can be reached from the 5, so it is the only number where the digit 5 appears.
Write a program or function that takes in a positive decimal integer (you may take it as a string if desired) and prints or returns a truthy value if the number can be expressed by a knight on a numpad in the way described, but otherwise outputs a falsy value.
The shortest code in bytes wins. Tiebreaker is earlier answer
Examples
Truthy:
1, 2, 3, 4, 5, 6, 7, 8, 9, 16, 18, 38, 61, 81, 294, 349, 381, 383, 729, 767, 38183, 38383, 18349276, 183492761, 618349276

Falsy:
10, 11, 50, 53, 55, 65, 95, 100, 180, 182, 184, 185, 186, 187, 188, 189, 209, 305, 2009, 5030, 3838384, 4838383, 183492760

What's with chess knights today? :-D

Hint: If you write the numbers out as wrapping line, then the knight is always jumping either four spaces clockwise or four spaces counter. I don't know if this is helpful.

@LuisMendo Wrapping. As in, if you treat is as an endless list of 78963214, repeated over and over. Count the distances – it's always four, one way or the other. I should've been clearer and explicitly said that you have to write it in circle order.

@QPaysTaxes Oh, I thought you meant circle but 123...9. Sorry

@LuisMendo No worries. Like I said, I should've been clearer about what I meant.

What is the expected behavior for 0? Is it truthy just like the other 1-digit numbers?

@KevinLau "Write a program or function that takes in a positive decimal integer" - i.e. you don't need to worry about 0.

@HelkaHomba - Yes, but a number with more than 1 digit could have 0's and still be positive.  I assume you are ruling those out?

@DarrelHoffman No. Some falsy examples clearly contain zeroes. Zero itself is not considered, but numbers with zeros cannot be ignored.

@HelkaHomba - That's what I meant - the presence of a 0 automatically rules out the number, i.e. makes it not a knight-number.  It'd be an interesting twist to allow 0, but have two of them since the 0-key is two keys wide, so you could go 305, or 406, but not 405 because you're on the wrong side of the 0 key.  This would invalidate a lot of answers though, so that'd be an entirely different challenge.

Jelly, 19 15 14 bytes
Doȷ’d3ạ2\P€=2P

Try it online! or verify all test cases.
How it works
Doȷ’d3ạ2\P€=2P  Main link. Argument: n (integer)

D               Convert n to base 10 (digit array).
  ȷ             Yield 1000.
 o              Logical OR. This replaces each 0 with 1000.
   ’            Decrement each digit.
    d3          Divmod; replace each digit k with [k:3, k%3].
      ạ2\       Pairwise reduce by absolute difference.
                For each pair of adjacent digits [i, j], this computes
                [abs(i:3 - j:3), abs(i%3 - j%3)].
         P€     Compute the product of each result.
                n is a Numpad's Knight Number iff all products yield 2.
           =2   Compare each product with 2.
             P  Multiply the resulting Booleans.

Python 2, 52 bytes
f=lambda n:n<6or`n%100`in'18349276167294381'*f(n/10)

Checks that any two consecutive digits are in the string '18349276167294381'. To get consecutive digits, rather than doing zip(`n`,`n`[1:]), the function repeatedly checks the last two digits and removes the last digit.

Retina, 58 40 bytes
Thanks to Sp3000 for suggesting this idea:
M&!`..
O%`.
A`16|18|27|29|34|38|49|67
^$

Try it online! (Slightly modified to run the entire test suite at once.)
Prints 1 for truthy and 0 for falsy results.
Explanation
M&!`..

Find all overlapping matches of .., i.e. all consecutive pairs of digits, and join them with linefeeds.
O%`.

Sort the digits in each line, so that we only need to check half as many pairs.
A`16|18|27|29|34|38|49|67

Remove all lines which correspond to a valid move.
^$

Count the matches of this regex. That is, if all lines were removed, this matches the resulting empty string once, otherwise it fails to match and gives zero instead.

Pyth - 35 28 bytes
!s.bt/@c`C"_xÖ({Î¶z"2tsNYztz

Test Suite.

Ruby, 57 bytes
Anonymous function. Argument is a string.
->n{(0..n.size).count{|i|!"16729438183492761"[n[i,2]]}<1}

Program with the test suite:
f=->n{(0..n.size).count{|i|!"16729438183492761"[n[i,2]]}<1}

a=%w{1 2 3 4 5 6 7 8 9 16 18 38 61 81 294 349 381 383 729 767 38183 38383 18349276 183492761 618349276
10 11 50 53 55 65 95 100 180 182 184 185 186 187 188 189 209 305 2009 5030 3838384 4838383 183492760}

a.each {|e|p [e, f[e]]}

I just encoded all the possible knight moves into a string and checked if every 2 digits within the input existed in that string.

Oh, that lookup string would also save me 17 bytes. Do you mind if I use that for my Retina answer?

Go for it! Just give credit, I guess.

Thanks, but I ended up with an even shorter solution based on a suggestion by Sp3000 :)

grep 58 bytes
grep "^((?=18|16|29|27|34|38|49|43|61|67|72|76|81|83|94|92).)*.$"

Because really, if you cannot beat grep...

Neither 5 nor 185 emit 1 with your command line, while 5 is in the truthy, and 185 in the falsy list.

@GuntramBlohm fixed -- got lost in regular negation

JavaScript (ES6), 65 62 bytes
s=>[...s].every((c,i)=>!i|"16729438183492761".match(s[i-1]+c))

Returns true or false. I'd previously tried a recursive solution, which takes 63 bytes, and map and even reduce but they took me 73 bytes.
Edit: Saved 3 bytes thanks to @user81655.

Couldn't do better, my best try was at 88 bytes. Bravo!

@user81655 You mean match works instead of ~search (but either way, that's really underhanded) and | can replace || (but not in the recursive version, sadly.)

@user81655 I was referring to the way that !i|...match works because the match result, if successful, is an array of a single string of two digits, which the | operator ends up coercing into a valid integer.

@Neil Ah, right.

Haskell 46 bytes
q=zip<*>tail
all(`elem`q"16729438183492761").q

Usage example: all(`elem`q"16729438183492761").q $ "183492761" -> True
How it works: It uses the lookup string found in @Kevin Lau's answer. q makes a list of pairs of adjacent chars from a string, e.g. q "1672" -> [('1','6'),('6','7'),('7','2')]. The function returns true if all pairs from the input appear in the pairs from the lookup string. q turns single digit inputs into the empty list, so elem always succeeds.

Why does zip<*>tail work like a flipped version of zip=<<tail? I think I don't understand what applicatives generalize.

@xnor: I just use it. <*> is defined as (<*>) f g x = f x (g x).

C, 85 81 bytes
Golfed:
i;f(char*b){i=*b++-49;return*b?(*b=="8749x7214"[i]||*b=="6983x1632"[i])&&f(b):1;}

Old non-recursive version (85 bytes):
i;f(char*b){for(;(i=*b++-49),*b&&*b=="8749x7214"[i]||*b=="6983x1632"[i];);return!*b;}

Old code with white-space and main program:
i;
f(char*b){
    for (; (i=*b++-49), *b     // i = index of digit + 1 in following arrays
        &&*b=="8749x7214"[i]   // 1st possible jump for 1..9
        ||*b=="6983x1632"[i];  // 2nd possible jump for 1..9
    );
    return !*b;
}

main(){
    char b[16];
    while(scanf("%s", b) == 1) printf("%d",f(b));
    return 0;
}

This accepts space-delimited numbers via standard input and outputs 0 if not-numpad-knight, or 1 otherwise.
The new 81-byte recursive version shaves 4 bytes.

78 bytes

MATL, 38 37 29 bytes
This uses @QPaysTaxes idea.
I:8JK5:7Pvj!Uttnqh?)d|2:EQm}h

The output is a 2D, complex, non-empty array. It is truthy if all its values have nonzero real part, and falsy otherwise.
Try it online!

Is this even allowed??

The question asks for a truthy or a falsy value, not a whole array.

@CatsAreFluffy This is our definition of truthy/falsy. As in MATLAB/Octave, arrays are truthy in MATL iff all of its elements are truthy. (example)

CC @n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

05AB1E, 29 bytes
Code:
"1Ôž±ÎqäÚ"•5(«U2÷¹¦2÷«vXyå})P

Uses CP-1252 encoding. Try it online!.

MATL, 25 24 33 26 bytes
Shaved off 1 byte thanks to @LuisMendo!
@Dennis found a bug, and then fixed it! Thanks!
'bSVYXbTUZW'j47-)d2^48\1=A

Takes integer as input. Outputs 1/0.
Try it online!

@LuisMendo Right on both counts, thanks!

@Dennis Updated, and hopefully correct. Thanks for your help.

I don't think you need the A at the end. MATL's vectors are truthy iff they do not contain a 0.

C, 140 92 bytes
c;L(char*i){while(*i&&(!c||*i=="6743x1212"[c-49]||*i=="8989x7634"[c-49]))c=*i++;return !*i;}

Assuming ASCII
Detailed Try it here
// valid transition from x to n[x-'1'][0 or 1]

int n[9][2] =
{
    {'6','8'},{'7','9'},{'4','8'},
    {'3','9'},{'x','x'},{'1','7'},
    {'2','6'},{'1','3'},{'2','4'}
};

// i is a pointer to where to start on a string

bool L(char * i)
{
    char c = 0;

    // move if not \0 and (not-first-char or is a valid move)

    while((*i) && (!c || (*i)==n[c-'1'][0] || (*i)==n[c-'1'][1]))
    {
        c = (*i++);
    }

    return !(*i); // success if it's \0
}

those lookup tables are huge. You can improve your score a lot if you get rid of all the delimiters {,}[] and encode it as a char* string instead. Also, note that your #define is not being cost-effective when you use it only twice: removing it would save you 4 bytes.

@tucuxi thanks for the tips, I managed to bring it down to 92, having \0 within the array caused undefined behavior so I replaced it with x

Nice - also, don't forget to use <s>oldscore</s> newscore when editing to reflect score improvements, and <!-- language-all: lang-c --> before your code starts to fix syntax highlighting. I also managed to reduce my byte-count somewhat by dropping the loop altogether

Your 'detailed' looks very different from a plain expansion of the golfed code (where's n in the short version?).  Also, you probably ought to mention that you're assuming ASCII encoding - you'll get different numbers on EBCDIC machines.

@TobySpeight the detailed version is supposed to show how it was built basically, yes I'm assuming ASCII which is the common case in C.

PowerShell v2+, 105 96 bytes
param($a)((1..$a.length|%{'27618349294381672'.IndexOf($a[$_-1]+$a[$_])+1})-join'*'|iex)-or$a-eq5

Iterates through the input (which must be encapsulated with "") by verifying that the index of any sequential pair of characters is in the valid lookup string. I see Kevin Lau had something similar, but I came up with this independently. Each of those indices are added with +1, as the .IndexOf() function will return -1 if the string isn't found. This will turn "not found"s into 0.
We then -join all the resultant integer values with * and pipe that to iex (similar to eval). This will mean if any one of the indices is not found, the entire expression will result in 0. That is encapsulated in parens and -or'd with $a-eq5 for the special case of input "5" to achieve our resultant output.
Test Runs
PS C:\Tools\Scripts\golfing> 1, 2, 3, 4, 5, 6, 7, 8, 9, 16, 18, 38, 61, 81, 294, 349, 381, 383, 729, 767, 38183, 38383, 18349276, 183492761, 618349276 | %{.\numpad-knight-numbers.ps1 "$_"}
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True

PS C:\Tools\Scripts\golfing> 10, 11, 50, 53, 55, 65, 95, 100, 180, 182, 184, 185, 186, 187, 188, 189, 209, 305, 2009, 5030, 3838384, 4838383, 183492760 | %{.\numpad-knight-numbers.ps1 "$_"}
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False

Julia, 51 49 bytes
n->diff(["@1634@8725"...][digits(n)+1]).^2%48⊆1

Verification
julia> f=n->diff(["@1634@8725"...][digits(n)+1]).^2%48⊆1
(anonymous function)

julia> all(map(f,(1,2,3,4,5,6,7,8,9,16,18,38,61,81,294,349,381,383,729,767,38183,38383,18349276,183492761,618349276)))
true

julia> any(map(f,(10,11,50,53,55,65,95,100,180,182,184,185,186,187,188,189,209,305,2009,5030,3838384,4838383,183492760)))
false

Actually, 30 bytes
;#pXZdX`Σ"67294381";'1+R+íu`Mπ

Takes input as a string. Outputs a positive integer for true and 0 for false.
Try it online!
Explanation:
;#pXZdX`Σ"67294381";'1+R+íu`Mπ
                                 (implicit) push input
;#pXZdx                         push zip(n[:-1], n[1;]) (pairs of digits)
       `Σ"67294381";'1+R+íu`M   map:
        Σ                         join digits
         "67294381";'1+R+         push "16729438183492761" (the magic string used in many other solutions)
                         íu       0-based index (-1 if not found), increment so 0 is not found and >=1 is the 1-based index
                             π  product

C, 78 85 bytes
char*a="9614397052";f(x){int b=x/10;return!b||b*x%5&&abs(a[x%10]-a[b%10])%6==1&f(b);}

Since everyone else has taken the input as a string, I tried doing it in integers.  It works recursively from the least-significant digit (a%10); if it's the only digit, then return true.  Otherwise, return true only if the tens digit (b%10) can't be reached from the units digit, and (recursively), the rest of the input satisfies the same test.
The test for reachability works by encoding the knight's tour linearly, and converting each digit to its position (zero to seven) on the tour.  For digits 0 and 5, we assign position nine, which is disconnected from the other positions. Then, mutually reachable numbers differ by one (mod eight); i.e. a[x%10]-a[b%10] is either ±1 or ±7.  So we test the absolute difference (mod 6) against 1.
This solution works for any character encoding that is valid for C (i.e. digits have contiguous codes from 0 to 9).

Fixed by testing that neither digit is a multiple of 5.

Java 8, 179 167 Bytes
Places the number pad ints (minus 5 and 0) in a circle. l holds the circle index of these ints. If the difference of two indices is +/- 3 mod 8,  then there is a knights move between the ints corresponding to those indices. Note that x is an int[].
x->{if(x.length<2)return 1;int[] l={0,0,1,2,7,0,3,6,5,4};int o=l[x[1]];for(int i:x){int n=l[i];if(i%5==0||(Math.abs(n-o)!=3&&Math.abs(n-o)!=5))return 0;o=n;}return 1;}

Update

-11 [16-12-10] Switched to a  lambda
-1 [16-12-10] Use <2 instead of ==1

authors: n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳