pjt33

#!/usr/bin/python3

from functools import lru_cache


class Partition:
    def __init__(self, maxPart, tail=None):
        self.part = maxPart
        self.tail = tail
        if tail is None:

pjt33

using System;
using System.Collections.Generic;
using System.Numerics;
using System.Text;

namespace Sandbox
{
    public class Rational
    {
        public Rational(BigInteger num, BigInteger denom)

pjt33

#!/usr/bin/python3

def flatten(index_map):
    flat = [0] * len(index_map)
    for key in index_map.keys():
        flat[index_map[key]] = key
    return flat


def emit_solution(x, partial_solution):

pjt33

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using BigInteger = System.Numerics.BigInteger;

namespace Sandbox
{
	// https://math.stackexchange.com/questions/2642142/complex-number-abc-conjecture
	// https://stackoverflow.com/questions/2269810/whats-a-nice-method-to-factor-gaussian-integers

pjt33

from sage.rings.polynomial.real_roots import *
x = polygen(ZZ)
def conv_p(p, n):
    if n == 0:
        return x
    else:
        return p(conv_p(p, n-1))

for n in range(1, 21): print add(map(lambda (a,b): b, real_roots(conv_p(x^3-2*x-1, n))))

pjt33

#!/usr/bin/python3

import math


def phi(n):
	# Naïve prime factorisation
	ps = set()
	m = n
	while m % 2 == 0:

pjt33

func eratosthenesSieve(to n: Int) -> [Int] {

    guard 2 <= n else { return [] }

    var composites = Array(repeating: false, count: n + 1)
    var primes: [Int] = []
    let d = Double(n)
    let upperBound = Int((d / _log(d)) * (1.0 + 1.2762/_log(d)))
    primes.reserveCapacity(upperBound)
    let squareRootN = Int(d.squareRoot())

pjt33

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

namespace Sandbox
{
    class MO338802
    {
        public static void Main()

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

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