docker_space/frontier_cs_8/math_analysis.py

#!/usr/bin/env python3
"""
Analyze the chain step count formula mathematically.

computeT(d, gy):
  Sv[0] = 0
  for j in 0..d-1:
    c[j] = (Sv[j] - Sv[gy[j]] + (j - gy[j]) + 1) mod P
    Sv[j+1] = (Sv[j] + c[j]) mod P
  T = (Sv[d] + d + 1) mod P

Where gy[j] in {0, ..., j} for each j.

For the standard chain (all gy[j]=0):
  c[j] = Sv[j] + j + 1
  Sv[j+1] = 2*Sv[j] + j + 1

Let's compute Sv[j] for gy[j]=0:
  Sv[0] = 0
  Sv[1] = 0 + 1 = 1
  Sv[2] = 2 + 2 = 4
  Sv[3] = 8 + 3 = 11
  Sv[j] = 2^(j+1) - j - 2

  T = 2^(d+1) - d - 2 + d + 1 = 2^(d+1) - 1

Now let's think about what happens when we change ONE gy value.
Say gy[k] = g instead of 0. Then:
  For j < k: everything is the same.
  At j = k: c[k] = Sv[k] - Sv[g] + (k - g) + 1 instead of Sv[k] + k + 1
  Difference: delta_c[k] = -(Sv[g] + g)

Wait, let me be more precise.
With gy[k]=g: c[k] = Sv[k] - Sv[g] + k - g + 1
With gy[k]=0: c[k] = Sv[k] - Sv[0] + k - 0 + 1 = Sv[k] + k + 1
Difference: c[k]_new - c[k]_old = -Sv[g] - g

For the standard chain (all gy[j]=0 for j != k):
  Sv[g] = 2^(g+1) - g - 2
  So delta = -(2^(g+1) - g - 2) - g = -2^(g+1) + 2

But this only works if all OTHER gy values are 0. In general it's more complex.

Let me think about the formula differently.
Define T(d, gy[]) mod P.

For d=27, we need T = 150994941 or 150994939.
Standard T(27, all zeros) = 2^28 - 1 = 268435455.

Can we reduce T by choosing some gy[j] != 0?
From the analysis above, setting gy[k]=g reduces T by roughly 2^(g+1) - 2 at level k,
but this also propagates to levels k+1, k+2, etc. (since Sv changes).

Actually the formula is more subtle. Let me think recursively.

T(d) = Sv[d] + d + 1
Sv[d] = sum of c[j] for j=0..d-1
c[j] = Sv[j] - Sv[gy[j]] + j - gy[j] + 1

This is a recurrence where each c[j] depends on all previous Sv values.

Key insight: c[j] represents the cost of "resolving the push at level j".
When gy[j] = g, the pushed char starts at level g and traverses to level j.
The cost of this traversal is: sum of c[i] for i = g..j-1, plus j-g contributions of 1.
Actually: c[j] = Sv[j] - Sv[g] + j - g + 1 = (sum of c[i] for i=g..j-1) + (j-g) + 1

Wait, Sv[j] - Sv[g] = sum of c[i] for i=g..j-1.
So c[j] = (sum c[i], i=g..j-1) + (j-g) + 1 = (sum c[i], i=g..j-1) + (j-g+1)

The (j-g+1) is the number of instructions traversed (including the push itself).
And sum c[i] for i=g..j-1 is the cost of all the sub-pushes encountered while traversing.

So the total T is like a tree of sub-pushes.
"""

P = 998244353

def computeT(d, gy):
    Sv = [0] * (d + 1)
    for j in range(d):
        c = (Sv[j] - Sv[gy[j]] + (j - gy[j]) + 1) % P
        Sv[j + 1] = (Sv[j] + c) % P
    return (Sv[d] + d + 1) % P

# For d=27, find what T values are achievable
d = 27
target1 = 150994941
target2 = 150994939

# Standard chain
T_all_zero = computeT(d, [0]*d)
print(f"d={d}, T(all zeros) = {T_all_zero}")
print(f"Target 1: {target1}, diff = {T_all_zero - target1}")
print(f"Target 2: {target2}, diff = {T_all_zero - target2}")

# The diff is what we need to subtract.
diff1 = (T_all_zero - target1) % P
diff2 = (T_all_zero - target2) % P
print(f"Need to reduce by {diff1} for target1")
print(f"Need to reduce by {diff2} for target2")

# Let's compute what happens when we set gy[j] = g for one j.
# With all other gy = 0.
print("\nEffect of single gy[j]=g changes:")
for j in range(d):
    for g in range(1, j+1):  # g=0 is baseline
        gy = [0]*d
        gy[j] = g
        T = computeT(d, gy)
        reduction = (T_all_zero - T) % P
        if reduction == diff1:
            print(f"  *** MATCH TARGET1: gy[{j}]={g}, T={T}, reduction={reduction}")
        if reduction == diff2:
            print(f"  *** MATCH TARGET2: gy[{j}]={g}, T={T}, reduction={reduction}")

print("\nSearching two-change combinations...")
# Two changes: gy[j1]=g1, gy[j2]=g2
# This is O(d^4) ≈ 27^4 ≈ 500K, feasible
import itertools

# First, compute reduction for each single change
single_reductions = {}
for j in range(d):
    for g in range(1, j+1):
        gy = [0]*d
        gy[j] = g
        T = computeT(d, gy)
        single_reductions[(j, g)] = T

# The problem: changes are NOT independent. Setting gy[j1] and gy[j2] together
# gives a different result than the sum of individual reductions.
# So we can't just combine single changes.

# But we can try all pairs.
found = False
for j1 in range(d):
    for g1 in range(1, j1+1):
        for j2 in range(j1+1, d):
            for g2 in range(1, j2+1):
                gy = [0]*d
                gy[j1] = g1
                gy[j2] = g2
                T = computeT(d, gy)
                if T == target1:
                    print(f"FOUND TARGET1: gy[{j1}]={g1}, gy[{j2}]={g2}, T={T}")
                    found = True
                    break
                if T == target2:
                    print(f"FOUND TARGET2: gy[{j1}]={g1}, gy[{j2}]={g2}, T={T}")
                    found = True
                    break
            if found: break
        if found: break
    if found: break

if not found:
    print("No two-change solution found. This confirms the current solution likely uses more changes.")