MathDB

Define a search algorithm called

\texttt{powSearch}

. Throughout, assume

A

is a 1-indexed sorted array of distinct integers. To search for an integer

b

in this array, we search the indices

2^0,2^1,\ldots

until we either reach the end of the array or

A[2^k] > b

. If at any point we get

A[2^k] = b

we stop and return

2^k

. Once we have

A[2^k] > b > A[2^{k-1}]

, we throw away the first

2^{k-1}

elements of

A

, and recursively search in the same fashion. For example, for an integer which is at position

3

we will search the locations

1, 2, 4, 3

.
Define

g(x)

to be a function which returns how many (not necessarily distinct) indices we look at when calling

\texttt{powSearch}

with an integer

b

at position

x

A

. For example,

g(3) = 4

. If

A

has length

64

, find

g(1) + g(2) + \ldots + g(64).

Problem Statement