Question I'm interested in

Assuming you have 1024 possibilities, if you divide half of the possibilites at each step it takes 10 steps to finish.

What about if you remove 1/4 of the possibilites

1/8 of the possibilites etc

How much longer does it take mathematically?  What is the formula/principle behind this?

log(# possibilities) / log(1/(fraction probabilities removed each step))

2^10 = 1024
4^5 = 1024
8^(10/3) = 1024

10,5,3.33, etc

Number of divisions: N
Number of steps: S
Number of possibilites: P

N^S = P
S*Ln(N) = Ln(P)
S = Ln(P)/Ln(N)

Thank you for the reply

>>2

so if I remove 1/4 of possibilites with each step I get

log(1024)/log(1/4)   = steps required?


>>3
I'm not sure exactly what you mean but assuming I plugged in

S = Ln(1024)/Ln(1/4) I would get the answer

which goes with what >>2 said

Anyway thanks again

Okay for the case of 1024 possibilites removing 1/4 of them each step

natural log(1024) / natural log(4) = 5 which can't be right.

with 4 on the denominator it gives me 5 which is impossible since it is faster then removing 1/2 each step.

log(1 024) / log(1 / (1 / 4)) = 5  also is wrong


My question wasn't how to get 4^5 = 1024 but given 1024 possibilities and removing 1/4 of them each step, how many steps until 1 or 0 possibilities are left.

I believe it takes 26ish(+-2) steps to leave no possibilities left (used recursive programming).

I'm wondering what formula would allow me to calculate this.

>>4
not quite.  You're removing 1/4, so 1/(1/4) = 4

Log(1024)/Log(4) if you remove 1/4 at each step.

If you don't have tidy exponents, you'll need to take the ceiling.

>>3 wrote the same thing, just tidier