Transcript The NumbersWithNames Program

The NumbersWithNames
Program
Simon Colton, University of
Edinburgh, UK
Louise Dennis, University of
Nottingham, UK
Some Light Number Theory

Perfect Numbers: 6, 28, 496, …
Equal to sum of proper divisors
 Are pernicious (prime num. 1s in binary)
 6 = 110, 28 = 11100, 496 = 111110000
 Not refactorable numbers


Puzzle (Paul Zeitz)

Numbers of the form n(n+1)(n+2)(n+3)
are never square numbers
Neil Sloane’s Encylcopedia
of Integer Sequences

Large database of sequences
E.g., Primes: 2, 3, 5, 7, 11, 13,…
 Contains 60,000+ sequences (36 years)
 Online: research.att.com/~njas/sequences


Identifies a sequence typed in
Uses tranformations to find matches
 Think of these as equiv. conjectures

NumbersWithNames
Program Overview
Enhances EIS conjecture making
 Uses a subset of 1000 sequences

Number types with names
 Prime, square, odd, perfect, triangle,…


Four step process (given seq. S)
Invents related sequences S1, S2, …
 Makes conjectures about S, S1, S2,…
 Prunes uninteresting conjectures
 Sorts conjectures by plausibility

Inventing Related Sequences


User chooses sequence: 2, 3, 5, 7, 11, …
Add one and take one


Monster-barring (Lakatos)



E.g, 3, 5, 7, 11, 13, … (primes except 2)
Difference sequence


E.g., 3, 4, 6, 8, 12, … (primes+1)
1, 2, 2, 4, … (difference between primes)
Other transformations + related seqs.
Combining sequence with ‘core’ seqs.


Conjunction and indexing,
e.g., palindrome primes, every second prime
Making Conjectures

Given a sequence S


Finds all super and sub-sequences


E.g., perfect numbers are even
Finds all disjoint sequences


E.g, perfect numbers: 6, 28, 496, …
E.g., primes numbers are not perfect
Makes ‘moonshine’ conjectures
Large number in S and another seq.
 E.g., 107374182 superperfect number

Pruning

All weaker conjectures are pruned
E-perfect numbers are refactorables
 E-perfect numbers are even refactorables


User supplies words for definition
Prune those which contain word
 Prune those which don’t contain word


Keywords from Encyclopedia

Core, Nice, etc.
Sorting using Plausibility

Plausibility measure of conjectures



E.g., odd refactorables are square
Squares numbers:



1, 4, 9, …, 1849 (44 terms)
Odd refactorable numbers


Probability of it being a coincidence
1,9,225,441,625,1089,1521,2025,…
P(n is square) = 44/1849
P(conjecture occurs by chance)
= (44/1849)7 = 4.3 x 10-12

Unlikely to be a coincidence
Demonstration

Type in your birthday numbers


Choose a sequence


NWN tells you about these numbers
Ask NWN to make conjectures
Very simple interface

Can also link to the online
Encyclopedia.
Results

Program available online:




Developed over many months
Many proved theorems discovered



machine-creativity.com/programs/nwn
Manual, Results, Project details
(n) is prime  (n) is prime
Perfects are nialpdrome+pernicious
Many theorems about refactorables


Congruent to 0,1,2 or 4 mod 8
Odd refactorables are square numbers
Sqrt(n)-rough numbers

Sqrt(n)-rough numbers (mail list)

Largest prime factor < n (e,g., 8)
3n(n+1) are sqrt(n)-rough numbers
 6n(n+1) are sqrt(n)-rough numbers
 Use Clam to plan a proof



2 days to specify lemmas about <, n
Clam plans a proof

Level of a “pen and paper” proof
Zeitz’s Problem
Hungarian maths competition
 Multiply four consecutive numbers

n(n+1)(n+2)(n+3)
 Never a square number


Add this sequence to NWN


Look for conjectures which help
Demonstration
Conclusions

Newell and Simon predict in 1958:
Computer discover and prove theorem
 Goal of our project (HR system also)


NWN program
Invents new seqs, makes conjectures
 Prunes dull ones, sorts by plausibility


Makes interesting conjectures in N.T.

Possibility of proving them automatically
Future Work
Add more transformations
 Add more sequences
 Strengthen link to Clam



Decision procedures
Encourage mathematicians to use it
Disappointing response so far
 I’m not a research mathematician


machine-creativity.com/programs/nwn