Mark Gritter (markgritter) wrote,
Mark Gritter

Solving stupid integer sequence problems

Problems of the form "what is the next number in the sequence A1, A2, A3, A4, ..." are dumb. They don't rely upon mathematical ingenuity. They depend on some social construct about what the "right" answer ought to be, in terms of simplicity or "things you might be expected to know". And yet they are pretty popular puzzles.

And, of course, mathematical psuedo-sophisticates make appeals to Kolmogorov complexity which is unhelpfully uncomputable.

What I would like instead are a collection of mechanisms for proving such questions meaningless--- that is, tool for constructing an arbitrary fit for an integer sequence. Here's a few to kick things off:

1. Fit the K integers as successive values x=1, x=2, x=3, ..., x=k of a polynomial of order N. There are N+1 coefficients, so when N+1 >= K we should be able to find an exact fit (except maybe in some degenerate cases not immediately obvious to me) and for N+1 > K we can find an arbitrary number of polynomials.

2. Take N=ceil(log2(max(Ai))). Then we can view the sequence as the operation of N separate N-bit binary functions. Since there are 2^N such binary functions and only K examples, the problem is not particularly constrained, even if we restrict ourselves to "simple" N-to-1-bit functions.

3. Define A_K as a (K-1)-ary function of its previous arguments. Backfill A_0, A_-1, A_-2 to make the sequence look non-arbitrary.

4. Take differences between terms enough times, until the resulting sequence is short enough to be matched to something trivial.

5. Split the sequence into two or more unrelated sequences that have been interleaved (which can be done in a variety of ways.)

6. Construct a rational number such that A1 A2 A3 ... AK (suitably zero padded) are the repeating digits (or initial digits, or a combination) of its decimal expansion.

7. Construct a number such that A1, A2, A3, ... AK are the first terms in its continued fraction representation.

Any other suggestions?
Tags: mathematics, puzzles
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.