A simple puzzle, with a foray into inequivalent expressions

[Needs cleanup… just dumping here for now.]

Mark Jason Dominus tweeted and later blogged about this puzzle:

From the four numbers [6, 6, 5, 2], using only the binary operations [+, -, *, /], form the number 17.

When he tweeted the first time, I thought about it a little bit (while walking from my desk to the restroom or something like that), but forgot about it pretty soon and didn’t give it much further thought. When he posted again, I gave it another serious try, failed, and so gave up and wrote a computer program.

This is what I thought this time.

Idea

Any expression is formed as a binary tree. For example, 28 = 6 + (2 * (5 + 6)) is formed as this binary tree (TODO make a proper diagram with DOT or something):

                   +
               6       *
                     2    +
                        5   6

And 8 = (2 + 6) / (6 – 5) is this binary tree:

                  /
              +       -
            2   6   6   5

Alternatively, any expression is built up from the 4 given numbers [a, b, c, d] as follows:
Take any two of the numbers and perform any operation on them, and replace the two numbers with the result. Then repeat, until you have only one number, which is the final result.

Thus the above two expressions 28 = 6 + (2 * (5 + 6)) and 8 = (2 + 6) / (6 – 5) can be formed, respectively, as:

1. Start with [6, 6, 5, 2]. Replace (5, 6) with 5+6=11 to get [6, 11, 2]. Replace (11, 2) with 11*2=22 to get [6, 22]. Replace (6, 22) with 6+22=28, and that’s your result.
2. Start with [6, 6, 5, 2]. Replace (2, 6) with 2+6=8 to get [8, 6, 5]. Replace (6, 5) with 6-5=1 to get [8, 1]. Replace (8, 1) with 8/1=8 and that’s your result.

So my idea was to generate all possible such expressions out of [6, 6, 5, 2], and see if 17 was one of them. (I suspected it may be possible by doing divisions and going via non-integers, but couldn’t see how.)

(In hindsight it seems odd that my first attempt was to answer whether 17 could be generated, rather than how: I guess at this point, despite the author’s assurance that there are no underhanded tricks involved, I still wanted to test whether 17 could be generated in this usual way, if only to ensure that my understanding of the puzzle was correct.)

Advertisement

Using Stellarium to make an animation / video

(I don’t have a solution yet.)

I just wanted to show what the sky looks like over the course of a week.

On a Mac with Stellarium installed, I ran the following

/Applications/Stellarium.app/Contents/MacOS/stellarium --startup-script stellarium.ssc

with the following stellarium.ssc:

// -*- mode: javascript -*-
core.clear('natural');  // "atmosphere, landscape, no lines, labels or markers"
core.wait(5);
core.setObserverLocation('Ujjain, India');
core.setDate('1986-08-15T05:30:00', 'utc');
core.wait(5);
for (var i = 0; i < 2 * 24 * 7; i += 1) {
    core.setDate('+30 minutes');
    core.wait(0.5);
    core.screenshot('uj');
    core.wait(0.5);
}
core.wait(10);
core.quitStellarium();

It took a while (some 10–15 minutes) and created those 336 images in ~/Pictures/Stellarium/uj*, occupying a total size of about 550 MB. This seems a start, but Imagemagick etc. seem to choke on creating a GIF from such large data.

Giving up for now; would like to come back in future and figure out something better, that results in a smaller GIF.

The “most natural” definition of the div and mod functions

[incomplete: must add examples and more discussion]

Most programming languages include a “remainder” or “modulo” function, and also an integer division (“quotient”) function. Given two integers and , let’s call the results of these functions and respectively.

For positive and , it is clear what and should be: is the largest integer such that , and is the remainder which therefore satisfies .

What should we do when, as frequently happens, is negative, or (as less frequently happens) is negative?

For negative and positive , there are two choices when lies between two multiples of (i.e. ):

(1) Set to the lesser value, so that continues to hold, or
(2) Set to the greater (and therefore smaller in magnitude) value.

There are very good reasons why (1) is preferable to (2): it ensures that the function is always positive no matter what the value of , so that, for example, .

And indeed that is what the more recent programming languages do. There is a table on Wikipedia: C, C++, Java, Go(!), OCaml(!), PHP, all have the “bad” behaviour, while Maple, Mathematica, Microsoft Excel, Perl, Python, Ruby have the “good” behaviour. Some languages have separate functions for both behaviours (e.g. Haskell has quotRem and divMod functions, similarly Common Lisp, Fortran, MATLAB).

