# Python program for OEIS A161531
# Michael S. Branicky, Jan 30 2023

# A161531 The number of reachable states in a simple two-player counting game, in which each player starts with the pair (1,1) and one move is to add one of the opponent's numbers to one of your own numbers, but no number can grow above a pre-defined maximum n. The game continues until one of the players has no legal moves left. The winner is the one having the higher sum of his numbers.		0
data = [1, 4, 13, 34, 75, 152, 301, 482, 794, 1197, 1842, 2522, 3582, 4772, 6408, 8229, 10728, 13285, 16851, 20569, 25361, 30380, 36927, 43251, 51692, 60199, 70668, 81452, 95083, 107664, 124360, 140539, 160222, 179821, 204026, 226607, 255551, 283320]

# FASTER VERSION for computing first segment of sequence a(1)..a(n)
# bc reach(n-1) = reach(n) - {states in reach(n) with max count == n}

# (Python)
import heapq
from itertools import islice
def agen(N=float('inf'), discard=False): # generator of terms up to N
    reach, pq = {((1, 1), (1, 1))}, [(1, (1, 1), (1, 1))]
    reached, prevd = 0, 1
    while len(pq) > 0:
        d, qa, qb = heapq.heappop(pq)  # first tuple, qa, is player-to-move
        if d > prevd:
            prevd = d
            yield reached
            if discard:
                reach = {(qa, qb) for qa, qb in reach if max(max(qa), max(qb)) >= prevd}
            if d == N+1:
                return
        reached += 1
        for i, j in [(0, 0), (0, 1), (1, 0), (1, 1)]:
            if qa[i] + qb[j] <= N+1:
                qan = tuple(sorted((qa[i] + qb[j], qa[1-i])))
                qn = (qb, qan)
                if qn not in reach:
                    heapq.heappush(pq, (max(max(qan), max(qb)), qb, qan))
                    reach.add(qn)

# ALTERNATE WAYS OF GENERATING DATA (each in seconds)
print(list(islice(agen(), 40))) # ~~~~
print(list(agen(40, discard=True))) # ~~~~
print(list(agen(40))) # ~~~~

print(data)
print()

from time import time
time0 = time()

N = 100

# generates N = 100 terms in ~4.5 mins in Google Colab
# ~7 mins if discard = True
g = agen(N)
for n in range(1, N+1):
    an = next(g)
    print(n, an, time()-time0)
    with open('bA161531.txt', 'a') as bfile:
        bfile.write(f"{n} {an}\n")