First Contact situations with Starfish Aliens have an inherent problem -- since the aliens are so incomprehensible, how will you even realize that they're intelligent? For that matter, how can you convince them that you are?
The generally accepted universal signal of intelligence in this situation is the ability to produce a sequence of prime numbers. If the aliens have math, they'll get this -- it's an aspect very closely tied to resource allocation, which is one of the first tricks any intelligent group has to figure out. You see, prime numbers are only divisible by the number one and themselves; for example, seven rocks cannot be divided up into any whole number of equal groups of rocks without breaking them. It doesn't matter what number base you are using or what you call the numbers; seven rocks (• • • • • • •) will always be the same, observable amount.