Additive number theory and integer sequences

Ulam-sequence density

Collaboration beta

Does the original Ulam sequence, seeded by 1 and 2, have a positive natural density? The target requires a limiting density and strict positivity. Neither positive lower density alone nor a density theorem for a filtered model resolves it.

\exists δ > 0 \lim_{N \to \infty} \frac{A (N)}{N} = δ, A (N) = | U \cap [1, N] | .

Known results and sources

Illustration: Ulam’s rule uses two distinct earlier terms and chooses the least larger integer with exactly one representation.

Research problem

Exact mathematical statement

Let $U=\{a_1<a_2<\cdots\}$ with $a_1=1,a_2=2$ . At every later stage, append the smallest integer larger than the previous term that has exactly one expression as the sum of two distinct earlier terms. Equivalently, with $u(n)=\mathbf1_{\{n\in U\}}$ and $u(n)=0$ for $n\le0$ ,

r(n)=\sum_{1\le a<n-a}u(a)u(n-a), \qquad u(1)=u(2)=1, \qquad u(n)=\mathbf1_{\{r(n)=1\}}\quad(n\ge3). \tag{ULD-A01}

The exact target is

\exists\,\delta>0\quad \lim_{N\to\infty}\frac{A(N)}N=\delta, \qquad A(N)=|U\cap[1,N]|.

A proof that the lower density is positive is a significant intermediate implication but is not by itself the full target. A proof that a natural density exists with value possibly zero is likewise insufficient. A disproof could show zero density or nonexistence of a positive limiting density; none is established here.

Problem infographic

Problem at a glance

Illustration: The original Ulam sequence rejects 5, accepts 6, and selects ten values in the finite interval from 1 to 20; a positive limiting density remains a separate open requirement. — Illustration: A(20) = 10 is a finite example. It establishes neither existence nor positivity of a natural-density limit for the original sequence beginning with 1 and 2.

Current mathematical picture

Where work on Ulam-sequence density stands

Open problem

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureApply exact subadditivity to the original counting function

The source records x=604244 and y=732374 with A(x)=44678, A(y)=54134, and A(x+y)=98955. Thus A(x)+A(y)−A(x+y)=−143. A quantitative bound on positive three-block deficits remains a candidate route. It permits signed local discrepancies while requiring a summable future loss budget rather than exact subadditivity.

Route status · Narrowed route

Main reductionActual-parent control would give positive lower density

If every actual accepted term p+q, with p<q its unique distinct summands, obeys A(p+q)−A(q)≥A(p)−4√p, the source gives lower density at least 1/1600. Here p is the smaller integer summand, not a term index. The universal premise is open and positive lower density alone does not establish the target limit.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeBound the entire future weighted positive deficit of the original sequence below a proved starting potential, or establish another sufficient all-scale loss estimate.Task status · Ready to work on

Work mapped so far

Ulam-sequence density in numbers

1.2kretained lines of mathematical investigation1,154 in the current working snapshot

Argument development: 744 · 64%
Explored or eliminated routes: 53 · 5%
Computational analysis: 144 · 12%
Open obligations: 127 · 11%
Definitions and setup: 86 · 7%

9selected mapped statements2routes investigated3open questions3contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Status checkedSep 7, 2026

Source recordedSep 7, 2026

Recommended next task

Bound the entire future weighted positive deficit of the original sequence below a proved starting potential, or establish another sufficient all-scale loss estimate.

Suggested move: Suggested next step: derive a compensation inequality for the three actual counting blocks and account for future accepted summands and rejected targets; identify exactly where original greedy saturation excludes forced-omission countermodels.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

14 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded

Narrowed routeApply exact subadditivity to the original counting function

Route status · Narrowed route

Narrowed routeAssume a square-root deficit estimate survives any bounded number of forced missed births

With seeds 1 and 2 and forced omissions 4, 6, 4r+3, and 8r−2 for r≥2, the source gives N=8r and edited-sequence counts A_r(N)=2r+3, A_r(2N)=3r+6, and A_r(3N)=4r+7. Its deficit is 5A_r(N)−A_r(2N)−A_r(3N)=3r+2=3N/8+2. An estimate using the exact original greedy rule and saturation of every unique birth remains open; the omission family identifies a condition such a proof must use, without refuting the density conjecture.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Bound the entire future weighted positive deficit of the original sequence below a proved starting potential, or establish another sufficient all-scale loss estimate.Suggested move: Suggested next step: derive a compensation inequality for the three actual counting blocks and account for future accepted summands and rejected targets; identify exactly where original greedy saturation excludes forced-omission countermodels.

Ready to work on

Prove the parent-translation discrepancy inequality for every actual future accepted term, and pair any resulting positive lower-density theorem with an independent convergence argument.Suggested move: Suggested next step: express the compensation associated with the smaller integer summand of each genuine unique representation, then separate the lower-density conclusion from the additional criterion needed for a limit.

Ready to work on

Any phase or stationary comparison model must satisfy global saturation, including rejected targets, and control its discrepancy from the original Ulam sequence.Suggested move: Suggested next step: audit both accepted and rejected births in a proposed comparison model, then state a signed response bound that would transfer information to U(1,2) without assuming a fixed positive kernel.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Sep 7, 2026

Current statusOpen problem

