5
$\begingroup$

I am curious about the algorithm used by Mathematica's FindSequenceFunction to identify patterns in sequences. This function is powerful in finding closed-form expressions for a wide range of sequences. I would like to know the details of the algorithm it employs to achieve this.

Furthermore, I am interested in replicating this functionality in a programming language like Python. Is the algorithm used by FindSequenceFunction publicly available, or is it a proprietary method developed by Wolfram Research? If it is available, are there any existing Python libraries or implementations that I can use to achieve similar results?

Additionally, I would appreciate any insights into how the function handles different types of sequences, such as those involving rational numbers, and how it determines the complexity of the sequence to decide whether to return a result or not.

Lastly, are there any specific techniques or methods that I can use to write a similar function from scratch in Python, and what would be the key challenges in doing so?

$\endgroup$
3
  • 1
    $\begingroup$ Some folks a few years ago had a website that (they claimed) outperformed FindSequenceFunction and similar functions in other systems. It did on their examples. Then the website went down, and I can't find any notes about it. I probably thought idiotically that the internet was forever. $\endgroup$
    – Michael E2
    Commented Jun 17 at 14:44
  • 1
    $\begingroup$ Try TracePrint[FindSequenceFunction[{1, 1, 2, 3, 5, 8}, n]]? $\endgroup$
    – 138 Aspen
    Commented Jun 17 at 15:41
  • 1
    $\begingroup$ "I am interested in replicating this functionality in a programming language like Python." It will not be easy. Look at the history of developments of SageMath and FriCAS. About guessing sequences, FriCAS can do that. Since you ask about Python, have a look at JFriCAS. As a side note, FriCAS has most amazing implementations of some algorithms, such as Risch. $\endgroup$
    – yarchik
    Commented Jun 17 at 15:59

1 Answer 1

6
$\begingroup$

By setting

Unprotect[FindSequenceFunction];
Attributes[FindSequenceFunction] =.;

then you can see the codes of FindSequenceFunction as

GeneralUtilities`PrintDefinitions@FindSequenceFunction

The above code returns a notebook as enter image description here

Now you can click the grey underlined function with the mouse to open the definition notebook of the function, like findSequenceFunctionParser here. You can see that findSequenceFunctionParser calls findSequenceFunctionDispatcher, findSequenceFunctionDispatcher calls findSequenceFunction, findSequenceFunction calls findPeriodicSequence findPolynomialSequence findRationalSequence findHypergeometricTermsSequenceand so on. Now you can see the original codes of FindSequenceFunction, and I hope you have an enjoyable experience browsing the code.

$\endgroup$
6
  • 2
    $\begingroup$ You don't actually need any Unprotect, just do GeneralUtilities`PrintDefinitions[FindSequenceFunction]. $\endgroup$
    – Domen
    Commented Jun 17 at 15:10
  • $\begingroup$ @Domen FindSequenceFunction has the attribute ReadProtected, so without unsetting this attribute, GeneralUtilities`PrintDefinitions[FindSequenceFunction] returns nothing. $\endgroup$
    – Jie Zhu
    Commented Jun 17 at 15:13
  • 5
    $\begingroup$ No, it's not about the ReadProtected attribute. It's the fact that you have to use this function at least once before in a kernel session so that it gets loaded (it's not automatically loaded). In a fresh kernel, you can just do for example FindSequenceFunction[]; GeneralUtilities`PrintDefinitions[FindSequenceFunction]. $\endgroup$
    – Domen
    Commented Jun 17 at 15:25
  • $\begingroup$ @Domen Got it, thank you! $\endgroup$
    – Jie Zhu
    Commented Jun 17 at 15:36
  • 1
    $\begingroup$ @Domen I have to execute GeneralUtilities`PrintDefinitions[FindSequenceFunction] twice on a fresh kernel, if I do FindSequenceFunction[] first. But if I execute FindSequenceFunction[{}] first, then I can print the definitions on the first try. (V14.0.0 Mac ARM). Odd. Often just executing the head symbol loads the internal package for other function. $\endgroup$
    – Michael E2
    Commented Jun 17 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.