## Archive for **January 10th, 2011**

## New Year

Some time in the last two weeks, I tried to figure out the answers to two questions:

- Why does the new year begin on January 1?
- Why does January 1 occur when it does?

That is, the history of the calendar. The former question is about the structure of the calendar, and the latter about its (arbitrary) point of origin.

I don’t have definitive answers yet (and I’m beginning to wonder if any exist); please help me if you know something.

Meanwhile, here’s what I’ve been able to piece together from reading Wikipedia. The calendar most of us use most of the time can be understood in three phases…

## Phase I: The (pre-Julian) Roman calendar: before 45 BCE

The Greeks used several lunar calendars. The Romans probably inherited such a calendar, and their early calendar was a lunar one. “According to Livy, Numa’s calendar was lunisolar with lunar months and several intercalary months spread over nineteen years so that the Sun returned in the twentieth year to the same position it had in the first year.”

According to Roman tradition, Rome was founded around 753 BCE by Romulus, and Romulus “invented” the following calendar:

Calendar of Romulus Martius (31 days) Aprilis (30 days) Maius (31 days) Iunius (30 days) Quintilis (31 days) Sextilis (30 days) September (30 days) October (31 days) November (30 days) December (30 days) [Total 304 days] "Winter" (About 61 days of winter, presumably)

Note that the names for months 5 to 10 (Quintilis to December) are just number names.

The arbitrariness of this calendar already makes no sense, but let’s start with it. We have to start somewhere.

In 713 BCE, Numa divided the winter into two months named Ianuarius and Februarius. Also, to make all the month lengths odd (considered lucky), he took away one day from each of the 30-day months.

Martius (31) Aprilis (29) Maius (31) Iunius (29) Quintilis (31) Sextilis (29) September (29) October (31) November (29) December (29) Ianuarius (29) Februarius (28) [Total 355 days]

[Apparently by 450 BCE, the civil calendar had also been changed to start with Ianuarius, so half the month names became misnomers. So here’s where the answer to the first question should come from: **why was the calendar changed to start with January**/Ianuarius instead of March/Martius?]

February was actually two parts of odd number of days each: Part 1, 23 days, ended with Terminalia (and so did the religious year), and then there was a remaining part of 5 days. From time to time, an intercalary month of 27 days (subsuming the last 5, so only 22 additional days) was added. (So the leap year had 377 or 378 days.) So far the months were still more or less lunar, it appears.

Because the true length of a year is roughly halfway between 355 and 377, the intercalary month was needed roughly every alternate year. Adding the intercalary month was left to the Pontifex Maximus, a pontiff in charge of such things.

However, since the Pontifices were often politicians, and because a Roman magistrate’s term of office corresponded with a calendar year, this power was prone to abuse: a Pontifex could lengthen a year in which he or one of his political allies was in office, or refuse to lengthen one in which his opponents were in power. If too many intercalations were omitted, as happened after the Second Punic War and during the Civil Wars, the calendar would drift rapidly out of alignment with the tropical year. Moreover, because intercalations were often determined quite late,

the average Roman citizen often did not know the date, particularly if he were some distance from the city. For these reasons, the last years of the pre-Julian calendar were later known as “years of confusion”. The problems became particularly acute during the years of Julius Caesar’s pontificate before the reform, 63–46 BC, when there were only five intercalary months, whereas there should have been eight, and none at all during the five Roman years before 46 BC. For example, Caesar crossed the Rubicon on January 10, 49 BC of the official calendar, but the official calendar had drifted so far away from the seasons that it was actually mid-autumn.

Whoa.

Eventually Julius Caesar became Pontifex Maximus, and reformed the calendar into the Julian calendar in 45 BCE. “The reform was intended to correct [the above] problem permanently, by creating a calendar that remained aligned to the sun without any human intervention.”

## Phase II: the Julian calendar (45 BCE to some time after 1582 CE)

The Julian Calendar: Eventually Julius Caesar became Pontifex Maximus, and in 45 BCE, “called in the best philosophers and mathematicians of his time” and reformed the calendar into the Julian calendar. He decided to approximate the tropical year, and so it became a calendar of 365 days with a leap year added to February (still the last month of the religious calendar?) every four years. So a year became exactly 365.25 days on average.

Somewhere here is where one should look for the answer to the second question: what about the start of the year?

“A passage in Macrobius has been interpreted to mean that Caesar decreed that the first day of the new calendar began with the new moon which fell on the night of 1/2 January 45 BC. However, more recent studies of the manuscripts have shown that the word on which this is based, which was formerly read as lunam, should be read as linam, meaning that Macrobius was simply stating that Caesar published an edict giving the revised calendar.”

