Wednesday, December 23, 2009

Fun stuff ahead

ischarmichael := n -> `and`(op(
map(
p_e -> (
(p, e) -> (irem(n - 1, p - 1) = 0) and (e = 1)
)(op(p_e)),
ifactors(n)[2]
)
));
  • "Charmichael? Prime? Congratulations! You satisfy every freshman's dream!"
    "Ghatage and Scott prove using Fermat's little theorem that (a+b)^n == a^n + b^n (mod n) (the freshman's dream) exactly when n is a prime or a Carmichael number" (source)
  • "3^2 x 29 x 41? Congratulations! You are 66.67% sexy!"
I have to say, though, that I need to start leveraging more powerful factorization and primality testing libraries for the back-end. Or Wolfram Alpha can just give me my API key already.
Okay, I found out that you can actually (ab)use Wolfram Alpha without an API key. Some fun queries that usually return results right away in plain scrapable text:
isprime {2,3,4}
ithprime {2,3,4}
factor 123456789
nextprime {10,100,1000}, prevprime {10,100,1000}
solve x^3+y^3=2716057 over integers
That last one, of course, is the infamous Bender-Flexo test.

Friday, December 18, 2009

First usage report

This morning I asked someone on Facebook who has hundreds of friends to test Are you prime? (up until that time, I've only tested such scenarios through simulations). It worked fine and found a few dozens prime user IDs. He met this with skepticism, however. He simply doesn't think that all of those numbers can possibly be primes. What his opinion was based upon, I dare not ask. It was obviously nothing mathematical, thus contradicting his own self-professed love for the subject.

Mathematics, of course, does not care what you think is and isn't true. Depending on the kind of person you are, I guess this can either be a good thing or a bad thing. In this case, though, it's a bad thing because he decided not to publish this result because he found it disagreeable (despite it being something that is rigorously verifiable).

I would be interested in the result of the following experiment: ask people to pick which of {4999999, 4916731} is a prime. Based on this anecdote, my guess is that most people would erroneously pick the latter, because "4999999 just doesn't look prime".

In any case, this would limit the potential growth of an application which already has a very niche appeal. As sad as this is to say, it appears that math just doesn't appeal to most people. And even when it does, half the time they already know their user ID is not a prime because it's even, and they may not be curious enough to check if any of their friends' are. Now I found out that even if they went as far as trying the app, they may still be skeptical enough of the result, severely limiting its virality by not sharing it.
There may be another explanation for his distrust of the result: perhaps it's not that the primes don't pass his own personal smell test, but that so many were found relatively easily.

If his limited exposure to prime numbers is through reading the occasional articles reporting that they just found another one after a lengthy and laborious search, then he might have the wrong impression that prime numbers are rare and hard to find.

A ridiculous suggestion, perhaps, but what other reasonably reasonable explanations are there?
Fun fact: several of my app's meager 24 users are from Italy. How it got there in the first place, I'll never know now (it happened before I implemented a more verbose logging system). None of them would publish their results, though. I wonder if language is the issue. Then again, the app uses basic English to speak the more universal language of mathematics! If absence of localization is such an issue, then why would they try it out in the first place??

Facebook app update

I've had ideas for other apps for a while now, so I thought I was done with Are you prime?, but I ended up updating it. I (re)learned some SQL to do some rudimentary logging. I'm not 100% sure that it's impervious to injection attacks, but we'll see. More visibly, I also used AJAX so that it can now check all of a user's friends.

The bug I pointed out on phpseclib was acknowledged and fixed. More importantly, though, now that I had the time to look at the code more carefully, I realized that their primality test algorithm is Miller-Rabin's, i.e. it's probabilistic. That defeats the purpose of the app as a silly little quiz based on absolute mathematical truth, but on the bright side, I learned a lot from the experience.
I just sent in a request for a Wolfram Alpha API key. I'm determined to do some more ambitious things with this idea.

I think it's a good idea for them to give me a free API key so I can help promote Wolfram Alpha within Facebook through my app. Of course, it's probably a better idea for them to write their own official Facebook app to do the same thing.

Sunday, December 13, 2009

First Facebook app

I wrote a silly little Facebook app (Are you prime?) that checks if a Facebook user's ID is a prime number. It also goes through the friends list and does the same check.

Some issues I've found:
  • How do I deal with the scaling problem if someone has a large number of friends? Can my app even finish fetching the list without timing out? It looks from the API documentation that this is an all-or-nothing request.
  • I used phpseclib to perform the primality testing. I'm quite certain that it has a major bug in that it determines all integers 3 <= n <= 1000 are composites. I added a work-around, but it makes me wonder if there are other major bugs that would have embarassing effects on my app. I would hope that something so simple would at least be correct.
I don't have time to implement all this, but here are some ideas:
  • Compute other mathematical properties about the number. Make the app find as many interesting thing as possible with any number. Of course, this would now become obvious Wolfram Alpha territory.
  • Animated trial-division factorization using client-side Javascript. This is actually not a half-bad idea.
  • Find interesting facts in pairs of numbers (i.e. a user's ID and one of his/her friends'), e.g. point out friendly pairs, sexy primes, etc.
  • Deal with the large friends list problem by making the app more dynamic. Maybe integrate this feature with the previous one, e.g. let users select a bunch of friends and then say something mathematically interesting about the whole group ("You're all members of a prime constellation!").
  • Log usage information to database.
Some comments on the social aspect of the app:
  • I really like the fact that right now my app encourages user-to-user connection by looking if any of a user's friends have prime IDs, and making it convenient for them to post on other people's wall to share this discovery. This way, even if a user is not prime, they can still potentially get something rewarding out of it.
  • Make it competitive by assigning points for having a prime user ID and for knowing people who do. This may lead to people aggressively seeking to connect with other people, although there will be obvious bias with people gravitating toward those whose user ID are primes.

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.

Links:

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:
More links on the problem: