Although people's legs are capable of a broad range of muscle-use and gait patterns, they generally prefer just two. They walk, swinging their body over a relatively straight leg with each step, or run, bouncing up off a bent leg between aerial phases. Walking feels easiest when going slowly, and running feels easiest when going faster. More unusual gaits seem more tiring. Perhaps this is because walking and running use the least energy. Addressing this classic conjecture with experiments requires comparing walking and running with many other strange and unpractised gaits. As an alternative, a basic understanding of gait choice might be obtained by calculating energy cost by using mechanics-based models. Here we use a minimal model that can describe walking and running as well as an infinite variety of other gaits. We use computer optimization to find which gaits are indeed energetically optimal for this model. At low speeds the optimization discovers the classic inverted-pendulum walk, at high speeds it discovers a bouncing run, even without springs, and at intermediate speeds it finds a new pendular-running gait that includes walking and running as extreme cases.