Humans learn and generate languages, music, games, and seemingly limitless varieties of other structures across domains. Unlike many AI systems, we often do so from little data. How do we learn such large varieties of richly structured representations so efficiently? One possibility is that people ``learn by programming,'' synthesizing data-generating algorithms to explain what we observe. We examine the nature and origins of this learning mechanism in adults, children, and nonhuman primates (macaque monkeys), using a highly unconstrained sequence prediction task. Although adults and children quickly learn many richly structured sequences, monkeys learn only the simplest sequences (e.g. lines). We test multiple learning models, finding that adults are best explained by a ``Language of Thought''-like program-learning model and monkeys by a simpler extrapolation strategy. Children exhibit varied learning strategies but are best fit in aggregate by an intermediately expressive model. Paper available at https://sites.google.com/view/patternlearning.