Yeah I think 159 digits is surely too low. What was your reasoning?
1 Like
I just spotted my mistake! 
I won’t share the exact number I arrived at yet (hoping for someone else to come up with it independently, to give me some more confidence that it’s the correct one!), but obviously the number will be of the form 
, so I worked out these numbers a, b, c and then finally printed…
Whoops…
Good news is, after changing that 3 to a 5 I do indeed get a number with 171 digits!
2 Likes
With O(n^4) dynamic programming - using Theta(n^3) words of space,
which concretely comes out to between 10GB and 11GB for this
problem size - I get that the answer is 2^241 * 3^120 * 5^60 .
However, according to wolframalpha, that has 172 digits:
It’s between 5 * 10^171 and 6 * 10^171 .
using Base: +
"FloatingNatural(typemax(UInt64),typemax(UInt64)) is positive infinity. In all other cases, FloatingNatural(m,n) is m*(2^n)."
struct FloatingNatural
coeff::UInt64
expnt::UInt64
end
"This is for interval arithmetic."
struct FloatNatInterval
left::FloatingNatural
right::FloatingNatural
end
function incrementfloat(x::FloatingNatural) ::FloatingNatural
(x.coeff == 0xffffffffffffffff) || (return FloatingNatural(x.coeff+0x0000000000000001,x.expnt))
(x.expnt == 0xffffffffffffffff) && (return x)
return FloatingNatural(0x8000000000000000,x.expnt+0x0000000000000001)
end
function add_rd_sameexp(xcoeff::UInt64,ycoeff::UInt64,expnt::UInt64) ::FloatingNatural
(0xffffffffffffffff-xcoeff < ycoeff) || (return FloatingNatural(xcoeff+ycoeff,expnt))
(expnt == 0xffffffffffffffff) && (return FloatingNatural(0xffffffffffffffff,0xffffffffffffffff))
return FloatingNatural((xcoeff >> 1)+(xcoeff & 0x0000000000000001 & ycoeff)+(ycoeff >> 1),expnt+0x0000000000000001)
end
"rd = round down"
function add_rd_(x::FloatingNatural,y::FloatingNatural) ::FloatingNatural
(x.expnt == y.expnt) && (return add_rd_sameexp(x.coeff,y.coeff,y.expnt))
if x.expnt < y.expnt
shift = y.expnt-x.expnt
return ((shift & 0xffffffffffffffc0 == 0x0000000000000000) ? add_rd_sameexp((x.coeff >> shift),y.coeff,y.expnt) : y)
end
shift = x.expnt-y.expnt
return ((shift & 0xffffffffffffffc0 == 0x0000000000000000) ? add_rd_sameexp(x.coeff,(y.coeff >> shift),x.expnt) : x)
end
"(xcoeff == typemax(UInt64) == ycoeff) & extra & (expnt != typemax(UInt64)) would cause integer overflow, resulting in this outputting a non-canonical zero despite
even the round-down sum being greater than 2^64. However, nothing in add_ru_sameexp or any of the other code here can call add_ru_sameexp with such inputs."
function add_ru_sameexp(xcoeff::UInt64,extra::Bool,ycoeff::UInt64,expnt::UInt64) ::FloatingNatural
(xcoeff == 0xffffffffffffffff == ycoeff) && extra && error("These inputs should have been impossible.")
(0xfffffffffffffffe-xcoeff < ycoeff) || (return FloatingNatural(xcoeff+extra+ycoeff,expnt))
if extra
(expnt == 0xffffffffffffffff) && (return FloatingNatural(0xffffffffffffffff,0xffffffffffffffff))
return FloatingNatural((xcoeff >> 1)+(xcoeff & 0x0000000000000001 & ycoeff)+0x0000000000000001+(ycoeff >> 1),expnt+0x0000000000000001)
end
(0xffffffffffffffff-xcoeff == ycoeff) && (return FloatingNatural(0xffffffffffffffff,expnt))
(expnt == 0xffffffffffffffff) && (return FloatingNatural(0xffffffffffffffff,0xffffffffffffffff))
return FloatingNatural((xcoeff >> 1)+((xcoeff | ycoeff) & 0x0000000000000001)+(ycoeff >> 1),expnt+0x0000000000000001)
end
"ru = round up"
function add_ru_(x::FloatingNatural,y::FloatingNatural) ::FloatingNatural
(x.expnt == y.expnt) && (return add_ru_sameexp(x.coeff,false,y.coeff,y.expnt))
if x.expnt < y.expnt
shift = y.expnt-x.expnt
(shift & 0xffffffffffffffc0 == 0x0000000000000000) || (return ((x.coeff == 0x0000000000000000) ? y : incrementfloat(y)))
return add_ru_sameexp((x.coeff >> shift),(trailing_zeros(x.coeff) < shift),y.coeff,y.expnt)
end
shift = x.expnt-y.expnt
(shift & 0xffffffffffffffc0 == 0x0000000000000000) || (return ((y.coeff == 0x0000000000000000) ? x : incrementfloat(x)))
return add_ru_sameexp(x.coeff,(trailing_zeros(y.coeff) < shift),(y.coeff >> shift),x.expnt)
end
function Base.:+(x::FloatNatInterval,y::FloatNatInterval) ::FloatNatInterval
return FloatNatInterval(add_rd_(x.left,y.left),add_ru_(x.right,y.right))
end
const FNIzero = FloatNatInterval(FloatingNatural(UInt64(0),UInt64(0)),FloatingNatural(UInt64(0),UInt64(0)))
const exponentsfor::NTuple{6,NTuple{3,Int16}} = ((0,0,0),(1,0,0),(0,1,0),(2,0,0),(0,0,1),(1,1,0))
function overwrite_with_one_roll_from_!_(overwritethis::Dict{NTuple{3,Int16},FloatNatInterval},prevfrequencies::Dict{NTuple{3,Int16},FloatNatInterval}) ::Nothing
empty!(overwritethis)
for ((poweroftwo,powerofthree,poweroffive),n) in pairs(prevfrequencies)
for (x,y,z) in exponentsfor
overwritethis[(poweroftwo+x,powerofthree+y,poweroffive+z)] = n+get(overwritethis,(poweroftwo+x,powerofthree+y,poweroffive+z),FNIzero)
end
end
return nothing
end
afterevennumofrolls::Dict{NTuple{3,Int16},FloatNatInterval} = Dict()
afteroddnumofrolls::Dict{NTuple{3,Int16},FloatNatInterval} = Dict()
afterevennumofrolls[Int16.((0,0,0))] = FloatNatInterval(FloatingNatural(UInt64(1),UInt64(0)),FloatingNatural(UInt64(1),UInt64(0)))
for _ in 1:181
overwrite_with_one_roll_from_!_(afteroddnumofrolls,afterevennumofrolls)
overwrite_with_one_roll_from_!_(afterevennumofrolls,afteroddnumofrolls)
end
length(afteroddnumofrolls)
maximum((val.left).expnt for val in values(afteroddnumofrolls))
maximum((val.left).coeff for val in values(afteroddnumofrolls) if (val.left).expnt == 0x0000000000000358)
any(0x0000000000000358 < (val.right).expnt for val in values(afteroddnumofrolls))
sum(Int32(((val.right).expnt == 0x0000000000000358) && (0xca6f37fa942d8aef <= (val.right).coeff)) for val in values(afteroddnumofrolls))
only(key for (key,val) in pairs(afteroddnumofrolls) if (((val.right).expnt == 0x0000000000000358) && (0xca6f37fa942d8aef <= (val.right).coeff)))
4 Likes
Very nice! That is the same number that I came up with (another silly mistake from me to say that 5.5e171 had 171 digits!).
My approach was to compute the solutions exactly for smaller number of dice (up to about 50). It then became apparent that the solutions followed a certain simple pattern. Extrapolated up to 361 dice, this pattern will give the answer 2^241 * 3^120 * 5^60. However, I did not prove that the pattern actually continues to hold indefinitely, so this solution is not rigorous yet .
Here is the formula I used to calculate the number of ways to to write 2^a * 3^b * 5^c as a product of N dice:
where 
The reasoning is that we start by choosing how many 4’s we will use (this is the number i), then the first two binomial coefficients are the number of ways to place the 4’s and 5’s. The last two binomial coefficients count the number of ways to place the remaining factors of 2 and 3, which can overlap in any way to produce 1’s, 2’s, 3’s and 6’s.
I used this formula to get solutions for smaller N like so:
from math import comb as C
def f(a, b, c, N):
return sum(C(N,i)*C(N-i,c)*C(N-i-c,b)*C(N-i-c,a-2*i) for i in range(min(N-c, a//2)+1))
for N in range(2, 50):
maxCount = 0
optimalProducts = []
for a in range(2*N+1):
for b in range(N+1):
for c in range(N+1):
count = f(a, b, c, N)
if count > maxCount:
maxCount = count
optimalProducts = [(a, b, c)]
elif count == maxCount:
optimalProducts.append((a, b, c))
print(N, optimalProducts)
Output
2 [(1, 1, 0), (2, 1, 0)]
3 [(2, 1, 0), (3, 1, 0)]
4 [(2, 1, 1), (3, 1, 1), (3, 2, 0)]
5 [(3, 2, 1)]
6 [(4, 2, 1)]
7 [(5, 2, 1)]
8 [(5, 3, 1), (6, 3, 1)]
9 [(6, 3, 1), (7, 3, 1)]
10 [(6, 3, 2), (7, 3, 2), (7, 4, 1)]
11 [(7, 4, 2)]
12 [(8, 4, 2)]
13 [(9, 4, 2)]
14 [(9, 5, 2), (10, 5, 2)]
15 [(10, 5, 2), (11, 5, 2)]
16 [(10, 5, 3), (11, 5, 3), (11, 6, 2)]
17 [(11, 6, 3)]
18 [(12, 6, 3)]
19 [(13, 6, 3)]
20 [(13, 7, 3), (14, 7, 3)]
21 [(14, 7, 3), (15, 7, 3)]
22 [(14, 7, 4), (15, 7, 4), (15, 8, 3)]
23 [(15, 8, 4)]
24 [(16, 8, 4)]
25 [(17, 8, 4)]
26 [(17, 9, 4), (18, 9, 4)]
27 [(18, 9, 4), (19, 9, 4)]
28 [(18, 9, 5), (19, 9, 5), (19, 10, 4)]
29 [(19, 10, 5)]
30 [(20, 10, 5)]
31 [(21, 10, 5)]
32 [(21, 11, 5), (22, 11, 5)]
33 [(22, 11, 5), (23, 11, 5)]
34 [(22, 11, 6), (23, 11, 6), (23, 12, 5)]
35 [(23, 12, 6)]
36 [(24, 12, 6)]
37 [(25, 12, 6)]
38 [(25, 13, 6), (26, 13, 6)]
39 [(26, 13, 6), (27, 13, 6)]
40 [(26, 13, 7), (27, 13, 7), (27, 14, 6)]
41 [(27, 14, 7)]
42 [(28, 14, 7)]
43 [(29, 14, 7)]
44 [(29, 15, 7), (30, 15, 7)]
45 [(30, 15, 7), (31, 15, 7)]
46 [(30, 15, 8), (31, 15, 8), (31, 16, 7)]
47 [(31, 16, 8)]
48 [(32, 16, 8)]
49 [(33, 16, 8)]
The pattern appears to repeat every 6 steps: the solutions for N+6 can be obtained by adding (4, 2, 1) to the solutions for N. Notice in particular that there is a unique solution precisely when N mod 6 is 0, 1 or 5! Also, when N is divisible by 6 the most frequent product is exactly 6!^(N/6), so this will indeed be a very good approximation for all N (maybe off by no more than a factor of 5 or so for N not divisible by 6).
Can somebody see a nice proof for why the optimal product(s) for N+6 dice is exactly 6! times bigger than the optimal product(s) for N dice? It’s probably possible to prove by induction (using the fact that 6! is the optimal product for 6 dice), but I haven’t looked at the details yet.
3 Likes
I’ve a slightly different problem, if someone is interested.
There’s a board game idea
:strip_icc()/pic7582811.jpg)
where’s it’s not so clear if there can be draws.
tldr;
game is N in a row, on an (N+2) x (N+2) size board,
Reversi/Othello captures. Flank/custodial capture flipping.
You can place in an open space but if it can capture it must, but if it can’t it’s still a legal placement.
Capture restriction - you can only capture if when you flip the pieces you make a longer line than the opponents lines you cut across.
Placement restriction - the outer edge can only be placed on in order to capture, but then the piece is removed.
Problem:
Can there be a draw? On what board size?
Intuition: If a piece is repeatedly flipped throughout the game the lines going through it need to get longer and longer - so the game is finite, but can the board fill up and deadlock/freeze with no legal move for either player?
One could try brute force searching to find a position, or one could try to prove, constructively or inductively or whichever that a position can’t have no legal move for both players.
3 Likes
Can the “longest friendly segment created” include more stones than the ones doing the flanking? Would black be allowed to play A here?
Also, I assume that it counts as “cutting” even if you only flip the end of a segment? Otherwise we could have an infinite cycle of (black A, white B) here, right?
1 Like
Yeah in the second picture, the Black A is prohibited because it would flip the corner, and then A would be removed again, but it would only make a strip of size 2, which isn’t strictly longer than the strip it cut across, which was 2 whites. You can only play on the edge when flipping 
A in the first one looks fine, as long as A isn’t on the perimeter. Then black will make a segment of length 4 which is longer than the three whites it’s cutting through.
1 Like
This was a kind of first attempt at a brute force search for a position with a draw in python
Python code
# check a board game for legal moves
# the board is NxN grid of squares
# the board is full of 0s and 1s, red and blue squares
# the game is over if there is N in a row of the same color or N in a column of the same color
# there is a legal move if a row or columns has q in a row and no orthogonal row cutting across it
# is longer than q. q is between 1 and N-1.
N = 4
def check_length(row, index):
# check length number of adjacent squares of same color starting at index
# check left
left = index
while left > 0 and row[left-1] == row[index]:
left -= 1
# check right
right = index
while right < N-1 and row[right+1] == row[index]:
right += 1
return right - left + 1
def check_board(board):
# return true if game is over, or there is a legal move for one player otherwise false
# check rows
for row in board:
if row.count(0) == 0 or row.count(1) == 0:
#game over
return True
# check columns
for i in range(N):
if [row[i] for row in board].count(0) == 0 or [row[i] for row in board].count(1) == 0:
#game over
return True
# loop over rows, find length of longest run of 0s and 1s from each side
# check columns, find length of longest run of 0s and 1s starting at each index
# check rows
for (i, row) in enumerate(board):
colorleft = row[0]
colorright = row[N-1]
# check left
left = 0
while left < N-1 and row[left+1] == colorleft:
left += 1
leftlength = left + 1
# check right
right = N-1
while right > 0 and row[right-1] == colorright:
right -= 1
rightlength = N - right
# check if longest run is longer than left for colorleft or right for colorright
# check columns cuttting through row, if all of these are shorter than leftlength or rightlength
# then there is a legal move
leftbool = True
for j in range(0,leftlength):
column = [row[j] for row in board]
leftbool = leftbool and check_length(column, i) <= leftlength
if not leftbool:
break
if leftbool:
return True
rightbool = True
for j in range(right,N):
column = [row[j] for row in board]
rightbool = rightbool and check_length(column, i) <= rightlength
if not rightbool:
break
if rightbool:
return True
# check rows cuttting through column, if all of these are shorter than leftlength or rightlength
# then there is a legal move
for i in range(N):
column = [row[i] for row in board]
colorleft = column[0]
colorright = column[N-1]
# check left
left = 0
while left < N-1 and column[left+1] == colorleft:
left += 1
leftlength = left + 1
# check right
right = N-1
while right > 0 and column[right-1] == colorright:
right -= 1
rightlength = N - right
# check if longest run is longer than left for colorleft or right for colorright
leftbool = True
for j in range(0,leftlength):
row = board[j]
leftbool = leftbool and check_length(row, i) <= leftlength
if not leftbool:
break
if leftbool:
return True
rightbool = True
for j in range(right,N):
row = board[j]
rightbool = rightbool and check_length(row, i) <= rightlength
if not rightbool:
break
if rightbool:
return True
return False
# loop over all NxN boards
for i in range(2**(N*N)):
# convert i to binary
binstr = bin(i)[2:]
# pad with zeros
binstr = '0'*(N*N - len(binstr)) + binstr
# convert to board
board = [[int(binstr[N*i+j]) for j in range(N)] for i in range(N)]
# check board
# print(board)
if not check_board(board):
print(board)
break
if i % 1000000 == 0:
print(i)
Some ideas for manually checking and ruling out small board sizes
Some Ideas on small sizes
If you think of whether the corner can be flipped, one can count how many of a certain colour are along the vertical and horizontal direction, and work though cases
(1,1)
This should always be a legal move for blue.
(2,1) or (1,2)
For this not to be a legal move for blue, there needs to be a size 3 or larger red chain cutting across like (4 in a row would be a win here)
but then that red 3 chain requires another larger chain cutting across, so in the case of 3 in a row a 4 in a row - which would be game over.
The (2,2) case would be similar, and the (3,1), (3,2), (3,3) all require a 4 in a row somewhere or a legal flip.
You can use that idea I believe on sizes 3,4,5 at least. It also helps to notice something like having a N-2 or N-1 in a row on the inner NxN grid (N+2 size board) would also lead to either a win or a legal move similar to the above.
1 Like
If we change the rules so that lengths of created segments do not include external stones that did not help with the flipping, then I think this kind of construction works:
(should be a 9x9 board, ignore the lines continuing to the lower right)
That is the closest I got, nothing I found was even close to working with the actual rules. So far it seems impossible
Oh so is it like, only the stones that are flipped are what’s being counted in that construction? Edit: ok you can include the “two” that contribute to the custodial capture, but in this case, not the one that’s being removed after.
So each time you would flip, there’s at least that many cutting across it. It’s a nice construction
I think the idea of these kinds of rules in some of mark’s games is that there’s something that’s causing an irreversible progress in the game, some counter that keeps increasing, in some games it might be largest group size, or pieces that are forced to move in one direction or pattern, or here I suppose it’s these lengths to flip a piece repeatedly.
Yeah somehow it seemed kind of natural to me to only count those stones, since other ones are not contributing to creating the new segment, they just happen to be sitting there adjacent to it. (I’m not saying this is more natural than the actual rules, but it didn’t seem too unreasonable and I honestly wasn’t sure just from the rule description which was intended)
At first I thought even with this more restricted ruleset (more restricted in the sense that fewer moves are legal) it might be impossible to create a drawn position, but apparently not!
Does Mark himself (or someone else) have a proof that draws are impossible, or is it an open question?
I think it’s an open question, but it’s kind of a prototype for an N in a row game that’s finite and hopefully without draws.
from Michael Amundsen there
There is no proof of its decisiveness. There is some hand-waiving and some failed attempts at making the game lock up without a winning line. Seems solid, but proof would be great. Its finitude is certain, though. The only way to cut a line is to make a longer line.
Edit: I thought it kind of fits in here, because one could maybe do some magic to optimise brute force searches to get to higher and higher board sizes, or one could try to do some tricks like stripping away parts of the board for a kind of induction, or maybe one could come up with a constructive method, or some counting function or whichever Flexible ideas for approaches.
1 Like
What is the most stones that one can place on a 9x9 board, such that no three form an acute triangle?
3 Likes
I don’t know what the largest is, but does this 17 count?
If two of the three stones are on the same side, and the third is on the other perpendicular side, one angle should be more than 90º.
2 Likes
And then say another 17
The idea being there’s two parallel lines, two of the stones line on one line, and one on another, but the smallest angle one can make one of angles (at the single stone) is 90º, because of the grid and the proximity of the parallel lines.
Edit: I think there’s a small caveat - if the single point is “between” the other two points, that’s the above illustration, but when it’s “outside” the two, it can be acute, but then another angle, the one at the closer of the two stones becomes obtuse.
1 Like
If we’re assuming a square board, squares of squares, does this work fo 18?
two parallel lines, at least two of the points belong to one line.
Cases:
- if two points are horizontally aligned it’ll have a right angle.
- If the two points are one space above and below the single point, it’s isosceles (assumptions about using the centre points and squares). Then the angle at the single stone is 90º.
- move the single stone out beyond (vertically higher or lower) than both stones, it increases the angle at the nearest of the two stones beyond 90º.
- move the two stones, further away from an inner single stone than one space apart, and the 90º angle at the stone increases.
?
4 Likes
^^ I think this one only has legal moves for Blue. There’s a few variations on it as well.
and I think a slightly smaller example
I think this might be a 19x19 board example of a “game” with no moves for either player, though whether you can guarantee to set it up, cooperatively say from playing it, I don’t know
Explanations of the numbers: The red and blue numbers around the perimeter are the length of segments if they could be flipped with a legal placement. The green lines highlight the blocking blue chains, and the white lines the blocking red chain, and then the lengths of those for convenience.
Not sure if there’s corner patterns that could lead to a smaller example. A lot of the centre is fairly redundant.
3 Likes
Wow, I was really leaning towards thinking it was impossible!
1 Like
I think one can prove that your 18-stone construction works as follows:
Given two distinct points, which define a line segment, we have restrictions on where a third point may lie in order to complete an acute triangle with these two.
- Draw two parallel lines, perpendicular to the line segment, each passing through one of the two points.
- Draw a circle with its diameter defined by the line segment.
The valid points to complete an acute triangle exactly corresponds to the points strictly between the two parallel lines and strictly outside of the circle. Applying this property to the above 18-stone example, we can see that we cannot find two stones that have a corresponding third stone in the allowable region.
2 Likes