Automatic Invention of Integer Sequences

Simon Colton, Alan Bundy, Toby WalshAAAI 2000 · OpenReview

Abstract: We report on the application of the HR program (Colton, Bundy, & Walsh 1999) to the problem of automatically inventing integer sequences. Seventeen sequences invented by HR are interesting enough to have been accepted into the Encyclopedia of Integer Sequences (Sloane 2000) and all were supplied with interesting conjectures about their nature, also discovered by HR. By extending HR, we have enabled it to perform a two stage process of invention and investigation. This involves generating both the definition and terms of a new sequence, relating it to sequences already in the Encyclopedia and pruning the output to help identify the most surprising and interesting results.

Introduction

In mathematics, integer sequences—such as primes, squares, or the Fibonacci sequence—serve as fundamental building blocks for theoretical development. However, discovering new sequences that are mathematically "interesting" is traditionally a manual, creative task for human mathematicians. A sequence is deemed interesting if it possesses non-obvious properties or surprising relationships to existing knowledge.

This research addresses the challenge of automating mathematical discovery. The goal is not merely to generate lists of numbers, but to define new concepts from fundamental building blocks, filter the output for aesthetic and mathematical value, and justify their significance by relating them to established mathematical theory.

Methodology

The core of this research is the HR program (named after Hardy and Ramanujan), which performs automated theory formation through a two-stage process: invention and investigation.

1. Invention

HR begins with basic mathematical objects (integers) and relations (divisors, multiplication). It then applies seven specific production rules to derive new concepts from these foundations.

Table of HR production rules and the types of concepts they produce.

The program employs a heuristic search guided by eight measures, including complexity (the number of steps required to build a concept) and novelty (how often the resulting categorization has been previously encountered). For instance, the "Size" and "Split" rules can be used sequentially to define primes by counting divisors and then filtering for numbers with exactly two divisors.

Visual representation of the 'Size' and 'Split' production rules transforming a table of divisors into a new sequence.

2. Investigation and Pruning

To ensure the output is meaningful, HR compares its inventions against a local copy of the Encyclopedia of Integer Sequences (OEIS). It identifies relationships such as subsequences, disjointness (e.g., no prime is a square), and record-setting values. Pruning methods are then applied to identify "surprising" results, ensuring that the relationships found are not merely coincidences of small numbers.

Datasets

The primary benchmark for this study was The Encyclopedia of Integer Sequences (Sloane 2000), which at the time contained approximately 54,000 sequences. HR used this repository to validate its inventions and find novel relationships. The program was initially seeded with basic number theory concepts: integers, divisors, and multiplication.

Key Insights

  • Relational Interestingness: A sequence's value often lies in its interaction with other known sequences. HR’s ability to identify that a new sequence is a subsequence of an existing one provides immediate mathematical context.
  • The Value of Simplicity: Lower-complexity concepts—those requiring fewer production rule steps—were often found to be more interesting to human mathematicians. This suggests that "shallow" searches across many initial concepts are more productive than "deep" searches that yield incomprehensible definitions.
  • Validation through Re-invention: HR successfully re-invented 14 "core" sequences (e.g., primes, squares) and 51 total existing sequences, validating that its production rules mirror human mathematical logic.

Results

The HR program demonstrated significant success in automated discovery:

  • OEIS Acceptance: 17 new sequences were accepted into the OEIS based on their novelty and the conjectures HR discovered about them.
  • Refactorable Numbers: HR independently discovered "refactorable numbers" (integers where the number of divisors is itself a divisor) and conjectured that all odd refactorable numbers are squares—a claim the authors subsequently proved.
  • Aesthetic Conjectures: HR discovered that if the sum of an integer's divisors is prime, then the number of its divisors must also be prime.
  • Efficiency: In a single 10-minute run, HR produced 233 sequences, 51 of which were already in the OEIS, and 137 of which were deemed worthy of further investigation.

Limitations and Future Work

Currently, HR cannot invent sequences requiring recursive definitions, such as factorials ($n!$). The authors are developing a "path" production rule to address this. Additionally, while HR is effective within single domains like number theory, future work aims to enable cross-domain discovery (e.g., linking geometry and number theory). The authors are also developing the "Integer Sequence Generator" (ISG), a Java-based tool designed to serve as an automated research assistant for mathematicians.

Summary updated

Abstract

We report on the application of the HR program (Colton, Bundy, & Walsh 1999) to the problem of automatically inventing integer sequences. Seventeen sequences invented by HR are interesting enough to have been accepted into the Encyclopedia of Integer Sequences (Sloane 2000) and all were supplied with interesting conjectures about their nature, also discovered by HR. By extending HR, we have enabled it to perform a two stage process of invention and investigation. This involves generating both the definition and terms of a new sequence, relating it to sequences already in the Encyclopedia and pruning the output to help identify the most surprising and interesting results.
BibTeX
@inproceedings{colton2000automatic,
  author = {Simon Colton and Alan Bundy and Toby Walsh},
  title = {{Automatic Invention of Integer Sequences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2000},
  url = {https://openreview.net/forum?id=r1ZA91W_WB},
}
Figure