Re: Re: Re: Super-Increasing List
- To: mathgroup at smc.vnet.net
- Subject: [mg40524] Re: [mg40501] Re: [mg40459] Re: [mg40438] Super-Increasing List
- From: Dr Bob <majort at cox-internet.com>
- Date: Wed, 9 Apr 2003 01:32:44 -0400 (EDT)
- References: <8EB1C3634596D6118952006008F711CD5BCD5E@debis.com>
- Reply-to: majort at cox-internet.com
- Sender: owner-wri-mathgroup at wolfram.com
Wolf,
I agree the "increasing" and "superincreasing" concepts are more useful if
kept separate.
Thanks for makeList. I was too impatient to think of a nice way to make up
counterexamples.
Bobby
On Tue, 8 Apr 2003 13:57:38 +0200, Wolf, Hartmut <Hartmut.Wolf@t-
systems.com> wrote:
> 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: [mg40524] [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: [mg40524] [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
>>
>>
>
>
--
majort at cox-internet.com
Bobby R. Treat