f(n)=max{f(j)+f(n−j)+j}
Let f be a function from the set of positive integers to the set of non-negative integers such that f(1)=0 and f(n) is defined as of above for n≥2. Determine the value of f(2020).
Note: The maximum in the definition of f(n) is considered over all j such that 1≤j≤n−1, i.e for all j for which f(n) and f(n−j) are defined.
The program at bottom calculated the values in the teble below. Before modification with the theories as to the direct formula, it produced only the first two columns n and f(n) from the definition. The quadratic was added later. The first row was manually inserted.
The finite differences f(n) - f(n-1) are all equal to n-1.
In the range where the quadratic is valid, it's f(n) = (n^2-n)/2.
n f(n) (n^2-n)/2
1 0 0
2 1 1
3 3 3
4 6 6
5 10 10
6 15 15
7 21 21
8 28 28
9 36 36
10 45 45
f(2020) = 2039190 (computed from definition)
(2020^2 - 2020)/2 = 2039190 (valid quadratic, verified)
Dim f(2022)
f(1) = 0
For n = 2 To 2020
mx = 0
For j = 1 To n - 1
If f(j) + f(n - j) + j > mx Then mx = f(j) + f(n - j) + j
DoEvents
Next
f(n) = mx
If n <= 10 Then Text1.Text = Text1.Text & n & Str(f(n)) & " " _
& (n * n - n) / 2 & vbCrLf
Next
Text1.Text = Text1.Text & vbCrLf & vbCrLf & f(2020) & vbCrLf
n = 2020
Text1.Text = Text1.Text & (n * n - n) / 2 & vbCrLf
|
|
Posted by Charlie
on 2020-09-03 12:11:10 |
computer solution and a fitted polynomial