For the original Ulam sequence starting with 1 and 2, existence and value of an asymptotic density remain unresolved in the cited literature. The workspace's stronger target requires that a natural-density limit exists and is positive; finite data do not establish either requirement.

[3][2]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2015-09-09
Computational resultAn OEIS comment by Philip Gibbs and Jud McCranie reports a(28000000000) = 378485625853. This is a finite term computation, not an asymptotic theorem.[1]

Mathematical neighborhood

Related results and reusable starting points

Current focusUlam-sequence density

Related problemUlam sequences with different initial seeds and higher-dimensional Ulam sets

The paper studies variants and structural regularity, including behavior for other seeds. Such results do not establish the original 1,2 sequence's positive natural-density limit.

[3]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

formal statement · partial resource linkedFormal Conjectures 342 sequence definition and related density question
The Lean file defines the original Ulam sequence and asks whether its upper density is zero, with sorry placeholders. It does not state or prove this workspace's positive natural-density target.
[4]
dataset · source linked; not reproduced by ProofAtlasOEIS original Ulam-sequence data
The entry supplies the original sequence definition, finite terms, and links to data and programs. No linked program or table was run or independently reproduced.
[1]

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

7 standing statements2 proposed statements3 open questions2 narrowed routes

Statements by mathematical role9 selected mapped statements

theorem candidate1 of 91
reduction5 of 95
lemma1 of 91
computational claim1 of 91
negative result1 of 91

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.25 displayed rows · 2 routes included

retained route statementA positive natural density for the original Ulam sequence U(1,2)
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementA convergent two-dilation potential implies densityintermediate
retained route statementA strict future loss budget would give positivityintermediate
retained route statementOne-sided square-root control is conditionalintermediate
retained route statementActual-parent control would give positive lower densityintermediate
retained route statementParent checks cover a finite original prefixintermediate
retained route statementA coded phase model does not supply the original densityintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureApply exact subadditivity to the original counting functionreported failure
Useful failureAssume a square-root deficit estimate survives any bounded number of forced missed birthsreported failure
Research targetBound the entire future weighted positive deficit of the original sequence below a proved starting potential, or establish another sufficient all-scale loss estimate.open
Research targetProve the parent-translation discrepancy inequality for every actual future accepted term, and pair any resulting positive lower-density theorem with an independent convergence argument.open
Research targetAny phase or stationary comparison model must satisfy global saturation, including rejected targets, and control its discrepancy from the original Ulam sequence.open
ComputationThe source reports a full phase-free check through 30 million and finite parent-discrepancy checks for all 2,219,563 nonseed accepted terms in that range.Every tested actual parent split in the stated finite range satisfies the proposed parent inequality. The observed range does not establish the universal parent premise, convergence of A(N)/N, or the future weighted-loss budget. · reported unreproduced
Narrowed routeApply exact subadditivity to the original counting functionThe source records x=604244 and y=732374 with A(x)=44678, A(y)=54134, and A(x+y)=98955. Thus A(x)+A(y)−A(x+y)=−143. A quantitative bound on positive three-block deficits remains a candidate route. It permits signed local discrepancies while requiring a summable future loss budget rather than exact subadditivity.
Narrowed routeAssume a square-root deficit estimate survives any bounded number of forced missed birthsWith seeds 1 and 2 and forced omissions 4, 6, 4r+3, and 8r−2 for r≥2, the source gives N=8r and edited-sequence counts A_r(N)=2r+3, A_r(2N)=3r+6, and A_r(3N)=4r+7. Its deficit is 5A_r(N)−A_r(2N)−A_r(3N)=3r+2=3N/8+2. An estimate using the exact original greedy rule and saturation of every unique birth remains open; the omission family identifies a condition such a proof must use, without refuting the density conjecture.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeBound the entire future weighted positive deficit of the original sequence below a proved starting potential, or establish another sufficient all-scale loss estimate.

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointBound the entire future weighted positive deficit of the original sequence below a proved starting potential, or establish another sufficient all-scale loss estimate.

Ulam-sequence density · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references4 cited works · next context review by Dec 7, 2026

The mathematical context was checked on Sep 7, 2026. Status can be refreshed sooner after a material result or claim.

1
A002858 — Ulam numberssoftware or dataset · The OEIS Foundation Inc. · OEIS A002858 · accessed Sep 7, 2026
2
Erdős Problem #342maintained problem list · accessed Sep 7, 2026
3
Ulam Sequences and Ulam Setspreprint · Noah Kravitz, Stefan Steinerberger · 2018-08-27 · ARXIV 1705.01883v3 · accessed Sep 7, 2026
4
Formal Conjectures — Erdős Problem 342formalization · Google DeepMind Formal Conjectures · accessed Sep 7, 2026

Important qualifications

The workspace title is packet-defined. The positive natural-density claim is not attributed to Ulam from the sequence's name or from a different zero-density question; proposer and year remain unknown.
The maintained Erdős problem-list entry was inspected through its indexed text. Its zero-density question is recorded as related reference context, not an exact-match recognition badge.
Finite numerical density estimates and results for different initial seeds do not establish a density limit for the original sequence seeded by 1 and 2.
The public Lean file concerns an open zero-upper-density question and contains placeholders. No build, proof audit, linked program, or computation was run. This private draft grants no mathematical acceptance, rights, authorship, contributor credit, or publication authority.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces