This question got me thinking.
If you have a list of length n and recursively delete every other element from the list until only one element remains, is there any relationship between the index of the last remaining item and n?
For example, with a list of length 100:
$[0, 1, 2, ..., 99]$
$[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]$
$[3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99]$
$[7, 15, 23, 31, 39, 47, 55, 63, 71, 79, 87, 95]$
$[15, 31, 47, 63, 79, 95]$
$[31, 63, 95]$
$[63]$
You get the 63rd index in the list.
But with a list of length 1000, you get 511. And with a list of length 10000, you get 8191.
I feel like there's something obvious but I'm missing it. What is mathematically being done here? Can we predict the index with n?
edit: a user posted the formula math.pow(2, math.floor(math.log(n, 2))) - 1 but I'd definitely love some explanation here.
You will always end up getting $2^n-1$ where n is maximum integer such that $2^n<K$