0
$\begingroup$
f[2 x_] := f[x]
f[1] := 3
f[0] := 0
f[2 x_ + 1] := f[x] + f[x + 1]
a[x_] := f[x]/f[x + 1]

Will this work as an recursive function ? I think there's something wrong with this because every integer will get an output of 3

any help would be appreciated, thank you so much

$\endgroup$
2
  • $\begingroup$ From what I'm guessing you're trying to get, I think you'll find fn = NestList[1/(1 - # + 2 Floor[#]) &, 0, #] &; most efficient to generate the first n terms, e.g. fn[1000000] will generate the result from index 0 to 1000000. $\endgroup$
    – ciao
    Apr 15, 2019 at 7:34
  • $\begingroup$ The reason this does not work, is because you can't match an integer to something like 2 x_ + 1: MatchQ[7, 2 x_ + 1] (* False *). An integer is just an integer: it's not structurally equal to an addition. The pattern matcher is not for matching mathematical patterns like these. Only structural ones. Besides, there's nothing in the pattern 2 x_ + 1 that even limits x to be an integer. $\endgroup$ Apr 15, 2019 at 12:25

2 Answers 2

2
$\begingroup$

Perhaps try this

f[0] := 0;
f[1] := 3;
f[x_/;EvenQ[x]] := f[x/2];
f[x_/;OddQ[x]] := f[(x-1)/2] + f[(x-1)/2 + 1];
a[x_] := f[x]/f[x + 1];
Table[{i,a[i]},{i,0,6}]

with output

{{0, 0}, {1, 1}, {2, 1/2}, {3, 2}, {4, 1/3}, {5, 3/2}, {6, 2/3}}

Please check this carefully to make certain I haven't made any mistakes

$\endgroup$
2
  • 2
    $\begingroup$ This is close to just nitpicking, but I'd personally use ?EvenQ and ?OddQ instead of /;EvenQ[x] etc here. For more complicated pattern matches, the ? notation seems to be faster typically. In this case, the difference isn't noticeable until x values of around 2^1024 on my machine and the recursion limit comes into play first, but I figured it should be noted. $\endgroup$
    – eyorble
    Apr 14, 2019 at 6:34
  • $\begingroup$ Thank you so much, I really appreciated your help. $\endgroup$ Apr 14, 2019 at 8:24
1
$\begingroup$

If you want to go to large values of $x$, then some memoization will speed up your recursion dramatically:

f[0] = 0;
f[1] = 3;
f[x_?EvenQ] := f[x] = f[x/2];
f[x_?OddQ] := f[x] = f[(x - 1)/2] + f[(x + 1)/2];
a[x_] := f[x]/f[x + 1]

try it out:

f[873813] // AbsoluteTiming

{0.000245, 32838}

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