typestar

collatz_record.wat in WebAssembly

Race every Collatz chain below 100 and return the record start: 97.

;; Collatz: which start below 100 takes the most steps to reach 1?
(module
  ;; Halve if even; 3n+1 if odd; count until the chain hits 1.
  (func $steps (export "chain_length") (param $n i32) (result i32)
    (local $count i32)
    (block $done
      (loop $next
        (br_if $done (i32.eq (local.get $n) (i32.const 1)))
        (if (i32.and (local.get $n) (i32.const 1))
          (then
            (local.set $n
              (i32.add (i32.mul (local.get $n) (i32.const 3))
                       (i32.const 1))))
          (else
            (local.set $n
              (i32.div_s (local.get $n) (i32.const 2)))))
        (local.set $count (i32.add (local.get $count) (i32.const 1)))
        (br $next)))
    (local.get $count))

  ;; Race every start below the limit and remember the record holder.
  (func $longest (export "longest_start") (param $limit i32)
        (result i32)
    (local $n i32)
    (local $best_n i32)
    (local $best i32)
    (local $s i32)
    (local.set $n (i32.const 1))
    (block $done
      (loop $scan
        (br_if $done (i32.ge_s (local.get $n) (local.get $limit)))
        (local.set $s (call $steps (local.get $n)))
        (if (i32.gt_s (local.get $s) (local.get $best))
          (then
            (local.set $best (local.get $s))
            (local.set $best_n (local.get $n))))
        (local.set $n (i32.add (local.get $n) (i32.const 1)))
        (br $scan)))
    (local.get $best_n))

  ;; 97 holds the under-100 record at 118 steps.
  (func (export "main") (result i32)
    (call $longest (i32.const 100))))

How it works

  1. $steps halves or 3n+1s until the chain reaches 1, counting.
  2. i32.and with 1 is the parity test choosing the branch.
  3. $longest tries each start and remembers the best; 97 takes 118 steps.

Keywords and builtins used here

The run, in numbers

Lines
43
Characters to type
1278
Tokens
293
Three-star pace
60 tpm

At the three-star pace of 60 tokens a minute, this run takes about 293 seconds.

Type this snippet

Step 2 of 3 in Encore, step 27 of 28 in Language basics.

← Previous Next →