There’s also the question of what to do when is negative, which turns out not to matter much (as long as it’s consistent with the above). One defintion is to continue to have be the lesser value, and the other is to continue to insist that . Both are fine, though sometimes the latter is nicer.

These are elaborated in The Euclidean Definition of the Functions div and mod by Raymond T. Boute, ACM Transactions on Programming Languages and Systems, Vol 14, No. 2, April 1992.

Colliding balls approximate pi

Found via G+, a new physical experiment that approximates , like Buffon’s needle problem: The Pi Machine.

Roughly, the amazing discovery of Gregory Galperin is this: When a ball of mass collides with one of ball , propelling it towards a wall, the number of collisions (assuming standard physics idealisms) is , so by taking , we can get the first digits of . Note that this number of collisions is an entirely determinstic quantity; there’s no probability is involved!

Here’s a video demonstrating the fact for (the blue ball is the heavier one):

The NYT post says how this discovery came about:

Dr. Galperin’s approach was also geometric but very different (using an unfolding geodesic), building on prior related insights. Dr. Galperin, who studied under well-known Russian mathematician Andrei Kolmogorov, had recently written (with Yakov Sinai) extensively on ball collisions, realized just before a talk in 1995 that a plot of the ball positions of a pair of colliding balls could be used to determine pi. (When he mentioned this insight in the talk, no one in the audience believed him.) This finding was ultimately published as “Playing Pool With Pi” in a 2003 issue of Regular and Chaotic Dynamics.

The paper, Playing Pool With π (The number π from a billiard point of view) is very readable. The post has, despite a “solution” section, essentially no explanation, but the two comments by Dave in the comments section explain it clearly. And a reader sent in a cleaned-up version of that too: here, by Benjamin Wearn who teaches physics at Fieldston School.

Now someone needs to make a simulation / animation graphing the two balls in phase space of momentum. :-)

I’d done something a while ago, to illustrate The Orbit of the Moon around the Sun is Convex!, here. Probably need to re-learn all that JavaScript stuff, to make one for this. Leaving this post here as a placeholder.

Or maybe someone has done it already?

The rest is commentary

Famous verses appear in many variants. Thanks to Google, it is easy to find many of them. For “paropakāraḥ puṇyāya, pāpāya parapīḍanam”, Google throws up a lot of variants for the first half.

The Vikramacarita has:

śrūyatāṃ dharmasarvasvaṃ, yad uktaṃ śāstrakoṭibhiḥ /
paropakāraḥ puṇyāya, pāpāya parapīḍanam

Other variants are:

saṅkṣepāt kathyate dharmo janāḥ kiṃ vistareṇa vaḥ |
paropakāraḥ puṇyāya pāpāya para-pīḍanam ||Panc_3.103||

or

aṣṭādaśapurāṇeṣu vyāsasya vacanadvayam /
paropakāraḥ puṇyāya pāpāya parapīḍanam //

or

ślokārdhena pravakṣyāmi yaduktaṃ grantha-koṭibhiḥ
paropakāraḥ puṇyāya pāpāya parapīḍanam

Going by the first line gives other verses:

śrūyatāṃ dharmasarvasvaṃ śrutvā caivāvadhāryatām | (or caiva vicāryatām ।)
ātmanaḥ pratikūlāni pareṣāṃ na samācaret ||

[Cāṇakya-nīti, Pañcatantra, Subhāṣitāvalī etc.]

See also:
https://en.wikipedia.org/wiki/Golden_Rule

prāṇā yathātmano ‘bhīṣṭā bhūtānām api te tathā |
ātmaupamyena gantavyaṃ buddhimadbhir mahātmabhiḥ

