This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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): |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/python3 | |
# https://math.stackexchange.com/q/3444274 | |
from fractions import Fraction | |
def build_states(target_dragon): | |
states = {} | |
def toBinary(x, width): |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from collections import Counter | |
from fractions import Fraction | |
def _gcd(a, b): | |
while a: | |
a, b = b % a, a | |
return b | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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()]) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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 |