[sage-devel] Recurrences and Sequence Formula Guessing Functions in Sage

[Maxie Schmidt]

Hello,

I have been working back and forth between Sage and Mathematica for a while
now trying to learn how to use Sage to replace Mathematica's core
functionality in my day to day use of it. One of the (sets of) functions
haven't yet found a suitable open source alternative for is related to
guessing formulas and generating functions for an input sequence (as in
Mathematica's FindSequenceFunction and FindGeneratingFunction). Related
functions are Mathematica's RSolve
(https://reference.wolfram.com/language/ref/RSolve.html?q=RSolve) used to
solve recurrence relations in closed-form formulas, and the closed-source
RISC Sigma package
(https://www.risc.jku.at/research/combinat/risc/software/Sigma/index.php)
which is able to generate recurrences for many sums and simplify sums
involving harmonic numbers.

The closest open source alternative I have come across so far is Rubey's
software written in FriCAS described at
http://axiom-wiki.newsynthesis.org/GuessingFormulasForSequences. However,
looking at the source code for the package leaves quite a bit of work to do
to reproduce the output of the Mathematica functions mentioned above. Is
there a better open source alternative to the Mathematica functions
FindSequenceFunction and RSolve that I'm missing in Sage?

If there isn't a good complete replacement for using Mathematica's routines
for sequence formula guessing and solving recurrences, I'm interested in
trying to write functions / packages that will replace Mathematica for
these tasks. I have already done some work in Sage related to guessing
formulas for special polynomial sequences in my Master's thesis at UIUC
posted at https://arxiv.org/abs/1609.07301. Any suggestions or links to
related open source software are appreciated.

Sincerely,

Maxie

['Martin R' via sage-devel]

I'd be interested in what output you'd like to have.

The hard part in the FriCAS package was to get decent speed, changing
output should be relatively straightforward.

(I guess that you are aware of the possibility of using the package from
within sage)

Martin

Post by Maxie Schmidt
Hello,
I have been working back and forth between Sage and Mathematica for a
while now trying to learn how to use Sage to replace Mathematica's core
functionality in my day to day use of it. One of the (sets of) functions
haven't yet found a suitable open source alternative for is related to
guessing formulas and generating functions for an input sequence (as in
Mathematica's FindSequenceFunction and FindGeneratingFunction). Related
functions are Mathematica's RSolve (
https://reference.wolfram.com/language/ref/RSolve.html?q=RSolve) used to
solve recurrence relations in closed-form formulas, and the closed-source
RISC Sigma package (
https://www.risc.jku.at/research/combinat/risc/software/Sigma/index.php)
which is able to generate recurrences for many sums and simplify sums
involving harmonic numbers.
The closest open source alternative I have come across so far is Rubey's
software written in FriCAS described at
http://axiom-wiki.newsynthesis.org/GuessingFormulasForSequences. However,
looking at the source code for the package leaves quite a bit of work to do
to reproduce the output of the Mathematica functions mentioned above. Is
there a better open source alternative to the Mathematica functions
FindSequenceFunction and RSolve that I'm missing in Sage?
If there isn't a good complete replacement for using Mathematica's
routines for sequence formula guessing and solving recurrences, I'm
interested in trying to write functions / packages that will replace
Mathematica for these tasks. I have already done some work in Sage related
to guessing formulas for special polynomial sequences in my Master's thesis
at UIUC posted at https://arxiv.org/abs/1609.07301. Any suggestions or
links to related open source software are appreciated.
Sincerely,
Maxie

[Maxie Schmidt]

I'm aware that the FriCAS package can be called from within Sage / Python,
and I don't see any reason to rewrite what's already there, just extend
it's current recognition capabilities and put a nice friendly wrapper
function around all of these disparate routines. Something like
find_sequence_formula([1,1,2,3,5,8,13]) or
find_polynomial_generating_function([...], x) would be nice. I'm willing to
work on writing the wrapper functions and help with extending the sequence
recognition capabilities that are already there. It's been a little while
since I've seriously thought about writing this sort of function in Sage,
but my intuition is that the FriCAS package can already pick up a lot of
what FindSequenceFunction will recognize out of the box.

I can / should put together a long list of sequence test cases that I'd
like to see recognized by these routines in Sage. Anything that's in the
Wolfram / Mathematica documentation is on the list. Also, sequences
involving factors, or polynomial multiples of, special sequences like the
Stirling, Bernoulli, and r-order harmonic numbers are something I'd like to
see.

How much does the existing FriCAS rely on being able to find a homogeneous
recurrence for the input sequences? There are a number of examples of sums
involving the Stirling and Bernoulli numbers that cannot be expressed this
way. Also, Mathematica tends to ignore closed-form sequence expressions
involving harmonic numbers (say for known formulas satisfied by the
Stirling numbers of the first kind), whereas if we have the FriCAS
package's analog to the RISC Guess package along with an OSS version of
Sigma and RSolve, these expressions are easy to obtain. These are just some
suggestions at a starting point for replacing my having to switch over to
Mathematica when I need sequence recognition functions.

Maxie

Post by 'Martin R' via sage-devel
I'd be interested in what output you'd like to have.
The hard part in the FriCAS package was to get decent speed, changing
output should be relatively straightforward.
(I guess that you are aware of the possibility of using the package from
within sage)
Martin

Post by Maxie Schmidt
Hello,
I have been working back and forth between Sage and Mathematica for a
while now trying to learn how to use Sage to replace Mathematica's core
functionality in my day to day use of it. One of the (sets of) functions
haven't yet found a suitable open source alternative for is related to
guessing formulas and generating functions for an input sequence (as in
Mathematica's FindSequenceFunction and FindGeneratingFunction). Related
functions are Mathematica's RSolve (
https://reference.wolfram.com/language/ref/RSolve.html?q=RSolve) used to
solve recurrence relations in closed-form formulas, and the closed-source
RISC Sigma package (
https://www.risc.jku.at/research/combinat/risc/software/Sigma/index.php)
which is able to generate recurrences for many sums and simplify sums
involving harmonic numbers.
The closest open source alternative I have come across so far is Rubey's
software written in FriCAS described at
http://axiom-wiki.newsynthesis.org/GuessingFormulasForSequences.
However, looking at the source code for the package leaves quite a bit of
work to do to reproduce the output of the Mathematica functions mentioned
above. Is there a better open source alternative to the Mathematica
functions FindSequenceFunction and RSolve that I'm missing in Sage?
If there isn't a good complete replacement for using Mathematica's
routines for sequence formula guessing and solving recurrences, I'm
interested in trying to write functions / packages that will replace
Mathematica for these tasks. I have already done some work in Sage related
to guessing formulas for special polynomial sequences in my Master's thesis
at UIUC posted at https://arxiv.org/abs/1609.07301. Any suggestions or
links to related open source software are appreciated.
Sincerely,
Maxie

[Dima Pasechnik]

Needless to say perhaps, but Maxima has some capabilities in this respect,
not sure how much of it is exposed in Sage.

E.g. ggf should be able to do rational generating functions:
http://maxima.sourceforge.net/docs/manual/maxima_60.html#Item_003a-ggf

And it does have things like Gosper and Zeilberger algorithms for finding
generating functions
implemented too.
http://maxima.sourceforge.net/docs/manual/maxima_87.html#Item_003a-Introduction-to-zeilberger

Post by Maxie Schmidt
I'm aware that the FriCAS package can be called from within Sage / Python,
and I don't see any reason to rewrite what's already there, just extend
it's current recognition capabilities and put a nice friendly wrapper
function around all of these disparate routines. Something like
find_sequence_formula([1,1,2,3,5,8,13]) or
find_polynomial_generating_function([...], x) would be nice. I'm willing to
work on writing the wrapper functions and help with extending the sequence
recognition capabilities that are already there. It's been a little while
since I've seriously thought about writing this sort of function in Sage,
but my intuition is that the FriCAS package can already pick up a lot of
what FindSequenceFunction will recognize out of the box.
I can / should put together a long list of sequence test cases that I'd
like to see recognized by these routines in Sage. Anything that's in the
Wolfram / Mathematica documentation is on the list. Also, sequences
involving factors, or polynomial multiples of, special sequences like the
Stirling, Bernoulli, and r-order harmonic numbers are something I'd like to
see.
How much does the existing FriCAS rely on being able to find a homogeneous
recurrence for the input sequences? There are a number of examples of sums
involving the Stirling and Bernoulli numbers that cannot be expressed this
way. Also, Mathematica tends to ignore closed-form sequence expressions
involving harmonic numbers (say for known formulas satisfied by the
Stirling numbers of the first kind), whereas if we have the FriCAS
package's analog to the RISC Guess package along with an OSS version of
Sigma and RSolve, these expressions are easy to obtain. These are just some
suggestions at a starting point for replacing my having to switch over to
Mathematica when I need sequence recognition functions.
Maxie

Post by 'Martin R' via sage-devel
I'd be interested in what output you'd like to have.
The hard part in the FriCAS package was to get decent speed, changing
output should be relatively straightforward.
(I guess that you are aware of the possibility of using the package from
within sage)
Martin

Post by Maxie Schmidt
Hello,
I have been working back and forth between Sage and Mathematica for a
while now trying to learn how to use Sage to replace Mathematica's core
functionality in my day to day use of it. One of the (sets of) functions
haven't yet found a suitable open source alternative for is related to
guessing formulas and generating functions for an input sequence (as in
Mathematica's FindSequenceFunction and FindGeneratingFunction). Related
functions are Mathematica's RSolve (
https://reference.wolfram.com/language/ref/RSolve.html?q=RSolve) used
to solve recurrence relations in closed-form formulas, and the
closed-source RISC Sigma package (
https://www.risc.jku.at/research/combinat/risc/software/Sigma/index.php)
which is able to generate recurrences for many sums and simplify sums
involving harmonic numbers.
The closest open source alternative I have come across so far is Rubey's
software written in FriCAS described at
http://axiom-wiki.newsynthesis.org/GuessingFormulasForSequences.
However, looking at the source code for the package leaves quite a bit of
work to do to reproduce the output of the Mathematica functions mentioned
above. Is there a better open source alternative to the Mathematica
functions FindSequenceFunction and RSolve that I'm missing in Sage?
If there isn't a good complete replacement for using Mathematica's
routines for sequence formula guessing and solving recurrences, I'm
interested in trying to write functions / packages that will replace
Mathematica for these tasks. I have already done some work in Sage related
to guessing formulas for special polynomial sequences in my Master's thesis
at UIUC posted at https://arxiv.org/abs/1609.07301. Any suggestions or
links to related open source software are appreciated.
Sincerely,
Maxie

['Martin R' via sage-devel]

out off the box, the FriCAS package can do the following (described in some
detail in https://arxiv.org/abs/math/0702086, the journal published a
shortened version):

1) Generating functions:

* rational (guessPade)
* algebraic (guessAlg)
* linear diffeq (guessHolo)
* polynomial diffeq (guessADE)

* Mahler type functional equations (guessFE)

* algebraic dependencies between a list of generating functions
(guessAlgDep)

2) Recurrences:

* linear, polynomial coefficients (guessPRec)
* polynomial, polynomial coefficients (guessRec)

3) Nested sums and products of the form sum_{k=1}^n f(k) and \prod_{k=1}^n
f(k), the most useful case being where f is a rational function in k. Note
that f must not depend on n, unfortunately.

4) Moreover, some special forms (guessBinRat, guessExpRat), which were not
really successful.

All of this works for lists of integers, algebraic numbers, polynomials,
and over finite fields.
Also, there are q-analogues of all these (most interesting are probably
q-differential equations).

There are some options, that can be used to restrict the search space, for
example, restricting to homogeneous differential equations, restricting the
degree of the polynomial coefficients, etc. If there is sufficient
interest, Jay Pantone found a (heuristically) better search space for
polynomial diffeqs, which would be straightforward to implement.

Martin

['Martin R' via sage-devel]

I forgot to add: once a diffeq for a generating function is found, the
package can also give you the 1783-th coefficient of the generating
function.

And, most importantly: the main thing to do to make it really useful for
sage, is to implement a better conversion from sage lists to fricas lists,
bypassing pexpect. This is possible (Waldek Hebisch provided the necessary
bits on the FriCAS side), but some work.

Martin

[Fredrik Johansson]

Post by Maxie Schmidt
Hello,
I have been working back and forth between Sage and Mathematica for a
while now trying to learn how to use Sage to replace Mathematica's core
functionality in my day to day use of it. One of the (sets of) functions
haven't yet found a suitable open source alternative for is related to
guessing formulas and generating functions for an input sequence (as in
Mathematica's FindSequenceFunction and FindGeneratingFunction). Related
functions are Mathematica's RSolve (
https://reference.wolfram.com/language/ref/RSolve.html?q=RSolve) used to
solve recurrence relations in closed-form formulas, and the closed-source
RISC Sigma package (
https://www.risc.jku.at/research/combinat/risc/software/Sigma/index.php)
which is able to generate recurrences for many sums and simplify sums
involving harmonic numbers.
The closest open source alternative I have come across so far is Rubey's
software written in FriCAS described at
http://axiom-wiki.newsynthesis.org/GuessingFormulasForSequences. However,
looking at the source code for the package leaves quite a bit of work to do
to reproduce the output of the Mathematica functions mentioned above. Is
there a better open source alternative to the Mathematica functions
FindSequenceFunction and RSolve that I'm missing in Sage?
If there isn't a good complete replacement for using Mathematica's
routines for sequence formula guessing and solving recurrences, I'm
interested in trying to write functions / packages that will replace
Mathematica for these tasks. I have already done some work in Sage related
to guessing formulas for special polynomial sequences in my Master's thesis
at UIUC posted at https://arxiv.org/abs/1609.07301. Any suggestions or
links to related open source software are appreciated.

Open source alternatives to Mathematica would be most welcome.

The ore_algebra package allows guessing holonomic sequences
(http://www.risc.jku.at/research/combinat/software/ore_algebra/doc/guessing.html)
but there is nothing in Sage for closed forms, Stirling-type sequences or
multi-sums as far as I know.

Fredrik

[David Roe]

Another thing that might be nice to tie in is the Online Encyclopedia of
Integer Sequences. Or at least include a link in the documentation, though
most people looking to guess a sequence will already be aware of OEIS.
David

On Sat, Nov 19, 2016 at 2:00 PM, Fredrik Johansson <

Post by Fredrik Johansson

Post by Maxie Schmidt
Hello,
I have been working back and forth between Sage and Mathematica for a
while now trying to learn how to use Sage to replace Mathematica's core
functionality in my day to day use of it. One of the (sets of) functions
haven't yet found a suitable open source alternative for is related to
guessing formulas and generating functions for an input sequence (as in
Mathematica's FindSequenceFunction and FindGeneratingFunction). Related
functions are Mathematica's RSolve (https://reference.wolfram.com
/language/ref/RSolve.html?q=RSolve) used to solve recurrence relations
in closed-form formulas, and the closed-source RISC Sigma package (
https://www.risc.jku.at/research/combinat/risc/software/Sigma/index.php)
which is able to generate recurrences for many sums and simplify sums
involving harmonic numbers.
The closest open source alternative I have come across so far is Rubey's
software written in FriCAS described at http://axiom-wiki.newsynthesis
.org/GuessingFormulasForSequences. However, looking at the source code
for the package leaves quite a bit of work to do to reproduce the output of
the Mathematica functions mentioned above. Is there a better open source
alternative to the Mathematica functions FindSequenceFunction and RSolve
that I'm missing in Sage?
If there isn't a good complete replacement for using Mathematica's
routines for sequence formula guessing and solving recurrences, I'm
interested in trying to write functions / packages that will replace
Mathematica for these tasks. I have already done some work in Sage related
to guessing formulas for special polynomial sequences in my Master's thesis
at UIUC posted at https://arxiv.org/abs/1609.07301. Any suggestions or
links to related open source software are appreciated.

Open source alternatives to Mathematica would be most welcome.
The ore_algebra package allows guessing holonomic sequences (
http://www.risc.jku.at/research/combinat/software/
ore_algebra/doc/guessing.html) but there is nothing in Sage for closed
forms, Stirling-type sequences or multi-sums as far as I know.
Fredrik
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[Thierry]

Post by David Roe
Another thing that might be nice to tie in is the Online Encyclopedia of
Integer Sequences. Or at least include a link in the documentation, though
most people looking to guess a sequence will already be aware of OEIS.
David

sage: oeis?

Post by David Roe
On Sat, Nov 19, 2016 at 2:00 PM, Fredrik Johansson <

Post by Fredrik Johansson

Post by Maxie Schmidt
Hello,
I have been working back and forth between Sage and Mathematica for a
while now trying to learn how to use Sage to replace Mathematica's core
functionality in my day to day use of it. One of the (sets of) functions
haven't yet found a suitable open source alternative for is related to
guessing formulas and generating functions for an input sequence (as in
Mathematica's FindSequenceFunction and FindGeneratingFunction). Related
functions are Mathematica's RSolve (https://reference.wolfram.com
/language/ref/RSolve.html?q=RSolve) used to solve recurrence relations
in closed-form formulas, and the closed-source RISC Sigma package (
https://www.risc.jku.at/research/combinat/risc/software/Sigma/index.php)
which is able to generate recurrences for many sums and simplify sums
involving harmonic numbers.
The closest open source alternative I have come across so far is Rubey's
software written in FriCAS described at http://axiom-wiki.newsynthesis
.org/GuessingFormulasForSequences. However, looking at the source code
for the package leaves quite a bit of work to do to reproduce the output of
the Mathematica functions mentioned above. Is there a better open source
alternative to the Mathematica functions FindSequenceFunction and RSolve
that I'm missing in Sage?
If there isn't a good complete replacement for using Mathematica's
routines for sequence formula guessing and solving recurrences, I'm
interested in trying to write functions / packages that will replace
Mathematica for these tasks. I have already done some work in Sage related
to guessing formulas for special polynomial sequences in my Master's thesis
at UIUC posted at https://arxiv.org/abs/1609.07301. Any suggestions or
links to related open source software are appreciated.

Open source alternatives to Mathematica would be most welcome.
The ore_algebra package allows guessing holonomic sequences (
http://www.risc.jku.at/research/combinat/software/
ore_algebra/doc/guessing.html) but there is nothing in Sage for closed
forms, Stirling-type sequences or multi-sums as far as I know.
Fredrik
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[David Roe]

Post by Maxie Schmidt

Post by David Roe
Another thing that might be nice to tie in is the Online Encyclopedia of
Integer Sequences. Or at least include a link in the documentation,

though

Post by David Roe
most people looking to guess a sequence will already be aware of OEIS.
David

sage: oeis?

I just meant, in whatever functions Maxie is planning on writing, either
use oeis as (part of) one of the guessing regimes, or at least include a
link to Sage's oeis function in the docstring.
David

Post by Maxie Schmidt

Post by David Roe
On Sat, Nov 19, 2016 at 2:00 PM, Fredrik Johansson <

On Saturday, November 19, 2016 at 4:56:42 PM UTC+1, Maxie Schmidt

Post by Maxie Schmidt
Hello,
I have been working back and forth between Sage and Mathematica for a
while now trying to learn how to use Sage to replace Mathematica's

core

Post by David Roe

Post by Maxie Schmidt
functionality in my day to day use of it. One of the (sets of)

functions

Post by David Roe

Post by Maxie Schmidt
haven't yet found a suitable open source alternative for is related to
guessing formulas and generating functions for an input sequence (as

in

Post by David Roe

Post by Maxie Schmidt
Mathematica's FindSequenceFunction and FindGeneratingFunction).

Related

Post by David Roe

Post by Maxie Schmidt
functions are Mathematica's RSolve (https://reference.wolfram.com
/language/ref/RSolve.html?q=RSolve) used to solve recurrence

relations

Post by David Roe

Post by Maxie Schmidt
in closed-form formulas, and the closed-source RISC Sigma package (
https://www.risc.jku.at/research/combinat/risc/

software/Sigma/index.php)

Post by David Roe

Post by Maxie Schmidt
which is able to generate recurrences for many sums and simplify sums
involving harmonic numbers.
The closest open source alternative I have come across so far is

Rubey's

Post by David Roe

Post by Maxie Schmidt
software written in FriCAS described at

http://axiom-wiki.newsynthesis

Post by David Roe

Post by Maxie Schmidt
.org/GuessingFormulasForSequences. However, looking at the source

code

Post by David Roe

Post by Maxie Schmidt
for the package leaves quite a bit of work to do to reproduce the

output of

Post by David Roe

Post by Maxie Schmidt
the Mathematica functions mentioned above. Is there a better open

source

Post by David Roe

Post by Maxie Schmidt
alternative to the Mathematica functions FindSequenceFunction and

RSolve

Post by David Roe

Post by Maxie Schmidt
that I'm missing in Sage?
If there isn't a good complete replacement for using Mathematica's
routines for sequence formula guessing and solving recurrences, I'm
interested in trying to write functions / packages that will replace
Mathematica for these tasks. I have already done some work in Sage

related

Post by David Roe

Post by Maxie Schmidt
to guessing formulas for special polynomial sequences in my Master's

thesis

Post by David Roe

Post by Maxie Schmidt
at UIUC posted at https://arxiv.org/abs/1609.07301. Any suggestions

or

Post by David Roe

Post by Maxie Schmidt
links to related open source software are appreciated.

Open source alternatives to Mathematica would be most welcome.
The ore_algebra package allows guessing holonomic sequences (
http://www.risc.jku.at/research/combinat/software/
ore_algebra/doc/guessing.html) but there is nothing in Sage for closed
forms, Stirling-type sequences or multi-sums as far as I know.
Fredrik
--
You received this message because you are subscribed to the Google

Groups

Post by David Roe

"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send

an

Post by David Roe

Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google

Groups "sage-devel" group.

Post by David Roe
To unsubscribe from this group and stop receiving emails from it, send
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[Maxie Schmidt]

Thanks for all of the suggestions. I think I will start by getting all of
Martin's package routines working under a single wrapper function and try
to improve from there. I will definitely include options to search the OEIS
database.

The only thing I'm a little concerned about if this would eventually get
bundled in Sage is getting the FriCAS source for the first package
installed. My Debian box doesn't have FriCAS or Axiom bundled with my from
source Sage install, and I remember a while back having multiple issues
getting FriCAS installed on a Gentoo machine.

Maxie

Post by David Roe

Post by Maxie Schmidt

Post by David Roe
Another thing that might be nice to tie in is the Online Encyclopedia of
Integer Sequences. Or at least include a link in the documentation,

though

Post by David Roe
most people looking to guess a sequence will already be aware of OEIS.
David

sage: oeis?

I just meant, in whatever functions Maxie is planning on writing, either
use oeis as (part of) one of the guessing regimes, or at least include a
link to Sage's oeis function in the docstring.
David

Post by Maxie Schmidt

Post by David Roe
On Sat, Nov 19, 2016 at 2:00 PM, Fredrik Johansson <

On Saturday, November 19, 2016 at 4:56:42 PM UTC+1, Maxie Schmidt

Post by Maxie Schmidt
Hello,
I have been working back and forth between Sage and Mathematica for a
while now trying to learn how to use Sage to replace Mathematica's

core

Post by David Roe

Post by Maxie Schmidt
functionality in my day to day use of it. One of the (sets of)

functions

Post by David Roe

Post by Maxie Schmidt
haven't yet found a suitable open source alternative for is related

to

Post by David Roe

Post by Maxie Schmidt
guessing formulas and generating functions for an input sequence (as

in

Post by David Roe

Post by Maxie Schmidt
Mathematica's FindSequenceFunction and FindGeneratingFunction).

Related

Post by David Roe

Post by Maxie Schmidt
functions are Mathematica's RSolve (https://reference.wolfram.com
/language/ref/RSolve.html?q=RSolve) used to solve recurrence

relations

Post by David Roe

Post by Maxie Schmidt
in closed-form formulas, and the closed-source RISC Sigma package (

https://www.risc.jku.at/research/combinat/risc/software/Sigma/index.php)

Post by David Roe

Post by Maxie Schmidt
which is able to generate recurrences for many sums and simplify sums
involving harmonic numbers.
The closest open source alternative I have come across so far is

Rubey's

Post by David Roe

Post by Maxie Schmidt
software written in FriCAS described at

http://axiom-wiki.newsynthesis

Post by David Roe

Post by Maxie Schmidt
.org/GuessingFormulasForSequences. However, looking at the source

code

Post by David Roe

Post by Maxie Schmidt
for the package leaves quite a bit of work to do to reproduce the

output of

Post by David Roe

Post by Maxie Schmidt
the Mathematica functions mentioned above. Is there a better open

source

Post by David Roe

Post by Maxie Schmidt
alternative to the Mathematica functions FindSequenceFunction and

RSolve

Post by David Roe

Post by Maxie Schmidt
that I'm missing in Sage?
If there isn't a good complete replacement for using Mathematica's
routines for sequence formula guessing and solving recurrences, I'm
interested in trying to write functions / packages that will replace
Mathematica for these tasks. I have already done some work in Sage

related

Post by David Roe

Post by Maxie Schmidt
to guessing formulas for special polynomial sequences in my Master's

thesis

Post by David Roe

Post by Maxie Schmidt
at UIUC posted at https://arxiv.org/abs/1609.07301. Any suggestions

or

Post by David Roe

Post by Maxie Schmidt
links to related open source software are appreciated.

Open source alternatives to Mathematica would be most welcome.
The ore_algebra package allows guessing holonomic sequences (
http://www.risc.jku.at/research/combinat/software/
ore_algebra/doc/guessing.html) but there is nothing in Sage for closed
forms, Stirling-type sequences or multi-sums as far as I know.
Fredrik
--
You received this message because you are subscribed to the Google

Groups

Post by David Roe

"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it,

send an
<javascript:>.

Post by David Roe

Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google

Groups "sage-devel" group.

Post by David Roe
To unsubscribe from this group and stop receiving emails from it, send

<javascript:>.

Post by David Roe
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an
<javascript:>.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

['Martin R' via sage-devel]

Post by Maxie Schmidt
Thanks for all of the suggestions. I think I will start by getting all of
Martin's package routines working under a single wrapper function and try
to improve from there.

I think that one question is how you want to represent the result of a
"guess". The fricas package always returns a list of elements of the
fricas domain "Expression Integer", which is roughly equivalent to
SymbolicRing in sage. For example:

sage: list_g = fricas("guessADE([n^n/factorial n for n in 1..40])"); list_g

2 3
n , 3 2 9x 32x 4
[[[x ]f(x): - f (x) + x f(x) + 2f(x) = 0,f(x)= 1 + 2x + --- + ---- + O(x
)]]
2 3
sage: g = list_g[0]
sage: g.eval("[n=50]")

2635987571800400710022355920186541715689493871043967230302851194475838001
-------------------------------------------------------------------------
3353585829598799392450336149309868736512000000000000

The FriCAS "type" of g above is Expression Integer, but I don't think there
is an exact equivalent in the current SymbolicRing, because g contains the
differential equation, the initial values and (hidden in the display) a
(slow, but generic) function that computes an arbitrary term.

I assume a convenient possibility would be to create a sage class that
wraps this information...


The only thing I'm a little concerned about if this would eventually get

Post by Maxie Schmidt
bundled in Sage is getting the FriCAS source for the first package
installed. My Debian box doesn't have FriCAS or Axiom bundled with my
from source Sage install, and I remember a while back having multiple
issues getting FriCAS installed on a Gentoo machine.

Are you saying that "sage -i fricas" does/did not work?

Martin

[Dima Pasechnik]

Post by Maxie Schmidt
Thanks for all of the suggestions. I think I will start by getting all of
Martin's package routines working under a single wrapper function and try
to improve from there. I will definitely include options to search the OEIS
database.
The only thing I'm a little concerned about if this would eventually get
bundled in Sage is getting the FriCAS source for the first package
installed. My Debian box doesn't have FriCAS or Axiom bundled with my from
source Sage install

Fricas is an experimental Sage package.
Just do

./sage -i fricas

Assuming that your ./sage is in good shape (say, compiled from source),
you'll be all set.

, and I remember a while back having multiple issues getting FriCAS

Post by Maxie Schmidt
installed on a Gentoo machine.
Maxie

Post by David Roe

Post by Maxie Schmidt

Post by David Roe
Another thing that might be nice to tie in is the Online Encyclopedia

of

Post by David Roe
Integer Sequences. Or at least include a link in the documentation,

though

Post by David Roe
most people looking to guess a sequence will already be aware of OEIS.
David

sage: oeis?

I just meant, in whatever functions Maxie is planning on writing, either
use oeis as (part of) one of the guessing regimes, or at least include a
link to Sage's oeis function in the docstring.
David

Post by Maxie Schmidt

Post by David Roe
On Sat, Nov 19, 2016 at 2:00 PM, Fredrik Johansson <

On Saturday, November 19, 2016 at 4:56:42 PM UTC+1, Maxie Schmidt

Post by Maxie Schmidt
Hello,
I have been working back and forth between Sage and Mathematica for

a

Post by David Roe

Post by Maxie Schmidt
while now trying to learn how to use Sage to replace Mathematica's

core

Post by David Roe

Post by Maxie Schmidt
functionality in my day to day use of it. One of the (sets of)

functions

Post by David Roe

Post by Maxie Schmidt
haven't yet found a suitable open source alternative for is related

to

Post by David Roe

Post by Maxie Schmidt
guessing formulas and generating functions for an input sequence

(as in

Post by David Roe

Post by Maxie Schmidt
Mathematica's FindSequenceFunction and FindGeneratingFunction).

Related

Post by David Roe

Post by Maxie Schmidt
functions are Mathematica's RSolve (https://reference.wolfram.com
/language/ref/RSolve.html?q=RSolve) used to solve recurrence

relations

Post by David Roe

Post by Maxie Schmidt
in closed-form formulas, and the closed-source RISC Sigma package (

https://www.risc.jku.at/research/combinat/risc/software/Sigma/index.php)

Post by David Roe

Post by Maxie Schmidt
which is able to generate recurrences for many sums and simplify

sums

Post by David Roe

Post by Maxie Schmidt
involving harmonic numbers.
The closest open source alternative I have come across so far is

Rubey's

Post by David Roe

Post by Maxie Schmidt
software written in FriCAS described at

http://axiom-wiki.newsynthesis

Post by David Roe

Post by Maxie Schmidt
.org/GuessingFormulasForSequences. However, looking at the source

code

Post by David Roe

Post by Maxie Schmidt
for the package leaves quite a bit of work to do to reproduce the

output of

Post by David Roe

Post by Maxie Schmidt
the Mathematica functions mentioned above. Is there a better open

source

Post by David Roe

Post by Maxie Schmidt
alternative to the Mathematica functions FindSequenceFunction and

RSolve

Post by David Roe

Post by Maxie Schmidt
that I'm missing in Sage?
If there isn't a good complete replacement for using Mathematica's
routines for sequence formula guessing and solving recurrences, I'm
interested in trying to write functions / packages that will replace
Mathematica for these tasks. I have already done some work in Sage

related

Post by David Roe

Post by Maxie Schmidt
to guessing formulas for special polynomial sequences in my

Master's thesis

Post by David Roe

Post by Maxie Schmidt
at UIUC posted at https://arxiv.org/abs/1609.07301. Any

suggestions or

Post by David Roe

Post by Maxie Schmidt
links to related open source software are appreciated.

Open source alternatives to Mathematica would be most welcome.
The ore_algebra package allows guessing holonomic sequences (
http://www.risc.jku.at/research/combinat/software/
ore_algebra/doc/guessing.html) but there is nothing in Sage for

closed

Post by David Roe

forms, Stirling-type sequences or multi-sums as far as I know.
Fredrik
--
You received this message because you are subscribed to the Google

Groups

Post by David Roe

"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it,

send an

Post by David Roe

Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google

Groups "sage-devel" group.

Post by David Roe
To unsubscribe from this group and stop receiving emails from it, send
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google
Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[Peter Luschny]

One of the (sets of) functions haven't yet found a suitable open source

alternative

for is related to guessing formulas and generating functions for an input

sequence

(as in Mathematica's FindSequenceFunction and FindGeneratingFunction).

I am amazed that no one has yet mentioned Gfun, the classic Maple package
for
the manipulation of generating functions by Bruno Salvy and others which is
released under the GNU Lesser General Public License (LGPL v2.1).

http://perso.ens-lyon.fr/bruno.salvy/software/the-gfun-package/
http://www.swmath.org/software/344
https://scm.gforge.inria.fr/anonscm/gitweb/?p=gfun/gfun.git;a=tree

Peter

[Ralf Stephan]

1. Sage can guess rational generating functions and provide formulae for
experimental math:

sage: C.<x> = CFiniteSequences(QQ)
sage: C.guess([1,3,5,7,9,11,13])
C-finite sequence, generated by (x + 1)/(x^2 - 2*x + 1)
sage: _.closed_form()
2*n + 1
sage: C.guess([0,1,1,2,3,5,8,13,21]).closed_form()
1/5*sqrt(5)*(1/2*sqrt(5) + 1/2)^n - 1/5*sqrt(5)*(-1/2*sqrt(5) + 1/2)^n

2.As to guessing holonomic recurrences there is the Ore algebra package. It
would be nice to have a tutorial.

3. Subham Tibra has added a holonomic function package to SymPy:
http://docs.sympy.org/dev/modules/holonomic/index.html
which is however in a newer version than the SymPy in Sage

Regards,

['Martin R' via sage-devel]

Did anybody ever compare the possibilities speed-wise?

The scope of these packages is quite different: ore_algebra is for the
holonomic and q-holonomic universe, the guessing facility in fricas is for
guessing only - but covers also polynomial recurrences and differential
equations (and their q-analogues), functional equations, etc...

Two remarks:

* the ore_algebra package is currently broken, see #21344.
* gfun is free, but maple is not.

Martin

['Martin R' via sage-devel]

Post by Ralf Stephan
2.As to guessing holonomic recurrences there is the Ore algebra package.
It would be nice to have a tutorial.

what's wrong with https://arxiv.org/abs/1306.4263 ?

Martin

[Ralf Stephan]

Post by Ralf Stephan
2.As to guessing holonomic recurrences there is the Ore algebra package.

Post by Ralf Stephan
It would be nice to have a tutorial.

what's wrong with https://arxiv.org/abs/1306.4263 ?

Let me rephrase that. It would be nice to have ore-algebra as standard
package and a Sage-internal tutorial.

[Maxie Schmidt]

I have a working draft of the sage code for sequence formula guessing
posted at https://github.com/maxieds/sage-guess. I'm still very much
working on adding the documentation / doc strings. Besides this, does
anyone else have any suggestions for what else I could add to this package
to improve it? It's obviously missing support for polynomial sequences
right now. I'm planning on adding a tracking ticket and a tutorial once I
have the documentation done and more tests written.

Maxie

[Dima Pasechnik]

Post by Maxie Schmidt
I have a working draft of the sage code for sequence formula guessing
posted at https://github.com/maxieds/sage-guess. I'm still very much
working on adding the documentation / doc strings. Besides this, does
anyone else have any suggestions for what else I could add to this package
to improve it? It's obviously missing support for polynomial sequences
right now. I'm planning on adding a tracking ticket and a tutorial once I
have the documentation done and more tests written.
Maxie

I just did a pull request there to make that code run with current Sage.