Hofstadter Function

For finished programs
Post Reply
piquadratpi2
Posts: 8
Joined: Thu Mar 12, 2020 6:19 pm

Hofstadter Function

Post by piquadratpi2 » Wed Jul 15, 2020 5:11 pm

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

User avatar
kibernetik
Site Admin
Posts: 147
Joined: Tue Aug 06, 2019 3:03 pm

Re: Hofstadter Function

Post by kibernetik » Sun Jul 19, 2020 4:11 am

Why argument cannot be greater than 41?
Do you get any errors when running with argument > 41?

piquadratpi2
Posts: 8
Joined: Thu Mar 12, 2020 6:19 pm

Re: Hofstadter Function

Post by piquadratpi2 » Sun Jul 19, 2020 3:50 pm

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...

Post Reply