Allow formulas to invoke OEIS sequences

[gwhitney]

The idea is to be able to visualize something like A000045(n) - A000045(n-1) - A000045(n-2) (and see in this case that it's all zeros ;-) in a relatively straightforward way.

Depends on #14.

[gwhitney]

Although #14 is closed, I feel this now also depends on #42.

[gwhitney]

To summarize the current plan: based on the discussion in #48, sequences need to return their first and last valid indices. And as noted in the discussion on #74, since that's potentially very difficult (i.e., insoluble in general like the halting problem) to figure out by formula analysis, we will do the computation in the backend. So the plan is to use math.js just to parse the formulas into a canonical string form (RPN with subexpressions in lexicographic order, I guess) and pass that to the backend, which will actually do the computation. An advantage there is that Python already does arbitrary-precision integer arithmetic, so that is a win. So we shouldn't really have to worry about adding bigints to math.js, after all. My tentative implementation plan is to: 1) Make a version of frontscope that produces canonical RPN formulas, that I won't commit (as it won't really add any functionality). Note the formulas need to use only URL-acceptable characters. 2) Make a version of backscope that can accept such formulas and produce output like the sequence endpoint does, and commit that to main. 3) Extend (1) to use the results from backscope to fully implement an OEIS-with-formulas Sequence class.

[katestange]

One comment: I don't know if it saves us doing bigints in math.js, as this is something visualizers will want, potentially (they may do all kinds of processing on the sequences they get in bigint form).

[gwhitney]

That's a good point, Kate. I guess how that's handled is partly up to whoever implements #48 and how that person goes about it.

While I am commenting, I am planning (eventually) to allow a formula writer optionally to indicate sequence limits via an inequality expression in the formula, something like: floor(sqrt(A000001(2*n)); 2 <= n <= 512 I am leaning toward this for a couple of reasons:

• I would like formulas to remain self-contained; i.e, a formula-based sequence should be completely describable by a single string, without multiple entry boxes. This desire is mainly motivated by the possibility that the sequences area could be replaced just by a panel of text boxes, each containing a formula. (And eventually those formulas could display in typeset math notation!)
• It also provides a nice place to specify the index variable, in case we ever want to get away from requiring that it be n.
• The semicolon could then be viewed as an operator that produces a sequence from a formula with one free variable, the name of that variable, and the limits on that variable. That would naturally allow things like a sum operator sum(i^2; 0 <= i < n)

If this notation and plan seem reasonable to you, especially in light of the last possibility, do you think it's better for the optional limits to come before, after, or in either order with the formula? In other words, do you like A000045(n)+A000045(n+1); 0<n<64 or 0<n<64; A000045(n)+A000045(n+1) or should either be allowed? One difficulty with simply allowing either order is that 0<n<64 is a perfectly legal math.js formula, with value 1 for n from 1 to 63, inclusive, and value 0 otherwise, so conceivably one would want such an inequality formula with its range specified by an inequality, and then if the order of expressions is ambiguous, such a ;-expression would be ambiguous (Is 0<n<10; -2 <= n <= 7 defined from 1 to 9 or -2 to 7?). On the other hand, that's a pretty weird edge case, and the system could just take the limits to be whichever is an inequality formula and complain to the user if both are.

[gwhitney]

Some brief updates:

• Since I was wrapping most everything in floor anyway and since it can't really hurt, I decided that all formulas should be implicitly wrapped in floor.
• I have pretty much completed step 1 from my comments above, except that it depends on what will be a fairly lengthy series of improvements to math.js's simplify function; that effort will hold up implementation for a while. I have just made the first PR to math.js (see https://github.com/josdejong/mathjs/pull/2372).

[gwhitney]

Kate points out that it would also be nice to be able to take two sequence objects, which might internally use the OEIS or not, and create a new sequence object representing, say, the entry-wise gcd of the two.

[gwhitney]

There is an issue related to that last point of detecting already-computed-and-stored subformulas. More specifically, to what extent, when computing and storing the results of a given formula, do we (a) store the results of subformulas (pre-cache partial results that haven't been asked for, and (b) check whether subformulas have been previously computed and stored (take fullest advantage of prior results)?