TAOCP 7.1.3 Exercise 141

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 141. ▶ [30] [30] The Ulam numbers ⟨U1, U2, . . . ⟩= ⟨1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, . . . ⟩are defined for n ≥3 by letting Un be the smallest integer > Un−1 that has a unique representation Un = Uj + Uk for 0 < j < k < n. Show that a million Ulam numbers can be computed rapidly with the help of bitwise techniques.

Verified: yes
Solve time: 4m34s

We restart the construction from a correct state model of representation counts and derive valid bit-parallel update rules.

1. Representation model

Let $A[x]$ be the bitset of already selected Ulam numbers:

$$ A[x] = [x \in {U_1,\dots,U_n}]. $$

For each integer $x$, let $c_n(x)$ be the number of representations

$$ x = U_i + U_j,\quad i < j \le n. $$

We truncate counts at 2 and maintain three bitsets:

$Z[x]$: $c_n(x)=0$
$O[x]$: $c_n(x)=1$
$T[x]$: $c_n(x)\ge 2$

with invariant

$$ Z ,\dot\cup, O ,\dot\cup, T = \mathbb{Z}_{\ge 0}. $$

Initially $A={1,2}$, $O=0$, $T=0$, and $Z$ is the complement.

2. Key observation: correct incremental update

When a new Ulam number $u=U_{n+1}$ is chosen, every new representation involving $u$ has the form

$$ x = u + a,\quad a \in A,\ a < u. $$

Define the shifted bitset

$$ S = A \ll u,\quad S[x]=A[x-u]. $$

This is correct because every unordered pair $(a,u)$ is introduced exactly once, when $u$ is inserted as the larger endpoint.

Thus, for each $x$, the update is:

if $S[x]=0$: no change
if $S[x]=1$: increment $c(x)$ by 1

So the problem reduces to correctly updating a 3-state counter ${0,1,\ge2}$ under a binary increment mask $S$.

3. Correct state transition

We derive the transitions directly from arithmetic.

3.1 Update of $T$

A value enters $T$ if:

it was already in $T$, or
it was in $O$ and receives a new increment

Thus:

$$ T' = T ;\lor; (O \wedge S). $$

This is exact: only a 1-count becoming 2+ creates a new $T$.

3.2 Update of $O$

We characterize all cases:

$x \in O$ and $S=0$: stays in $O$
$x \in O$ and $S=1$: moves to $T$
$x \in Z$ and $S=1$: moves to $O$
$x \in T$: never returns to $O$

Hence:

$$ O' = (O \wedge \neg S \wedge \neg T') ;\lor; (S \wedge \neg O \wedge \neg T). $$

The first term keeps exact-ones not hit by $S$ and not absorbed into $T'$.

The second term creates new exact-ones from zeros.

3.3 $Z$ is implicit

We never need to store it:

$$ Z = \neg(O \lor T). $$

4. Selection rule

The next Ulam number is

$$ U_{n+1} = \min {x > U_n : O[x] = 1}. $$

This is found by scanning machine words of $O$.

After selection, we set:

$$ A[U_{n+1}] = 1. $$

5. Why the update is correct

Fix an integer $x$. Consider all unordered pairs $(a,b)$ with $a<b$.

Each pair contributes to exactly one update step: when $b$ is inserted, the pair $(a,b)$ contributes once to $S$ at position $x=a+b$.

Therefore:

every pair is counted exactly once,
$c(x)$ is incremented exactly once per representation,
truncation at 2 is correctly handled by the $O \to T$ transition.

Thus the three-state machine exactly matches the definition of Ulam numbers.

6. Bit-parallel implementation

All operations are word-wise on bitsets:

shift: $A \ll u$
AND, OR, NOT on machine words

Each update costs $O(M/w)$, where $M$ is the bitset size and $w$ the machine word length.

Each iteration performs:

one shift
$O(1)$ bitwise passes over bitsets

so total cost per Ulam number is $O(M/w)$.

7. Complexity

For $N$ Ulam numbers up to a bound $M$:

$$ O!\left(\frac{NM}{w}\right). $$

No quadratic recomputation occurs, because each ordered pair $(a,b)$ is processed exactly once via the shift at insertion of $b$.

8. Conclusion

The correct method is not based on XOR heuristics but on an explicit truncated counting automaton with states $0,1,\ge2$. The shifted bitset $S = A \ll u$ cleanly encodes all new representations, and the derived transition rules preserve the exact representation counts needed to identify Ulam numbers.

This yields a fully correct bit-parallel algorithm capable of computing $10^6$ Ulam numbers efficiently.