Happy New Year!

January 1, 2016

We’ll look at two solutions. The first makes a list of the first n triangular numbers by adding the next number to the previous sum; for instance, the 4th triangular number is 10, and the 5th triangular number is the 4th triangular number plus 5:

(define (tri-list n)
  (let loop ((i 0) (ts (list 0)))
    (if (= n i) (reverse ts)
      (loop (+ i 1) (cons (+ i (car ts) 1) ts)))))

There is a closed-form solution that finds the n th triangular number, famously “discovered” by Gauss as a schoolboy, though it probably dates to the Pythagoreans about 500BC; the story is that Gauss’ teacher, as a punishment to the class, ordered them to sum the numbers from 1 to 100, and Gauss noticed that there were 50 pairs that each summed to 101 (for instance, 1 and 100, 2 and 99, and so on), so he could immediately compute the sum as 50 * 101 = 5050:

(define (tri n) (* n (+ n 1) 1/2))

Here are two examples:

> (tri-list 63)
(0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171
 190 210 231 253 276 300 325 351 378 406 435 465 496 528 561
 595 630 666 703 741 780 820 861 903 946 990 1035 1081 1128
 1176 1225 1275 1326 1378 1431 1485 1540 1596 1653 1711 1770
 1830 1891 1953 2016)
> (tri 63)
2016

The 63rd triangular number is 2016: Happy New Year!

You can run the program at http://ideone.com/r5bltM.

Pages: 1 2

4 Responses to “Happy New Year!”

  1. matthew said

    Nice. 2016 is not only triangular (and hexagonal) but is also the difference between powers of 2 (2048 and 32) (it is 11111100000 in binary). Also it is the sum of consecutive cubes (so is the difference between two square hyperpyramid numbers). Also, being triangular, it is obviously also the difference between two triangular numbers (itself and 0, as well as triangle(2016) and triangle(2015)) but there are other ways (the number of ways is apparently known as the politeness of the number).

    Here’s some Python (adapted from something I wrote for the “sum of consecutive squares” problem a while back) that uses a heap/priority queue to find such differences in an ascending sequence reasonably efficiently:

    import heapq
    
    def makediff(a,b,s,f):
        if b == len(s): s.append(f(b,s[-1]))
        return (s[b]-s[a], a, b)
    
    def find2016(n,f,c):
        s = [n]
        diff = lambda a,b: makediff(a,b,s,f)
        q = [diff(0,1)]
        while True:
            (value,a,b) = heapq.heappop(q)
            if value == 2016:
                print("%d = s[%d] - s[%d] = %d - %d (%s)"
                      %(value,b,a,s[b],s[a],c))
            if value > 2016: break
            if b == a+1: heapq.heappush(q,diff(b,b+1))
            heapq.heappush(q,diff(a,b+1))
    
    find2016(1,lambda n,m: 2*m,"powers of 2")
    find2016(0,lambda n,m: n+m,"triangular")
    find2016(0,lambda n,m: n*n*n+m,"sums of cubes")
    
    2016 = s[11] - s[5] = 2048 - 32 (powers of 2)
    2016 = s[63] - s[0] = 2016 - 0 (triangular)
    2016 = s[106] - s[85] = 5671 - 3655 (triangular)
    2016 = s[228] - s[219] = 26106 - 24090 (triangular)
    2016 = s[291] - s[284] = 42486 - 40470 (triangular)
    2016 = s[673] - s[670] = 226801 - 224785 (triangular)
    2016 = s[2016] - s[2015] = 2033136 - 2031120 (triangular)
    2016 = s[9] - s[2] = 2025 - 9 (sums of cubes)
    

    Have a good 2016…

  2. Atif Farooq said

    #include
    using namespace std;
    int NaturalSum(int X);
    void main(void)
    {
    cout << NaturalSum(63)<<endl;
    }
    int NaturalSum(int X)
    {
    if (X == 1)
    return 1;
    else return X + NaturalSum(X – 1);
    }

  3. r. clayton said

    A couple of solutions in Racket.

  4. Praveen said

    The 63rd triangular number is 2016.
    for nth triangular number the formula is n*(n+1)/2;

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: