pjt33

#!/usr/bin/pypy3

"""
Tile representation is as four nibbles for ease of manually writing out the tiles
From most significant to least significant they are top, right, bottom, left edge of the tile.
0 indicates that the space is free; fifteen colours of track are therefore supported in principle.
This is not a complete solver in that it doesn't check that each colour forms a single loop.
"""

def tilestr(tile):

pjt33

from typing import Dict, List, Iterable, Optional
from math import gcd

def is_probable_prime(n: int) -> bool:
	"""
	Pseudo-primality test using Baillie-Pomerance-Selfridge-Wagstaff
	"""
	return _is_probable_prime_miller_rabin(n, 2) and _is_probable_prime_selfridge(n)

pjt33

#!/usr/bin/sage

def partial_spans(idx, mask, blocked_rowspans):
	if not mask:
		yield tuple(), blocked_rowspans
		return

	while (mask & 1) == 0:
		idx += 1
		mask >>= 1

pjt33

#!/usr/bin/pypy3

def gen_union_closed_families(n, forced_inclusions = []):
	all_bits = (1 << n) - 1

	def search(i, incl):
		if i > all_bits:
			yield incl
			return

pjt33

#!/usr/bin/pypy3

def vecs(n, width):
	# width should be chosen so 2^width > n.
	if n == 0:
		yield 0
		return

	for hd in vecs(n-1, width):
		yield hd << width

pjt33

#!/usr/bin/pypy3

from functools import lru_cache

# Limit memory usage to 8GB
import resource
resource.setrlimit(resource.RLIMIT_AS, (8 * 1024**3, 8 * 1024**3))


"""

pjt33

#!/usr/bin/pypy3

"""
Ethan Dlugie asked [1] "How do we know there are no more Deligne-Mostow/Thurston lattices?"
than the 94 enumerated by Thurston [3]. This program combines case analysis with exhaustive search
to show that the list is in fact complete.

There is a subtle difference between Thurston's claim (Theorem 0.2) and Mostow's ΣINT condition [2]:
Mostow only allows one set of equal angles to give half-integer reciprocals (condition (c) below),
whereas Thurston allows multiple sets. This code uses Thurston's condition, as more straightforward,

pjt33

One solution per line. Format
n ((a_1, b_1), (a_2, b_2), ..., (a_n, b_n))

1 ((0, 0))

2 ((0, 1), (1, 0))

3 ((0, 1), (1, 1), (2, 0))
3 ((0, 2), (1, 0), (1, 1))

pjt33

R.<n> = PolynomialRing(QQ)

def p(x):
	return x^5 + n^2*x^4 - (2*n^3 + 6*n^2 + 10*n + 10)*x^3 + (n^4 + 5*n^3 + 11*n^2 + 15*n + 5)*x^2 + (n^3 + 4*n^2 + 10*n + 10)*x + 1

def s(x):
	return (n + 2 + n*x - x*x) / (1 + 2*x + n*x)

R2.<xtmp> = PolynomialRing(FractionField(R))
R3.<x1> = R2.quotient(p(xtmp))

pjt33

"""
Identify and count (by size) the subsets with odd beta_n using MacMahon's inclusion-exclusion formula for beta_n
as presented in theorem 2.3 of https://arxiv.org/pdf/1710.11033.pdf
"""

def bit_subsets_of(bitmask):
	# Nice bit hack from Thomas Beuman
	current = bitmask
	yield current
	while current: