MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Part specification... is neither an integer nor a list of integers

  • To: mathgroup at smc.vnet.net
  • Subject: [mg109702] Re: Part specification... is neither an integer nor a list of integers
  • From: Albert Retey <awnl at gmx-topmail.de>
  • Date: Wed, 12 May 2010 07:35:24 -0400 (EDT)
  • References: <hsbbft$jmd$1@smc.vnet.net>

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




  • Prev by Date: Re: Unstructured Interpolation in V7?
  • Next by Date: Re: Scoping with Module
  • Previous by thread: Re: Part specification... is neither an integer nor a list of integers
  • Next by thread: Re: Part specification... is neither an integer nor a list of integers