RE: Re: Re: Super-Increasing List
- To: mathgroup at smc.vnet.net
- Subject: [mg40516] RE: [mg40501] Re: [mg40459] Re: [mg40438] Super-Increasing List
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Wed, 9 Apr 2003 01:30:48 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Bobby,
you're right of course, and indeed had I lost of sight the trivial
implications of condition (a). What Flip didn't state however, if he liked
to consider negative elements at all. If we do, then we find e.g.
In[69]:= superIncreasing[Range[-10, 12]]
Out[69]= True
In[70]:= superIncreasing[Range[-10, 13]]
Out[70]= False
To me, this appears to be a questionable concept, conditions (a) && (b)
together that is. If however the first element is non-negative, the (a)
follows from (b) and your algorithm simplifies (considerably) to
Catch[Fold[If[#1 < #2, #1 + #2, Throw[False]] &, First[t], Rest[t]]; True]
as stated. On the other hand, if we dispense with condition (a) at all, and
also allow for negative values, then we might find (more) exciting
sequences, your counterexample included.
In[12]:= makelist[init_, inc_, n_] := Block[{s = init, e, c = 0},
Prepend[Array[(s += (e = inc[#] + s); e) &, {n - 1}], init]]
In[72]:= t2 = makelist[-3, 1 &, 5]
Out[72]= {-3, -2, -4, -8, -16}
--
Hartmut
>-----Original Message-----
>From: Dr Bob [mailto:majort at cox-internet.com]
To: mathgroup at smc.vnet.net
>Sent: Tuesday, April 08, 2003 9:05 AM
>To: mathgroup at smc.vnet.net
>Subject: [mg40516] [mg40501] Re: [mg40459] Re: [mg40438] Super-Increasing List
>
>
>Thanks for pointing out that the original requirement was a strictly
>increasing series and OrderedQ[list] doesn't check for that.
>
>However, we DO have to check whether the series is increasing, as the
>following example shows:
>
>ClearAll[test, sum]
>sum[1] = test[1];
>sum[n_Integer?Positive] := sum[n - 1] + test[n]
>test[1] = -3; test[2] = -2;
>test[n_Integer?Positive] := 1 + sum[n - 1]
>list = test /@ Range[5]
>
>{-3, -2, -4, -8, -16}
>
>treat[t_List] := Catch[Fold[If[And @@ Thread[#1 < #2], #2 + #1{1, 0},
> Throw[False]] &, {1, 1}First@t, Rest@t]; True]
>wolf[t_List] := And @@ Thread[Drop[FoldList[
> Plus, First[t], Rest[t]], -1] < Rest[t]]
>
>treat@list
>wolf@list
>
>False
>True
>
>Bobby
>
>On Mon, 7 Apr 2003 11:09:05 +0200, Wolf, Hartmut <Hartmut.Wolf@t-
>systems.com> wrote:
>
>> This is a bit obfuscated,...
>>
>> Catch[Fold[If[#1 < #2, #1 + #2, Throw[False]] &, First[t], Rest[t]];
>> True]
>>
>> ...will do.
>>
>>
>> Bob Hanlon's solution assumes all list elements to be
>positive; however,
>> this might be accounted for:
>>
>> And @@ Thread[Drop[FoldList[Plus, First[t], Rest[t]], -1] < Rest[t]]
>>
>>
>> Bill Rowe made the same assumption and additionally checked for the
>> sequence
>> to be increasing (which is not neccessary), furthermore
>OrderedQ is not
>> quite appropiate (apart from being less efficient), as
>>
>> In[39]:= OrderedQ[{1, 1}]
>> Out[39]= True
>>
>>
>> --
>> Hartmut Wolf
>>
>>
>>
>>
>>> -----Original Message-----
>>> From: Dr Bob [mailto:majort at cox-internet.com]
To: mathgroup at smc.vnet.net
>To: mathgroup at smc.vnet.net
>>> Sent: Sunday, April 06, 2003 10:35 AM
>>> To: mathgroup at smc.vnet.net
>>> Subject: [mg40516] [mg40501] [mg40459] Re: [mg40438] Super-Increasing List
>>>
>>>
>>> superIncreasing[t_List] :=
>>> Catch[
>>> Fold[If[And @@ Thread[#1 < #2], #2 + #1{1, 0}, Throw[False]] &,
>>> {1, 1}First@t, Rest@t]; True]
>>>
>>> Bobby
>>>
>>> On Sat, 5 Apr 2003 04:00:35 -0500 (EST), flip
><flip_alpha at safebunch.com>
>>> wrote:
>>>
>>>> Hello,
>>>>
>>>> does a command or module exist which can test a list of values and
>>>> determine
>>>> if it is a super-increasing list?
>>>>
>>>> A super-increasing list satifies the conditions:
>>>>
>>>> a. the list is in increasing order
>>>> b. each element of the list is greater than the sum of
>it's previous
>>>> elements
>>>>
>>>> Example:
>>>>
>>>> list = {2, 3, 7, 15, 31}
>>>>
>>>> So check:
>>>>
>>>> a. It is in increasing order and
>>>> b. 3 > 2, 7 > 3+ 2, 15 > 7 + 3 + 2 and 31 > 15 + 7 + 3 + 2,
>>>>
>>>> hence the list is super-increasing.
>>>>
>>>> Thanks for any inputs, Flip
>>>>
>>>> To email me, remove "_alpha".
>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>>
>>> -- majort at cox-internet.com
>>> Bobby R. Treat
>>>
>>>
>>
>>
>
>
>
>--
>majort at cox-internet.com
>Bobby R. Treat
>
>