Just for alan.com

Posted 30th 2016f March, 2016 by aielyn
Categories: Uncategorized

Hi everyone at alan.com, Glen here. Yes, this is my blog. If you really want to stickybeak, check out my comments about my efforts to get fit, further down, or the maths stuff that I posted most recently (in 2011).

More on Mersenne

Posted 8th 2011f August, 2011 by aielyn
Categories: Mathematics, Prime Numbers

I wrote this something like a year and a half ago, but I never actually hit the “publish” button. Well, here it is:

I’ve continued to look into the whole Mersenne factoring issue, and I’ve generalised my equations somewhat.

Suppose that n|2^p-1 and f doesn’t divide 2^p-1. Then, we have

n | \gcd(2^p-1, (nf-a)^p+a^p)

Let a = 2pq+f and n = 2pm+1, so that n | \gcd(2^p-1, (p(mf-q))^p + (2pq+f)^p). If we now assume that mf-q = 2^k c, then we get that

n | \gcd(2^p-1, (pc)^p + (2pq+f)^p)

This is a more general form than seen in the previous post. If we take f=1 and c = 2pr+1, then we get a useful subset:

n | \gcd(2^p-1, p^p (2pr+1)^p + (2pq+1)^p)

To see the power of this, consider that, for p=41, m=163. If we take r=0, then q = 35. But if we take r=7, then q=0.

Of course, p=41 is relatively uninteresting, so we look for a harder example. For p=67, m=1445580, and thus the best q = 397004. But if r=337, then q=492. And because 2pr+1 and 2pq+1 are of the same form, you only need to calculate (2pq+1)^p 492 times in total while searching, and when you calculate for q=337, you can reuse the result in testing r=337. There may be further ways to accelerate or simplify the process, too.

A change of focus

Posted 2nd 2009f October, 2009 by aielyn
Categories: Uncategorized

Well, this blog has basically been left inactive for quite a while. I decided I’d start using it again… but in a different way.

As some may be aware, I’m a mathematician (actually, Mathematical physicist, but I’m also big on pure Mathematics). So I’m going to turn this blog into a mathematical blog. Sorry to those who severely dislike mathematics… but you should really get over it, maths is fun.

Anyway, this post will cover some thoughts I’ve had regarding the Mersenne Prime search.

What is the Mersenne Prime search? It’s a search for primes of the form 2^p - 1, where p is a prime number (if p isn’t prime, then 2^p - 1 cannot be prime). Numbers of that form are known to be prime for p=2,3,5,7,13,17,19,31... – but it’s not true for all primes p by any means. So that’s where the “searching” comes into it.

The common method of testing Mersenne numbers to see if they are prime is to use what is called the “lucas-lehmer test”, which is relatively fast, but still extremely slow when you get larger powers. It is also incapable of determining any factors of the number if it is composite. To date, we know of less than 50 Mersenne Primes. But I think it is possible to come up with a faster prime-test algorithm. And here’s a thought I’ve been having.

Mersenne numbers with prime powers can only even have factors of the form 2kp+1, with k=0 and k=\frac{2^{p-1}-1}{p} being equivalent to the trivial factors 1 and 2^p-1. This gives us a hint as to how to test for factors. But it’s not quite enough.

Suppose that n is a factor of 2^p-1. Then n | \gcd(2^p-1,(n+a)^p-a^p) for all values of “a”. This is because a-b | a^p-b^p. This fact can be used to derive a number of interesting results. What is notable immediately is that if either n+a or a is a multiple of 2, you can divide that number by 2 and not change the result of the gcd operation – this is because applying 2^p = 1 in the second part of the gcd doesn’t change the result of the gcd.

One choice of a that is interesting is a = -(2pq+1), which, assuming that n=2pm+1, allows us to conclude that n|\gcd(2^p-1,(2p(m-q))^p + (2pq+1)^p). But we can go further – if the difference between m and q is a power of 2 (that is, m-q = 2^k), then n|\gcd(2^p-1, p^p + (2pq+1)^p), because of the aforementioned 2^p = 1 rule. Because q is an arbitrary number we have chosen, anyway, the requirement that m-q = 2^k is easily satisfied by choosing q = m-2^k.

What this means is that q can be chosen to be the distance between m and the nearest power of 2 to m. For instance, if p=41, the smallest m (not counting m=0) is m=163. For this value of m, the smallest q is q = 163 – 128 = 35. But in testing q=35, you automatically are also checking m = 36, 37, 39, 43, 51, 67, 99, 291, 547… and so on. And so, a greater number of factors are tested at the same time. This advantage is good for smaller values of q, but as q increases, the number of factors being tested shrinks. Thus, more needs to be done.

Another step that can be taken is to note that p is not a factor of 2^p-1, and thus can be divided out of the right hand side. This gives, using p^{-1} = 2\frac{2^{p-1}-1}{p} under the gcd, the conclusion that (put on the next line for clarity):

n | \gcd(2^p-1, (\frac{2^{p-1}-1}{p}-q)^p-1)

There are a number of advantages to this form – for one, p^p doesn’t have to be calculated. For another, rather than having to multiply numbers for each q, one only has to add them, before raising to the given power. It also shows us an interesting formula – if we choose q such that \frac{2^{p-1}-1}{p}-q = 2^j, then n is equal to 2^p-1. And this will be true for any integer j. Note that n hasn’t changed throughout this consideration, so one can propagate this conclusion back throughout the sequence. However, this conclusion isn’t useful, as it is true whether 2^p-1 is prime or not, and doesn’t determine any factors.

To demonstrate this approach in action, consider p=29. For this number, 2^{29}-1 = 536870911. The value \frac{2^{p-1}-1}{p} = 9256395. Now, as it so happens, the smallest m for this number is m=4, which is a power of 2, and thus can be found with q=0. So we test like this:

\gcd(2^{29}-1, (\frac{2^{28}-1}{29})^{29}-1) = \gcd(536870911, 9256395^{29}-1)

This is equal to gcd(536870911,k) where k is of the order of 10^{202}, and thus won’t be actually included here. But what I can say is that k = 253486758 \mod 2^{29}-1, and therefore, the gcd(536870911,k) = 233. 233 is a prime factor of 536870911 (in fact, 233 = 2*29*4 + 1, just as I said – the m = 4). Interestingly, if one uses q=3, one actually gets the product of TWO factors out, of the three prime factors of the number. This is because the second m value is m=19 = 16+3, while the first one is m=4 = 1 + 3. And so, the gcd ends up being 233*1103 = 256999.

Now, there are avenues of investigation I still have, to try to further refine the approach. For instance, if m_1 and m_2 are both m-values for factors of a prime number, then m_1 + m_2 = \frac{2^{p-1}-1}{p} \mod p. This fact may be of value, in conjunction with the aforementioned gcd considerations, to further narrow the number of situations requiring testing.

Why does America hate liberals and socialism?

Posted 13th 2009f January, 2009 by aielyn
Categories: Philosophy, Politics

I honestly cannot understand it. Why is America, on the whole, so blind that the concept of being “liberal” in America is equivalent to what most other developed nations consider “conservative”? Why is Socialism so excessively maligned in America that Obama nearly lost the election for the phrase “spread the wealth”?

You keep hearing “Free Market” this and “Free Market” that from American media, and from the politicians. Even the most left-wing members of congress and senators espouse Free Market ideals – sure, they say that some regulation is necessary, but it’s only ever the bare minimum necessary. Why? And why is it that America is the only developed nation that had a backlash that led to “Happy Holidays” becoming almost the symbol of hatred, when it’s actually the best choice for tolerance?

Why is the country best-known for “separation of church and state” being in their constitution also the country most rife with religion being imposed on its citizens (at least amongst the developed countries)? Why is my own nation of Australia more tolerant of other religions, without having such a constitutional requirement?

Why am I writing about this now? Because I just watched a video that was somewhat eye-opening. I’ll link it here for you to watch (after the jump).

Read the rest of this post »

To review critiques

Posted 15th 2008f December, 2008 by aielyn
Categories: Video Games

Well, it’s been a little too long, again, but not nearly as bad as the last gap.

There was a recent post on Kotaku about Journalism versus Criticism, which refers to a comment by someone during a roundtable on the issue of reviews, and how to write them. In that comment, the person notices that, when most sites review a game, they’re actually trying to critique it, even though that isn’t the purpose of reviews.

The point, of course, is that reviews are, as he puts it, “consumer reports on the elements of a game that advise the person of what they’re buying”. In other words, they’re intended to inform the reader on what they’re buying, rather than to work out how artistic and innovative a game is.

Read the rest of this post »

A post after a long delay

Posted 14th 2008f October, 2008 by aielyn
Categories: Video Games

Well, it has been a fair while since I last posted, so I thought I’d make a post reviewing what has happened in gaming since the last post.

First, there’s E3. I made a prediction that E3 would be huge this year… I was off by a long, long shot. The thing is, had I actually paid attention to how Nintendo would view E3, and Nintendo’s overall strategy, I would have seen what was to come from a mile away. For you see, Nintendo placed a lot of their focus at E3 on peripherals and casual games. The only real “core” announcement was that GTA would be coming to the DS. As you can see by looking a couple of blog posts back, I made predictions of a long list of titles revealed at E3… and yes, I was way off. Most “core” gamers were waiting for a repeat of Nintendo’s spectacular E3 2006, and thus were beyond disappointed when it was merely comparable to E3 2007.

Mind you, the announcements that were made weren’t all that bad – a new peripheral that would make the Wiimote significantly more sensitive to rotational motion, thus allowing 1-to-1 motion control, along with a game that shows off its capabilities. A voice chat solution in the form of the “Wii Speak” microphone, to be introduced late in 2008 along with the newest entry in the Animal Crossing series.  Wii Music to be released in 2008 was also announced, with gameplay shown off… albeit rather poorly.

None of this on its own would be a problem. The problem was that they didn’t announce anything else of significance, resulting in a lacklustre E3 presentation. But as I said, we should have seen it coming from a mile away. Why?

Because E3 changed between 2006 and 2007. In 2006, it was the Electronics Entertainment Expo, an event for the gaming public first and foremost. It was also Nintendo’s big coming-out, their chance to show off the Wii in all its glory. In 2007, E3 had become the “E3 media and business summit” – that’s right, a summit for media and business, not for the public. Indeed, the public weren’t even allowed in. In both 2007 and 2008, Nintendo targetted their presentations to who would actually be in attendance – mainstream media and potential investors. And there’s nothing that the mainstream media and potential investors love more than peripherals and simple games that’ll sell hugely well, unless it’s the announcement of an extremely huge franchise showing up on a Nintendo platform – GTA.

What’s more, there was a significant risk that Microsoft or Sony would start actually “attacking” Nintendo by shifting towards the new value system that Nintendo introduced with the Wii.  That, too, was a good reason for Nintendo to emphasise their “casual” expanded audience side. However, neither Microsoft nor Sony bothered to attack Nintendo, thus making Nintendo’s defensive mode useless – Microsoft and Sony instead targetted each other, as they have done so many times before.

Disaster suddenly popped up on the OFLC’s classifications board, despite rumours that it had been cancelled. A couple of weeks later, details and screenshots of the game started to show up again, and surely enough, the game was still on its way. It has now been released in Japan, and will be releasing in PAL regions in November. Strangely, Nintendo aren’t releasing it in America until they see how it performs in other regions… an odd choice, given that Disaster’s style best suits the American core gamer crowd, and the game itself is set in America. Suffice it to say, the confirmation that this game was coming in 2008 was a nice surprise.

More games have been announced for the Wii, too – for instance, Cursed Mountain is yet another survival horror title. But most of these announcements happened at the next two significant conferences.

The first of these was Nintendo’s Fall conference, which was really two conferences – one in Japan, the other in America, held on the same day. Some “hardcore” gamers say that this was Nintendo making up for their poor E3 showing. Those with a critical eye, however, see that it was a matter of audience – at E3, it was mainstream media and potential investors. At this Fall conference, it was gaming media almost exclusively. And what did Nintendo announce there?

First Party titles: Punch Out, Sin and Punishment 2, Trace Memory Wii, Endless Ocean 2,  Cosmic Walker, Dynamic Slash, Tact of Magic, Spawn Smasher, and Line Attack Heroes, as well as Fire Emblem: Shadow Dragon and Mario & Luigi 3 on the DS, and I believe there were a couple more DS titles, too.

Third Party titles: Let’s Tap, 428, Family Ski World Ski and Snowboard, Dynasty Warriors, Joysound, Tenchu 4, Harvest Moon: Animal March, Rune Factory Frontier, as well as a number of DS titles. And the biggest of the revelations? Final Fantasy Crystal Chronicles: Echoes of Time to release on Wii and DS with connectivity, separate from The Crystal Bearers.

And then there’s the “Play on Wii” line of Wiimakes of classic Nintendo Gamecube first-party titles, like Pikmin, Metroid Prime, and Donkey Kong Jungle Beat. And Nintendo reconfirmed  the existence of Pikmin 3, distinct from the Wiimake of Pikmin. And they announced the DSi, which is a half-generation step up from the DS Lite – much as the GameBoy experienced a half-generation step in the form of GameBoy Colour.

And then there’s TGS, where many, many DS titles and Wii titles were shown off, even though Nintendo themselves weren’t there. Arc Rise Fantasia, Little King’s Story, Sonic Unleashed, and others were in attendance… but bigger news came, in the form of Suda 51, who announced that the sequel to No More Heroes, called “No More Heroes: Desperate Struggle”, was revealed to be coming to the Wii exclusively. And it’s not the only info to come from TGS, either… but my post has gone on long enough.

Suffice it to say, the Wii is looking to have a blockbuster year, as is the DS/DSi. And to think, we don’t even know a quarter of the titles that we’ll be seeing next year.

Political disruption

Posted 24th 2008f June, 2008 by aielyn
Categories: disruption, Philosophy, Politics

I’ve posted in reference to Sean Malstrom’s writings before, but something in one of his recent news posts, EA versus Ubisoft; Purpose Brand Vs. Birdmen, caught my eye. Here’s what he said:

When Xbox 360 gamers protest, Ubisoft replies, “You guys don’t know business. We must appeal to the demographics of the system.” You only appeal to demographics if you are running for Congress. Politicians pander. Businesses make products. If your product’s differentiation is just pandering, it won’t sell. If the product’s differentiation is better performing a job, it will sell.

And this is what made me stop and think. I didn’t even finish reading the article (I will after posting this), because I was too inspired to focus on reading.

Why do politicians pander? Why do people running for congress, or political appointments in general, appeal to demographics? Read the rest of this post »


Follow

Get every new post delivered to your Inbox.