3
$\begingroup$

Following is the recurrence relation:

a[1] = 1;
a[n_] := a[n - a[n - 1]] + 1
Array[a, 28]

I tried to use RSolve, but it doesn't gives a correct answer.

Clear[a]
RSolve[{a[n] == a[n - a[n - 1]] + 1}, a[n], a]
$\endgroup$
5
$\begingroup$

First, I believe your RSolve syntax is incorrect. I think you want n as the last argument, and you should also have the a[1] == 1 rule:

RSolve[{a[n] == a[n - a[n - 1]] + 1, a[1] == 1}, a[n], n]

This gives a more informative (error?) message:

RSolve::nestdv: The expression a[-1+n] has nested dependent variables. >>

Apparently RSolve doesn't like that.

Second, your recursive function is very inefficient because it lacks memoization. Adding that will make it more practical:

a[1] = 1;
a[n_] := a[n] = a[n - a[n - 1]] + 1

Array[a, 500000] // Timing // First
1.529

Finally, we can work out a function for the nth term manually. Observe that in your sequence each number n repeats n times:

1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ...

The jump points are therefore triangular numbers:

# (# + 1)/2 & ~Array~ 5
{1, 3, 6, 10, 15}

We can invert this equation with Solve:

Solve[n (n + 1)/2 == x, n]
{{n -> 1/2 (-1 - Sqrt[1 + 8 x])}, {n -> 1/2 (-1 + Sqrt[1 + 8 x])}}

Then pick the correct branch and add Ceiling:

fn[x_] := Ceiling[ (Sqrt[1 + 8 x] - 1)/2 ]

Now:

fn ~Array~ 15
{1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5}
$\endgroup$
  • 3
    $\begingroup$ Warning : in Mathematica 8 and later Solve[1/2 n (1 + n) == k, n, Integers] yields the result in terms of ConditionalExpression. You should rather use simply Solve[1/2 n (1 + n) == k, n]. +1. $\endgroup$ – Artes Jan 31 '13 at 13:15
  • $\begingroup$ @Artes Thanks for the correction. $\endgroup$ – Mr.Wizard Jan 31 '13 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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