Processing math: 100%

Thursday, April 12, 2018

Implementing Goodstein Sequences in J

I recently read about Goodstein sequences for the first time, and was interested in writing a J verb that can generate a sequence. Goodstein sequences are defined here: definition A Goodstein sequence is defined in terms of hereditary representations of numbers. An example of hereditary representation of 100 using base 2. 100=26+25+22=222+2+222+1+22. Let the hereditary representation of n using base 2 be G0(n), i.e. the start of the sequence. Then G1(n) uses the hereditary representation of n base 2, but exchanges 3 for 2 in all places in this representation. Finally, we minus 1. We can continue, so in general, Gm+1(n)=Hm+1(Gm)1 where Ha(x) is the base a hereditary representation of x. For example: G0(100)=100=26+25+22=222+2+222+1+22. G1(100)=333+3+333+1+331=228767924549636. G2(100)=34860300617850752458892464995335199931446351133540222782081259753676586478191222... G3(100)=59814694315693446387155462718734091954899936833389952752466750303416092596593874... This sequence grows explosively fast for most values of n. Interestingly, Goodstein's Theorem states that it will always terminate at 0 eventually. For all positive values of n. Even though it is futile to attempt computing a Goodstein sequence for most values of n, as the numbers involved become unmanageable very quickly, it is still interesting and worthwhile writing a verb to do such a thing. Here is one implementation in J:
goodstein=: 4 : 0"0 0

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

G=: <:@:goodstein`]@.(0&=@:])

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
  if. val = 0 do. break.end.
end.
vals
)
There are three verbs here, goodstein, G, genSeq. goodstein is a recursive dyadic verb which calculates the hereditary representation of the right argument, with base the left argument, and then exchanges occurences of the base by base+1. The reason for the recursion is that for each exponent of the base in the hereditary representation sum, we also need to calculate a hereditary representation. G merely subtracts one from the return value of goodstein.FInally, genSeq, is used to simply generate a sequence. It takes three arguments; the start base (which should be 2); the starting value; the number of iterations to calculate. Example:
genSeq 2 100 3
will return 100 228767924549636 34860300617850752458892464995...

ODBC with J to connect to MySQL Database

If you are using the J programming language and wish to connect to a DBMS (MySQL, PostgreSQL, etc), you can use J's ODBC interface. W...