1
$\begingroup$

I would appreciate if somebody could help me with the following problem:

Q: How can the following recursion equations be solved using RecurrenceTable?

$\qquad a_{2n}=2\,a_n-1,\, a_{2\,n+1}=2\,a_n+1,\, a_{1}=1$ 

RecurrenceTable[{a[2 n] == 2 a[n] - 1 , a[2 n + 1] == 2 a[n] + 1, a[1] == 1}, a, {n, 1, 15, 1}]

But...

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ You should attempt to explain your issue if possible, rather than leave people to guess what the "But.." refers to. In the documentation for RecurrenceTable it says that the equations must be in the form of a[n + i] where i is any fixed integer. Based on that, I would guess that your problem cannot be defined using RecurrenceTable. Idk if this helps, but you could define the relation like this: a[1] = 1; a[n_] := If[EvenQ[n], 2 a[n/2] - 1, 2 a[(n - 1)/2] + 1] and that will at least get you the values for each n value. $\endgroup$
    – MassDefect
    Commented Jan 27, 2019 at 6:28
  • $\begingroup$ Do you have to use the command RecurrenceTable ? $\endgroup$
    – user59583
    Commented Jan 27, 2019 at 8:57

3 Answers 3

Reset to default
2
$\begingroup$

I don't think the built-in function RecurrenceTable can handle the kind of recurrence you present in this question. However, the problem is amenable to the approach I discussed in your previous question.

First, observe that the recurrence relation is really a matter of odd and even numbrs; i.e., it is defined one way for odd numbers and only slightly differently for even ones.

Second, write a recursive function based on this observation. Like so:

Clear[a]
a[1] = 1;
a[n_?EvenQ] := 2 a[n/2] - 1
a[n_?OddQ] := 2 a[Floor[n/2]] + 1

Now, it is possible to generate a sequence to any specified length, say 63. 

Table[a[i], {i, 63}]

{1, 
 1, 3, 
 1, 3, 5, 7, 
 1, 3, 5, 7, 9, 11, 13, 15, 
 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 
 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 
    33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63}
Improve this answer
$\endgroup$
2
$\begingroup$

From the analysis presented above it's not that hard to show that the general solution is

a[n_] := 2*n - 2^(Floor[Log[2, n]] + 1) + 1

But, if you are after the generating function for a[n], then you should look up the generated coefficients on the OEIS to find that this is the Josephus problem (A006257).

Improve this answer
$\endgroup$
0
$\begingroup$

As has been observed this is the solution of the Josephus problem (2 step)

Here are the implementations of provided solutions and also one that shows cyclic shift of binary representation of number. Note the b and the f easily demonstrate that 1 (position 1 in the Josephus problem) is always the result for $n=2^j$ for $j$ natural number.

a[1] = 1;
a[n_?EvenQ] := 2  a[n/2] - 1
a[n_?OddQ] := 2  a[Floor[n/2]] + 1
b[n_] := 2  n - 2^(Floor[Log[2, n]] + 1) + 1
f[n_] := 
 With[{a = RotateLeft[IntegerDigits[n, 2]]}, 
  a . PowerRange[2^(Length[a] - 1), 1, 1/2]]
TableForm[Table[{a[j], b[j], f[j]}, {j, 20}], 
 TableHeadings -> {Range[20], {"a", "b", "f"}}]
TableForm[Table[AbsoluteTiming[j[10000]], {j, {a, b, f}}], 
 TableHeadings -> {{"a", "b", "f"}, {"Timing", "Result"}}]

enter image description here

Improve this answer
$\endgroup$

Your Answer

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

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