How can I find the next number in this series?

Additional material

Navid Haddadi (haddadi@sipi.usc.edu) asks:

        Am I missing something or are the questions of this type
        (i.e. next number in the sequence) meaningless?

This is a philosophical question with a long history.  Two examples
from this century are Wittgenstein's discussion of following a rule in
Philosophical Investigations (where he states, e.g., "This is our
paradox:  no course of action could be determined by a rule, because
every course of action can be made to accord with the rule"), and Nelson
Goodman's all emeralds are blue/all emeralds are green paradox which
points out the emptiness of saying the future will be like the past
because there are an infinite number of possible descriptions of the
past.  Shades of the same problem can be found as far back as Plato.

The bottom line is that being intelligent (e.g., in the sense of being
able to complete such a series) may simply amount to giving the same
answer we intelligent people give.

-- John McLean <mclean@itd.nrl.navy.mil>

[ Editor: the help file of N. J. A. Sloane's "superseeker" e-mail
service, as returned to Chris Cole in May 1998, copied in full.  The
addresses are as given then; the Encyclopedia is now at oeis.org. ]

Greetings from "superseeker".   This program will accept a
sequence of integers and try very hard to find an explanation.


It is based on several things:

1. The On-Line Encyclopedia of Integer Sequences
                   N. J. A. Sloane
        AT&T Research Labs, Florham Park, NJ 07932-0971 USA

2. The Encyclopedia of Integer Sequences, by N. J. A. Sloane
and S. Plouffe, published by Academic Press, 1995.

3. The "gfun" Maple package of Bruno Salvy and Paul Zimmerman.

4. A Mathematica program from Olivier Gerard to carry out various
sequence transformations.

5. And also incorporates many new programs.


INSTRUCTIONS:
To submit a sequence, send mail to

superseeker@research.att.com

containing a line of the form

lookup 1 2 4 6 10 14 20 26 36 46 60 74 94 114

The terms must be separated by spaces (not commas).
It is best to give between 10 and 20 terms.

Only one request may be submitted at a time, and (since this
program does some serious computing), only one request per user
per hour.  (There is a list of special users who are exempt from
this restriction.  If you feel you have a genuine need to be
placed on this list, send mail to njas@research.att.com, giving
your reasons!)

[To simply look up sequences in the Encyclopedia, it is 
more efficient to use the on-line server at
   
   sequences@research.att.com

- send an empty email message to that address to get instructions.}


RECOMMENDATIONS:
. Start from the beginning of the sequence (although of course
        keep in mind that different people may define the zero-th
        term (say) in different ways

. Minus signs (if any) should be INCLUDED, since most of the
        programs will make use of them

. If you receive 10 matches from the Encyclopedia, try again
        giving more terms

. If you give too many terms, it will tie up my machine for a long
        time, and my boss will be unhappy

. For an array of numbers, try looking up the individual
        rows, columns or diagonals, whichever seem appropriate

. The program is (mostly) concerned only with infinite sequences

. The program only handles integers.  (For a sequence of
        rationals, try the sequences of numerators and
        denominators separately.)

. The word "lookup" may only appear once in the message
        The "subject" line is thrown away.


TESTS USED

The program will apply some or all of the following tests.
(The program gives up once it has found a sufficient number
of possible explanations.  The more trivial the sequence,
the less time the program will spend studying it.
Also some of these tests are not applicable to all sequences.
Only potentially useful results are reported.)

. Look up in the Encyclopedia both the sequence and the sequence
        with the first term omitted.
            (The reply will report all matches found, up to a limit of 7.)

. Test if a(n) is a polynomial in n  [a(n) denotes the n-th term]
            In other words, are the differences of some order constant?

. Test if the differences of some order are periodic.
            (Suppose the kth order differences are  d(1), ...,d(n).
            They are said to be periodic if there is a number p, the period,
            with 1 <= p <= n-2, such that d(i) = d(j) whenever i = j (mod p).)

. Test if any row of the difference table of some depth is essentially
            constant.  This detects such sequences as 4^n - n^4.
        (Let the usual difference table be
            a(0), a(1), a(2), ...
                b(0), b(1), ...
                       c(0), c(1), ...
                              ....
        This is the difference table of depth 1. The table of depth 2
        has as top row
                a(0), b(0), c(0), ...;
        and so on.)

. For a 2-valued sequence, find the 6 characteristic integer sequences
           and look them up in the table
          (Suppose the sequence takes the values X and Y.  The 6
        characteristic sequences, all equivalent to the original,
        are: replace X,Y by 1,2; by 2,1; the positions of the X's,
        of the Y's; the run lengths; and the derivative, i.e. the positions
        where the sequence changes.)

. Form the generating functions (g.f.) for the sequence for each of
        the following 6 types:

        ogf        ordinary generating function
        egf        exponential generating function
        revogf        reversion of ordinary generating function
        revegf        reversion of exponential generating function
        lgdogf        logarithmic derivative of ordinary generating function
        lgdegf        logarithmic derivative of exponential generating function

            and attempt to represent them as rational functions,
            hypergeometric series, or the solution to a linear differential
            equation with polynomial coefficients.

. Look for a linear recurrence with polynomial coefficients for the
            coefficients of the above 6 types of g.f.'s.

. Look for a polynomial equation in y and x for the g.f. y(x) of each
            of the above 6 types.

. Apply the transformations listed below to the sequence and look up
          the result in the table.  Stop when 10 matches have been found.

. If the original sequence is not in the table, find the 3 closest
            sequences in the table using the L1 metric.
          (If the original sequence is a(1),...,a(n), and s(1),...,s(m)
        is a sequence in the table, compute SUM |a(i)-s(i)| ; i=1..min(n,m);
        i.e. the sum of the absolute values of the differences betweeen the
            given sequence and the one in the table.  Only sequences for
            which this is less than 20 are considered, and the <= 3 best
            are reported.)
              This will pick up cases in which you have sent in more terms
            than are in the table.  It may also correct errors in your
            sequence or in the table.

. Test if the sequence is a Beatty sequence; also test if the sequence
        itself or the sequence of partial sums is quasi-linear.
          (A Beatty sequence is one in which the n-th term is [nz],
        where z is irrational.  The complementary sequence is [ny],
        where 1/x + 1/y = 1.  Refs: N. J. A. Sloane,
        Handbook of Integer Sequences, 1973, p. 29; R. Honsberger,
        Ingenuity in Mathematics, 1970, p. 93.  If this is a Beatty
        sequence the value given for z will produce the given terms,
        but is very far from being unique.
          We define a sequence to be "quasi-linear" if its squared
        correlation coeffient with the sequence of natural numbers 1,2,3,4,...
        exceeds .999.  A Beatty sequence is necessarily quasilinear.)

. If the original sequence is not in the table, find the 3 closest
            sequences in the table in the sense of having the largest
            squared correlation coefficient, using the Maple Rsquared
            function.  Only coefficients >.999 are considered, and of these
            the 3 best are noted. If there are more than 3 with the
            same highest correlation, only the first 3 found are reported.
            This test is intended to detect - among other things - sequences
            of the form a*S + b, where S is a sequence in the table and
            a,b are unknown constants. Later: This test has been withdrawn!

. Other tests are in preparation


LIST OF TRANSFORMATIONS THAT MAY BE APPLIED

Abbreviations used in the following list of transformations:
u[j]        =        j-th term of the sequence
v[j]        =        u[j]/(j-1)!
Sn(z)        =        ordinary generating function
En(z)        =        exponential generating function

T001  the sequence itself
T002  integers not in the sequence
T003  sequence divided by the gcd of its elements
T004  sequence divided by the gcd of its elements, from the 2nd term
T005  sequence divided by the gcd of its elements, from the 3rd term
T006  elements of odd index in the sequence
T007  elements of even index in the sequence
T008  sequence u[j]/(j-1)!
T009  sequence u[j]*j
T010  sequence u[j]/j!
T011  sequence 2*u[j]
T012  sequence 3*u[j]
T013  coefficients of 1/Sn(z)^2
T014  coefficients of Sn(z)^2
T015  coefficients of 1/Sn(z)
T016  coefficients of Sn(z)*(1+z)/(1-z)
T017  coefficients of Sn(z)*(1-z)/(1+z)
T018  sequence u[j+1]-u[j]
T019  sequence u[j+2]-2*u[j+1]+u[j]
T020  sequence u[j+3]-3*u[j+2]-3*u[j+1]+u[j]
T021  coefficients of Sn(z)/(1-z)
T022  coefficients of Sn(z)/(1-z)^2
T023  coefficients of Sn(z)/(1-z)^3
T024  sequence u[j]+u[j+1]
T025  sequence u[j]+u[j+2]
T026  coefficients of Sn(z)/(1+z)
T027  coefficients of Sn(z)/(1+z^2)
T028  sequence u[j]+u[j+1]+u[j+2]
T029  coefficients of Sn(z)/(1+z+z^2)
T030  sequence u[j+2]-u[j]
T031  coefficients of Sn(z)/(1-z^2)
T032  sequence u[j+2]-u[j+1]-u[j]
T033  coefficients of Sn(z)/(1-z-z^2)
T034  sequence u[j]+j
T035  sequence u[j]+2
T036  sequence u[j]+3
T037  sequence u[j]-j
T038  sequence u[j]-2
T039  sequence u[j]-3
T040  sequence u[j]+1
T041  sequence u[j]-1
T042  coefficients of Sn(z)/(1-z+z^2)
T043  sequence u[j+2]-u[j+1]+u[j]
T044  coefficients of Sn(z)/(1+z-z^2)
T045  sequence u[j]+u[j+1]-u[j+2]
T046  sequence u[j]+2*u[j+1]+u[j+2]
T047  sequence u[j]+3*u[j+1]+3*u[j+2]+u[j+3]
T048  coefficients of Sn(z)/(1+z)^2
T049  coefficients of Sn(z)/(1+z)^3
T050  jth coefficient of Sn(z)*(1-z)^j
T051  jth coefficient of Sn(z)*(1+z)^j
T052  jth coefficient of Sn(z)/(1-z)^j
T053  jth coefficient of Sn(z)/(1+z)^j
T054  coefficients of 1/En(z)^2
T055  coefficients of En(z)^2
T056  coefficients of 1/En(z)
T057  coefficients of En(z)*(1+z)/(1-z)
T058  coefficients of En(z)*(1-z)/(1+z)
T059  sequence v[j+1]-v[j]
T060  sequence v[j+2]-2*v[j+1]+v[j]
T061  sequence v[j+3]-3*v[j+2]-3*v[j+1]+v[j]
T062  coefficients of En(z)/(1-z)
T063  coefficients of En(z)/(1-z)^2
T064  coefficients of En(z)/(1-z)^3
T065  sequence v[j]+v[j+1]
T066  sequence v[j]+v[j+2]
T067  coefficients of En(z)/(1+z)
T068  coefficients of En(z)/(1+z^2)
T069  sequence v[j]+v[j+1]+v[j+2]
T070  coefficients of En(z)/(1+z+z^2)
T071  sequence v[j+2]-v[j]
T072  coefficients of En(z)/(1-z^2)
T073  sequence v[j+2]-v[j+1]-v[j]
T074  coefficients of En(z)/(1-z-z^2)
T075  sequence v[j]+j
T076  sequence v[j]+2
T077  sequence v[j]+3
T078  sequence v[j]-j
T079  sequence v[j]-2
T080  sequence v[j]-3
T081  sequence u[j]+j!
T082  sequence u[j]-j!
T083  coefficients of En(z)/(1-z+z^2)
T084  sequence v[j+2]-v[j+1]+v[j]
T085  coefficients of En(z)/(1+z-z^2)
T086  sequence v[j]+v[j+1]-v[j+2]
T087  sequence v[j]+2*v[j+1]+v[j+2]
T088  sequence v[j]+3*v[j+1]+3*v[j+2]+v[j+3]
T089  coefficients of En(z)/(1+z)^2
T090  coefficients of En(z)/(1+z)^3
T091  jth coefficient of En(z)*(1-z)^j
T092  jth coefficient of En(z)*(1+z)^j
T093  jth coefficient of En(z)/(1-z)^j
T094  jth coefficient of En(z)/(1+z)^j
T095  coefficients of product( 1/(1-z^j)^u[j], j=1..inf )
T096  inverse transform to T095, which was "coefficients of product( 1/(1-z^j)^u[j], j=1..inf )"
T097  coefficients of product( 1/(1-z^j)^v[j], j=1..inf )
T098  inverse transform to T097, which was "coefficients of product( 1/(1-z^j)^v[j], j=1..inf )"
T099  sort terms, remove duplicates
T100  binomial transform: b(n)=SUM C(n,k)a(k), k=0..n
T101  inverse binomial transform: b(n)=SUM (-1)^(n-k)*C(n,k)*a(k), k=0..n
T102  boustrophedon transform (see http://www.research.att.com/~njas/doc/bous.ps)
T103  inverse boustrophedon transform (see http://www.research.att.com/~njas/doc/bous.ps)
T104  Euler transform: define b by 1+SUM b(n)x^n = PRODUCT (1-x^n)^-a(n)
T105  inverse Euler transform: define b by 1+SUM a(n)x^n = PRODUCT (1-x^n)^-b(n)
T106  exponentiate: define b by 1 + EGF_B (x) = exp EGF_A (x)
T107  exponential convolution, expand EGF(x)^2
T108  invert: define b by 1+SUM b(n)x^n = 1/(1 - SUM a(n)x^n)
T109  invert: define b by 1+SUM a(n)x^n = 1/(1 - SUM b(n)x^n)
T110  log: define b by EGF of b = log (EGF of a)
T111  Mobius: define b by b(n)=SUM mu(n/d)*a(d), d divides n
T112  inverse Mobius: define b by b(n)=SUM a(d), d divides n
T113  multiply all except leading terms by 2
T114  Stirling-2 transform: b(n) = SUM S(n,k)a(k), k=0..n
T115  Stirling-1 transform: b(n) = SUM s(n,k)a(k), k=0..n




NOTATION USED IN THE ENCYCLOPEDIA

%I = identification line:
        Annnnnn = absolute catalogue number of sequence,
        Mnnnn = number in "The Encyclopedia of Integer Sequences"
        by N.J.A. Sloane and S. Plouffe,
        Academic Press, San Diego, CA, 1995.
        Nnnnn = number (if any) in "Handbook of Integer Sequences" (1973)

%S, %T, %U = beginning of sequence (with all signs omitted)
%V, %W, %X = signed version of sequence if appropriate and if known
        (we are gradually adding these)
%N = name
%R = references
        references to journals give volume, page, year.
%Y = cross-references to other sequences
%F = formula (if not included in %N line),
%A = authority
%O = offset = [a,b]: a is subscript of first entry, b gives the
        position of the first entry >= 2.
%H = URL address of source
%D = details of references
%p = Maple; %t = Mathematica; %o = other computer languages

%K = keywords, as follows:
base:  dependent on base used for sequence
bref:  sequence is too short to do any analysis with
cofr:  a continued fraction expansion of a number
cons:  a decimal expansion of a number
core:  an important sequence
dumb:  an unimportant sequence
easy:  it is very easy to produce terms of sequence
fini:  a finite sequence
frac:  numerators or denominators of sequence of rationals
hard:  next term not known, may be hard to find.
        would someone please extend this sequence?
huge:  contains terms too big for Fortran or C
look:  need to find out if this sequence contains negative numbers
        and if it does we need a copy of the signed version
        (see below)
more:  we need more terms!  would someone please extend this sequence?
nonn:  a sequence of nonnegative numbers
sign:  sequence contains negative numbers
        we need %V, %W, %X lines (matching the %S,T,U lines)
        giving the signed sequence
tabl:  typically a triangle of numbers, such as Pascal's triangle,
       made into a sequence by reading it row by row.
word:  depends on words in some language for the sequence


CONTRIBUTING NEW SEQUENCES TO THE ENCYCLOPEDIA:
New sequences, comments, corrections, extensions, etc.,
accompanied whenever possible by references, should be sent to:
     N. J. A. Sloane, AT&T Labs-Research, Room C233,
     PO Box 971, 180 Park Ave, Florham Park NJ 07932-0971   U.S.A.
     email:  njas@research.att.com   

The sequences should be infinite (although some very long finite
ones are also included).  Only nonnegative sequences are included:
negative numbers are replaced by their absolute values.



COMMON ERRORS:
Make sure that
the word "lookup" does not appear in the message in the same line as
any non-numeric characters.  Make sure that the lookup line
has the form

lookup 1 4 9 16 25                                         GOOD!

and avoid any lines that say things like:

Subject: lookup please                                     BAD!
Subject: lookup                                            BAD!
Subject: lookup 1 4 9 16 25                                BAD!
To: lookup <sequences@research.att.com>                    BAD!
lookup 1,4,9,16,...      [no commas or dots are allowed!]  BAD!
lookup 1 4 9 16 ?                                          BAD!

In a submission to superseeker the word "lookup" may only
appear once in the entire message.


----------

[ Editor: a sci.math discussion of December 1993 - January 1994 on
whether "next number" questions have a best answer, which grew out of
the Titan test sequences (see series/titan.sequences). ]

Manoj P Samanta (samanta@en.ecn.purdue.edu) wrote:
: Article <SGAURE.93Dec29154804@ask.uio.no> says:
: >> I just solved it in under 30 seconds.  What does that make my IQ?
: >>
: >>    2               = 2
: >>    15              = 3 * 5
: >>    1001            = 7 * 11 * 13
: >>    215441          = 17 * 19 * 23 * 29
: >>    95041567        = 31 * 37 * 41 * 43 * 47
: >
: >This is of course wrong, it's way too simple for an IQ test.
: >There's no real *logic* in this solution.

: Are you joking ? I do not know how *real* logic is defined, but I can
: clearly see some logic in this solution.

I have always been baffled by ``puzzles'' of this sort.  I would like
someone to explain what is meant by `` Find the next integer in the
following sequence a1, a2, a3, a4, a5,...''.

Presumably you are intended to find some computational ``rule'' which
given the first n terms of the sequence will yield the n+1 term.  But
in general there are infinitely many such rules given only finitely
many terms in the sequence.

OK.  So we are intended to find the simplest such ``rule''.

My question is ``Is there always a reasonable criterion for what is
the simplest rule?'' and ``Does such a simplest rules always exist?''.

-- Jeremy Wilson <jcrw@fmg.bt.co.uk>

----------

In the simple minds of IQ-test creators such rules always exist.  If
you ask those minds to specify the criterion they will not do that.  I
guess that's because the criteria for simpleness can't be communicated
to people with low IQ.  From that I can deduce that I must have low IQ;
hence I'm not able to discuss this properly.  Still I try to do so, so
in fact I'm unable to recognise my own low IQ, this lowers the IQ by at
least 17, to a level where I can cope with it.  At least I think so.
This rises many interesting questions, but I'm unable to understand
them, I would guess.

:-)

-- Simen Gaure <sgaure@ask.uio.no>

----------

I agree with the sentiment here.

Suppose for example one were given the sequence:

1, 4, 9, 16, 25, ....

and asked for the "simplest" explanation for this sequence.  One
obvious answer is the set of consecutive squares in Z.  But is this the
"simplest"?  I would say not.  I can give a simpler answer, which
requires far less knowledge of mathematics: This is simply an
increasing set of integers.  Is the explanation "increasing set of
integers" any simpler than "successive squares"?  I think it is because
it is a more general answer, and requires fewer specifications to
define the sequence.

What these puzzle makers seem to want is: 'find a "clever" and
"unique" explanation for this series and give the next number'.  They
are too stupid to realize of course, that there are many such
explanations and no unique answer.

-- Bob Silverman <bs@gauss.mitre.org>

[ Editor: Silverman's two "obligatory puzzles" are in
series/titan.sequences. ]

----------

I also agree to this point.  One very good example was to find the
next alphabet in this sequence   o t t f.  It was given to some kids
and they immediately answered 'f' matching with first letters of one,
two, three ....  When given to graduate students, they took hours and
could not come up with any satisfactory reply.  Is IQ (if anything
like that exists) higher in kids than graduates?

-- Manoj P Samanta <samanta@en.ecn.purdue.edu>

----------

Simplicity can of course be described explicitly:  The simplicity (or
perhaps I should say complexity) of a sequence is the length of the
first program that generates it, where programs are ordered first by
length in tokens and then by any ordering on the tokens.  A generating
program is one that prints the n-th element of the sequence when given
the number n as input.

The next number in a sequence is the one given by the first program
that generates the previous elements.

Of course, this relies on the choice of programming language.  Granted,
certainly the simplicity of a series x will be different when measured
with one language than with another -- but in how many languages will
_different_ next numbers be generated given the definition above?

I would expect that in any programming language in common use, the
first program that generates 1, 4, 9, 16, and 25 would generate 36
next.  Can you show a program that generates a different number yet
precedes every program that simply prints n*n?

It could be argued that this still leaves the ambiguous, somewhat
arbitrary "common use" in the definition.  But while without this
definition simplicity is a somewhat vague concept, this definition is
much more focused -- to support an alternate next number, one would
have to present an obviously contrived programming language.  The
boundary between simple and complex is sharpened and made apparent.

-- Eric Postpischil <edp@rusure.enet.dec.com>

----------

For many of these IQ-test sorts of sequences, I would expect the
shortest program to be one that has hardwired in values.  (Imagine
writing a program some other way that got the sequence

  When, in, the, course, of, human, ___

right.)  I don't think that this is that useful a definition in
practice.

-- David Carlton <carlton@husc.harvard.edu>

----------

Well, we have to compare the following programs (although someone can
probably find some efficiency improvement).

main(){while (1) do printf("1,4,9,16,25,");}

main(){int n=0; while(++n) do printf("%d,",n*n);}

I think this is debatable.  We can probably even trim off the "25" to
favor the first program more.

>The boundary between simple and complex is sharpened and made
>apparent.

This approach has all the advantages and disadvantages of any attempt
to make a vague concept precise: there can now be no argument about
which rule is "simpler," but inevitably the precise concept will fail
to capture the original intuition in some crucial instances.

-- Tim Chow <tycchow@math.mit.edu>

----------

Well, the first program does not define a proper series.  Output does
not depend on n.  The program should be such that if I want say, 7th
no., program will automatically generate it.

-- Manoj P Samanta <samanta@en.ecn.purdue.edu>

----------

In article <2futq7$pv5@linus.mitre.org> bs@gauss.mitre.org (Robert D.
Silverman) writes:
>In article <SGAURE.93Dec30161400@ask.uio.no> sgaure@ask.uio.no (Simen
>Gaure) writes:
>>In the simple minds of IQ-test creators such rules always exist.  If
>>you ask those minds to specify the criterion they will not do that.

No, the reason is that the concept of simplicity has no satisfactory
explicit description.  However, I do not think that this means that the
concept of simplicity is an invalid one.  If I were to ask you to
specify the criterion by which you judge that a mathematical proof or
theory or theorem is "deep" or "elegant" or "beautiful" or "powerful"
or "obvious," you would probably not answer either.  But that does not
mean that these concepts are illegitimate.

>One obvious answer is the set of consecutive squares in Z. But is this
>the "simplest"? I would say not. I can give a simpler answer, which
>requires far less knowledge of mathematics: This is simply an
>increasing set of integers.

However, suppose you were doing research and were computing explicitly
a few small examples of whatever you were investigating.  Suppose the
above sequence manifested itself.  Would you say to yourself, "This is
simply an increasing set of integers.  I will therefore pick an
arbitrary integer greater than 25 and conjecture that that is the next
number in the sequence."  You guess 47, and compute the next number.
It turns out to be 36.  "Well, I guess 47 was wrong, but it's still an
increasing sequence.  Let me see if I can prove that the sequence is
increasing."  Say you find such a proof.  Would you stop there?  *I*
sure wouldn't!

Of course we all know that there are infinitely many rules compatible
with a given finite sequence of integers.  So what?  In the majority of
cases on IQ tests, it is clear which rule is the "simplest" even if we
cannot precisely define what "simplest" means.

Such discussion is not necessarily idle.  It is common experience that
in mathematics (also in science, though perhaps less so), the
"simpler" conjectures are often the most fruitful.  Thus the ability to
recognize simplicity is valuable.  So I don't think that Gaure and
Silverman have given valid arguments against questions of this sort.
(This doesn't mean that I think that such questions measure some kind
of innate mental property.)

-- Tim Chow <tycchow@math.mit.edu>

----------

In article <1993Dec31.001919.26609@xsoft.xerox.com> dhall@hv-3 (Donn
Hall) writes:

> >edp@math.zk3.dec.com (Eric Postpischil) asks:
> >
> >>I would expect that in any programming language in common use, the
> >>first program that generates 1, 4, 9, 16, and 25 would generate 36
> >>next. Can you show a program that generates a different number yet
> >>precedes every program that simply prints n*n?
>
> >printf("1, 4, 9, 16, 25, 0");   ?
>
> f(n) = n*n + g(n)*{(n-1)*(n-2)*(n-3)*(n-4)*(n-5)}/5! where n=1,2,...
>
> f(n) produces 1,4,9,16,25, and then any arbitary number you wish as a
> function of g(6)

While there may be some ambiguity about which is the shortest program,
that ambiguity will disappear as the specified initial sequence grows
longer.  For a sufficiently long initial sequence, the program to
display n**2 will be shorter than either of the two above.  In general,
the simple printf("...") will always lose for a non-random sequence.
Indeed, that can be the basis of a definition of "random".  [cf.
Chaitin's work on algorithmic information theory]

-- Dan Prener <prener@watson.ibm.com>

----------

In article <2fvq99$1qt@linus.mitre.org>, bs@gauss.mitre.org (Robert D.
Silverman) writes:

>But which rule is "simpler" is now dependent on the choice of
>language.

I said that in my posting.  But the definition is still sharper,
because the dependency is weak -- you can choose C, FORTRAN, Pascal,
and many other languages and still find that 36 is the next number
following 1, 4, 9, 16, and 25.

How would you explain the observation that programs that generate n*n
are shorter than other programs that generate 1, 4, 9, 16, and 25
followed by something other than 36 in almost all languages in common
use?  Is that just random chance?  If it is not random chance, it must
be something else -- what?

Is it just human prejudices, or would you expect languages developed by
other intelligences to show similar results?

-- Eric Postpischil <edp@rusure.enet.dec.com>