Thirty-nine cities need more DNA than the Earth

By the 42Math team · 22 August 20266 min read

A brute-force route search with one DNA strand per candidate ordering needs half a gram of DNA for twenty cities. For thirty-nine it needs more than the mass of the Earth.

In 1994 Leonard Adleman dissolved a combinatorial problem in a test tube. He encoded a seven-city road network as short strands of DNA, let them anneal into every route the network allowed, and then filtered the soup down to the routes that visited each city exactly once. The answer precipitated out of a vial. It took about a week of laboratory work to solve a problem a student solves on paper in a minute, and that was entirely beside the point: something like 10¹⁴ strands had each tried a route simultaneously, in a volume you could hold between two fingers.

The promise was obvious and enormous. Exponential search is hard because the candidates explode; here was a machine that looked at every candidate at once. Thirty years later nothing in your pocket runs on DNA, and the reason is not engineering. It is arithmetic you can do on an envelope.

Count the strands, then weigh them

Molecular parallelism is bought one molecule at a time. Every candidate needs its own physical strand, so the DNA required is the number of candidates multiplied by the mass of one strand.

The second factor is very small. Single-stranded DNA runs about 330 grams per mole of bases, so at twenty bases per city a twenty-city strand weighs roughly 2 × 10⁻¹⁹ grams. The first factor is a factorial, and a factorial does not care how small the second factor is.

Twenty cities: 0.53 grams. A pinch of powder.

Thirty cities: 8.7 × 10¹³ grams. That is 87 million tonnes, roughly a fifth of the combined mass of every human being alive.

Thirty-nine cities: more than the mass of the Earth.

Nineteen cities separate "a pinch" from "the planet", which is why DNA Computing Scale is a slider rather than a paragraph. Walk it up one city at a time and the comparable scale climbs from "less than a gram" through kilograms and tonnes to "at least one Earth mass". Watching that happen does something that reading the exponent does not.

The obvious objection is that nobody would enumerate all n! orderings. Fix the starting city and refuse to count a tour and its mirror image separately, and the count divides by 2n. Do it: the crossing moves from thirty-nine cities to forty-one. That is the entire return on the whole symmetry group — two cities.

This is what "parallelism does not change the complexity class" means once it is concrete. Adleman's tube bought a speed-up of about 10¹⁴, which is an astonishing number and still a constant. A factorial eats 10¹⁴ and asks for the next course. Doubling the tube buys a fraction of one city.

The same wall, hit from the other side

Biology reached this argument first and used it to prove the opposite point.

In 1969 Cyrus Levinthal asked how a protein finds its shape. Take a chain of a hundred residues and allow each junction only three orientations, a wild underestimate. That is 3¹⁰⁰, about 5 × 10⁴⁷ conformations. Let the chain try one every 10⁻¹³ seconds, roughly a molecular vibration and about as fast as physics allows. Sampling them all takes 1.6 × 10²⁷ years: 10¹⁷ times the present age of the universe.

Proteins fold in milliseconds.

Levinthal's paradox is not a puzzle about folding quickly. It is a proof that folding is not a search. The energy landscape is not a flat lottery of conformations but a funnel, and a chain in a funnel is never choosing among 10⁴⁷ options. It is falling. Zwanzig, Szabo and Bagchi worked out in 1992 how little tilt the funnel needs. They took a simple model and showed that an energy bias of order a few kT against locally unfavourable configurations is enough to cut Levinthal’s time to a biologically reasonable size. Not a clever algorithm. A slope.

Push the residue count and the states per residue around in the Levinthal Paradox Explorer and watch how violently the number resists being made reasonable. Cutting the states per residue from three to two buys a factor of 10¹⁷·⁶ and still leaves a hundred-residue chain needing a good fraction of the age of the universe. The base is worth one payment; the exponent charges again for every residue.

Now put the two arguments side by side, because they are the same arithmetic. A protein cannot enumerate its conformations. A test tube cannot enumerate its routes. Nature's answer was to stop enumerating and build a landscape that funnels. DNA computing's answer was to enumerate harder, in parallel, with more molecules, which is precisely the move the counting forbids.

What survives

None of this makes molecular computing a dead end. It makes the sales pitch wrong, which is a different thing, and the honest pitch is the better one.

Start with energy. Landauer showed in 1961 that erasing one bit irreversibly must dissipate at least kT ln 2: at body temperature, 3.0 × 10⁻²¹ joules. That is a floor set by thermodynamics, not by fabrication. One ATP hydrolysis, the coin biology actually spends, releases about twenty kT: 8.6 × 10⁻²⁰ joules, or 29 times the floor. A logic operation in good CMOS costs something near a femtojoule, which is 337,000 times the floor.

molecular event ≈ 29 × kT ln 2   ·   silicon logic ≈ 337,000 × kT ln 2

Four orders of magnitude, and they are on the wrong side for silicon. A cell computes slowly and at nearly the thermodynamic minimum, tens of kT from a floor that a transistor misses by hundreds of thousands. Set the temperature and the per-operation energy in Energy per Operation and the gap is hard to unsee.

Then storage. Encode data in the bases instead of the routes and the density that made brute force absurd becomes the entire selling point: around 3 × 10²⁰ bytes per gram. Every film ever released, in less volume than a sugar cube, stable for centuries in the dark and drawing no power to sit still. DNA Data Storage puts the real overheads in — indexing, primer binding sites, the codes that avoid long runs of one base — and the density survives them comfortably.

So the exponential that kills DNA as a search engine is the same exponential that makes it an extraordinary archive. Searching needs one molecule per candidate, and candidates grow factorially. Archiving needs one molecule per datum, and data grow linearly. Identical chemistry, identical density, opposite verdicts, and the only difference is which quantity you asked to scale.

The shape of the argument

When something offers you massive parallelism, ask what the parallelism multiplies. Against an exponential it does not matter how large the constant is: 10¹⁴ and 10²³ are the same number when the opponent is a factorial. Adleman's experiment was a beautifully executed demonstration of a constant factor, and the field read it as a slope.

Levinthal ran the same count and drew the correct conclusion at once, because he was not selling anything: if the count is impossible, the mechanism is not the one you assumed. What was left over when the search story went away — near-optimal energy per event, absurd density per gram — is a genuinely good hand, and nobody would have looked at it twice while the search story was still on the table.

Published 22 August 2026 · corrections welcome via the corrections page.