[Jprogramming] Recursive verbs

Wed Nov 28 21:57:13 UTC 2018

Yes. For this problem I actually needed the "scan" version, which also lists intermediate results.
It was just the juggling with reverse that appeared a bit confusing at first.
For reference:
 rfold =. /
 rscan =. /\
 lfold =. 1 : 'u~/&|.'
 lscan =. 1 : 'u~/\.&.|.'
Thanks.
________________________________
From: Programming <programming-bounces at forums.jsoftware.com> on behalf of Raul Miller <rauldmiller at gmail.com>
Sent: Wednesday, November 28, 2018 3:30 PM
To: Programming forum
Subject: Re: [Jprogramming] Recursive verbs
For what it's worth, if you think of
 u/ y
as a "right fold"
Then
 u~/ |.y
might be thought of as a "left fold".
Thanks,
--
Raul
On Wed, Nov 28, 2018 at 2:26 PM Nimp O <traws at outlook.com> wrote:
>> Very interesting mathematical solution Mike.
>> My initial idea to solve this type of sequence formula was using folds.
> The idea is to define a fold function g and fold it on a list of _1 and 1, considering an initial value.
> The result was:
>> g =. ]+2*[
> 4 ((g~/\.&.|.)@, ]$(_1 1)"_) 5
>> 4 7 15 29 59 117
>> I found a bit difficult to work this left foldlist in J. Folds from right seem more natural.
>> This same idea can be implemented in Mathematica as:
>> In[1]:= FoldList[2 #1 + #2 &, 4, {-1 , 1 , -1 , 1, -1}]
> Out[1]= {4, 7, 15, 29, 59, 117}
> ________________________________
> From: Programming <programming-bounces at forums.jsoftware.com> on behalf of 'Mike Day' via Programming <programming at jsoftware.com>
> Sent: Wednesday, November 28, 2018 2:08 PM
> To: programming at jsoftware.com
> Subject: Re: [Jprogramming] Recursive verbs
>> Yes, this is one way to get high terms without having to evaluate all
> their predecessors.
> Bear in mind that it's calculating 2^n twice, and the zero-th term
> should surely be the
> starting value. Also, it assumes that starting value is 4; just change
> "4" to "x" in the
> 13 : ... expression to make it apply for any starting value.
>> So here's a lovely compact tacit version which addresses those issues,
> at the expense
> of returning the wrong sign for a negative starting value:
>> fa=: (* ([: | -) 3 %~ [: <: ]) _2&^ NB. with a [: to keep Linda
> happy
> So,
> 4 fa 200x
> 5892106162282964343653861005250929542581410977203573729438379
> cf
> 4 (13 :'x p.~(([:(2&^)>:),.~ _1r3 *([:(2&^)>:) + _1&^)y' ) 199x
> 5892106162282964343653861005250929542581410977203573729438379
>> If you want a table, the rank needs to be imposed:
> 4 5 fl"0/ 3 4 5
> 29 59 117
> 37 75 149
>> A possibly easier way to understand why we need ((_2^n) - 1) % 3 is perhaps
> to inspect the general term.
> We have
> a1 = 2a0 - 1 NB. using "Mathematical" notationrather than APL/J
> a2 = 2a1 + 1 = 4a0 - 2 + 1
> a3 = 2a2 - 1 = 8a0 - 4 + 2 - 1
> ...
> an = (2^n).a0 - (2^[n-1]) + (2^[n-2]) ... + (-1)^n
>> The absolute sum of all terms except the first is | sum {i=0,n-1} _2^i | ,
> which we know from High School maths is | [(_2^n) - 1]%[_2 -1] | ,
> ie | [(_2^n) - 1]% 3 |
>> If you want the correct sign for negative starting values, use
> (fa * * [) NB. ... which isn't quite so neat.
>> Cheers,
>> Mike
> NB - previous correspondence not trimmed
>>> On 28/11/2018 09:49, Linda Alvord wrote:
> > Hi Cliff,
> >
> > It took a while but I got the explicit verb to work.
> >
> > f=: 13 :'4 p.~(([:(2&^)>:),.~ _1r3 *([:(2&^)>:) + _1&^)y'
> >
> > f i.10
> > 7 15 29 59 117 235 469 939 1877 3755
> >
> > f
> > 4 p.~ ([: 2&^ >:) ,.~ _1r3 * ([: 2&^ >:) + _1&^
> >
> > Linda
> >
> > -----Original Message-----
> > From: Programming<programming-bounces at forums.jsoftware.com> On Behalf Of Cliff Reiter
> > Sent: Tuesday, November 27, 2018 12:38 PM
> > To:programming at jsoftware.com
> > Subject: Re: [Jprogramming] Recursive verbs
> >
> > I like that solution. Here is another approach
> >
> > 4 p.~(2&^@>: ,.~ _1r3 * 2&^@>: + _1&^)i. 10
> > 7 15 29 59 117 235 469 939 1877 3755
> >
> > I found this by composing the linear poly's and noting the constant terms satisfy a two step recursion with eigenvalues 2 and _1.
> >
> > lc=.({.@[+{:@[*{.@]),*&{:
> > lc/\.(7$_1 2,:1 2)
> > _43 128
> > _21 64
> > _11 32
> > _5 16
> > _3 8
> > _1 4
> > _1 2
> >
> >
> > On 11/27/2018 11:06 AM, Raul Miller wrote:
> >> Sure, ... that's a bit bulkier than I prefer, but it works.
> >>
> >> Here's another alternative:
> >>
> >> evenodd=: , (_1 2,:_1 4)&p.@{:
> >> evenodd evenodd 4
> >> 4 7 15 29 59
> >>
> >> Thanks,
> >>
> > ----------------------------------------------------------------------
> > For information about J forums seehttps://eur04.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.jsoftware.com%2Fforums.htm&data=02%7C01%7C%7C677fb1d024fe4e3d937308d6548f1c93%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636789370963003978&sdata=iWGjGzFd70epkTr2UBP7DapC8imlNBoaBgTzKw3eTE8%3D&reserved=0
> > ----------------------------------------------------------------------
> > For information about J forums seehttp://www.jsoftware.com/forums.htm
>>>> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm