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.