Skip to content

Instantly share code, notes, and snippets.

View MO419698.py
"""
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:
@pjt33
pjt33 / A074881.py
Last active Feb 22, 2022
B-file for A074881
View A074881.py
from collections import Counter
from math import gcd
def phi(n):
# Not exactly over-optimised...
rv = 1
for p in range(2, n + 1):
if n == 1:
break
@pjt33
pjt33 / MO405736.py
Last active Oct 20, 2021
Counting Dynkin systems
View MO405736.py
def extend_closure(omega, included, extension, excluded):
# We start with a closure which we want to extend
closure = set(included)
# Use a queue
q = set([extension])
while q:
x = next(iter(q))
q.remove(x)
closure.add(x)
@pjt33
pjt33 / MO405101.sage
Created Oct 6, 2021
MO405101: lines through (c^m, c^n)
View MO405101.sage
from collections import defaultdict
from itertools import combinations
from sage.rings.polynomial.real_roots import real_roots
R.<alpha, x, y> = PolynomialRing(QQ, order='lex')
S.<z> = PolynomialRing(QQ)
def P(n, p, q):
return ((1 - x^p) + alpha * (x^n - x^q)) // (1 - x^gcd(p, abs(n-q)))
@pjt33
pjt33 / MO404760.py
Last active Oct 4, 2021
Interpolating integer polynomials with small coefficients
View MO404760.py
#!/usr/bin/pypy3
from heapq import heappush, heappop
def mod_inv(a: int, m: int) -> int:
lastremainder, remainder = a % m, m
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient*x, x
@pjt33
pjt33 / MO244949.cs
Created Aug 26, 2021
Snake and Hunter
View MO244949.cs
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.
View Permutations.txt
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 6, 5
1, 2, 3, 5, 4, 6
1, 2, 3, 5, 6, 4
1, 2, 3, 6, 4, 5
1, 2, 3, 6, 5, 4
1, 2, 4, 3, 5, 6
1, 2, 4, 5, 3, 6
1, 2, 5, 3, 4, 6
1, 2, 5, 4, 3, 6
@pjt33
pjt33 / unsorting.sage
Created Aug 16, 2021
Sage code for brute force generation of uniform permutation networks
View unsorting.sage
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
pjt33 / MO29478.sage
Created Aug 12, 2021
Analyse https://mathoverflow.net/q/29478 by integer relation search with LLL
View MO29478.sage
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
pjt33 / Caveats.txt
Last active Jul 16, 2021
Searching for periodic hypergeometric functions
View Caveats.txt
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)