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.
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")Have a good 2016…
#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);
}
A couple of solutions in Racket.
The 63rd triangular number is 2016.
for nth triangular number the formula is n*(n+1)/2;