[math-fun] Sequence meeting
Looks like a fun weekend ahead! http://dimacs.rutgers.edu/Workshops/OEIS/abstracts.html A missing talk: How to look hard for sequence combinations? Neil must have addressed this in Superseeker, but I haven't seen any writeup. Suppose I have generated a new sequence M(n), and it's not in OEIS. Maybe it's some combination of OEIS sequences. What's a good way to proceed? I can look for M(n) = A(n) + B(n) reasonably efficiently (assuming I have a local copy), but trying A+B+C etc. rapidly outruns available computing resources. Also, automatically rejecting false positives looks hard. This seems like a natural area for research. Rich
Rich, An early version of Superseeker did try to find a match with a linear combination of two sequences. It looked at c*A(n) + d*B(n+n_0), and tried small values of c,d,n_0 and all pairs A,B from the database. The trouble was, it was slow, it found a lot of false matches, and IIRC it never found anything useful. So I dropped it. It is certainly a project worth doing off-line though. Take all triples A, B, C of sequences and see if there is a linear dependence among them. To cut down on trivial matches, restrict A to be a sequence that has no known formula. Although the hard part would be to decide if a positive result was a known identity (which it would be most of the time) or a new discovery. Neil On Tue, Sep 23, 2014 at 3:48 PM, <rcs@xmission.com> wrote:
Looks like a fun weekend ahead!
http://dimacs.rutgers.edu/Workshops/OEIS/abstracts.html
A missing talk:
How to look hard for sequence combinations? Neil must have addressed this in Superseeker, but I haven't seen any writeup. Suppose I have generated a new sequence M(n), and it's not in OEIS. Maybe it's some combination of OEIS sequences. What's a good way to proceed? I can look for M(n) = A(n) + B(n) reasonably efficiently (assuming I have a local copy), but trying A+B+C etc. rapidly outruns available computing resources. Also, automatically rejecting false positives looks hard. This seems like a natural area for research.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
Neil, I'm imagining a button on the search page that asks the user if he wants to look for combinations, but clearly you've got to keep the compute cost down. The 'slow' part can be partially addressed with a clever algorithm. If you want to see if A[n] = B[n] + C[n], sort the data set on X[1], and scan through the values A[1]-X[1] looking for a match with the reverse-sorted X'[1]s. For your case below, with unknown TBD coefficients c and d, looking for a cross-ratio coincidence between (A1 B3 - A3 B1) / (A1 B2 - A2 B1) and (A1 C3 - A3 C1) / (A1 C2 - A2 C1) would find candidate B,C pairs. The false-positive problem might be addressable when more terms of A are available -- analogous to the real-number version of the problem where we just compute a few more decimals. The "Nothing Useful" problem is more serious -- it says the cost of finding for a new discovery is very high, and not just compute cycles, but research effort. Perhaps Euler's zeta2 = pi^2/6 was the only time the cost/benefit ratio was favorable. A look into what you've tried with Superseeker would be interesting. Rich ---- Quoting Neil Sloane <njasloane@gmail.com>:
Rich, An early version of Superseeker did try to find a match with a linear combination of two sequences. It looked at c*A(n) + d*B(n+n_0), and tried small values of c,d,n_0 and all pairs A,B from the database.
The trouble was, it was slow, it found a lot of false matches, and IIRC it never found anything useful. So I dropped it.
It is certainly a project worth doing off-line though. Take all triples A, B, C of sequences and see if there is a linear dependence among them. To cut down on trivial matches, restrict A to be a sequence that has no known formula.
Although the hard part would be to decide if a positive result was a known identity (which it would be most of the time) or a new discovery.
Neil
On Tue, Sep 23, 2014 at 3:48 PM, <rcs@xmission.com> wrote:
Looks like a fun weekend ahead!
http://dimacs.rutgers.edu/Workshops/OEIS/abstracts.html
A missing talk:
How to look hard for sequence combinations? Neil must have addressed this in Superseeker, but I haven't seen any writeup. Suppose I have generated a new sequence M(n), and it's not in OEIS. Maybe it's some combination of OEIS sequences. What's a good way to proceed? I can look for M(n) = A(n) + B(n) reasonably efficiently (assuming I have a local copy), but trying A+B+C etc. rapidly outruns available computing resources. Also, automatically rejecting false positives looks hard. This seems like a natural area for research.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Dear Friends, I have now retired from AT&T. New coordinates:
Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Just in case anyone is interested, I had a master's student look into this very question some time ago. We developed some techniques that could speed up questions like: is a given sequence the linear combination of two sequences in the table? But I do not know any way to do this for more than two sequences in a reasonable length of time. You can see my master's student essay here: https://cs.uwaterloo.ca/~shallit/peter-liu-masters.pdf On 9/24/14 6:14 PM, rcs@xmission.com wrote:
Neil, I'm imagining a button on the search page that asks the user if he wants to look for combinations, but clearly you've got to keep the compute cost down.
The 'slow' part can be partially addressed with a clever algorithm. If you want to see if A[n] = B[n] + C[n], sort the data set on X[1], and scan through the values A[1]-X[1] looking for a match with the reverse-sorted X'[1]s. For your case below, with unknown TBD coefficients c and d, looking for a cross-ratio coincidence between (A1 B3 - A3 B1) / (A1 B2 - A2 B1) and (A1 C3 - A3 C1) / (A1 C2 - A2 C1) would find candidate B,C pairs.
The false-positive problem might be addressable when more terms of A are available -- analogous to the real-number version of the problem where we just compute a few more decimals.
The "Nothing Useful" problem is more serious -- it says the cost of finding for a new discovery is very high, and not just compute cycles, but research effort. Perhaps Euler's zeta2 = pi^2/6 was the only time the cost/benefit ratio was favorable.
A look into what you've tried with Superseeker would be interesting.
Rich
---- Quoting Neil Sloane <njasloane@gmail.com>:
Rich, An early version of Superseeker did try to find a match with a linear combination of two sequences. It looked at c*A(n) + d*B(n+n_0), and tried small values of c,d,n_0 and all pairs A,B from the database.
The trouble was, it was slow, it found a lot of false matches, and IIRC it never found anything useful. So I dropped it.
It is certainly a project worth doing off-line though. Take all triples A, B, C of sequences and see if there is a linear dependence among them. To cut down on trivial matches, restrict A to be a sequence that has no known formula.
Although the hard part would be to decide if a positive result was a known identity (which it would be most of the time) or a new discovery.
Neil
On Tue, Sep 23, 2014 at 3:48 PM, <rcs@xmission.com> wrote:
Looks like a fun weekend ahead!
http://dimacs.rutgers.edu/Workshops/OEIS/abstracts.html
A missing talk:
How to look hard for sequence combinations? Neil must have addressed this in Superseeker, but I haven't seen any writeup. Suppose I have generated a new sequence M(n), and it's not in OEIS. Maybe it's some combination of OEIS sequences. What's a good way to proceed? I can look for M(n) = A(n) + B(n) reasonably efficiently (assuming I have a local copy), but trying A+B+C etc. rapidly outruns available computing resources. Also, automatically rejecting false positives looks hard. This seems like a natural area for research.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Dear Friends, I have now retired from AT&T. New coordinates:
Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* rcs@xmission.com <rcs@xmission.com> [Oct 12. 2014 15:28]:
Looks like a fun weekend ahead!
http://dimacs.rutgers.edu/Workshops/OEIS/abstracts.html
[...]
Awesome it was! Best, jj (jet-laggged)
participants (4)
-
Jeffrey Shallit -
Joerg Arndt -
Neil Sloane -
rcs＠xmission.com