OFFSET
2,1
COMMENTS
This sequence is given in this order: (2,2), (3,2), (3,3), (4,2), (4,3), (4,4), etc.
The idea of the program below is that the first row, first column, and the (1,1)th element uniquely determine the rest of the matrix. Hence, all permutations of m+n integers in the range 0..m*n-1 are generated to fill the first row, first column, and (1,1). Then the empty spots in the matrix are filled in and if at any point a condition is violated (duplicate, < 0, >= M*N), the program immediately moves on to the next permutation.
Much of the conversation in the main chat room of the Programming Puzzles and Code Golf Stack Exchange site - the Nineteenth Byte - following the linked message in the Links section deals with finding the terms of this sequence.
Observation: at least the first 15 terms are divisible by 8. - Omar E. Pol, Oct 20 2015, Nov 21 2015
When M and N are both even, the block sum is 2(MN-1). When one or both is odd the block sum can vary: e.g., for M=N=3, it varies from 12 to 20. - Peter J. Taylor, Oct 21 2015
When M and N are both even, all solutions are toroidal: the block sums created by wrapping from the last column to the first column or the last row to the first row also equal 2(MN-1). When one of M or N is even, all solutions are cylindrical, with wrapping in the even dimension, but they are toroidal only in the trivial case of Odd X 2. When both M and N are odd, except in the trivial case of 1 X 1, solutions do not wrap in either direction. - Peter J. Taylor, Oct 21 2015
LINKS
The Nineteenth Byte, Originating chat message, ChatRoom.
EXAMPLE
One 3 X 3 solution (with a sum of 19) is:
0 4 2
8 7 6
3 1 5
One 4 X 4 solution (with a sum of 30) is:
0 3 4 7
12 15 8 11
1 2 5 6
13 14 9 10
One 5 X 5 solution (with a sum of 48) is:
0 24 1 23 2
9 15 8 16 7
10 14 11 13 12
19 5 18 6 17
20 4 21 3 22
The triangle T(M, N) begins:
M\N 2 3 4 5 6 ...
2: 24
3: 112 376
4: 768 2160 20352
5: 5376 5904 86208 51840
6: 64512 56736 1628352 1342656 44084736
...reformatted. - Wolfdieter Lang, Dec 16 2015
PROG
(Python)
from itertools import permutations as P
n = 4; m = 4; permutes = P(range(m*n), m+n); counter = 0
for p in permutes:
grid = [p[:n]]
for i in range(m-1):
grid.append([p[n+i]]+[-1]*(n-1))
grid[1][1] = p[-1]
s = p[0]+p[1]+p[n]+p[-1]
has = list(p)
fail = 0
for y in range(1, m):
for x in range(1, n):
if x == y == 1: continue
r = s - (grid[y-1][x-1] + grid[y-1][x] + grid[y][x-1])
if r not in has and 0 <= r < m*n:
grid[y][x]=r
has.append(r)
else:
fail = 1
break
if fail: break
if not fail:
counter += 1
print(counter)
CROSSREFS
KEYWORD
AUTHOR
Lee Burnette, Oct 20 2015
STATUS
approved