"""Erdős #85 from the known values of R(C4, K_{1,s}) (OEIS A006672, s = 1..38; R(C4, K_{1,0}) = 1).

f(n) = n - g(n), where g(n) is the largest s with R(C4, K_{1,s}) <= n. Checks:
  * f(n+1) >= f(n) for every n where f is determined (4 <= n <= 44),
  * the plateaus R(s+1) = R(s) and the dips f(n+1) < f(n) correspond as proved in the paper,
  * where f(n) < sqrt(n) + 1 fails.
"""
import math

R = [1, 4, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27, 28, 29, 30,
     31, 32, 33, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45]   # R[s] for s = 0..38
S = len(R) - 1

def g(n):
    best = max(s for s in range(S + 1) if R[s] <= n)
    return best if best < S else None          # maximality needs R(best + 1) known

f = {n: n - g(n) for n in range(4, R[S]) if g(n) is not None}
print('f(n) for n =', min(f), '..', max(f), ':', ' '.join(str(f[n]) for n in sorted(f)))
dips = [n for n in sorted(f) if n + 1 in f and f[n + 1] < f[n]]
plateaus = [s for s in range(S) if R[s + 1] == R[s]]
print('dips f(n+1) < f(n):', dips or 'none')
print('plateaus R(s+1) = R(s):', [(s, R[s]) for s in plateaus],
      '-> predicted dips at n = R - 1:', [R[s] - 1 for s in plateaus], '(only n >= 4 is in range)')
print('f(n) >= sqrt(n) + 1 at:', [(n, f[n], round(math.sqrt(n) + 1, 3)) for n in sorted(f) if f[n] >= math.sqrt(n) + 1])
print('f(n) <= sqrt(n) + 1 everywhere:', all(f[n] <= math.sqrt(n) + 1 + 1e-12 for n in f))