Add files using upload-large-folder tool

1fd0050 verified 6 months ago

5.11 kB

#!/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.")

	#!/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.")