google-deepmind / google-deepmind/formal-conjectures

Formalize Van Eck's sequence coverage conjecture (OEIS A181391)

Open
#5,162 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Lean
Stars
1.3k
Forks
485
Avg merge
1d 20h
Merged PRs (30d)
327

Description

### What is the conjecture

OEIS A181391 starts with $a(1)=0$. To obtain the next value, look at the current value. If it
has appeared before, write the distance back to its most recent previous occurrence; if it has not
appeared before, write zero.

The sequence begins

$$0,0,1,0,2,0,2,2,1,6,0,5,\ldots$$

OEIS A181391 lists the conjecture:

> every number eventually appears.

Sloane's 2016 open-problems slides also present the coverage statement as unresolved.
The Lean function shifts the source once, so Lean's `a 0` represents OEIS's `a(1)`.

References:

- [OEIS A181391](https://oeis.org/A181391)
- N. J. A. Sloane, [“Some Open Problems”](https://neilsloane.com/doc/EMMay2016.pdf#page=14)

### Prerequisites needed

A primitive-recursive state can store the current value and the most recent prior index of each
value. Mathlib's natural-number arithmetic, `Option`, pointwise function update, and
`Function.Surjective` are sufficient. No addition to `FormalConjecturesForMathlib` is needed.

### [AMS categories](https://github.com/google-deepmind/formal-conjectures/labels?q=ams-)

* ams-11

### Choose either option

- [x] I plan on adding this conjecture to the repository
- [ ] This issue is up for grabs: I would like to see this conjecture added by somebody else

Contributor guide

Open the contributing guide

Research direction

Start by locating the existing Lean function for the shifted sequence and review nearby formalized conjectures. Model the primitive-recursive state using natural-number arithmetic, Option, and pointwise function update, then state the coverage claim with Function.Surjective. Done means the conjecture is added and the project checks it without requiring a new FormalConjecturesForMathlib addition.

Written by the indexing model from the issue text.

Assessment

Domain
tooling
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.