COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

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

• Email
• Follow

```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
function g(n)--don't spoil my fun).

Thanks,
Chandler

```
 0

See related articles to this posting

```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@comcast.net
http://home.comcast.net/~djmpark/

From: Chandler May [mailto:cjmay4754@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
function g(n)--don't spoil my fun).

Thanks,
Chandler

```
 0

```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
> function g(n)--don't spoil my fun).
>
> Thanks,
> Chandler
>

```
 0

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

```
 0

```Add memory to the definition

Clear[g]

g[0] = 0;
g[n_] := g[n] = n - g[g[n - 1]];

g /@ Range[0, 10]

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

?? g

Bob Hanlon

---- Chandler May <cjmay4754@gmail.com> wrote:

=============
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
function g(n)--don't spoil my fun).

Thanks,
Chandler

```
 0

```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@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
>> function g(n)--don't spoil my fun).
>>
>> Thanks,
>> Chandler
>>
>
>

```
 0