Part specification... is neither an integer nor a list of integers
in [Mathematica]
|
From: Chandler May on 11 May 2010 06:28 Hi Mathematica sages, I want to implement a recursive function on the natural numbers: g(n) = n - g(g(n-1)) g(0) = 0 First I tried the following in Mathematica. g[0] := 0 g[n_] := n - g[g[n-1]] This worked, but it was much too slow. In hopes of reducing the number computations, I thought I would make a function gseq[n_] to generate the sequence of successive values of g(n) like so: gseq[0] := {0} gseq[n_] := With[{s=gseq[n-1]}, Append[s, n - s[[Last[s]]]]] However, when I ask for gseq[n] for n > 1, Mathematica complains that the "Part specification... is neither an integer nor a list of integers", like the first line here <http://reference.wolfram.com/mathematica/ref/message/General/pspec.html> (sorry, I don't have Mathematica in front of me at the moment). gseq[1] gives me something like {0, 1 - List}. What exactly is going wrong, and how do I mend it? Also, in the With construct, will gseq[n-1] be evaluated once and stored in s, or will every instance of s be replaced by a call to gseq[n-1] (so that gseq[n-1] is wastefully evaluated three times per call to gseq[n])? If gseq[n-1] will be evaluated more than once (per call to gseq[n]), is there a way to change the code so that it won't be? If there's a better way to efficiently implement g(n) altogether, please share (but please don't reveal any mathematical properties about the particular function g(n)--don't spoil my fun). Thanks, Chandler
From: David Park on 12 May 2010 07:33 Maybe this will help. Lookup tutorial/FunctionsThatRememberValuesTheyHaveFound in the Documentation Center search box. g[0] := 0 g[n_] := g[n] = n - g[g[n - 1]] David Park djmpark(a)comcast.net http://home.comcast.net/~djmpark/ From: Chandler May [mailto:cjmay4754(a)gmail.com] Hi Mathematica sages, I want to implement a recursive function on the natural numbers: g(n) = n - g(g(n-1)) g(0) = 0 First I tried the following in Mathematica. g[0] := 0 g[n_] := n - g[g[n-1]] This worked, but it was much too slow. In hopes of reducing the number computations, I thought I would make a function gseq[n_] to generate the sequence of successive values of g(n) like so: gseq[0] := {0} gseq[n_] := With[{s=gseq[n-1]}, Append[s, n - s[[Last[s]]]]] However, when I ask for gseq[n] for n > 1, Mathematica complains that the "Part specification... is neither an integer nor a list of integers", like the first line here <http://reference.wolfram.com/mathematica/ref/message/General/pspec.html> (sorry, I don't have Mathematica in front of me at the moment). gseq[1] gives me something like {0, 1 - List}. What exactly is going wrong, and how do I mend it? Also, in the With construct, will gseq[n-1] be evaluated once and stored in s, or will every instance of s be replaced by a call to gseq[n-1] (so that gseq[n-1] is wastefully evaluated three times per call to gseq[n])? If gseq[n-1] will be evaluated more than once (per call to gseq[n]), is there a way to change the code so that it won't be? If there's a better way to efficiently implement g(n) altogether, please share (but please don't reveal any mathematical properties about the particular function g(n)--don't spoil my fun). Thanks, Chandler
From: Patrick Scheibe on 12 May 2010 07:34 Hi, your first element in your list is 0. In the call s[[Last[s]]] you are taking the zero'th element of s which is the head "List". This is sure not what you want. Check this out: g[0] = 0 g[n_] := g[n] = n - g[g[n - 1]] but note that the $RecursionLimit is set to 256 per default, so: $RecursionLimit = 2000; g[1900] Cheers Patrick Am May 11, 2010 um 12:28 PM schrieb Chandler May: > Hi Mathematica sages, > > I want to implement a recursive function on the natural numbers: > > g(n) = n - g(g(n-1)) > g(0) = 0 > > First I tried the following in Mathematica. > > g[0] := 0 > g[n_] := n - g[g[n-1]] > > This worked, but it was much too slow. In hopes of reducing the > number computations, I thought I would make a function gseq[n_] to > generate the sequence of successive values of g(n) like so: > > gseq[0] := {0} > gseq[n_] := With[{s=gseq[n-1]}, Append[s, n - s[[Last[s]]]]] > > However, when I ask for gseq[n] for n > 1, Mathematica complains that > the "Part specification... is neither an integer nor a list of > integers", like the first line here > <http://reference.wolfram.com/mathematica/ref/message/General/pspec.html > > > (sorry, I don't have Mathematica in front of me at the moment). > gseq[1] gives me something like {0, 1 - List}. > > What exactly is going wrong, and how do I mend it? Also, in the With > construct, will gseq[n-1] be evaluated once and stored in s, or will > every instance of s be replaced by a call to gseq[n-1] (so that > gseq[n-1] is wastefully evaluated three times per call to gseq[n])? > If gseq[n-1] will be evaluated more than once (per call to gseq[n]), > is there a way to change the code so that it won't be? If there's a > better way to efficiently implement g(n) altogether, please share (but > please don't reveal any mathematical properties about the particular > function g(n)--don't spoil my fun). > > Thanks, > Chandler >
From: Albert Retey on 12 May 2010 07:35 Am 11.05.2010 12:28, schrieb Chandler May: > Hi Mathematica sages, > > I want to implement a recursive function on the natural numbers: > > g(n) = n - g(g(n-1)) > g(0) = 0 > > First I tried the following in Mathematica. > > g[0] := 0 > g[n_] := n - g[g[n-1]] > > This worked, but it was much too slow. In hopes of reducing the > number computations, I thought I would make a function gseq[n_] to > generate the sequence of successive values of g(n) like so: > > gseq[0] := {0} > gseq[n_] := With[{s=gseq[n-1]}, Append[s, n - s[[Last[s]]]]] > > However, when I ask for gseq[n] for n > 1, Mathematica complains that > the "Part specification... is neither an integer nor a list of > integers", like the first line here > <http://reference.wolfram.com/mathematica/ref/message/General/pspec.html> > (sorry, I don't have Mathematica in front of me at the moment). > gseq[1] gives me something like {0, 1 - List}. > > What exactly is going wrong, and how do I mend it? Also, in the With > construct, will gseq[n-1] be evaluated once and stored in s, or will > every instance of s be replaced by a call to gseq[n-1] (so that > gseq[n-1] is wastefully evaluated three times per call to gseq[n])? > If gseq[n-1] will be evaluated more than once (per call to gseq[n]), > is there a way to change the code so that it won't be? If there's a > better way to efficiently implement g(n) altogether, please share (but > please don't reveal any mathematical properties about the particular > function g(n)--don't spoil my fun). I haven't looked at the details of your problem, but the actual problem is perfect for the technique of memoization, which is what I think you try to implement in a much more complicated way. This works in a matter of, well milliseconds: g[0] = 0 g[n_] := g[n] = n - g[g[n - 1]]; Note that whatever recursive approach you want to use, you need to increase $RecursionLimit, otherwise the code will produce errormessages and huge results... In[4]:= Block[{$RecursionLimit = 100000}, Timing[g[10000]]] Out[4]= {0.078, 6180} For very large values, there seem to be other limits for the recursion depth which make kernel quit on my machine, but I think that is probably true for every recursive approach... hth, albert
From: Chandler May on 13 May 2010 07:23 Thanks everyone, that clears it up. I was neglecting that indices start at one, not zero, but the g[n_] := g[n] = n - g[g[n-1]] form is much nicer anyway. Very cool! Chandler On Tue, May 11, 2010 at 11:55 PM, Patrick Scheibe <pscheibe(a)trm.uni-leipzig.de> wrote: > Hi, > > your first element in your list is 0. In the call s[[Last[s]]] you are > taking > the zero'th element of s which is the head "List". This is sure not what you > want. > > Check this out: > > g[0] = 0 > g[n_] := g[n] = n - g[g[n - 1]] > > but note that the $RecursionLimit is set to 256 per default, so: > > $RecursionLimit = 2000; > g[1900] > > Cheers > Patrick > > > Am May 11, 2010 um 12:28 PM schrieb Chandler May: > >> Hi Mathematica sages, >> >> I want to implement a recursive function on the natural numbers: >> >> g(n) = n - g(g(n-1)) >> g(0) = 0 >> >> First I tried the following in Mathematica. >> >> g[0] := 0 >> g[n_] := n - g[g[n-1]] >> >> This worked, but it was much too slow. In hopes of reducing the >> number computations, I thought I would make a function gseq[n_] to >> generate the sequence of successive values of g(n) like so: >> >> gseq[0] := {0} >> gseq[n_] := With[{s=gseq[n-1]}, Append[s, n - s[[Last[s]]]]] >> >> However, when I ask for gseq[n] for n > 1, Mathematica complains that >> the "Part specification... is neither an integer nor a list of >> integers", like the first line here >> <http://reference.wolfram.com/mathematica/ref/message/General/pspec.html> >> (sorry, I don't have Mathematica in front of me at the moment). >> gseq[1] gives me something like {0, 1 - List}. >> >> What exactly is going wrong, and how do I mend it? Also, in the With >> construct, will gseq[n-1] be evaluated once and stored in s, or will >> every instance of s be replaced by a call to gseq[n-1] (so that >> gseq[n-1] is wastefully evaluated three times per call to gseq[n])? >> If gseq[n-1] will be evaluated more than once (per call to gseq[n]), >> is there a way to change the code so that it won't be? If there's a >> better way to efficiently implement g(n) altogether, please share (but >> please don't reveal any mathematical properties about the particular >> function g(n)--don't spoil my fun). >> >> Thanks, >> Chandler >> > >
|
Pages: 1 Prev: Announce: O'Reilly Mathematica Cookbook Published Next: implicit function |