pjt33

using System;
using System.Collections.Generic;
using System.Linq;
using BITMASK = System.UInt64;

namespace Sandbox
{
    using STATE = System.ValueTuple<BITMASK, System.Byte, System.Byte>;

    // One way to formalise the snake constraint is to treat internal vertices as deleted.

pjt33

def swap_sequences_inlined(n, swap_vars):
  f = factorial(n)

  def extend_swap_sequence(seq, equivalence_classes, distrib, swap_vars):
    if len(distrib) * (2^len(swap_vars)) < f:
      # We can't hit all permutations, so fail fast
      return

    if not swap_vars:
      yield (seq, [weight - 1/f for weight in distrib.values()])

pjt33

def integer_relation(vals_to_relate, precision = 200):
    n = len(vals_to_relate)
    m = matrix(n, n+1)
    for i in range(n): m[i,i] = 1
    for i in range(n):
        m[i,n] = int(vals_to_relate[i]*RealField(precision)(2)^(precision-20))//2^10

    L = m.LLL()
    return L.row(0)

pjt33

In principle, we should derive essentially the same solutions for $(k,l,m)$ as for $(l,k,m)$ by symmetry in the upper arguments,
and for $(k,l,m)$ as for $(-k,-l,-m)$ by effectively negating the sign of $t$.
I haven't implemented negative $l$ or positive $m$ so can't check the latter.
For the former, I see the symmetry correctly observed in many cases but there is the odd troubling exception.

(1,0,-1)
 Ideal (x - 2, b0, a0 - b0 + c0 - 1, A - 1)
(0,1,-1)
 Ideal (x, a0)
 Ideal (a0, A - 1)

pjt33

from collections import Counter
from fractions import Fraction


def _gcd(a, b):
	while a:
		a, b = b % a, a
	return b

pjt33

#!/usr/bin/python3

# https://math.stackexchange.com/q/3444274

from fractions import Fraction


def build_states(target_dragon):
    states = {}
    def toBinary(x, width):

pjt33

#!/usr/bin/python3

from functools import lru_cache

@lru_cache(None)
def binom(n, k):
	if n < 0 or k < 0 or k > n:
		return 0
	rv = 1
	for i in range(k):

pjt33

#!/usr/bin/python3

import timeit
from numpy import mod
from numpy.polynomial.polynomial import Polynomial


def is_prime_naive(n):
    if n <= 2 or n % 2 == 0:
        return n == 2

pjt33

Let's define $a_{n,m}$ to be the number of words of length $n$ with a surplus of $m$ A's. E.g. with $k=2$, AAAB would contribute $1$ to $a_{4,1}$; with $k=3$ it would contribute $1$ to $a_{4,0}$.

Given a word of length $n-1$ we can always append an A to get a valid word; we can append a B to get a valid word iff the surplus is at least $k$. So if we set up the generating function $$f(x,z) = \sum_{n \ge 0} \sum_{m=0}^n a_{n,m} x^n z^m$$ we find that $$f(x, z) = 1 + xz f(x, z) + xz^{-p} \sum_{n \ge 0} \sum_{m=p}^n a_{n,m} x^n z^m \tag{1}$$ which doesn't look very promising.

However, I believe Deutsch proved that this kind of regression always gives a Riordan array, so let's assume that we can write $f(x, z)$ in the form $$f(x, z) = \sum_{m \ge 0} z^m d(x) (xh(x))^m \tag{2}$$

Useful observation: the length minus the surplus is always a multiple of $k+1$ (easily shown by induction), so $d(x)$ only has non-zero coefficients at powers of $x^{k+1}$, or $d(x) = d_k(x^{k+1})$.

Useful observation: if we ext

pjt33

using System;
using System.Collections.Generic;
using System.Linq;

// WARNING: THIS IS A QUICK HACK, NOT PRODUCTION CODE. IT CAN PROBABLY BE OPTIMISED QUITE SIGNIFICANTLY.

namespace Sandbox
{
    // https://math.stackexchange.com/q/3306917
    static class DriveYaNuts