#!/usr/bin/env coffee ## This file is dedicated to the public domain. ## Count up duplicates in an array, and get a map where keys are ## set members, and values are the number of occurrences. ## Only works when all the duplicates are next to each other, ## which they are in count_open_toratopes where it's called. map_dupes = (ar) -> r = {} last = num = null for ari in ar if ari is last ++num else r[last] = num if num? last = ari num = 1 r[last] = num if num? r choose = (n, k) -> return 0 if k > n return 1 if k < 1 return 1 if k is n return n if k in [1, n-1] # Optimise to avoid calculating factorials (and running into overflow issues), # by only multiplying and dividing what we actually need to. p = n-k r = n while --n > 1 if p < n > k r *= n else if p >= n <= k r /= n r ## List out all the partitions of n, only using parts between the specified minimum and maximum. partitions = (n, min_part=1, max_part=null) -> max_part ?= n r = [] r.push [n] if n <= max_part i = n - min_part i = max_part if i > max_part while i >= min_part r.push ([i].concat x for x in partitions(n-i, min_part, i))... --i r toratope_partitions = (n) -> partitions n, 2, n-2 ## Number of open toratopes in n dimensions. ## Half the number of total toratopes in n dimensions. ## Same as http://oeis.org/A000669 count_open_toratopes = (n) -> n = parseInt(n) if n <= 2 1 else sum = 2*count_open_toratopes(n-1) for p in toratope_partitions n prod = 1 for m, k of map_dupes p prod *= choose(count_open_toratopes(m) + k - 1, k) sum += prod sum console.log count_open_toratopes process.argv[2]