Wednesday, November 18, 2009

Wish my math classes were like this!

Math Class (by Robert A. Kraus)

The math teacher addressed the class. "I have chosen a positive integer (base 10). It has 4 digits, none of which are 0. I have calculated the sum of its digits, the sum of the squares of its digits, and the product of its digits, and no 2 of these 3 quantities has the same number of digits. Consider the following 9 statements:
(1) The number is a prime.
(2) The sum of its digits is a prime.
(3) The sum of the squares of its digits is a prime.
(4) The number is a square.
(5) The sum of its digits is a square.
(6) The sum of the squares of its digits is a square.
(7) The number is triangular.
(8) The sum of its digits is triangular.
(9) The sum of the squares of its digits is triangular.

You must use them to determine the number."
"But they can't all be true!", interjected one of the students.
"I never said they were! Some of the statements are true and some are false."
"Well we will need more information. Tell us which are true and which are false."
"If I told you that you would easily be able to determine the number!"
"Well at least tell us how many are true."
"If I told you that now, you would be able to determine the number too easily!"
"Well, what more can you tell us?"
"Nothing! I have told you enough!"

What was the number?
A straightforward solution in Maple:

Friday, November 13, 2009

My first OEIS contributions!

I made my first ever contributions to N.J.A. Sloane's On-Line Encyclopedia of Integer Sequences yesterday. They're basically enumerations of all admissible basis for the postage stamp problem.
 ```k\h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ``` ```(A167809) 2 1 2 5 17 65 292 1,434 7,875 47,098 305,226 2,122,983 15,752,080 124,015,310 1,031,857,395 9,041,908,204 83,186,138,212 ``` ```(A167810) 3 1 3 13 86 760 8,518 116,278 1,911,198 37,063,964 835,779,524 21,626,042,510 635,611,172,160 ``` ```(A167811) 4 1 4 26 291 4,752 109,640 3,380,466 136,053,274 6,963,328,612 444,765,731,559 ``` ```(A167812) 5 1 5 45 750 20,881 880,325 54,329,413 4,727,396,109 563,302,698,378 ``` ```(A167813) 6 1 6 71 1,694 73,126 5,235,791 593,539,539 102,141,195,784 ``` ```(A167814) 7 1 7 105 3,407 217,997 24,929,035 4,863,045,067 ```
Anyone with a reasonable brute force solver can generate these exact numbers, so I don't really take much in terms of credit for being the "author". I can always submit more sequences by varying the parameters if I just want to senselessly "stake my claim" on them, so to speak, but I see little point in doing any more than I already did. I do think that these sequences are important for several reasons:
• One can quantify the size of the search space and its growth rate, and assess the limits of practicality of a brute force solver.
• Having some terms is better than none when you're trying to define a tight asymptotic bound, or better yet, an exact formula.
• More practically, these are the benchmark numbers to compare to once you start pruning the search tree.
• It's always useful to have these sequences on record since they may unexpectedly pop up elsewhere, or be in some other way related to other sequences in the encyclopedia.

Thursday, November 12, 2009

Robert A. Kraus' Logic Puzzles

I just found out about half an hour ago that GeoCities has shut down.

Within the last decade, I've only visited 2 sites within GeoCities: mine (created when I was still a teenager), and another by Robert A. Kraus. Frankly, only the latter is worth talking about.

Kraus had authored several logic puzzles and hosted it on the site. The most interesting collection for me is what he called "meta-puzzles". These puzzles are way too tedious to solve manually, and a spreadsheet program is the suggested tool to use.

I enjoyed these puzzles. If I were to introduce someone who enjoys puzzles and brain teasers to the joy of problem solving with a computer, this would be the way.

Here's my solution to one of his meta-puzzles in Maple.
Inheiritance Envelopes (by Robert A. Kraus)

A wealthy man had three sons all of whom were quite good at math and logic. To get a share of his inheiritance each had to correctly determine a positive integer which he had chosen. He told them that the number had four different non-zero decimal digits, in ascending order.

He prepared three sealed envelopes each of which contained a number. The first contained the product of the four digits, the second contained the sum of the squares of the four digits, the third contained the sum of the product of the first two digits and the product of the last two digits, and the envelopes were clearly marked as such. He showed the three envelopes to the three sons and had them each take one at random.

The sons were stationed at three different computers so that they couldn't communicate with one another (but were linked to the father's computer). After one hour they could submit a number or decline. Anyone who submitted a wrong answer would be eliminated and get nothing. If one or more submitted the correct answer they would each receive a share of the inheritance, and the contest would end with the others getting nothing. If no one submitted the correct answer they would be instructed to work on the problem for another hour. The process would repeat as often as necessary. Each of the sons decided not to submit an answer unless they sure it was correct.

At the end of the first hour no one had submitted an answer.
At the end of the second hour no one had submitted an answer.
At the end of the third hour no one had submitted an answer.
At the end of the fourth hour all three of them submitted the correct answer!

Can you determine the number?

Wednesday, November 11, 2009

SoD: 90% Milestone

I finally scored in the 90s today, entering the Top 50, thanks to a new brute force algorithm written from scratch. This was the minimum achievement that I set for myself, and I finally did it.

It's only going to get harder from now on just to maintain this score and/or rank, not to mention climb the ladder further. Thankfully, I still have a few unimplemented ideas up my sleeve.

Brute force can only take you so far, though. At some point I'm going to need to explore significantly different approaches. Again, thankfully I already have a few in mind.

Monday, November 9, 2009

Bit shifting in C#

Answer quick: what is `1 << 32`?

I would argue that `232` is a correct answer. It comes from an understanding of binary arithmetic, an important requirement when you need to optimize certain calculations for the digital computer hardware.

I would also argue that `0` is a correct answer. It comes from awareness of the range limitations of the primitive numeric data types in your choice of programming language, an important requirement when you need to take arithmetic overflows into consideration.

I didn't think a third correct answer is possible. Alas, I just found out today that in C#, `1 << 32 == 1`. I have to admit that this was a rather unexpected discovery. Fortunately I was able to find this "bug" rather quickly, and end up spending more time writing about it instead.

Apparently by design, C# shifts a 32-bit number using only the lower 5-bit of the count operand. Initially I thought this was a very odd, almost unjustifiable behavior, but apparently it comes from how x86 processors handle arithmetic shifts. An argument could be made that this behavior isn't appropriate for what is supposed to be a high-level programming language, though.

References:
I should also add that it's quite likely that `undefined` is technically a correct answer as well. I'm not about to look up the official C/C++ spec to confirm this, though.
I wonder if there's a language that accepts a negative count operand and just do what you'd expect it to. I don't think this scenario happens often, but I do remember specifically wishing for this feature once or twice in my 15+ years of programming.
AH *\$&(#! Java behaves like C# in this case too! GOOD TO KNOW!!!

Sunday, November 8, 2009

On aliakseis' Opus #2

Somewhere within the discussion threads on the Yahoo! Groups for AZSPCS is a link to a code that solves the `D=3` problem by brute force. After careful inspection of the code, I can safely say that I've fully understood it now.

The algorithm generates all admissible basis to find one with the best score. At each level of the recursion, it tries in increasing order all numbers strictly larger than the previous number, but less than or equal to the score of the numbers we have so far. Score is implicit in the global data structure that it maintains throughout the search. The common leave-it-as-you-found-it principle is enforced, and thus changes made to the data structure needs to be undone upon backing out of the recursion.

Conceptually, the data structure can be described as follows. Let `count[x][d]` be the number of ways the number `x` can be represented as a sum of exactly `d` numbers (`d = 1, 2,` or `3`) in the basis we have so far. The current score, then, will be the lowest value `s` such that `count[s][1]`, `count[s][2]`, and `count[s][3]` are all zeroes.

We start with no numbers in the basis, so `count` is initialized to all zeroes. Then, when a number b is introduced to the basis, we must update `count` as follows:
```count[b][1]++
for j = b+1 to 3*b
count[j][2] += count[j-b][1]
count[j][3] += count[j-b][2]```
It should be noted here that `count` needs to be updated left to right because of the directional data dependency. Conversely, to undo this update, we would need to go subtracting right to left, and decrementing `count[b][1]` after the loop.

The code essentially implements the above algorithm, spiced up with various low-level optimizations. The most important one here is the packing of `count[x][3], count[x][2], count[x][1]` into one number. This is quite ingenious because the two `O(D)` operations (checking if all are zeroes, and the shifted addition/subtraction) are now `O(1)`.

Another obvious optimization is the use of what I later found out is called the Duff's device. I'm familiar with the concept of loop unrolling, but was nonetheless previously unaware of this construct (or even that a switch statement can be (ab)used in this manner!).

And that pretty much describes the code in a nutshell.

Saturday, November 7, 2009

Son of Darts: An Introduction

2 weeks ago I came across Al Zimmermann's Programming Contests. The current contest, which ends in June 2010, is the Son of Darts. I later found out that this is an extension of an earlier contest in 2001 (hence the name).

I did some readings on the subject, and learned that this is the classic Global Postage Stamp Problem, which in the general case is an unsolved problem in number theory and computationally intractable (which of course makes the year-long contest the more interesting).

Here are some papers on the subject: