# codejamhelpers documentation¶

A library of helper functions useful for solving Google Code Jam problems.

Contents:

class codejamhelpers.Primes(frontier=None)

The prime numbers, prepopulated up to frontier, with lazy evaluation beyond.

__contains__(n)

Test whether n is prime

__getitem__(i)

The ith prime

count(x)

Count the number of primes less than or equal to x

Given an increasing function $$f$$, find the greatest non-negative integer $$n$$ such that $$f(n) \le t$$. If $$f(n) > t$$ for all $$n \ge 0$$, return None.

codejamhelpers.powers_of_two()

Powers of 2, from 1

codejamhelpers.minimise_convex(f)

Given a U-shaped (convex and eventually increasing) function f, find its minimum over the non-negative integers. That is $$m$$ such that $$f(m) \le f(n)$$ for all $$n$$. If there exist multiple solutions, return the largest. Uses binary search on the derivative.

codejamhelpers.minimise_convex2(f)

Given a U-shaped (convex and eventually increasing) function f, find its minimum over the non-negative integers. That is $$m$$ such that $$f(m) \le f(n)$$ for all $$n$$. If there exist multiple solutions, return the largest. Uses ternary search.

codejamhelpers.kth_root(n, k)

Calculate the greatest non-negative integer $$r$$ such that $$r^k \le n$$.

codejamhelpers.trials(P)

Given the individual probabilities $$P_i$$ of n independent trials, calculate the probabilities $$Q_k$$ that exactly $$0 \le k \le n$$ are successful.