Simple and intuitive. O(n²) though, so it's slow for long strings. I would replace i.islower() with i.isalpha() for more readable code.

Well, islower() returns False if isalpha() is False, so islower() is actually used to check if the character is alphabetical, since all the alphabetical characters are already lower case, so it will only be False for only non-alphabetical characters. It's not wrong, but it would be more logical and readable if isalpha() was used instead.

You may want to use:

range(len(arr))

The current code always tests every number from 0 to 999, even if the list has only 5 elements. It also can't find the smallest unused ID if it's bigger than 999.

How can you know that the smallest unused ID isn't 1000? Or some other number bigger than 999? The code only checks numbers up to 999. Try using:

range(len(arr))

Yes, it is very slow, O(n²), and one should use a different solution for bigger lists, eg. using a set/hash table. However, there is no solution with O(log n). You need to look through all items in the list, so you will always have at least O(n). Solutions using sorting (eg. quicksort) or building hash tables will probably have O(n log n) at least.

Nice solution. Notice that you can use

  4*while i >= base**(max_fours):

instead of

  while i >= base**(max_fours):

Then the loop will only need to run 1/4 as many times :)

This doesn't actually calculate the answers though.