WeChall - Van Eck

Posted on Edited on Views: Disqus:

Challenge

In this programming challenge you have to find the x in van_eck(x), where a resulting value of 133731337 occurs the first time.

Van Eck 序列定义：

  • a(0) = 0
  • 对 n >= 1，若 a(n-1) 之前最后一次出现在位置 m，则 a(n) = n-1-m
  • 若之前没出现过，则 a(n) = 0

前几项：

1
0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, ...

目标是找到值 133731337 首次出现的 index。

Solution Attempt

朴素算法必须维护 value -> last_position：

1
2
3
4
5
6
7
8
9
10
11
TARGET = 133731337
last_pos = {}
prev = 0

for n in range(1, MAX):
    curr = n - 1 - last_pos[prev] if prev in last_pos else 0
    last_pos[prev] = n - 1
    if curr == TARGET:
        print(n)
        break
    prev = curr

这个算法逻辑正确，但资源需求很高。

实测记录：

  • Python 跑到 1.5B step，约 740s，即约 2M steps/s，不是早期草稿误写的 40M steps/s。
  • dict 中已有约 150M 个 unique value，最大值约 281M，仍未找到目标。
  • C 版 open-addressing hash table 如果负载太高会 probe 过长；限制 probe 又会破坏序列正确性。
  • 2^30 slot 即使每 slot 只 16B 也约 16GiB，2^31 约 32GiB；实际还要留余量，建议 64GB+ RAM。

Current Status

这题不是“不会做”，而是当前机器资源不划算。朴素路线已验证可行，但要继续需要：

  • 64GB+ 内存机器；或
  • 更紧凑的专用 hash table / 分块算法；或
  • 找到数学性质优化首次出现搜索。

当前 32GB 级别环境容易 swap thrashing。建议暂时 skip 实际求解，仅保留算法和资源门槛。