Given a list of integers a1, a2, …, ak (k ≥ 2) and a positive integer m, write a function or a complete program that calculates the next m numbers of the list. Assume that ai = P(i) where

P(x) = bk-1 xk-1 + bk-2 xk-2 + … + b0

is the unique polynomial of minimum order which fits the points.



If the code is a function, input is given by an integer k, an array a1, a2, …, ak and an integer m.

If the code is a program, input (through stdin) is given by space-separated k a1 a2 … ak m.

You can assume that k ≥ 2 and m > 0.


(Of course, the code can calculate the result in different way, but the result should be same.)

Find the polynomial P(x) which satisfies ai = P(i) for all 1 ≤ i ≤ k and has a degree of (no more than) k - 1. For example, if a list is 1,2,3,4,5, then P(x) = x. If a list is 1,4,9,16,25, then P(x) = x2.

Then, calculate ak+1 = P(k+1), ak+2 = P(k+2), …, ak+m = P(k+m). These are the results.


If the code is a function, return an array [ak+1, ak+2, …, ak+m].

If the code is a full program, print those numbers to stdout, separated by an any character you want.

  • \$\begingroup\$ I think you should require some separator for the output: 1 4 9 16 25 is much less ambiguous than 1491625. \$\endgroup\$ Commented Dec 10, 2011 at 2:32
  • \$\begingroup\$ @IlmariKaronen OK then. \$\endgroup\$
    – JiminP
    Commented Dec 10, 2011 at 2:34
  • \$\begingroup\$ NB This is almost a duplicate of codegolf.stackexchange.com/questions/1230/… . The differences are that it's over a field of characteristic 0; that the x-coords are implicit; and that it asks for extrapolation to k+1, ... k+m rather than to 0. \$\endgroup\$ Commented Dec 11, 2011 at 7:36

5 Answers 5


Golfscript, 46 42 40 38 chars


This uses a simple difference table approach, which is described in more detail on my GolfScript blog.

  • \$\begingroup\$ +100: You beat Ilmari's 40 char-or-less challenge :) \$\endgroup\$
    – mellamokb
    Commented Dec 12, 2011 at 16:05
  • \$\begingroup\$ Bounty awarded. Congratulations! Now I just need to learn enough GolfScript to be able to understand your code. :) \$\endgroup\$ Commented Dec 13, 2011 at 16:22
  • \$\begingroup\$ @IlmariKaronen, I might write it up for my GolfScript blog in a few days. The -2% is quite interesting in that it's something I didn't really see much point to before. \$\endgroup\$ Commented Dec 13, 2011 at 16:55
  • 1
    \$\begingroup\$ @IlmariKaronen, code dissection posted to my blog. \$\endgroup\$ Commented Dec 14, 2011 at 23:42

Maple, 41 chars


For example, c(3, [1, 2, 4], 4) returns 7, 11, 16, 22.

This function interprets the spec literally, taking both k and a as separate arguments. If the list a does not have exactly k elements, an error occurs. For convenience, here's a 45-char version that omits k from the argument list:


I was first thinking of trying this in Perl, but hell, let's use the right tool for the job.

  • \$\begingroup\$ BTW, since this is code golf, 'the right tool' is golfscript. :P \$\endgroup\$
    – JiminP
    Commented Dec 10, 2011 at 9:47
  • 1
    \$\begingroup\$ @JiminP: OK, challenge accepted. The first person to solve this task in 40 or fewer chars in GolfScript gets a 100 rep bounty from me. \$\endgroup\$ Commented Dec 10, 2011 at 16:20
  • \$\begingroup\$ @PeterTaylor When inputs are integers, outputs might always be integers (there's a way to calculate outputs by using only integers), even though I don't have any proofs. \$\endgroup\$
    – JiminP
    Commented Dec 11, 2011 at 7:51
  • \$\begingroup\$ Challenge met. Don't feel obliged to give me the bounty, though; I'm doing ok for rep already. \$\endgroup\$ Commented Dec 12, 2011 at 0:16
  • \$\begingroup\$ @PeterTaylor: I'll give it to you anyway, it's not like I'm starved for rep either. And I did promise. (I assume I have to wait until the question is old enough, though, since I don't see any "start a bounty" link yet.) \$\endgroup\$ Commented Dec 12, 2011 at 0:42

Jelly, 18 bytes, language postdates challenge


Try it online!

Jelly's functions only support up to two arguments, so I don't take in k (which is redundant) as an argument. I hope that's acceptable. The program defines a function that obeys the specification in the question.


Helper function (takes input λ, ρ, and expands λ by ρ elements):

       ø  µ ? If
           L    {λ} is nonempty,
I               take differences of consecutive elements of {λ};
 ß              call 1ŀ recursively on this value and {ρ};
  ;@            prepend
    Ḣ           the first element of {λ};
     +\         and take the cumulative sum {and return it}.
        ṁ⁹      {return} {0} repeated ρ times.

This is fairly magical in the way in which Jelly happens to pick out the exactly values I need it to operate on at every stage. Some of it is the result of me manipulating things; in particular, the unusual choice ø for the separator (rather than the more usual µ) means that all implicit arguments are set to 0, which is fairly handy in this case. However, I have no idea why ;@Ḣ parses the way it does, but it seems to work…

Main function (takes input λ, ρ, and returns the next ρ elements of λ):

ç             Call 1ŀ on {λ} and {ρ};
 U            reverse it;
  ḣ           take the first {ρ} elements;
   U          and reverse it {and return that value}.

This is just massaging the output into the form requested (if we were allowed to return the terms we were already given, that would remove a whole 5 bytes). Jelly doesn't have a "last n elements" function; of the various ways to synthesize it out of other functions, UḣU is convenient here because it happens to pick up ρ as a default argument.


Golfscript, 51 characters

Similar approach to Peter's one.


When run on input

2 3 12 35 78

it yields the result

[147 248 387 570]

There are still possible places where the solution might be golfable further.


Scala, 128 bytes


Try it online!


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.