# Finding a sequence with RecurrenceTable

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

• 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. Commented Jan 27, 2019 at 6:28
• Do you have to use the command RecurrenceTable ?
– user59583
Commented Jan 27, 2019 at 8:57

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}


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

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"}}]