Re: [Jprogramming] Goodstein Sequences and Hereditary base-n notation

2018-04-11 Thread 'Jon Hough' via Programming 
Very nice solution. This style of solution what I wanted to write.

Just to compare:
   timespacex 'genSeq 2 4 20'
0.000741 13184
   timespacex ' gs^:(0~:{:)^:20 ] 4x'
0.000892 49024

As an FYI, there is also a Haskell solutiuon here: 
https://oeis.org/A211378/a211378.hs.txt
In that file there are the ids of various Sloane Number sequences for Goodstein 
Sequences, just
in case you wanted to verify your solution.
e.g.
A056193
A222117
A059933
A211378
   
Thanks,
Jon

On Thu, 4/12/18, Louis de Forcrand <ol...@bluewin.ch> wrote:

 Subject: Re: [Jprogramming] Goodstein Sequences and Hereditary base-n  notation
 To: programm...@jsoftware.com
 Date: Thursday, April 12, 2018, 12:01 AM
 
 Hi,
 
 This is my tacit version. Not claiming speed
 (or anything in the way of code legibility for that matter).
 The important verb is hbi, hereditary base-x incrementation
 of y used in creating the Goodstein sequence.
 My gs verb uses a starting base of 2, and gss
 starts with base x:
 
 hbi=:
 ([ (] +/ . * >:@[ ^ [ $: i.@-@#@]) #.^:_1)`]@.(0 =
 ])"0
 gs=: , >:@# <:@hbi {:
 gss=: ] , (+ <:@#) <:@hbi {:@]
 
    gs^:(0~:{:)^:10 ] 3x
 3 3 3 2 1 0
    gs^:(0~:{:)^:10
 ] 4x
 4 26 41 60 83 109 139 173 211 253
 299
    gs^:(0~:{:)^:3 ] 19x
 19 7625597484990
 
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084099
 191101259794547752035640455...
 
    3 gss^:(0~:{:@])^:10 ] 3x
 3
 3 2 1 0
 
 
 Sorry if I didn’t explain my code, kind of
 short on time. I’m pretty sure it works though!
 
 Cheers,
 Louis
 
 > On
 11 Apr 2018, at 15:15, 'Jon Hough' via Programming
 <programm...@jsoftware.com>
 wrote:
 > 
 > My first
 answer was actually comletely wrong, and only works for the
 simplest cases. This is a more robust and correct
 solution
 > 
 >
 goodstein=: 4 : 0"0 0
 > if. y = x
 do.
 >  x+1 return.
 >
 elseif. y = 0 do.
 >  0 return.
 > end.
 > s=. I. x
 (|.@:((>:@:>.@:^. # [) #: ])) y
 >
 d=. (x+1) ^ (x:x) goodstein x: s
 > +/d
 > )
 > 
 > G=: <:@:goodstein
 >
 
 > NB. generates sequence
 > genSeq=: 3 : 0"1
 >
 'base val its'=. y
 > c=. 0
 > vals=. val
 > whilst.
 its > c=. c+1 do.
 >  val=. base G
 val
 >  vals=. vals,val
 >  base=. base+1
 >
 end.
 > vals
 > )
 > 
 > genSeq 2 4 10
 > 4 26 41 60 83 109 139 173 211 253 299
 > 
 > genSeq 2 19 3
 > 19 7625597484990
 
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084099
 
19110125979454775203564045597039645991980810489900943371395127892465205302426158030...
 > 
 > 
 >
 
 > On Wed, 4/11/18, 'Jon Hough' via
 Programming <programm...@jsoftware.com>
 wrote:
 > 
 > Subject:
 [Jprogramming] Goodstein Sequences and Hereditary base-n
 notation
 > To: "Programming
 Forum" <programm...@jsoftware.com>
 > Date: Wednesday, April 11, 2018, 5:14
 PM
 > 
 >
 Goodstein's theorem: https://en.wikipedia.org/wiki/Goodstein%27s_theorem
 > This states  that every Goodstein
 > sequence eventually terminates at 0.
 > The wikipedia page defines Goodstein
 > sequences in terms of Hereditary base-n
 notation
 > one such sequence is
 4,26,41,60...
 > 
 >
 Copying verbatim from wikipedia:
 >
 ==
 > The Goodstein sequence
 G(m) of a number
 > m is a sequence of
 natural numbers. The first element in the
 > sequence G(m) is m itself. To get the
 second, G(m)(2), write
 > m in hereditary
 base-2 notation, change all the 2s to 3s,
 > and then subtract 1 from the result. In
 general, the
 > (n + 1)-st term
 G(m)(n + 1) of the Goodstein
 >
 sequence of m is as follows:
 > 
 > Take the hereditary base-n + 1
 > representation of G(m)(n).
 > Replace each occurrence of the
 > base-n + 1 with n + 2.
 > Subtract one. (Note that the next term
 > depends both on the previous term and on
 the index n.)
 > Continue until the result
 is zero, at
 > which point the sequence
 terminates.
 > ===
 > 
 > The sequences take
 an impossibly long
 > time to terminate
 for most inputs, so there is no use
 >
 writing a verb that iterates until convergance. This is
 my
 > verb that will calculate the first N
 elements of the
 > sequence,
 > starting with a given base and val. the
 > base should start at 2, to conform to the
 above definition.
 > 
 >
 
 > goodstein=: 3 : 0
 >
 'base val its'=. y
 > vals=.
 ''
 > c=: 0
 >
 whilst.its> c=: c+1 do.
 >   if. val =
 0 do. vals return.
 >   else.
 >     t=: ((1+
 >>
 .base^.val)#base) #: val
 >     if. base
 < # t do.
 >       if. 0 &

Re: [Jprogramming] Goodstein Sequences and Hereditary base-n notation... CRASH!

2018-04-11 Thread 'Jon Hough' via Programming 
Must be due to  x ^ y returning floating datatypes, and losing precision.

depth=:0
S=: 1 :0
:
y=.<.y  NB.  <-  floor of y
if. 0= y do. 0
  else. 
'q r'=. (0,m) #: y
( r *(1+m) ^ (0 (m S) x)) + (1+x) m S q NB. <-- ^ returns 
floating
end.
)

That will also fix it.

This bug (is it a bug?) is in j805:
   JVERSION
Engine: j805/j64/darwin
Release: commercial/2016-12-11T08:17:56
Library: 8.05.14
Qt IDE: 1.5.4s/5.6.2
Platform: Darwin 64
Installer: J805 install




On Thu, 4/12/18, Arie Groeneveld <agroeneveld...@gmail.com> wrote:

 Subject: Re: [Jprogramming] Goodstein Sequences and Hereditary base-n 
notation... CRASH!
 To: programm...@jsoftware.com
 Date: Thursday, April 12, 2018, 6:38 AM
 
 I noticed it has to do with the
 0=y testing in S. Instead of producing a 
 zero at a certain point it gives a small value
 4.4e_16 and then 
 starts filling the 
 stack.
 
 Op 11-04-18 om 22:05
 schreef Jose Mario Quintana:
 > You might
 like to look also at Arie Groeneveld's message,
 >
 > [Jprogramming] Crash
 calculating large hyper operations
 > http://www.jsoftware.com/pipermail/programming/2015-November/043351.html
 >
 > Unfortunately,
 running on the latest stable release,
 >
 >     JVERSION
 > Engine: j806/j64nonavx/windows
 > Release: commercial/2017-11-06T10:01:33
 > Library: 8.06.09
 > Qt
 IDE: 1.6.2/5.6.3
 > Platform: Win 64
 > Installer: J806 install
 > InstallPath: j:/program files/j
 > Contact: www.jsoftware.com
 >
 > the following,
 >
 > S=: 1 :0
 > :
 > if. 0= y do. 0
 >    else. 'q r'=. (0,m) #: y
 >          ( r *(1+m) ^ (0 (m S) x)) +
 (1+x) m S q
 > end.
 >
 )
 >
 > G=: (>:@[ $:
 _1+ 4 : '0 (x S)y')`[@.(0=])
 >
 > 2 G"0 i.4
 >
 > now produces a crash ("J has stopped
 working") instead of,
 >
 > 2 3 5 7
 >
 > As far as I can see, the code should run
 on J804 but I do not know if it
 > runs on
 J805 (or on the latest and greatest j807).
 >
 > Anyway, in theory, 2
 G"0 i.5 should include the additional number,
 >
 > _1 + 3 * 2 ^
 402653211x
 >
 > in
 practice, of course, it cannot (even trying to execute the
 sentence _1 +
 > 3 * 2 ^ 402653211x
 produces a limit error).
 >
 >
 >
 >
 On Wed, Apr 11, 2018 at 9:15 AM, 'Jon Hough' via
 Programming <
 > programm...@jsoftware.com>
 wrote:
 >
 >> My
 first answer was actually comletely wrong, and only works
 for the
 >> simplest cases. This is a
 more robust and correct solution
 >>
 >> goodstein=: 4 : 0"0 0
 >> if. y = x do.
 >>    x+1 return.
 >> elseif. y = 0 do.
 >>    0 return.
 >> end.
 >> s=. I. x
 (|.@:((>:@:>.@:^. # [) #: ])) y
 >> d=. (x+1) ^ (x:x) goodstein x: s
 >> +/d
 >> )
 >>
 >> G=:
 <:@:goodstein
 >>
 >> NB. generates sequence
 >> genSeq=: 3 : 0"1
 >> 'base val its'=. y
 >> c=. 0
 >> vals=.
 val
 >> whilst. its > c=. c+1 do.
 >>    val=. base G val
 >>    vals=. vals,val
 >>    base=. base+1
 >> end.
 >> vals
 >> )
 >>
 >> genSeq 2 4 10
 >>   4 26 41 60 83 109 139 173 211 253
 299
 >>
 >> genSeq
 2 19 3
 >>   19 7625597484990
 134078079299425970995740249982
 >>
 058461274793658205923933777235614437217640300735469768018742
 >>
 98166903427690031858186486050853753882811946569946433649006084099
 >>
 191101259794547752035640455970396459919808104899009433713951
 >> 27892465205302426158030...
 >>
 >>
 >>
 
 >> On Wed, 4/11/18, 'Jon Hough'
 via Programming <programm...@jsoftware.com>
 >> wrote:
 >>
 >>   Subject: [Jprogramming] Goodstein
 Sequences and Hereditary base-n notation
 >>   To: "Programming Forum"
 <programm...@jsoftware.com>
 >>   Date: Wednesday, April 11, 2018,
 5:14 PM
 >>
 >>  
 Goodstein's theorem: https://en.wikipedia.org/wiki/Goodstein%27s_theorem
 >>   This states  that every
 Goodstein
 >>   sequence eventually
 terminates at 0.
 >>   The wikipedia
 page defines Goodstein
 >>   sequences
 in terms of Hereditary base-n notation
 >>   one such sequence is
 4,26,41,60...
 >>
 >>   Copying verbatim from wikipedia:
 >>   ==
 >>   The Goodstein sequence G(m) of a
 number
 >>   m is a sequence of
 natural numbers. The first element in the
 >>   sequence G(m) is m itself. To get
 the second, G(m)(2), write
 >>   m in
 hereditary base-2 notation, change all the 2s to 3s,
 >>   and then subtract 1 from the
 result. In general, the
 >>   (n +
 1)-st term G(m)(n + 1) of the Goodstein
 >> 

Re: [Jprogramming] Goodstein Sequences and Hereditary base-n notation... CRASH!

2018-04-11 Thread Arie Groeneveld 
I noticed it has to do with the 0=y testing in S. Instead of producing a 
zero at a certain point it gives a small value 4.4e_16 and then 
starts filling the  stack.


Op 11-04-18 om 22:05 schreef Jose Mario Quintana:

You might like to look also at Arie Groeneveld's message,

[Jprogramming] Crash calculating large hyper operations
http://www.jsoftware.com/pipermail/programming/2015-November/043351.html

Unfortunately, running on the latest stable release,

JVERSION
Engine: j806/j64nonavx/windows
Release: commercial/2017-11-06T10:01:33
Library: 8.06.09
Qt IDE: 1.6.2/5.6.3
Platform: Win 64
Installer: J806 install
InstallPath: j:/program files/j
Contact: www.jsoftware.com

the following,

S=: 1 :0
:
if. 0= y do. 0
   else. 'q r'=. (0,m) #: y
 ( r *(1+m) ^ (0 (m S) x)) + (1+x) m S q
end.
)

G=: (>:@[ $: _1+ 4 : '0 (x S)y')`[@.(0=])

2 G"0 i.4

now produces a crash ("J has stopped working") instead of,

2 3 5 7

As far as I can see, the code should run on J804 but I do not know if it
runs on J805 (or on the latest and greatest j807).

Anyway, in theory, 2 G"0 i.5 should include the additional number,

_1 + 3 * 2 ^ 402653211x

in practice, of course, it cannot (even trying to execute the sentence _1 +
3 * 2 ^ 402653211x produces a limit error).



On Wed, Apr 11, 2018 at 9:15 AM, 'Jon Hough' via Programming <
programm...@jsoftware.com> wrote:


My first answer was actually comletely wrong, and only works for the
simplest cases. This is a more robust and correct solution

goodstein=: 4 : 0"0 0
if. y = x do.
   x+1 return.
elseif. y = 0 do.
   0 return.
end.
s=. I. x (|.@:((>:@:>.@:^. # [) #: ])) y
d=. (x+1) ^ (x:x) goodstein x: s
+/d
)

G=: <:@:goodstein

NB. generates sequence
genSeq=: 3 : 0"1
'base val its'=. y
c=. 0
vals=. val
whilst. its > c=. c+1 do.
   val=. base G val
   vals=. vals,val
   base=. base+1
end.
vals
)

genSeq 2 4 10
  4 26 41 60 83 109 139 173 211 253 299

genSeq 2 19 3
  19 7625597484990 134078079299425970995740249982
058461274793658205923933777235614437217640300735469768018742
98166903427690031858186486050853753882811946569946433649006084099
191101259794547752035640455970396459919808104899009433713951
27892465205302426158030...



On Wed, 4/11/18, 'Jon Hough' via Programming 
wrote:

  Subject: [Jprogramming] Goodstein Sequences and Hereditary base-n notation
  To: "Programming Forum" 
  Date: Wednesday, April 11, 2018, 5:14 PM

  Goodstein's theorem: https://en.wikipedia.org/wiki/Goodstein%27s_theorem
  This states  that every Goodstein
  sequence eventually terminates at 0.
  The wikipedia page defines Goodstein
  sequences in terms of Hereditary base-n notation
  one such sequence is 4,26,41,60...

  Copying verbatim from wikipedia:
  ==
  The Goodstein sequence G(m) of a number
  m is a sequence of natural numbers. The first element in the
  sequence G(m) is m itself. To get the second, G(m)(2), write
  m in hereditary base-2 notation, change all the 2s to 3s,
  and then subtract 1 from the result. In general, the
  (n + 1)-st term G(m)(n + 1) of the Goodstein
  sequence of m is as follows:

  Take the hereditary base-n + 1
  representation of G(m)(n).
  Replace each occurrence of the
  base-n + 1 with n + 2.
  Subtract one. (Note that the next term
  depends both on the previous term and on the index n.)
  Continue until the result is zero, at
  which point the sequence terminates.
  ===

  The sequences take an impossibly long
  time to terminate for most inputs, so there is no use
  writing a verb that iterates until convergance. This is my
  verb that will calculate the first N elements of the
  sequence,
  starting with a given base and val. the
  base should start at 2, to conform to the above definition.


  goodstein=: 3 : 0
  'base val its'=. y
  vals=. ''
  c=: 0
  whilst.its> c=: c+1 do.
if. val = 0 do. vals return.
else.
  t=: ((1+
  >.base^.val)#base) #: val
  if. base < # t do.
if. 0 < base {
  |.t do.
  tr=: 0
  (base}) |.t
  if.
  (base+1) < # tr do.
ts=:
  (1+(base+1){tr) ((x+1)}) tr
ts=:
  |.ts
  else.
ts=:
  tr,1
ts=:
  |.ts
  end.
else. ts=: t end.
  else.
ts=: t
  end.
  val=. <:(base+1) #.
  ts
  vals=. vals,val
  base=. base+1
end.
  end.
  vals
  )



  NB. example
  goodstein 2 4 9
  26 41 60 83 109 139 173 211 253
  NB. continues to very large numbers.

   goodstein 2 3 5
  3 3 2 1 0   NB. terminates after 6
  iterations

  Is was hoping the goodstein verb could
  be defined tacitly, but my verb is clearly a bit of a mess.
  Just for fun, any elegant solutions?

  Thanks,
  Jon
  --
  For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Goodstein Sequences and Hereditary base-n notation... CRASH!

2018-04-11 Thread Arie Groeneveld 

Use this:

   2x G"0 i.4
2 3 5 7




Op 11-04-18 om 22:05 schreef Jose Mario Quintana:

You might like to look also at Arie Groeneveld's message,

[Jprogramming] Crash calculating large hyper operations
http://www.jsoftware.com/pipermail/programming/2015-November/043351.html

Unfortunately, running on the latest stable release,

JVERSION
Engine: j806/j64nonavx/windows
Release: commercial/2017-11-06T10:01:33
Library: 8.06.09
Qt IDE: 1.6.2/5.6.3
Platform: Win 64
Installer: J806 install
InstallPath: j:/program files/j
Contact: www.jsoftware.com

the following,

S=: 1 :0
:
if. 0= y do. 0
   else. 'q r'=. (0,m) #: y
 ( r *(1+m) ^ (0 (m S) x)) + (1+x) m S q
end.
)

G=: (>:@[ $: _1+ 4 : '0 (x S)y')`[@.(0=])

2 G"0 i.4

now produces a crash ("J has stopped working") instead of,

2 3 5 7

As far as I can see, the code should run on J804 but I do not know if it
runs on J805 (or on the latest and greatest j807).

Anyway, in theory, 2 G"0 i.5 should include the additional number,

_1 + 3 * 2 ^ 402653211x

in practice, of course, it cannot (even trying to execute the sentence _1 +
3 * 2 ^ 402653211x produces a limit error).



On Wed, Apr 11, 2018 at 9:15 AM, 'Jon Hough' via Programming <
programm...@jsoftware.com> wrote:


My first answer was actually comletely wrong, and only works for the
simplest cases. This is a more robust and correct solution

goodstein=: 4 : 0"0 0
if. y = x do.
   x+1 return.
elseif. y = 0 do.
   0 return.
end.
s=. I. x (|.@:((>:@:>.@:^. # [) #: ])) y
d=. (x+1) ^ (x:x) goodstein x: s
+/d
)

G=: <:@:goodstein

NB. generates sequence
genSeq=: 3 : 0"1
'base val its'=. y
c=. 0
vals=. val
whilst. its > c=. c+1 do.
   val=. base G val
   vals=. vals,val
   base=. base+1
end.
vals
)

genSeq 2 4 10
  4 26 41 60 83 109 139 173 211 253 299

genSeq 2 19 3
  19 7625597484990 134078079299425970995740249982
058461274793658205923933777235614437217640300735469768018742
98166903427690031858186486050853753882811946569946433649006084099
191101259794547752035640455970396459919808104899009433713951
27892465205302426158030...



On Wed, 4/11/18, 'Jon Hough' via Programming 
wrote:

  Subject: [Jprogramming] Goodstein Sequences and Hereditary base-n notation
  To: "Programming Forum" 
  Date: Wednesday, April 11, 2018, 5:14 PM

  Goodstein's theorem: https://en.wikipedia.org/wiki/Goodstein%27s_theorem
  This states  that every Goodstein
  sequence eventually terminates at 0.
  The wikipedia page defines Goodstein
  sequences in terms of Hereditary base-n notation
  one such sequence is 4,26,41,60...

  Copying verbatim from wikipedia:
  ==
  The Goodstein sequence G(m) of a number
  m is a sequence of natural numbers. The first element in the
  sequence G(m) is m itself. To get the second, G(m)(2), write
  m in hereditary base-2 notation, change all the 2s to 3s,
  and then subtract 1 from the result. In general, the
  (n + 1)-st term G(m)(n + 1) of the Goodstein
  sequence of m is as follows:

  Take the hereditary base-n + 1
  representation of G(m)(n).
  Replace each occurrence of the
  base-n + 1 with n + 2.
  Subtract one. (Note that the next term
  depends both on the previous term and on the index n.)
  Continue until the result is zero, at
  which point the sequence terminates.
  ===

  The sequences take an impossibly long
  time to terminate for most inputs, so there is no use
  writing a verb that iterates until convergance. This is my
  verb that will calculate the first N elements of the
  sequence,
  starting with a given base and val. the
  base should start at 2, to conform to the above definition.


  goodstein=: 3 : 0
  'base val its'=. y
  vals=. ''
  c=: 0
  whilst.its> c=: c+1 do.
if. val = 0 do. vals return.
else.
  t=: ((1+
  >.base^.val)#base) #: val
  if. base < # t do.
if. 0 < base {
  |.t do.
  tr=: 0
  (base}) |.t
  if.
  (base+1) < # tr do.
ts=:
  (1+(base+1){tr) ((x+1)}) tr
ts=:
  |.ts
  else.
ts=:
  tr,1
ts=:
  |.ts
  end.
else. ts=: t end.
  else.
ts=: t
  end.
  val=. <:(base+1) #.
  ts
  vals=. vals,val
  base=. base+1
end.
  end.
  vals
  )



  NB. example
  goodstein 2 4 9
  26 41 60 83 109 139 173 211 253
  NB. continues to very large numbers.

   goodstein 2 3 5
  3 3 2 1 0   NB. terminates after 6
  iterations

  Is was hoping the goodstein verb could
  be defined tacitly, but my verb is clearly a bit of a mess.
  Just for fun, any elegant solutions?

  Thanks,
  Jon
  --
  For information about J forums see http://www.jsoftware.com/forums.htm
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Goodstein Sequences and Hereditary base-n notation... CRASH!

2018-04-11 Thread Henry Rich 

What is the maximum recursion depth reached by this program?

Henry Rich

On 4/11/2018 4:05 PM, Jose Mario Quintana wrote:

You might like to look also at Arie Groeneveld's message,

[Jprogramming] Crash calculating large hyper operations
http://www.jsoftware.com/pipermail/programming/2015-November/043351.html

Unfortunately, running on the latest stable release,

JVERSION
Engine: j806/j64nonavx/windows
Release: commercial/2017-11-06T10:01:33
Library: 8.06.09
Qt IDE: 1.6.2/5.6.3
Platform: Win 64
Installer: J806 install
InstallPath: j:/program files/j
Contact: www.jsoftware.com

the following,

S=: 1 :0
:
if. 0= y do. 0
   else. 'q r'=. (0,m) #: y
 ( r *(1+m) ^ (0 (m S) x)) + (1+x) m S q
end.
)

G=: (>:@[ $: _1+ 4 : '0 (x S)y')`[@.(0=])

2 G"0 i.4

now produces a crash ("J has stopped working") instead of,

2 3 5 7

As far as I can see, the code should run on J804 but I do not know if it
runs on J805 (or on the latest and greatest j807).

Anyway, in theory, 2 G"0 i.5 should include the additional number,

_1 + 3 * 2 ^ 402653211x

in practice, of course, it cannot (even trying to execute the sentence _1 +
3 * 2 ^ 402653211x produces a limit error).



On Wed, Apr 11, 2018 at 9:15 AM, 'Jon Hough' via Programming <
programm...@jsoftware.com> wrote:


My first answer was actually comletely wrong, and only works for the
simplest cases. This is a more robust and correct solution

goodstein=: 4 : 0"0 0
if. y = x do.
   x+1 return.
elseif. y = 0 do.
   0 return.
end.
s=. I. x (|.@:((>:@:>.@:^. # [) #: ])) y
d=. (x+1) ^ (x:x) goodstein x: s
+/d
)

G=: <:@:goodstein

NB. generates sequence
genSeq=: 3 : 0"1
'base val its'=. y
c=. 0
vals=. val
whilst. its > c=. c+1 do.
   val=. base G val
   vals=. vals,val
   base=. base+1
end.
vals
)

genSeq 2 4 10
  4 26 41 60 83 109 139 173 211 253 299

genSeq 2 19 3
  19 7625597484990 134078079299425970995740249982
058461274793658205923933777235614437217640300735469768018742
98166903427690031858186486050853753882811946569946433649006084099
191101259794547752035640455970396459919808104899009433713951
27892465205302426158030...



On Wed, 4/11/18, 'Jon Hough' via Programming 
wrote:

  Subject: [Jprogramming] Goodstein Sequences and Hereditary base-n notation
  To: "Programming Forum" 
  Date: Wednesday, April 11, 2018, 5:14 PM

  Goodstein's theorem: https://en.wikipedia.org/wiki/Goodstein%27s_theorem
  This states  that every Goodstein
  sequence eventually terminates at 0.
  The wikipedia page defines Goodstein
  sequences in terms of Hereditary base-n notation
  one such sequence is 4,26,41,60...

  Copying verbatim from wikipedia:
  ==
  The Goodstein sequence G(m) of a number
  m is a sequence of natural numbers. The first element in the
  sequence G(m) is m itself. To get the second, G(m)(2), write
  m in hereditary base-2 notation, change all the 2s to 3s,
  and then subtract 1 from the result. In general, the
  (n + 1)-st term G(m)(n + 1) of the Goodstein
  sequence of m is as follows:

  Take the hereditary base-n + 1
  representation of G(m)(n).
  Replace each occurrence of the
  base-n + 1 with n + 2.
  Subtract one. (Note that the next term
  depends both on the previous term and on the index n.)
  Continue until the result is zero, at
  which point the sequence terminates.
  ===

  The sequences take an impossibly long
  time to terminate for most inputs, so there is no use
  writing a verb that iterates until convergance. This is my
  verb that will calculate the first N elements of the
  sequence,
  starting with a given base and val. the
  base should start at 2, to conform to the above definition.


  goodstein=: 3 : 0
  'base val its'=. y
  vals=. ''
  c=: 0
  whilst.its> c=: c+1 do.
if. val = 0 do. vals return.
else.
  t=: ((1+
  >.base^.val)#base) #: val
  if. base < # t do.
if. 0 < base {
  |.t do.
  tr=: 0
  (base}) |.t
  if.
  (base+1) < # tr do.
ts=:
  (1+(base+1){tr) ((x+1)}) tr
ts=:
  |.ts
  else.
ts=:
  tr,1
ts=:
  |.ts
  end.
else. ts=: t end.
  else.
ts=: t
  end.
  val=. <:(base+1) #.
  ts
  vals=. vals,val
  base=. base+1
end.
  end.
  vals
  )



  NB. example
  goodstein 2 4 9
  26 41 60 83 109 139 173 211 253
  NB. continues to very large numbers.

   goodstein 2 3 5
  3 3 2 1 0   NB. terminates after 6
  iterations

  Is was hoping the goodstein verb could
  be defined tacitly, but my verb is clearly a bit of a mess.
  Just for fun, any elegant solutions?

  Thanks,
  Jon
  --
  For information about J forums see http://www.jsoftware.com/forums.htm
--
For information about J forums see http://www.jsoftware.com/forums.htm

Re: [Jprogramming] Goodstein Sequences and Hereditary base-n notation

2018-04-11 Thread Louis de Forcrand 
Hi,

This is my tacit version. Not claiming speed (or anything in the way of code 
legibility for that matter). The important verb is hbi, hereditary base-x 
incrementation of y used in creating the Goodstein sequence.
My gs verb uses a starting base of 2, and gss starts with base x:

hbi=: ([ (] +/ . * >:@[ ^ [ $: i.@-@#@]) #.^:_1)`]@.(0 = ])"0
gs=: , >:@# <:@hbi {:
gss=: ] , (+ <:@#) <:@hbi {:@]

   gs^:(0~:{:)^:10 ] 3x
3 3 3 2 1 0
   gs^:(0~:{:)^:10 ] 4x
4 26 41 60 83 109 139 173 211 253 299
   gs^:(0~:{:)^:3 ] 19x
19 7625597484990 
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084099
 191101259794547752035640455...

   3 gss^:(0~:{:@])^:10 ] 3x
3 3 2 1 0


Sorry if I didn’t explain my code, kind of short on time. I’m pretty sure it 
works though!

Cheers,
Louis

> On 11 Apr 2018, at 15:15, 'Jon Hough' via Programming 
>  wrote:
> 
> My first answer was actually comletely wrong, and only works for the simplest 
> cases. This is a more robust and correct solution
> 
> goodstein=: 4 : 0"0 0
> if. y = x do.
>  x+1 return.
> elseif. y = 0 do.
>  0 return.
> end.
> s=. I. x (|.@:((>:@:>.@:^. # [) #: ])) y
> d=. (x+1) ^ (x:x) goodstein x: s
> +/d
> )
> 
> G=: <:@:goodstein
> 
> NB. generates sequence
> genSeq=: 3 : 0"1
> 'base val its'=. y
> c=. 0
> vals=. val
> whilst. its > c=. c+1 do.
>  val=. base G val
>  vals=. vals,val
>  base=. base+1
> end.
> vals
> )
> 
> genSeq 2 4 10
> 4 26 41 60 83 109 139 173 211 253 299
> 
> genSeq 2 19 3
> 19 7625597484990 
> 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084099
>  
> 19110125979454775203564045597039645991980810489900943371395127892465205302426158030...
> 
> 
> 
> On Wed, 4/11/18, 'Jon Hough' via Programming  
> wrote:
> 
> Subject: [Jprogramming] Goodstein Sequences and Hereditary base-n notation
> To: "Programming Forum" 
> Date: Wednesday, April 11, 2018, 5:14 PM
> 
> Goodstein's theorem: https://en.wikipedia.org/wiki/Goodstein%27s_theorem
> This states  that every Goodstein
> sequence eventually terminates at 0.
> The wikipedia page defines Goodstein
> sequences in terms of Hereditary base-n notation
> one such sequence is 4,26,41,60...
> 
> Copying verbatim from wikipedia:
> ==
> The Goodstein sequence G(m) of a number
> m is a sequence of natural numbers. The first element in the
> sequence G(m) is m itself. To get the second, G(m)(2), write
> m in hereditary base-2 notation, change all the 2s to 3s,
> and then subtract 1 from the result. In general, the
> (n + 1)-st term G(m)(n + 1) of the Goodstein
> sequence of m is as follows:
> 
> Take the hereditary base-n + 1
> representation of G(m)(n).
> Replace each occurrence of the
> base-n + 1 with n + 2.
> Subtract one. (Note that the next term
> depends both on the previous term and on the index n.)
> Continue until the result is zero, at
> which point the sequence terminates.
> ===
> 
> The sequences take an impossibly long
> time to terminate for most inputs, so there is no use
> writing a verb that iterates until convergance. This is my
> verb that will calculate the first N elements of the
> sequence,
> starting with a given base and val. the
> base should start at 2, to conform to the above definition.
> 
> 
> goodstein=: 3 : 0
> 'base val its'=. y
> vals=. ''
> c=: 0
> whilst.its> c=: c+1 do.
>   if. val = 0 do. vals return.
>   else.
> t=: ((1+
>> .base^.val)#base) #: val
> if. base < # t do.
>   if. 0 < base {
> |.t do.
> tr=: 0
> (base}) |.t
> if.
> (base+1) < # tr do.
>   ts=:
> (1+(base+1){tr) ((x+1)}) tr
>   ts=:
> |.ts
> else.
>   ts=:
> tr,1
>   ts=:
> |.ts
> end.
>   else. ts=: t end.
> else.
>   ts=: t
> end.
> val=. <:(base+1) #.
> ts
> vals=. vals,val
> base=. base+1
>   end.
> end.
> vals
> )
> 
> 
> 
> NB. example
> goodstein 2 4 9
> 26 41 60 83 109 139 173 211 253 
> NB. continues to very large numbers.
> 
>  goodstein 2 3 5
> 3 3 2 1 0   NB. terminates after 6
> iterations
> 
> Is was hoping the goodstein verb could
> be defined tacitly, but my verb is clearly a bit of a mess.
> Just for fun, any elegant solutions?
> 
> Thanks,
> Jon
> --
> 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

Re: [Jprogramming] Goodstein Sequences and Hereditary base-n notation

2018-04-11 Thread 'Jon Hough' via Programming 
My first answer was actually comletely wrong, and only works for the simplest 
cases. This is a more robust and correct solution

goodstein=: 4 : 0"0 0
if. y = x do.
  x+1 return.
elseif. y = 0 do.
  0 return.
end.
s=. I. x (|.@:((>:@:>.@:^. # [) #: ])) y
d=. (x+1) ^ (x:x) goodstein x: s
+/d
)

G=: <:@:goodstein

NB. generates sequence
genSeq=: 3 : 0"1
'base val its'=. y
c=. 0
vals=. val
whilst. its > c=. c+1 do.
  val=. base G val
  vals=. vals,val
  base=. base+1
end.
vals
)

genSeq 2 4 10
 4 26 41 60 83 109 139 173 211 253 299

genSeq 2 19 3
 19 7625597484990 
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084099
 
19110125979454775203564045597039645991980810489900943371395127892465205302426158030...



On Wed, 4/11/18, 'Jon Hough' via Programming  wrote:

 Subject: [Jprogramming] Goodstein Sequences and Hereditary base-n notation
 To: "Programming Forum" 
 Date: Wednesday, April 11, 2018, 5:14 PM
 
 Goodstein's theorem: https://en.wikipedia.org/wiki/Goodstein%27s_theorem
 This states  that every Goodstein
 sequence eventually terminates at 0.
 The wikipedia page defines Goodstein
 sequences in terms of Hereditary base-n notation
 one such sequence is 4,26,41,60...
 
 Copying verbatim from wikipedia:
 ==
 The Goodstein sequence G(m) of a number
 m is a sequence of natural numbers. The first element in the
 sequence G(m) is m itself. To get the second, G(m)(2), write
 m in hereditary base-2 notation, change all the 2s to 3s,
 and then subtract 1 from the result. In general, the
 (n + 1)-st term G(m)(n + 1) of the Goodstein
 sequence of m is as follows:
 
 Take the hereditary base-n + 1
 representation of G(m)(n).
 Replace each occurrence of the
 base-n + 1 with n + 2.
 Subtract one. (Note that the next term
 depends both on the previous term and on the index n.)
 Continue until the result is zero, at
 which point the sequence terminates.
 ===
 
 The sequences take an impossibly long
 time to terminate for most inputs, so there is no use
 writing a verb that iterates until convergance. This is my
 verb that will calculate the first N elements of the
 sequence,
 starting with a given base and val. the
 base should start at 2, to conform to the above definition.
 
 
 goodstein=: 3 : 0
 'base val its'=. y
 vals=. ''
 c=: 0
 whilst.its> c=: c+1 do.
   if. val = 0 do. vals return.
   else.
     t=: ((1+
 >.base^.val)#base) #: val
     if. base < # t do.
       if. 0 < base {
 |.t do.
         tr=: 0
 (base}) |.t
         if.
 (base+1) < # tr do.
           ts=:
 (1+(base+1){tr) ((x+1)}) tr
           ts=:
 |.ts
         else.
           ts=:
 tr,1
           ts=:
 |.ts
         end.
       else. ts=: t end.
     else.
       ts=: t
     end.
     val=. <:(base+1) #.
 ts
     vals=. vals,val
     base=. base+1
   end.
 end.
 vals
 )
 
 
 
 NB. example
 goodstein 2 4 9
 26 41 60 83 109 139 173 211 253 
 NB. continues to very large numbers.
 
  goodstein 2 3 5
 3 3 2 1 0   NB. terminates after 6
 iterations
 
 Is was hoping the goodstein verb could
 be defined tacitly, but my verb is clearly a bit of a mess.
 Just for fun, any elegant solutions?
 
 Thanks,
 Jon
 --
 For information about J forums see http://www.jsoftware.com/forums.htm
--
For information about J forums see http://www.jsoftware.com/forums.htm