I tried to caculate some values of the very recursive Hofstadter function H. It only runs if the argument isn't larger than 41. Is there a way to make this faster and evaluate H(n) for n>41? Any help would be great. Many thanks in advance.
Here is the program:
INPUT n
DEF H(n) 'Hofstadter function
IF (n <= 2) THEN RETURN 1
RETURN H(n  H(n  1)) + H(n  H(n  2))
END DEF
print("Hofstadter function")
print("")
print
for i=1 to n
print(i,"H(";i;") = ",H(i))
next i
Hofstadter Function
 kibernetik
 Site Admin
 Posts: 147
 Joined: Tue Aug 06, 2019 3:03 pm
Re: Hofstadter Function
Why argument cannot be greater than 41?
Do you get any errors when running with argument > 41?
Do you get any errors when running with argument > 41?

 Posts: 8
 Joined: Thu Mar 12, 2020 6:19 pm
Re: Hofstadter Function
Today I tested it again on an iMac and a new Mac mini and it works even if I put in 42 for n. But it lasts very very long. Maybe I had some other apps running in background when I got the error last time with n=42. H(41)=23, H(42)=23, H(43)=24, H(44)=24...