A338772 The number of different probabilities p for which a coin that lands heads with probability p can, using n flips, perfectly model one flip of a fair coin.

1, 3, 19, 271, 8635, 623533

Offset: 1

Author

H. Tracy Hall, Nov 08 2020

Keywords

• nonn
• hard
• more

Comments

This counts the distinct roots in the range 0 to 1 occurring among a set of degree-n polynomials the number of which is given by A055612. The 2^n possible outcomes of n coin flips are divided into n + 1 classes depending on how many times heads comes up, and there is one polynomial for each way of deciding how many of each class goes on which side of the partition of outcomes that will model a fair coin flip.

Examples

			For n = 2 the a(2) = 3 different values of p are, in increasing order:
1 - sqrt(1/2), which can model a fair flip with the partition (HH, HT, TH), (TT);
1/2, which can model a fair flip with the partition (HH, HT), (TH, TT) (i.e., by ignoring the second flip); and
sqrt(1/2), which can model a fair flip with the partition (HH), (HT, TH, TT).
		

Links

• Zach Wissner-Gross, Can You Make An Unfair Coin Fair?

Programs

SageMath

P.
 = QQ[]
def polystream(nn, pol=P(0), kk=0):
    if kk >= nn:
        yield pol - 1
    else:
        for ii in sxrange(binomial(nn, kk) + 1):
            for xx in polystream(nn, pol + 2 * ii * p^kk * (1-p)^(nn-kk), kk + 1):
                yield xx
def calculate(nn):
    solutions = Set()
    for pol in polystream(nn):
        rootlist = [xx[0] for xx in pol.roots(ring=QQbar)]
        for root in rootlist:
            if root.real() == root and 0 <= root <= 1:
                solutions += Set([root])
    return len(solutions)