All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
A peculiar function! (Posted on 2020-09-03) Difficulty: 4 of 5
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.

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution. | Comment 1 of 5
f(2020) = 2039190
f(n) = n*(n-1)/2

I made  a little recursive program in Python which worked fine but started to choke at about n=18 due to all the recursion calls.

So I added a dictionary to store values for f(n) as the became known.  Much faster..

my_dictionary = {1:0}
def f(n):
    if n == 1:
        return 0
    else:
        if n in my_dictionary:
            return my_dictionary[n]
        else:
            my_max = 0
            for j in range(1,n):   # this will go from 1 to n-1
                test = f(j)+f(n-j)+j
                my_max = max(my_max,test)
            my_dictionary[n] = my_max
            return my_max

Edited on September 3, 2020, 8:47 am
  Posted by Larry on 2020-09-03 08:41:56

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (2)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information