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

>>2
>>3
>>4
FAIL.

Ceil[-Log(1024)/Log(1-(1/4))]

>>2
>>3
>>4
>>5
>>6
Christ, so much fail in one thread. Removing one fourth of the possibilities at each step:
0th step: 1024
1st step: 768
2nd step: 576
3rd step: 432
4th step: 324
5th step: 243
...
10th step: 57.67
...

The nth step (with n = 0 corresponding to 1024) will have 1024*3^n/4^n possibilities remaining, meaning that we need 25 steps in order to get down to 1 possibility. All of you did the calculation for removing THREE fourths of the possibilities at each step.

>>8
Or, instead of fucking around with all of that, just do:
Log(1024)/Log(0.75) = -24.0942
-Log(1024)/Log(0.75) = 24.0942
Ceiling(-Log(1024)/Log(0.75)) = 25

YW

>>9
How did you think I came up with 25? The list of values was only to head off the inevitable argument from the morons that posted >>2-6