Ah, if the new moon explanation were correct, it would have answered the second question! So close.

In any case, this wasn’t the end. “the pontifices apparently misunderstood the algorithm for leap years. They added a leap day every three years, instead of every four years. […] After 36 years, this resulted in three too many leap days. Augustus remedied this discrepancy by restoring the correct frequency. He also skipped three leap days in order to realign the year. Once this reform was complete—after AD 8 at the latest—the Roman calendar was the same as the Julian proleptic calendar.”

Ah, finally! The year is fixed. Sort of.

The solstices and the equinoxes were now: 25 December, 25 March, 24 June, 24 September.

Quintilis was renamed Iulius after Iulius Caesar, and Sextilis was renamed Augustus after his successor Augustus Caesar. (Incidentally, these were not the only months to be renamed, just the only renamings to survive: “Caligula renamed September (“seventh month”) as Germanicus; Nero renamed Aprilis (April) as Neroneus, Maius (May) as Claudius and Iunius (June) as Germanicus; and Domitian renamed September as Germanicus and October (“eighth month”) as Domitianus. At other times, September was also renamed as Antoninus and Tacitus, and November (“ninth month”) was renamed as Faustina and Romanus. Commodus was unique in renaming all twelve months after his own adopted names […]” So apparently the trick in getting a month named after you is to do the renaming when the calendar is in flux, not after it’s been fixed.

## Phase III: the Gregorian calendar: a few years after 1582 to today

The Gregorian calendar is what we use today, more or less.

The Julian calendar’s average of 365.25 days a year instead of about 365.2425 days a year is about 11 minutes extra each year, or about 3 days extra every 4 centuries. So the year had drifted, which had to be corrected, and in future, 3 leap days had to be removed every 4 centuries. Pope Gregory decreed this in 1582, though it took many countries a few centuries to take (or be forced to take) him seriously. This explains the “century years are not leap years unless divisible by 400” rule. Of course, Gregory’s calculation also wasn’t entirely perfect, but it’s handled nowadays by adding leap seconds etc. to the official clocks, and most of us aren’t even aware of it. (This is a mess, which David Madore has written about here.) When the calendar was introduced, it also dropped 10 days, and those who switched centuries later had to drop 10/11/12/13 days.

That’s about all of the history I have time for right now…

(It seems the answer to starting on 1 January may have something to do with some consul’s decision on when to start; the 2nd question is harder.)

**Bonus**: Why Christmas is on December 25th. The popular explanation is that it was a pagan winter-solstice festival that was appropriated, but according to some Christians, only the festival is pagan, not necessarily the date.

## Not all best rational approximations are the convergents of the continued fraction!

[For more background on continued fractions and why they are so wonderful at approximations (and wonderful generally) — eventually I may edit this post to mention that. For now I just want to quickly clarify something, which surprisingly many popular expositions of continued fractions seem to mislead by leaving out.]

Any real number can be written as a continued fraction. For instance, the square root of 3 is

written as ,

and π is

i.e. (more terms below),

and *e* is (proved here).

Rational numbers have finite continued fractions, and irrational numbers have infinite continued fractions, of which only quadratic irrationals (like √3 above) have periodic continued fractions. Non-quadratic irrationals may still have some recognisable patterns in their representation, like *e* above, or not, like π.

The numbers you get by truncating the continued fraction — taking only the first few terms — are called its *convergents*. The continued fraction for π is [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2…] (sequence A001203 in OEIS), and the sequence of convergents is 3/1, 22/7, 333/106, 355/113, 103993/33102… (A002485/A002486):

Each of these convergents is a *best rational approximation*, in the following sense.

**Definition**: A fraction p/q is a best rational approximation of a real number x if p/q is closer to x than any other fraction with a smaller denominator. That is, for any other fraction with and , we have .

Thus among all fractions with denominator at most 7, the fraction 22/7 is closest to π. Among all fractions with denominator at most 113, the fraction 355/113 is closest to π. And so on.

Every convergent is a best rational approximation, **but these aren’t all of the best rational approximations!** The sequence of best approximations of π is actually **3/1**, 13/4, 16/5, 19/6, **22/7**, 179/57, 201/64, 223/71, 245/78, 267/85, 289/92, 311/99, **333/106**, **355/113**, 52163/16604… (A063674/A063673), where only the bold terms are convergents. (Aside: Notice how good 355/113 is: it is the best among all fractions with denominator at most 16603. This is because of the large term 292 in the continued fraction of π.) The others are *semi-convergents* (*intermediate fractions*), as explained below.

In general, for any real number, the convergents of its continued fraction are always best rational approximations, but they aren’t *all* of the best rational approximations. To get all of them, you also have to take the semi-convergents: fractions of the form for some integer n≥1. Specifically, taking — the next term in the continued fraction expansion — gives , and the ones to take are precisely from (if it’s better than the previous convergent, else ) to . This is also mentioned on Wikipedia.

Thus for π = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2…], the best rational approximations are:

```
3/1 = [3]
13/4 = [3; 4]
16/5 = [3; 5]
19/6 = [3; 6]
22/7 = [3; 7]
179/57 = [3; 7, 8]
201/64 = [3; 7, 9]
223/71 = [3; 7, 10]
245/78 = [3; 7, 11]
267/85 = [3; 7, 12]
289/92 = [3; 7, 13]
311/99 = [3; 7, 14]
333/106 = [3; 7, 15]
355/113 = [3; 7, 15, 1]
52163/16604 = [3; 7, 15, 1, 146]
52518/16717 = [3; 7, 15, 1, 147]
```*… (terms from [3; 7, 15, 1, 148] to [3; 7, 15, 1, 291])...*
103993/33102 = [3; 7, 15, 1, 292]
104348/33215 = [3; 7, 15, 1, 292, 1]
...

The above is the natural meaning of “best rational approximation”. This is also known as “best rational approximation of the first kind”. There is a different definition of “best rational approximation” under which the convergents *are* precisely all the best rational approximations: basically, instead of considering the distance , we consider . That is: A fraction is a **best approximation of the second kind** of a real number if for every fraction with and , we have

This measure turns out to have a nicer theory, but to omit specifying that this non-obvious definition is the one being used is misleading.

## Program

For illustration, here’s a C program (why it’s written in C is not important right now) that given a positive real number, generates its continued fraction, its convergents, and the sequence of best rational approximations. The function `find_cf`

finds the continued fraction (putting the terms in a[] and the convergents in p[] and q[] — excuse the global variables), and the function `all_best`

prints all the best rational approximations.

#include <math.h> #include <stdio.h> #include <assert.h> // number of terms in continued fraction. // 15 is the max without precision errors for M_PI #define MAX 15 #define eps 1e-9 long p[MAX], q[MAX], a[MAX], len; void find_cf(double x) { int i; //The first two convergents are 0/1 and 1/0 p[0] = 0; q[0] = 1; p[1] = 1; q[1] = 0; //The rest of the convergents (and continued fraction) for(i=2; i<MAX; ++i) { a[i] = lrint(floor(x)); p[i] = a[i]*p[i-1] + p[i-2]; q[i] = a[i]*q[i-1] + q[i-2]; printf("%ld: %ld/%ld\n", a[i], p[i], q[i]); len = i; if(fabs(x-a[i])<eps) return; x = 1.0/(x - a[i]); } } void all_best(double x) { find_cf(x); printf("\n"); int i, n; long cp, cq; for(i=2; i<len; ++i) { //Test n = a[i+1]/2 separately. Enough to test when a[i+1] is even, actually. n = a[i+1]/2; cp = n*p[i]+p[i-1]; cq = n*q[i]+q[i-1]; if(fabs(x-(double)cp/cq) < fabs(x-(double)p[i]/q[i])) printf("%ld/%ld,", cp, cq); //And print all the rest, no need to test for(n = (a[i+1]+2)/2; n<=a[i+1]; ++n) { printf("%ld/%ld,", n*p[i]+p[i-1], n*q[i]+q[i-1]); } } } int main(int argc, char **argv) { double x; if(argc==1) { x = M_PI; } else { sscanf(argv[1], "%lf", &x); } assert(x>0); printf("%.15lf\n\n", x); all_best(x); printf("\n"); return 0; }

## Examples

Here’s the output of this program, in about 0.003 seconds (i.e., it’s truly better than looping through all possible denominators!), line-wrapped for readability:

```
% ./a.out
3.141592653589793
3: 3/1
7: 22/7
15: 333/106
1: 355/113
292: 103993/33102
1: 104348/33215
1: 208341/66317
1: 312689/99532
2: 833719/265381
1: 1146408/364913
3: 4272943/1360120
1: 5419351/1725033
14: 80143857/25510582
13/4, 16/5, 19/6, 22/7, 179/57, 201/64, 223/71, 245/78, 267/85, 289/92, 311/99,
333/106, 355/113, 52163/16604, 52518/16717, 52873/16830, 53228/16943, 53583/17056,
53938/17169, 54293/17282, 54648/17395, 55003/17508, 55358/17621, 55713/17734,
56068/17847, 56423/17960, 56778/18073, 57133/18186, 57488/18299, 57843/18412,
58198/18525, 58553/18638, 58908/18751, 59263/18864, 59618/18977, 59973/19090,
60328/19203, 60683/19316, 61038/19429, 61393/19542, 61748/19655, 62103/19768,
62458/19881, 62813/19994, 63168/20107, 63523/20220, 63878/20333, 64233/20446,
64588/20559, 64943/20672, 65298/20785, 65653/20898, 66008/21011, 66363/21124,
66718/21237, 67073/21350, 67428/21463, 67783/21576, 68138/21689, 68493/21802,
68848/21915, 69203/22028, 69558/22141, 69913/22254, 70268/22367, 70623/22480,
70978/22593, 71333/22706, 71688/22819, 72043/22932, 72398/23045, 72753/23158,
73108/23271, 73463/23384, 73818/23497, 74173/23610, 74528/23723, 74883/23836,
75238/23949, 75593/24062, 75948/24175, 76303/24288, 76658/24401, 77013/24514,
77368/24627, 77723/24740, 78078/24853, 78433/24966, 78788/25079, 79143/25192,
79498/25305, 79853/25418, 80208/25531, 80563/25644, 80918/25757, 81273/25870,
81628/25983, 81983/26096, 82338/26209, 82693/26322, 83048/26435, 83403/26548,
83758/26661, 84113/26774, 84468/26887, 84823/27000, 85178/27113, 85533/27226,
85888/27339, 86243/27452, 86598/27565, 86953/27678, 87308/27791, 87663/27904,
88018/28017, 88373/28130, 88728/28243, 89083/28356, 89438/28469, 89793/28582,
90148/28695, 90503/28808, 90858/28921, 91213/29034, 91568/29147, 91923/29260,
92278/29373, 92633/29486, 92988/29599, 93343/29712, 93698/29825, 94053/29938,
94408/30051, 94763/30164, 95118/30277, 95473/30390, 95828/30503, 96183/30616,
96538/30729, 96893/30842, 97248/30955, 97603/31068, 97958/31181, 98313/31294,
98668/31407, 99023/31520, 99378/31633, 99733/31746, 100088/31859, 100443/31972,
100798/32085, 101153/32198, 101508/32311, 101863/32424, 102218/32537, 102573/32650,
102928/32763, 103283/32876, 103638/32989, 103993/33102, 104348/33215, 208341/66317,
312689/99532, 833719/265381, 1146408/364913, 3126535/995207,
4272943/1360120, 5419351/1725033, 42208400/13435351, 47627751/15160384,
53047102/16885417, 58466453/18610450, 63885804/20335483, 69305155/22060516,
74724506/23785549, 80143857/25510582,
```

All these terms are correct, though if you increase MAX you start getting errors because of precision. I’m myself impressed with how many terms you get with only 13 convergents. (As you can see, there’s a small bug where it sometimes doesn’t print the very first “n/1” approximation, or prints it incorrectly — I leave it for you to fix!)

You can try with √2, whose continued fraction is [1; 2, 2, 2, 2…]:

```
% ./a.out 1.41421356237309504880
1.414213562373095
1: 1/1
2: 3/2
2: 7/5
2: 17/12
2: 41/29
2: 99/70
2: 239/169
2: 577/408
2: 1393/985
2: 3363/2378
2: 8119/5741
2: 19601/13860
2: 47321/33461
3/2, 4/3, 7/5, 17/12, 24/17, 41/29, 99/70, 140/99, 239/169, 577/408, 816/577, 1393/985, 3363/2378, 4756/3363, 8119/5741, 19601/13860, 47321/33461,
```

Or the golden ratio φ = (1+√5)/2 whose continued fraction is [1; 1, 1, 1, …]:

```
% ./a.out 1.61803398874989484820
1.618033988749895
1: 1/1
1: 2/1
1: 3/2
1: 5/3
1: 8/5
1: 13/8
1: 21/13
1: 34/21
1: 55/34
1: 89/55
1: 144/89
1: 233/144
1: 377/233
2/1, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, 55/34, 89/55, 144/89, 233/144, 377/233,
```

(See the Fibonacci numbers? Here the convergents are all the approximants.)

Or with rational numbers like 4/3 = [1; 3]:

```
% ./a.out 1.33333333333333333333
1.333333333333333
1: 1/1
3: 4/3
3/2, 4/3,
```

or 14/11 = [1; 3, 1, 2]:

```
% ./a.out 1.27272727272727272727
1.272727272727273
1: 1/1
3: 4/3
1: 5/4
2: 14/11
3/2, 4/3, 5/4, 9/7, 14/11,
```

[**2011-11-04**: Fixed the bug and the description.]