Costas Array Generator

What this generator does

Produces one arrangement of dots satisfying the Costas condition, at the size you ask for, along with the difference triangle that demonstrates it. Up to order ten it lists every array of that size first and then picks one of them at random, so the draw is even across the whole set and the page can tell you how large that set is. The closest tool here is the Golomb ruler generator, which does the one-dimensional version — marks on a ruler with no two pairs the same distance apart. Going from distances to arrows changes the character of the problem completely: long Golomb rulers are easy to find, and large Costas arrays are not known to exist at all beyond a certain size.

How to use this tool

1. Choose the size of the board, from three up to twelve.
2. Press the button to draw an array.
3. Read the row of numbers: it says which row the dot sits in, column by column.
4. Check the difference triangle underneath — no row of it repeats a value, and that is the whole condition.
5. Type a seed if you want the same array again later.

Understanding the controls

Order

The size of the board, and also the number of dots. Below ten every array of that size is listed before one is chosen, so the draw is even and the total is shown; order ten takes about half a second for that reason. Eleven and twelve are found by searching instead, because listing them would take seconds rather than fractions of one.

Seed (optional)

Type anything to get the same array back. The work is counted in placements rather than in time, so the same seed gives the same array however busy the machine is. A seed exists to make a result reproducible rather than to keep it hidden, so it is not cryptographic and nothing here treats it as though it were.

Common use cases

• A hopping pattern for a frequency-agile transmitter, or a teaching example of one
• A schedule of time slots where no gap between two events ever repeats at the same spacing
• Worked material for a lesson on permutations and difference sets
• Seeing how fast a counting problem can collapse: twelve dots have 479 million arrangements and 7,852 good ones

How this generator works

The search fills the board column by column, and at each column it tries only rows that keep every displacement distinct so far. That is what makes the problem tractable: an arrangement that already repeats a displacement can never be fixed by what comes later, so the whole family of arrangements below it is skipped rather than being discovered at the last column. The condition itself is read off the finished arrangement by a separate check that knows nothing about how it was built — it rebuilds the difference triangle and looks for a repeat in any row. The strongest evidence that all of this is right is not internal. The number of these arrays at each size is a published quantity, settled by exhaustive searches with no connection to this site, and counting them here gives 1, 2, 4, 12, 40, 116, 200, 444, 760 and 2,160 for the first ten sizes — the published figures, to the unit, at every one. Two published recipes for building them, Welch's and Lempel's, were run for every primitive root of the primes up to 31, and the check accepted every array either of them produced.

Randomness and fairness

Up to order ten the whole set of arrays is listed and one is kept by a method that leaves every member equally likely, so the draw is even across all of them. Above that the array is found by search with the rows tried in a random order, which is quick but is not an even draw from the whole set — the page says which of the two you got. Either way the source is your browser's cryptographic one unless you give a seed, which replaces it with a repeatable source.

For how randomness is produced across the whole site, see how Generate Random works.

Limitations and good to know

• Orders three to twelve only. Listing every array of order eleven takes over two seconds and order thirteen over half a minute, which is too long to sit behind a button, and the searched arrays above order twelve get rapidly harder to find.
• Above order ten the array is found rather than drawn evenly, so some arrays are much likelier to turn up than others. Below that the draw is even across the whole set.
• Rotations and reflections of one array are counted and drawn as different arrays, which is the convention the published counts use. At small sizes that means several of the results you get are the same picture turned round.
• Nothing here says an array is good for any particular radar or sonar system. Real systems constrain the hopping pattern in ways — bandwidth, dwell time, regulatory allocation — that this knows nothing about.
• Costas arrays are not known for every size. None has ever been found at order 32 or 33, and whether they exist at every larger size is an open question; nothing offered here goes near that boundary.

Privacy and your data

The array is searched for and checked entirely in your browser. Nothing you type as a seed, and no array built from it, leaves the device.

Frequently asked questions

What is the difference triangle, and why does it prove anything?

Each row of the triangle takes the dots a fixed number of columns apart and records how many rows apart they are. The first row does neighbours, the second does pairs two columns apart, and so on. Between them those rows cover every pair of dots exactly once, so saying no row of the triangle repeats a value is the same as saying no two pairs of dots are separated by the same arrow — which is the definition.

What were these actually invented for?

Sonar and radar. A pulse that hops between frequencies over time traces a pattern of this shape, and what matters is that the pattern should overlap itself in at most one place when it is shifted in time or in frequency. The distinct-displacement condition is exactly that requirement, which is why the arrangement has a name rather than being a curiosity.

How are they related to Golomb rulers?

A Golomb ruler is the same idea in one dimension: marks on a line with no two pairs the same distance apart. A Costas array keeps the condition but gives the separation a direction as well as a size. The extra dimension makes them scarcer rather than more plentiful, and unlike rulers there is no construction that covers every size.

Can you build these without searching?

For some sizes, yes. Two published recipes — Welch's and Lempel's — produce one directly from the arithmetic of a prime number, and between them they cover the sizes one less and two less than a prime. They do not cover every size, which is why sizes like 32 remain unsettled, and they are used here only to check that the condition is being applied correctly.