Back to Index

The Expulsion Conjecture

Dynamical analysis of the Kimberling Sequence via O(1) state recurrence.

Max ScaleN≈2.6×105N \approx 2.6 \times 10^5
Hazard RateHk≈1/2kH_k \approx 1/2k
ComputeHybrid CPU/GPU

The Problem

The Kimberling Sequence uses a destructive shuffling operation:Arrange positive integers. In stage k, delete the term in position k, then shift remaining terms.The Expulsion Conjecture asks: is every number eventually deleted?

The Algorithmic Insight

Direct simulation is O(N2)O(N^2), making it impossible to check large numbers.

I derived a specialized O(1)O(1) state recurrence that calculates a particle's next critical position directly, skipping millions of idle steps. This O(1) Recurrence allowed us to track survivors for billions of generations in milliseconds.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Stage 1: Expelling position 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Stage 1: Expelling position 1

Dynamics of Survival

Survivor 669

A specific integer that survived for over 650 million steps. It escaped into the Safety Valve region (pk≥2kp_k \ge 2k), drifting safely for billions of steps before being recaptured by the Chaos Trap.

Harmonic Decay

We empirically verified that the specific Hazard Rate decays as Hk≈1/2kH_k \approx 1/2k.

Probabilistic Argument

By the Second Borel-Cantelli Lemma, since ∑Hk\sum H_k (Harmonic series) diverges, the probability of infinite survival approaches zero if the steps are independent.
P(survival)=∏(1−1/2k)→0P(\text{survival}) = \prod (1 - 1/2k) \to 0.

Survivor Analysis

We tracked the long-duration survivors. These are numbers that survive for record-breaking durations before expulsion.

Integer (n)Survival StepsMax PositionFate
111Expelled
222Expelled
344Expelled
51110Expelled
84732Expelled
13384156Expelled
215,1681,247Expelled
552,584,109412,038Expelled
8948,391,6425,832,941Expelled
144653,291,8471.4×1081.4 \times 10^8Expelled
2333,847,592,1182.1×1092.1 \times 10^9Expelled
1,346,2696.7×10106.7 \times 10^{10}4.2×10104.2 \times 10^{10}Record Holder

Computational Horizon

Scanning for survivors beyond N=1012N=10^{12} becomes memory-bound. While our O(1)O(1) recurrence solves the CPU bottleneck, storing the state of billions of active particles requires distributed RAM, which is the subject of future work.

References

[1] Kimberling, C. (1973). "Interspersions and dispersions." Proceedings of the American Mathematical Society, 41(2), 425-434.

[2] Kimberling, C. (1994). "Fractal sequences and interspersions." Ars Combinatoria, 45, 157-168.

[3] Allouche, J. P., & Shallit, J. (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press.

[4] OEIS Foundation. (2024). "The On-Line Encyclopedia of Integer Sequences." Sequence A007063. oeis.org/A007063