18th Nov: We've switched servers and will be updating the old code over the next couple months, meaning that several things might break. Please report issues here.

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 ^{note }Why? Because prime numbers are only divisible by the number one and themselves. For example, it doesn't matter what number base you are using or what you call the numbers, 7 rocks cannot be divided up into any whole number of equal groups of rocks without breaking them. If the aliens have math, they'll get this — resource allocation is one of the first tricks any group has to figure out.—the idea is that they're too irregular to arise from any natural process ^{note }Although reproduction cycle periods of some insects tend to be a prime number of years to prevent matching another kind and then predators synchronising on them (i.e., no mathematical equation is known that will exhaustively produce them in reasonable time ^{note }There are equations that can produce an unlimited amount of prime numbers, but not all of them, and methods that will get them all, but the computation time is enormous.), but mathematically simple enough that it's assumed any intelligent being can recognize them as nonrandom. More generally, anything obviously recognizable as simple math (such as digits of pi, or a proof of the Pythagorean theorem) can serve the same function. Of course, the digits of pi will change if the aliens don't have a base10 system ( odds are that they don't), while the prime numbers will not change if you represent them properly.
Often this can look like an instance of Only Smart People May Pass (just like plenty of humans do not know about prime numbers or basic math, plenty of otherwise intelligent aliens won't know what to do with the puzzle). However, while Only Smart People May Pass happens in the context of a precreated puzzle or situation, the entire point of First Contact Math is that it provides the best hope we might have of communicating without having any context at all.
See also First Contact Team, for when First Contact Math might fail and you need to plan for any contigency.
Examples:
open/close all folders
Comic Books
 Life on Another Planet (1978) by Will Eisner. An artificial radio signal from Barnard's Star listing prime numbers (although the term "prime" is never used in the story) is received at the Mesa Radio Astronomy Observatory.
 Ultimate Fantastic Four  When Reed makes contact with some residents of the Negative Zone, their first few exchanges are conducted in binary. After Reed sends them Pi and the human symbol for 'hydrogen', their computer takes over and downloads the first contact package he prepared.
Fan Works
 The basic story of Arrow 18 Mission Logs is of first contact between humans and ponies. After Twilight Sparkle leaves Randy (the human astronaut who just landed in Equestria) a basket with some food, he leaves a sheet of paper with basic math problems on them (including a chart indicating that "1" means one, "2" means two, etc.) Twilight's reaction when she figures out that the "stridetaur" is trying to communicate with math is one of unbridled glee.
 Discussed but ultimately averted in The Next Frontier. The odds of anything remotely recognisable as prime numbers or similar at interstellar distances are pretty much nil, but a single repeating tone or a noise like this could carry much further. And by the time first contact actually happens, the aliens have Learned English from Watching Television anyway.
 Notably averted in Mass Effect Clash Of Civilizations. Both the UNSC and Citadel have their own method of deciphering language, neither of which involve mathematics.
Film
 Colossus The Forbin Project. How Colossus establishes a common language with the Soviet Master Computer Guardian. It starts with 1+1=2 and in a few hours has developed an entire new language for them to communicate. Unfortunately this alarms both governments as they can't be sure strategic secrets aren't being leaked, so the President and Premier decide to break the link. The computers do not react well.
 Contact has aliens contact Earth by sending a sequence of prime numbers. Later, they send instructions for building a machine to reach them by imbedding basic universal math principles into the instructions so any race with knowledge of mathematics can decode it and build the machine.
Literature
 Contact: The alien transmission begins with a sequence of prime numbers, before continuing on to more useful mathematics and science. The novel by Carl Sagan (who also championed the use of primes in this context in Real Life SETI) makes considerably more of this, also using prime numbers in the encoding of the more complex layers of the transmission.
 In Schild's Ladder by Greg Egan, the protagonists realize that there's intelligent life inside a pseudovacuum when they notice that a series of pulses coming from it represent consecutive prime numbers.
 In Arthur C. Clarke's novel version of 2001: A Space Odyssey, Dave Bowman tries (unsuccessfully) to talk to the Iapetus monolith by broadcasting primes at it.
 Tom Swift Jr. and his father communicate with some aliens by sending mathematical symbols at them (and vice versa) throughout his entire series. Exactly what is meant by "mathematical symbols" is never made particularly explicit.
 The Barbara Hambly novel The Silicon Mage shows Antryg and Joanna communicating with an extradimensional via Pi and Planck's Constant.
 The Action Heros Handbook has a chapter on communicating with extraterrestrials, and suggests starting with basic concepts like numbers and shapes because the authors of the book believe that no matter how alien the culture is, they would still be able to have dialogue about that, especially if they're able to go into space.
 This fails in Calculating God by Robert J Sawyer; transmissions to Delta Pavonis go unnoticed by the native Wreed, because the Wreed have a brain structure that makes them incapable of doing math. (They can automatically recognize numbers of up to 46, and that's it.) They are very good at ethical problems and analog simulations, though. The Forhilnor also admit that they were astonished to find a civilization on the Wreed homeworld, but stoutly defend their intelligence, noting that the Wreed build beautiful cities out of the sparse available materials there.
 In C. J. Cherryh's Chanur Saga, when the human Tully is cornered by the felinoid Hani, he writes out (in his own blood) numbers from zero on up. When he gets to 10 they realize that he might be using a positional notation system.
 Used, then subverted in the series beginning with Emprise. An alien transmission is recognized and eventually translated into a simple depiction of the aliens and their system. However, one mathematician claims to have found many more levels of meaning embedded in the message, a la The Bible Code. Ultimately, it turns out that these new levels are the product of his overactive imagination.
 Double subverted in that the message turns out to be from the remnants of a human colony from humanity's first attempt at interstellar colonization during the last ice age, which came to an abrupt end when the real Starfish Aliens wiped out (almost) all of the colonies and bombed Earth back into the stone age.
 The alien ship in Anathem has a proof of the Pythagorean Theorem on its hull for this reason.
 Larry Niven and Jerry Pournelle's The Mote In Gods Eye has the human exploration party and the Moties use this method for initiating communications.
Cargill and Horvath's team worked together to answer the pulses. One, two, three, four blinked the light, and Cargill used the forward batteries to send five, six, seven. Twenty minutes later the light sent three one eight four eleven, repeated, and the ship's brain ground out: Pi, base twelve. Cargill used the computer to find e to the same base and replied with that. But the true message was, We want to talk to you. And MacArthur's answer was, Fine. Elaborations would have to wait.
 In the French novel Ceux de nulle part, the protagonist tries to communicate with an alien by using basic math and fails. Then again, normal physical laws do not seem to apply to said alien.
 The Polish short story "Koła na piasku" by Adam Pietrasiewicz parodies this: a human and an alien talk to each other friendlily by radio before realizing what the other is. They immediately proceed to follow the "standard first contact procedures"; the human draws a Pythagorean triangle, while the alien draws some squiggly lines. They then go back to their vehicles and complain by radio that they can't comprehend what the other one drew (and none of them knows math very well, so they don't even know what they drew, only that they were told to draw them).
 The Murderous Maths book discussing the properties of numbers discusses this trope.
 In H. G. Wells' The First Men in the Moon, Cavor discusses using math to communicate with his alien captors, but he doesn't really have any idea how to do so.
 In a related "First Contact Chemistry", in James P. Hogan's Inherit the Stars the key to deciphering an alien language comes when someone recognizes a Periodic Table of the Elements in an alien book.
 H. Beam Piper's short story "Omnilingual" is an earlier example of the Periodic Table as universal key. It helps that the Martian language tends to make new words by combining existing ones, so that (for example) the word for "metal" is part of the names of various metallic elements.
 In Michael Crichton's Sphere this is the way Harry manages to first make meaningful contact with the mysterious alien presence.
 In The Andromeda Affair the aliens are transmitting a sequence of bits whose length is the product of two primes. The hero assumes correctly that this implies the bits should be arranged in a twodimensional grid to be understood.
 Isaac Asimov's nonfiction book about the concept of "parity" in physics, The Left Hand of the Electron, uses this as a Framing Device. If you were sending an interstellar radio message to an alien culture about which you know nothing, how would you explain the concepts of "right" and "left"?
 In Dreamcatcher by Stephen King, a population of infected send pleading messages interspersed with a recitation of prime numbers. One of the characters speculates it is to prove they've an intelligent species. They must not be that intelligent though, since they include 27 and 117 in their list. (Also 1, but that's actually reasonable.) This deviation from the primes isn't noted in the novel though, and was probably either unintentional or done because the numbers have significance to Derry, the novel's setting.
 The Real Life attempts by SETI are described in Earth (The Book) or, as Jon Stewart calls it, "drunkdialing the universe".
Live Action TV
 In the Farscape episode "Through The LookingGlass", Crichton realizes an extradimensional being is trying to communicate with the crew rather than hunt them when he recognises that the talon slashes that it makes in reality are the first few successive prime numbers.
 In the Star Trek: The Next Generation episode "Allegiance", Picard is kidnapped by unknown aliens; he attempts to convince them that he's intelligent by repeatedly tapping out the first six prime numbers.
 In an episode of Star Trek: Voyager, an alien species living on a planet where time moves extremely fast attempt to communicate with the Voyager (or, as they call it, the Sky Ship) via radio by using prime numbers and universal constants. Since, by the time they receive and recognize the signals, the scientist who sent them is long dead, the Voyager crew don't bother responding.
 Amusingly played with in "Future's End", where after being sent back in time to Earth in the year 1996, they're picked up by an astronomer who attempts to communicate with the "aliens" in orbit by sending the SETI message. A crewman asks Harry if they should respond, to which Harry says, "Absolutely not."
 Subverted in an episode of Babylon 5. A probe sent out by an advanced species containing mathematical riddles appears to be this at first... until it's found out the thing's actually a way for the isolationist species to figure out which other races are a threat and destroy them. Fortunately, the probe's fairly stupid.
Video Games
 In Rama (based on the novel Rendezvous with Rama), the Ramans put many mathbased obstacles in your path, presumably for this reason.
Web Original
Other
Real Life
 So far as anyone can prove beyond a shadow of a doubt, we haven't done any first contact yet to see if this works. Some of the messages we've beamed into space have included this just in case.
 In the free ebook released by NASA Archaeology, Anthropology, and Interstellar Communication is is posited that while math may be great for first contact we may run into some stumbling blocks trying to understand language without context to go by. The book cites how for years the Mayan number system was decoded and understood, however scholars were stumped for many years after by the written language. If we had that much trouble with a human language, things may be even harder working out an alien language, even if we can agree on math.
 "Prime Numbers and the Search for Extraterrestrial Intelligence" by Carl Pomerance, is an academic paper which discusses the idea in depth.
 Space probes (like Pioneer 10) we sent out of the Solar System usually contain this in some form. ^{note }And a star map telling them where we are. And naked people. (That last one is presumably to show what humans actually look like. It Makes Sense in Context — otherwise the aliens might assume that the probe itself is the intelligent life!
 Lincos is one possible example of how to extend the message into actual communication, building up to a complete language from only the natural numbers (fiction, being written by writers, usually skips this bit).
 The notion mentioned above for The Andromeda Affair ("a repeating sequence with a period that is the product of two primes is an indicator that it represents a [unique] rectangular grid^{note } A unique rectangle with only two possible useful rotations, thereby reducing arrangement of the data to a maximum of two simple bruteforce attempts") is not a stunning leap of logic for anyone familiar with SETI, since it's been used in human broadcasts as well.
 The idea of First Contact Math is Older Than Radio, albeit back then it was more about proving that Earth is inhabited by a sentient species, rather than communicating after having already found out about each other. These early ideas involved sending messages to the Martians by means such as Pythagorean triangles in form of tracts of farmland in the Siberian woods, or ditches filled with burning oil in nighttime Sahara.