तस्माद्धर्मप्रधानेन भवितव्यं यतात्मना ।
तथा च सर्वभूतेषु वर्तितव्यं यथात्मनि ॥ Mahābhārata Shānti-Parva 167:9
(http://blog.practicalsanskrit.com/2013/05/do-unto-others-golden-rule-of-humanity.html)

05,039.057a na tatparasya saṃdadhyāt pratikūlaṃ yadātmanaḥ
05,039.057b*0238_01 ātmanaḥ pratikūlāni vijānan na samācaret
05,039.057c saṃgraheṇaiṣa dharmaḥ syāt kāmād anyaḥ pravartate

As Hillel says, the rest is commentary.

For (some) commentary, go here.

New Year

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

1. Why does the new year begin on January 1?
2. 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.

Conscious consumption

Late-night sleepy ramblings; please do not read :p

I have been taking a break, and it has helped me gain some perspective. Or so I thought.

Like some who might be reading this, I subscribe to a large number of blogs. Google Reader says 106 subscriptions, but a few of them are aggregators which combine the updates from several blogs.

For about three months (since June 10th, I think), I have not been reading them, nor reading the news. I’m not exactly sure why… it started as a day’s break (which was a big deal), then became four days (which was an even bigger deal), then it got easier and easier. Probably, I thought I was taking a break from (parts of) the internet in order to catch up with (parts of) my life. It didn’t work, of course. I merely found other sinks in which to dump my time. (I spent more time on Wikipedia than ever before, read more actual books than I had in the last couple of years, and so on.)

I did, however, discover a couple of things.

One is that Google Reader stops updating the count of unread items at “1000+”. (It also automatically marks items more than 30 days old as read, and, as I have “only” about 1500 items a month, I don’t know if it counts to “2000+”.)

The other is some general observations about what our lives have become.

It seems that the meanings of words like “recreation” have become somewhat quaint. Now “entertainment” is not always something to indulge in because one requires relaxation, or because it is a rewarding pursuit in itself, but simply “because it’s there”.

Macports and Fink: software packaging for Mac OS X

One of the ways in which (good) Linux distributions—by which I mean Debian and Ubuntu—are better than Mac OS X is that it’s trivial to install, upgrade and uninstall packages: you just use the package management system.

On OS X, things aren’t so great. There is a good set of software that comes installed by default — Perl, Python, Bash, Zsh, CVS, Subversion, Emacs, Vim… — but at some point of time you’ll need more. (Mutt, MPlayer…)

This is where the likes of Macports and Fink come in. They package free software, somewhat analogous to what Linux distributions do, although neither comes close to any good distribution.

Fink was the first one I tried. They have a better-looking website and it says “Fink uses Debian tools like dpkg and apt-get to provide powerful binary package management.” Oh it’s like Debian, so it must be good, right? Wrong.
After trying Fink for a few months, I realised that using Debian tools does not a Debian make. As has been astutely observed, “the fanatical devotion of the Debian package maintainers makes the difference”. The packaging system — apt, dpkg — are just an offshoot of their great work, but without similar packagers, it’s no good. The Fink developers are competent and good, but their packages just aren’t satisfactory. Everything in their “stable” category is too old, and their “unstable” category really is unstable. And as far software with a GUI goes, they have only X11 apps, no Aqua ones.

Macports is more pragmatic. They have only one category, no stable v/s unstable. Everything is at the newest version that someone has managed to compile. They move fast, are more responsive to user questions, and have a more active IRC channel and mailing lists. They are also clearly less “l33t” than the Fink people, because their system is written in Tcl (really!) by people who have long since disappeared, and none of the current ones have a very good idea of what to do with the system. Nonetheless, they recognise that it is the packages that are important, not the system.
There are other bad things — (1) no binary packages, must compile from source. Improving. (2) Variants. Stupid idea, but could be worse.

Gentoo Prefix. I tried it. It’s Gentoo. It sucks.

Pkgsrc: Haven’t tried it.

Drag-and-drop on web pages

Many web interfaces (like the WordPress dashboard in which I type this) allow you to drag and drop sections of the page to rearrange them. I think I first saw it when the personalised Google homepage (google.com/ig) came out, but I don’t know if it was the first. Here are some libraries that seem to help you

• JQuery: UI/Droppable
• script.aculo.us: Draggable
• Yahoo! UI Library: Drag & Drop Examples
• Google Web Toolkit (example)
• Dojo toolkit: I know it has it, but I can’t find it and here it is.

So it seems that all JavaScript frameworks have it. It also seems that JQuery has “won”.

But it seems YUI’s “Reordering a List” example is the closest match to what we actually want, but it seems to require too many lines of code.

Some of the rest seem even worse: unless you are actually using the library for a lot of things, it is simply too much code to just drop into a bare-bones web page you’ve been writing from scratch.