-
-
Notifications
You must be signed in to change notification settings - Fork 596
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
guessing k-regular sequences #21204
Comments
Commit: |
comment:2
Is it correct that (the generating function If so, then you could reuse the guessing functionality in FriCAS. Of course, FriCAS is not a standard package, although I think it should be, for many reasons. In any case, the guessing package within is fast and well tested, and covers a lot of ground - essentially everything which is available for 1-dimensional guessing. For example:
|
comment:3
Replying to @mantepse:
I've found in the book of Allouche and Shallit: "It is known that k-regular power series satisfy Mahler functional equations; see Rand ́e [1992], Dumas [1993a], and Becker [1994]." so I believe the answer to your question is affirmative.
I didn't know about this feature of FriCAS, but looks good :) Are there any plans to make FriCAS standard (I tried with |
comment:4
Replying to @dkrenn:
How does it fail? That's very bad indeed! |
comment:5
Replying to @mantepse:
Posted on https://groups.google.com/forum/#!topic/sage-devel/6_rBQvKdGPo |
comment:6
this is to update FriCAS: #21209 probably the current version of FriCAS (1.2.7) should compile with current ECL just fine. |
comment:8
The new fricas interface is #21231. It would be very easy to add a dedicated command for guessing k-regular sequences to FriCAS. If this is interesting, I could probably further improve the interface to avoid (Currently, passing long lists to FriCAS is very very slow. But I would like to have at least some confirmation of interest before I spend more time on the interface) |
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
|
comment:10
Replying to @mantepse:
You mean guessing the Mahler functional equation, right?
I think having this would be interesting and good. I am still not sure how exactly I would get the k-regular sequence out of it; I have to dig into this topic a bit further, I guess. (At the moment, I do not see directly, where the parameter k comes into play, as the FriCAS guessing works without this parameter.) As FriCAS is an optional package, I would guess, when having the interface you speak about, would be used as an alternative choice which guessing-algorithm was used. (Maybe even if FriCAS was a standard package...not sure at the moment...)
From what you can suggest by reading the above, I am not sure what the implications for this ticket are. However, having such a functionality of guessing the functional equation would definitely something nice to have in SageMath. |
comment:11
Replying to @dkrenn:
Hm. I actually meant to add a command that guesses the equation for the k-regular sequence. But I just found out that I was slightly mistaken about the nature of k-regular sequences: apparently there is no single equation determining it, but rather a bunch of them, right? It should still be possible to reuse the machinery. |
Branch pushed to git repo; I updated commit sha1. New commits:
|
Branch pushed to git repo; I updated commit sha1. New commits:
|
Branch pushed to git repo; I updated commit sha1. New commits:
|
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
|
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
|
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
|
comment:18
|
comment:38
Sorry, that was a wrong push. I'll fix it soon. |
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
|
Branch pushed to git repo; I updated commit sha1. New commits:
|
Branch pushed to git repo; I updated commit sha1. New commits:
|
Reviewer: Clemens Heuberger |
comment:42
I started reading this and have a lot of questions. I might then have to reread the code because I am not yet confident that I understand everything, so I apologise in advance if some further questions pop up at a later iteration. While reading the code, I tried to make some notes on what the various routines are doing; I pushed those notes to branch
|
…-guess-documentation' into u/dkrenn/sequences/k-regular-guess * cheuberg/u/cheuberg/sequences/k-regular-guess-documentation: Add some further comments Add ALGORITHM section to docstring Trac sagemath#21204: Fix typo Fix pycodestyle issue E306
…ar-warning * t/21204/sequences/k-regular-guess: (11522 commits) Trac sagemath#21204: fixup code and tests Trac sagemath#21204: cherry-pick to avoid merge conflict Trac sagemath#21319: fixup due to changes in dependencies Trac sagemath#21318: fixup due to recent changes in dependencies Updated SageMath version to 9.3 build/pkgs/fplll/spkg-install.in: Configure --without-qd if we use gcc from spkg build/pkgs/fplll/spkg-configure.m4: Add depcheck on gcc build/pkgs/ppl/spkg-configure.m4: Add depcheck on gcc build/pkgs/brial/spkg-configure.m4: Add depcheck on gcc build/pkgs/{freetype,libgd}/spkg-configure.m4: Add depcheck for gcc build/pkgs/zeromq/spkg-configure.m4: Add depcheck for gcc build/pkgs/ntl/spkg-configure.m4: Add depcheck for gcc Trac sagemath#21295 review issue 29: notice minimize vs field Trac sagemath#21295 review issue 7: document accessing coefficients Trac sagemath#21295 review issue 33: rename to number_of_zeros (as it should be) Trac sagemath#21203 review issue 4: rename to coefficient ring Trac sagemath#21295: rename to coefficient_ring Trac sagemath#21203 review issue 3: example for __getitem__ and __iter__ Trac sagemath#21203 review issue 2: extend odds in Pascal's triangle Trac sagemath#21203 review issue 1: better binary sum of digits ...
…ar-warning * t/21204/sequences/k-regular-guess: Trac sagemath#21204: fix punctuation Trac sagemath#21319: fix punctuation Trac sagemath#21318: rmul/lmul preserve identity for multiplying by 1 Trac sagemath#21325: fixup test .subsequence being identity Trac sagemath#21318: rmul/lmul preserve identity for multiplying by 1 Trac sagemath#21325: use (new) decorator minimize_result Trac sagemath#21325: remove empty lines, fix punctuation Trac sagemath#21325: remove iteritems Trac sagemath#21318: fix rmul/lmul issues Trac sagemath#21318: use "correct" 1 Trac sagemath#21318: use tensor_product in method hadamard_product Trac sagemath#21318: use is_trivial_zero in doctest of _neg_ Trac sagemath#21318: use (new) .linear_representation in doctests Trac sagemath#21318: fix empty lines and punctuation Trac sagemath#21318: decorator minimize_result Trac sagemath#21203 review issue 10: use "raise ... from None" where approriate
gh-35896: deal with bad chosen representations of k-regular sequences ### 📚 Description It deals with the situation when mu[0]*right != right in k-regular sequences. Fixes #21343. This PR is created from the branch/code that has been on the corresponding trac ticket + merging in a current SageMath version. See also meta issue #21202. ### 📝 Checklist - [x] The title is concise, informative, and self-explanatory. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [x] I have created tests covering the changes. - [x] I have updated the documentation accordingly. ### ⌛ Dependencies - #21204: guessing k-regular sequences from the first few values No formal dependencies, but there are trivial merge conflicts---in both branches, methods are inserted at the same position in the code--- between: - #21343: deal with mu[0]*right != right in k-regular sequences - #35894: Regular sequences: implement convolution / ring structure URL: #35896 Reported by: Daniel Krenn Reviewer(s): cheuberg, Daniel Krenn
* t/21343/k-regular-warning: (11523 commits) Trac sagemath#21343: adapt to removed transpose-property in dependency Trac sagemath#21204: fixup code and tests Trac sagemath#21204: cherry-pick to avoid merge conflict Trac sagemath#21319: fixup due to changes in dependencies Trac sagemath#21318: fixup due to recent changes in dependencies Updated SageMath version to 9.3 build/pkgs/fplll/spkg-install.in: Configure --without-qd if we use gcc from spkg build/pkgs/fplll/spkg-configure.m4: Add depcheck on gcc build/pkgs/ppl/spkg-configure.m4: Add depcheck on gcc build/pkgs/brial/spkg-configure.m4: Add depcheck on gcc build/pkgs/{freetype,libgd}/spkg-configure.m4: Add depcheck for gcc build/pkgs/zeromq/spkg-configure.m4: Add depcheck for gcc build/pkgs/ntl/spkg-configure.m4: Add depcheck for gcc Trac sagemath#21295 review issue 29: notice minimize vs field Trac sagemath#21295 review issue 7: document accessing coefficients Trac sagemath#21295 review issue 33: rename to number_of_zeros (as it should be) Trac sagemath#21203 review issue 4: rename to coefficient ring Trac sagemath#21295: rename to coefficient_ring Trac sagemath#21203 review issue 3: example for __getitem__ and __iter__ Trac sagemath#21203 review issue 2: extend odds in Pascal's triangle ...
Code for guessing the parameters of k-regular sequences from the first few entries of a list/sequence/etc.
See also Meta ticket #21202.
Depends on #21319
CC: @rwst
Component: combinatorics
Author: Daniel Krenn
Branch/Commit: u/cheuberg/sequences/k-regular-guess @
ae06d17
Reviewer: Clemens Heuberger
Issue created by migration from https://trac.sagemath.org/ticket/21204
The text was updated successfully, but these errors were encountered: