How it works: weight × level + jump
Take a strictly increasing sequence of whole numbers — the primes, the squares, any sequence of the OEIS. Each term, together with the next one, is written as a product plus a jump:
a(n) = k(n) · L(n) + d(n)
k is the weight, L the level and d the jump. Every term that can be decomposed is decomposed in exactly one way, by three steps.
The three steps
- The jump. d = a(n+1) − a(n), the distance to the next term.
- What is left. l = a(n) − d. The term decomposes only if l > d, that is a(n) > 2d; otherwise the jump is too large and the term is skipped.
- Weight and level. The weight k is the smallest divisor of l that is larger than d, and the level is L = l / k. Then a(n) = k·L + d, and k > d: the weight always exceeds the jump.
Three primes, worked by hand
113
next prime 127, so d = 14
l = 113 − 14 = 99
divisors of 99: 1, 3, 9, 11, 33, 99
the smallest above 14 is k = 33, and L = 99 / 33 = 3
113 = 33 × 3 + 14 · level class, k > L
1009
next prime 1013, so d = 4
l = 1009 − 4 = 1005
divisors of 1005: 1, 3, 5, 15, 67, …
the smallest above 4 is k = 5, and L = 1005 / 5 = 201
1009 = 5 × 201 + 4 · weight class, k ≤ L
7
next prime 11, so d = 4
l = 7 − 4 = 3
3 is not larger than 4: no divisor of 3 can exceed the jump
7 does not decompose (7 ≤ 2 × 4)
A term is in the level class when k > L and in the weight class when k ≤ L; the ties k = L sit on the diagonal. For the primes the weight is never even, and a prime above 3 is the lesser of a twin pair exactly when its weight is 3.
A little theory
A Euclidean division
Since the weight exceeds the jump, 0 ≤ d < k, and a = k·L + d is exactly the Euclidean division of a by k: the level L is the quotient and the jump d is the remainder. So the weight can be read another way: k is the smallest number above d for which dividing a by k leaves the remainder d, the distance to the next term. For 113: dividing by 15, 16, …, 32 leaves other remainders; 113 = 33 × 3 + 14 is the first division by a number above 14 whose remainder is 14. It is the same condition as before, since a leaves the remainder d on division by k exactly when k divides a − d.
When a term decomposes
If a > 2d, then l = a − d > d, and l is itself a divisor of l larger than d: a weight always exists and is unique, with d < k ≤ l. If a ≤ 2d, then l ≤ d and no divisor of l can exceed d: the term does not decompose. In other words a term decomposes unless the next term is at least 1.5 times as large, which only fast-growing sequences do all the time: the powers of 2, or the Fibonacci numbers, whose ratio tends to 1.618.
Weight or level: the window (d, √l]
Because k·L = l, the weight class k ≤ L is the same as k ≤ √l. A term is therefore in the weight class exactly when l has a divisor in the window d < k ≤ √l, and in the level class when that window holds no divisor of l. Three consequences:
- Forced level. When l ≤ d², the window is empty whatever l is made of, and the term is in the level class without looking at its divisors. Sequences whose jumps grow faster than the square root of the terms (the squares of primes, many polynomials) are almost entirely forced level.
- The level line L = 1. L = 1 means k = l: no divisor of l lies strictly between d and l. This always happens when l is a prime larger than d.
- Ties. k = L means l = k²: the least divisor above d is exactly the square root of l.
The natural numbers and the sieve of Eratosthenes
For the natural numbers the jump is always d = 1, so the weight of a is the least divisor of a − 1 above 1: its smallest prime factor. That is what the sieve of Eratosthenes computes: it crosses out every composite number first with its smallest prime factor. The weight–level plate of the naturals is the sieve drawn in the plane: one column k = p for each prime p, holding the terms a for which p is the smallest prime factor of a − 1.
| a | l = a − 1 | k, smallest prime factor of l | L | k × L + d | class |
|---|---|---|---|---|---|
| 3 | 2 | 2 | 1 | 2 × 1 + 1 | level |
| 4 | 3 | 3 | 1 | 3 × 1 + 1 | level |
| 5 | 4 | 2 | 2 | 2 × 2 + 1 | weight, tie |
| 6 | 5 | 5 | 1 | 5 × 1 + 1 | level |
| 7 | 6 | 2 | 3 | 2 × 3 + 1 | weight |
| 8 | 7 | 7 | 1 | 7 × 1 + 1 | level |
| 9 | 8 | 2 | 4 | 2 × 4 + 1 | weight |
| 10 | 9 | 3 | 3 | 3 × 3 + 1 | weight, tie |
| 11 | 10 | 2 | 5 | 2 × 5 + 1 | weight |
| 12 | 11 | 11 | 1 | 11 × 1 + 1 | level |
| 13 | 12 | 2 | 6 | 2 × 6 + 1 | weight |
| 14 | 13 | 13 | 1 | 13 × 1 + 1 | level |
| 15 | 14 | 2 | 7 | 2 × 7 + 1 | weight |
| 16 | 15 | 3 | 5 | 3 × 5 + 1 | weight |
| 17 | 16 | 2 | 8 | 2 × 8 + 1 | weight |
The window (1, √l] contains a divisor of l exactly when l is composite, so the level class of the naturals is the set of terms with a − 1 prime, all on the line L = 1: 9,592 of the first 10⁵ terms, one per prime below 10⁵. The ties are the squares of primes, a − 1 = p² (65 of them). For any other sequence the jump plays the role of a starting point: the divisors up to d are skipped, as if the sieve began at d + 1.
Try it
Type or paste increasing terms, or start from a sequence below. The table and the plate follow as you type.
| n | a(n) | d | l = a − d | k | L | k × L + d | class |
|---|
Fibonacci is a sequence where nothing decomposes: each term is less than twice the jump to the next.
Reading the site
- The plates of the gallery put every decomposable term at (log k, log L), scaled by the largest term: blue for the weight class, orange for the level class. The dashed diagonal is k = L, the edge k·L = a is where the jump is small against the term.
- The 3-D viewer adds the jump d as a third axis. Its flat views are the plate (k–L), and the jump against the weight (k–d) or the level (L–d); the level line L = 1 holds the terms whose l is itself the weight.
- Each sequence page gives the counts, a note on its shape, and a CSV of all 10⁵ terms with their weight, level and jump. Good places to start: the primes, the natural numbers (d = 1: the weight is the least divisor of a − 1 above 1), the squares.
The decomposition is described in arXiv:0711.0865 and on decompwlj.com.