GreedyAlgorithm : Prop ≡
∀n ∈ ℤ⁺ . GreedyDecomposition(n) is valid φ-representation
where
GreedyDecomposition(n) ≡
if n = 0 then ∅
else let k = max{i : F(i) ≤ n} in
{k} ∪ GreedyDecomposition(n - F(k))
Proof of existence:
By strong induction on n.
Base: n = 1, use I = {1}, since F(1) = 1
Inductive step: Assume true for all m < n.
Let k = max{i : F(i) ≤ n}
Case 1: n = F(k)
Then I = {k} works
Case 2: n > F(k)
Let r = n - F(k) < n
By IH, r has φ-representation J
Claim: k ∉ J and k-1 ∉ J
Proof: If k-1 ∈ J, then F(k-1) ≤ r = n - F(k)
So F(k) + F(k-1) ≤ n
But F(k) + F(k-1) = F(k+1) ≤ n
Contradicts maximality of k
Therefore I = {k} ∪ J is valid ∎
Proof by contradiction:
Assume I ≠ J with decode(I) = decode(J) = n
Let k = max(I △ J) (symmetric difference)
WLOG assume k ∈ I, k ∉ J
Key observation: ∀i > k . i ∈ I ↔ i ∈ J
Consider partial sums:
S_I = ∑_{i∈I, i≤k} F(i) = F(k) + ∑_{i∈I, i<k} F(i)
S_J = ∑_{j∈J, j≤k} F(j)
Since total sums equal: S_I = S_J
Claim: This is impossible
Proof:
- If k-1 ∈ J: violates non-consecutive with some j > k
- If k-1 ∉ J: Then S_J < F(k) ≤ S_I
Contradiction in both cases ∎
Proof of bijection:
1. Well-defined: Clear from definition
2. Injective:
If φ(b) = φ(b'), then same φ-representation
By uniqueness, same index sets
Therefore b = b'
3. Surjective:
By existence, every n has φ-representation I
Define b where bᵢ = 1 iff i ∈ I
Then φ(b) = n ∎
Proof of length bound:
Let k = max{i : i ∈ φ-repr(n)}
By greedy property: F(k) ≤ n < F(k+1)
Using Binet formula:
F(k) ≈ φᵏ/√5
Therefore:
φᵏ/√5 ≲ n ≲ φᵏ⁺¹/√5
Taking logarithms:
k ≈ log_φ(n√5) = log_φ(n) + O(1) ∎
def verify_existence(max_n):
for n in range(1, max_n):
repr = greedy_decomposition(n)
# 验证和
if sum(fib[i] for i in repr) != n:
return False, n, "sum mismatch"
# 验证非连续性
sorted_repr = sorted(repr)
for i in range(len(sorted_repr)-1):
if sorted_repr[i+1] - sorted_repr[i] < 2:
return False, n, "consecutive indices"
return True, None, None
def greedy_decomposition(n):
"""贪心算法计算φ-表示"""
result = []
fib = generate_fibonacci(n)
i = len(fib) - 1
while n > 0 and i >= 1:
if fib[i] <= n:
result.append(i)
n -= fib[i]
i -= 2 # 跳过相邻
else:
i -= 1
return result
def phi_encode(binary_string):
"""从二进制串计算对应整数"""
total = 0
for i, bit in enumerate(binary_string, 1):
if bit == '1':
total += fib[i]
return total