Maths/Stats challenge - 1 of 2 - polls

[Albert Chan]

(05-24-2022 10:21 AM)Joe Horn Wrote:  Aha! I understand now.

For what it's worth, George Chrystal's "Algebra" (first published in 1889, available through Amazon from Dover Press, AMS Chelsea, and some other publishers) seems to cover this problem. Chapter X is called "Continued Fractions", with sub-section 10.15 called "Approximation by convergents".

Unfortunately, it is possible solutions not from the convergents (even semi-convergents)
With small search range (<100), brute force (for "roundtrip") may be the simplest solution.

Code:

function badn(n,P)
    for i=1,#P do
        if round(round(P[i]*n/100)*100/n) ~= P[i] then return true end
    end
end

Note: to reduce binary->decimal conversion errors, we "wasted" some cycles.
Note: round(), does half-way-away-from-zero. For half-way-to-even, use rint() instead.

lua> P = {16,2,51,31} -- one of EdS2's example
lua> n = ceil(100/(16-2+1)) -- = ceil(100/15) = 7
lua> while badn(n,P) do n=n+1 end
lua> n -- smallest solution
45

Had we do convergents/semi-convergents of, say, 31%, we get this:

Code:

31% 0   3   4   2   3
1   0   1   4   9  31
0   1   3  13  29 100

Checked convergents/semi-convergents denominator (<100): 13, 29, 42, 71, none will work.
We would have missed all these:

lua> for n=45,99 do
:      if not badn(n,P) then io.write(n,' ') end
:      end

45 49 51 55 61 81 83 85 86 87 88 89 90 91 93 94 95 96 97 98 99