I was making a similar thing for puzzle 135... I put in babystep file only public keys that starts with "145d" and sometimes I had 2000 keys between 2 "145d" points and sometimes I had 120.000 keys between 2 "145d"...
So in average it will be 65.000 but I can not skip 65.000 keys each time when I find "145d" point
I haven't tested with public keys because, although they have similarities with a hash, they are not exactly a hash and can behave differently. You need to do exhaustive tests based on the distribution over public keys, but you cannot rely on low prefix matches to omit; you need to know the rest of the chain. My script examines in reverse 21 prefixes from most to least to make the calculation with the highest match and does not omit 65,000, but rather a smaller percentage depending on the prefix length.