results.txt

1 2 51896
1 4 28770
1 8 18104
1 16 13628
1 32 12163
1 64 12041
1 128 12360
2 2 53888
2 4 32692
2 8 23860
2 16 21028
2 32 20889
2 64 21593
3 2 56000
3 4 36852
3 8 29862
3 16 28574
3 32 29445
4 2 57720
4 4 40138
4 8 34480
4 16 34088
4 32 35405
5 2 59906
5 4 44286
5 8 40290
5 16 41086
6 2 61614
6 4 47492
6 8 44662
6 16 46196
7 2 63478
7 4 51096
7 8 49658
7 16 51956
8 2 65488
8 4 54796
8 8 54538
8 16 57514
9 2 66970
9 4 57534
9 8 58138
10 2 69028
10 4 61214
10 8 63012
11 2 70734
11 4 64306
11 8 66990
12 2 72730
12 4 67922
12 8 71544
13 2 74052
13 4 70226
13 8 74450
14 2 76036
14 4 73674
14 8 78694
15 2 77234
15 4 75710
15 8 81212
16 2 79846
16 4 80238
17 2 81272
17 4 82618
18 2 82824
18 4 85370
19 2 84462
19 4 87936
20 2 86074
20 4 90576

testefficiency.py

import random
POSITIVE_RATE = 7
MIX = 16
x = []
for i in range(100000):
    x.append(random.choices(
        (True, False), (POSITIVE_RATE, 100 - POSITIVE_RATE))[0])
tests = 0
positive = 0
def test(sample):
    global tests, positive
    l = len(sample)
    tests += 1
    if True in sample:
        if l == 1:
            positive += 1
            return
        test(sample[:l//2])
        test(sample[l//2:])
while x:
    sample, x = x[:MIX], x[MIX:]
    test(sample)
print(tests)
print(positive)