4
$\begingroup$

I'm trying to find Hofstadter's Q-Sequence.

I tried:

RSolve[{Q[n] == Q[n - Q[n - 1]] + Q[n - Q[n - 2]], Q[1] == 1, Q[2] == 1}, Q[n], n]

but it doesn't work.

Then I tried:

Q[1] := 1
Q[2] := 1
Q[n_] := Q[n - Q[n - 1]] + Q[n - Q[n - 2]]

Table[Q[n], {n, 15}]

{1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10}

but it works very slowly.

I want to plot first 200 terms of Q-Sequence but there is no answer...

ListPlot[Table[Q[n]/n, {n, 200}]]
$\endgroup$
1
  • $\begingroup$ Can anyone suggest a duplicate of this question to mark as the original? $\endgroup$
    – Mr.Wizard
    Jan 24, 2017 at 7:52

1 Answer 1

11
$\begingroup$

Proper memoization is the key:

Q[1] = 1;
Q[2] = 1;
Q[n_] := Q[n] = Q[n - Q[n - 1]] + Q[n - Q[n - 2]]

data = Table[Q[n]/n, {n, 10000}]; // AbsoluteTiming

{0.051379, Null}

ListPlot[data]

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.