cp's OEIS Frontend

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.

%I A338772 #12 Nov 19 2023 19:16:01
%S A338772 1,3,19,271,8635,623533
%N 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.
%C A338772 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.
%H A338772 Zach Wissner-Gross, <a href="https://fivethirtyeight.com/features/can-you-make-an-unfair-coin-fair/">Can You Make An Unfair Coin Fair?</a>
%e A338772 For n = 2 the a(2) = 3 different values of p are, in increasing order:
%e A338772 1 - sqrt(1/2), which can model a fair flip with the partition (HH, HT, TH), (TT);
%e A338772 1/2, which can model a fair flip with the partition (HH, HT), (TH, TT) (i.e., by ignoring the second flip); and
%e A338772 sqrt(1/2), which can model a fair flip with the partition (HH), (HT, TH, TT).
%o A338772 (SageMath)
%o A338772 P.<p> = QQ[]
%o A338772 def polystream(nn, pol=P(0), kk=0):
%o A338772     if kk >= nn:
%o A338772         yield pol - 1
%o A338772     else:
%o A338772         for ii in sxrange(binomial(nn, kk) + 1):
%o A338772             for xx in polystream(nn, pol + 2 * ii * p^kk * (1-p)^(nn-kk), kk + 1):
%o A338772                 yield xx
%o A338772 def calculate(nn):
%o A338772     solutions = Set()
%o A338772     for pol in polystream(nn):
%o A338772         rootlist = [xx[0] for xx in pol.roots(ring=QQbar)]
%o A338772         for root in rootlist:
%o A338772             if root.real() == root and 0 <= root <= 1:
%o A338772                 solutions += Set([root])
%o A338772     return len(solutions)
%K A338772 nonn,hard,more
%O A338772 1,2
%A A338772 _H. Tracy Hall_, Nov 08 2020