Euler Project: Challenge #3

Ok, so a while back (I don’t remember exactly when). I tried to get into the Euler Project. What it is is a series of difficult mathematical (programming) challenges. When I first tried it, I solved the first two challenges, and couldn’t progress much further.

Anyway, I was recently on a bit of a programming spree, and gave challenge #3 another shot. Instead of coding my solution in Javascript, I have now switched to Python (a newer, lower level, yet more elegant, programming language). This post is an explanation of how I solved it, so if you don’t want the solution spoiled, go and figure it out yourself (then please come back here to tell me how inefficient mine is).

The exact problem, as stated on the website, is:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

As you can see, it is quite a nicely stated problem since it gives you a number you can test out before trying to compute the highest prime of the monster 12-digit number. Initially, I went about coding my solution in a fairly obvious way (pseudo code)

loop bigNumber:

  if number%bigNumber == 0 (i.e. if there is no remainder, then it’s a factor) then
   loop through factor to check if it has factors. if it has none, then it’s prime!

Now, this logic worked fine for the relatively small 13195 (in 0.011 seconds, I might add) but when I threw the huge number at it, the program just hung (sat there, showing no result). After examining it in more detail, I found that it was simply going to take too many life times to check all the factors.

However, I knew there must be a solution that didn’t involve a supercomputer, since I know a guy who solved this problem. Back to the drawing board…

My basic problem was one of efficiency. So in my second version of the program, I changed the program in two different ways. I manually multiplied the number (also known as chunking, a mistake in hindsight, since the computational equivalent of long-division is, in fact, faster). The second change I made was a bit more complicated, but I personally found it fascinating. So, please humour me for a moment with this explanation:


Let’s find out if 13 is a prime number.
So we’ll check the potential factors one by one:

  1. 2 times 2 is 4
  2. 2 times 3 is 6
  3. 2 times 4 is 8
  4. 2 times 5 is 10
  5. 2 times 6 is 12
  6. 2 times 7 is 14 (greater than 13, so we’ll jump to the next number)
  7. 3 times 2 is 6
  8. 3 times 3 is 9
  9. 3 times 4 is 12
  10. 3 times 5 is 14 (greater than 13, so we’ll jump to the next number)
  11. 4 times 2 is 8
  12. 4 times 3 is 12
  13. 4 times 4 is 16 (greater than 13, so we’ll jump to the next number)
  14. 5 times 2 is 10
  15. 5 times 3 is 15 (greater than 13, so we’ll jump to the next number)
  16. 6 times 2 is 12
  17. 6 times 3 is 16 (greater than 13, so we’ll jump to the next number)
  18. 7 times 2 is 14 (greater than 13, so we’ll jump to the next number)
  19. 8 times 2 is 16 (greater than 13, so we’ll jump to the next number)
  20. 9 times 2 is 18 (greater than 13, so we’ll jump to the next number)
  21. 10 times 2 is 20 (greater than 13, so we’ll jump to the next number)
  22. 11 times 2 is 22 (greater than 13, so we’ll jump to the next number)
  23. 12 times 2 is 24 (greater than 13, so we’ll jump to the next number)

Now, since none of the numbers we’ve checked multiplied neatly into 13, we can conclude that 13 is a prime number. However, did you notice that after 4, every single potential factor we checked had already been checked in reverse?

For example, 5 times two (line 14) had already been checked (as 2×5) on line 4!

By simply ending the sequence when we start to see the same number again, we half the number of steps needed. If we do this for a bigger number, like 23, we cut it down by 6 sevenths! So as you can imagine,

There were a few other efficiencies I implemented (like not chunking, for example) and there might even be more still (like looking into how the program does long division, and trying to make it easier relative to the problem). But as it turns out, this simple change knocked the program run time from multiple lifetimes to about 3 seconds! So yes, I did find the highest prime number that factors into 600851475143 and I hope that you can too!


I really enjoyed this challenge, and can see myself attempting more in the future (even reattempting the ones I’ve done in order to do them better). I also see myself switching to a lower level language (like C), so that I can program an even faster and more efficient solution (even though it will make doing so more complex). Perhaps this project can be my doorway into really understanding the truly complex mathematics which has hitherto evaded me.

Advertisements

More Toki Pona

One day I’ll get sick of this constructed language once and for all, but for the moment, there still seem to be some things that bring me back to Toki Pona. I had a more thorough read of the book today, and frustratingly read through the “Toki Pona Proverbs section”, which managed to concentrate all the things that I didn’t like about the language…

And don’t get me wrong, the sound of the words doesn’t bother me that much. My current solution (though technically breaking the phonetic rules) are simply to change the stress patterns of the language. So instead of saying TOki POna LI TOki POna, one says toKI poNA li toKI poNA, which personally I find sounds a lot better.

No what bothers me is the shallow philosophy that seems to sit in the background of The Toki Pona Book: Truth is Relative, Simplicity is Goodness, non-essentials are bad (literally “Ike). So instead of rehashing all these frustrations, i decided to write a Toki Pona “sequence” (it doesn’t display enough structure to be called a poem, but it might just resemble one):

pona li pona ala nanpa ali
 
 wan ijo li pona ala e ali
 wan li pona e oko
 mute ijo li ike e ala ali
 oko li oko e mute pona
 
 mute ali li ike ala
 mute li pona
 wan wan li ike ala
 wan li pona
 
 pona li pona ala
 ike li ike ala

And no, don’t worry. This time, I wont be daft enough to leave you without a translation, even though it is rough, and won’t carry the same tone as the (extremely ambiguous) original:

simple is not good always
 
 one thing does not make good all
 one does good to the eye
 many things do not bad to all
 the eye sees a lot good
 
 not many is all bad
 many is good
 one one is all bad
 one is good
 
 simple is not good
 non-essential is not bad

If you concluded that that made very little sense, don’t worry. You’re probably right!

Freedom (of speech) as the founding principle of politics

I recently started getting into an interview show called the Rubin Report. I don’t particularily agree with Rubin’s political (or philosophical) points of view, but I do like his interview style, and am very interested in some of the characters he interviews. Anyway, whether or not you care to watch it, this is the interview which sparked the idea behind this (short) post:

I had a discussion about “Freedom” the other night, and what we had to establish quite early on was that I’m not talking about freedom in general. A political system can never garuntee freedom, because other people exist. The best we can do is try and let people do what they want, so long as it doesn’t affect others. This ofcourse means that the system has to make some calls as to where that line is drawn. This is why I think the nitty gritty of politics will always exist.

However, it’s not so much that kind of freedom that I’d like to discuss, but rather freedom of speech, a term you may hear discussed a lot in the realm of American politics (ceirtainly in the above video, anyway). At first I think the idea of granting complete freedom of speech seems sort of obvious: Words don’t hurt people, so why shouldn’t we be able to say whatever we want? In a given set of ideas, the challenge of new ideas is important to help the system grow: To actualise a type of ideological natural selection, so to speak.

However, there is a difference between letting another speak, and being forced to listen. If somebody setup a speaker in the street, blaring (politically ambiguous bizarre example coming) Mary had a Little Lamb on repeat, I might be justified in taking issue. Just with other kinds of freedom, there needs to be a line drawn somewhere.

However, it’s not so much examples like this that really matter to all of us when it comes to this discussion, but rather other peoples philosophical or moral ideas. Should we be free to discuss the possibility of something morally wrong or abhorrent? You might say we should be, but at some point it goes a bit far. An extreme example could be: A public gathering of people discussing the possibility of mass suicide/genocide. Should we just stand by and let that happen? So even in ideological freedom of speech, there is a line (n.b. I realise my example is not the best, feel free to comment/disagree, I’d be happy to come up with another).

The thing is, when a group of people become sufficiently philosophically distant, a political system becomes impossible. At some point, even democracy stops working. I don’t personally think complete freedom of speech should be the first principle in politics, because I think like all other factors, it has it’s limits. However, I must admit to not being completely made up on this issue, and I ceirtainly have not thought of an adequate replacement first principle!

Listening to “both sides” – A critique of oversimplification

I’m a big fan of critical thinking: Of being happy to be proven wrong or of trying to imagine yourself arguing your opponents case (hopefully, so well that you can argue it better than they can). This idea is called the ideological turning test, and was introduced to me by the philosopher-statistician blogger Leah Libresco (whose blog has sadly been rather inactive recently). Her focus with the idea was on Theology, but of course it can be applied anywhere.

eternalrose

Complexity… ?

However, I think it’s important not to imagine the world in one of two camps. This is something I’ve began to realise more and more, especially in light of recent world events (I imagine you know exactly what I’m talking about). There are people who  one half agrees with, there are people who one almost completely agrees with, and there are people one completely disagrees with (but one might very much enjoy a discussion with them).

Yes, with a given assertion, it can either be true or false (I still like that system as a solid form of debate). But there are many many assertions that can be and are made, and one can agree with some, whilst completely disagreeing with others that are typically associated with the first.

But this leaves one with a problem when trying to always listen to “both sides of the argument” (in an attempt to be “open minded”). Because the thing is, there aren’t just two points of view. There aren’t just two opinion columns. More recently, with the rise of the internet, we come in contact with an extreme variety of nuanced views, to which we can’t all listen to.

What is the solution? I think perhaps the solution is not to care as much about the generalised viewpoints, but rather individual people you actually know, with nuanced opinions you can interact with. Keeping up with what everybody keeps up with is perhaps not as important as keeping up with everybody full stop. That may seem like a jump: It is. Is it too much of a jump…? What do you think?

 

Goals in Language Acquisition

When attempting to acquire any language, in order to maintain motivation, it is very helpful to have a series of concrete goals so that one can actually notice progress instead of trying for the ever elusive goal of fluency. In light of this (¿debido a que?), I am making this list to show all the various things I know can be achieved, and other goals that I hope to achieve.

First Conversation

Whether it’s as simple as a ¿Puedo tener un café? or “Ça Va?”, that first meaningful (non-mother-tongue) conversation can make or break the start of learning a language, and is key to motivation. I would note that my first conversation in Portugese did not go too well, which as superficial as it sounds, was one of the reasons I did not pursue it!

The “Toki Pona” Stage

This is the lowest level of anything resembling “fluency” (which I hope a lot of people skip over), which I assert can be achieved with as little as 200 of the right words. This is when one can explain most concepts by stretching and juggling what one knows. Note: This may also result in extreme confusion and insult. Use at your own risk. For those of you who just want to “communicate”, this stage is for you. Taking the 80:20 rule to the limit, I reckon with a bit of knack, one could express one’s-self in another language rather quickly!

“I Can’t speak English properly”

Ah! When your brain starts to imitate foregin grammar so well, you start saying: I have hunger (tengo hambre), or “It makes cold” (il fait froid). This stage will hopefully be quickly followed by it’s matured version:

When one’s English levels up:

Now I know not everyone does study grammar, but when I started to reflect on grammatical and vocabulary differences between French and English, my English, after taking a dip, eventually started getting better than it was originally.

For example, as a result of learning how to use French pronouns: I now am a firm believer in the old use of the word “one” as a non-specific human potential pronoun (e.g. One probably can’t understand me). In a similar way, I now try to avoid the verb “to get” like the plague, and end up using phrases like “I will descend” over (“I’m coming downstairs” (doesn’t that sound so much better?;)

The Broken Translator

This is when you decide that it would be a good idea to incorporate the language you are learning into your life, by attempting to translate everything you hear and think. Good luck turning this little voice in your head off!

I Speak All-ish

This is when you begin to realise that some phrases simply mean more accurately what you intend to express in such as such a language. So of course, one inflicts this passion on those around him. As snobbish as it sounds, I only like saying “Nous Verrons” in french because “We will see” just doesn’t seem to fit. However, I have learned that not everybody cares to know!

Thinking in target language

Okay, I haven’t quite got here (not conciously anyway) but I did find myself noting something in Spanish the other day, and then translating it into english in my head. But sadly it was just two words (está allí), so not quite a victory yet!

First serious conversation

I heard a theory recently that you can’t have a serious conversation with somebody you’ve known for a long time in a language other than the language you normally speak. Well I am happy to say that I have recently broken this rule multiple times! (and in multiple foregin languages, I might add :)

Finally got a sentence right

Okay, so I use a website called Lang-8 to get corrections on things I write. And generally, I try to write the kind of thing that I might actually write about. This of course means I attempt to use grammar way ahead of what I even think I know, meaning that I very rarely have a sentence without even a small grammatical error. Well, times are a’changing – Today I wrote a 12 sentence text, and got not one, but half of them marked as “Perfect, no Correction Needed”!

Other Goals:

Mistaken for a foreigner – Nope, not yet achieved. The problem with this is the deeper subtleties of accent are very hard to imitate (unless you do principally sound based learning, which I’m not). I also think that one needs to know a fair amount of slang to achieve this, which I don’t intend to do! In fact I would go so far as to say my intention is not to sound like a native, since I’m not, and I don’t intend to be disingenuous.

Deliver a 1 hour debate on “Contrasting Shakespeare and Molière” in target language:

I think that what some people forget when searching for fluency in a languge (C2, european framework, for example) is that they might not even be too fluent, or able to express themselves, in their own language. So here’s a goal I am not even able to achieve in English, let alone another language!

So, I hope you (ye) enjoyed this article on language learning. Are you currently learning a language? If so, do you disagree, or have any further suggestions?

 

The advantages of learning two languages at once – Briefly!

  1. You can play them off against each other (Going back to French grammar, for example, after so much Spanish (which is significantly more foreign, and precise), is very comfortable!).
  2. It’s more difficult to burn out, since you can always switch.
  3. Therefore your time is spent more efficiently.
  4. Allthough one can get things confused, it’s means you learn to distinguish the languages early on (like putting cogs in the right places before letting them grow… if only cogs grew!). n.b. I don’t really know if this last assertion holds up!

Language Fascination (Spanish, Lojban and More)

I’ve been spending a while reading about languages. Well, by a while, I mean three or four weeks, but for a relatively new hobby, that’s a long time! I’ve been trying to brush up on my Spanish, and while taking a break, I’ve been dabbling in Greek, Toki Pona and Lojban!

It all started with a Spanish conversation I had recently. I learned Spanish when I was younger, but had never really spoken it. But I sat down on a porch one day, and said “Hola” to the guy next to me. What followed was an almost 100% Spanish conversation. Admittedly it was probably about the weather, and such, and I was speaking terribly broken Spanish, but I was speaking it! I had dabbled in it a bit recently (Duolingo) but this was the first real Spanish conversation, and from then on, the spark was struck!

So I have been spending hours on Memrise, Spanish newspapers, podcasts, radio, grammar lessons (on youtube), language learning theories, a bit of Duolingo, bringing it up to scratch. This is my serious language learning. But on the side, I started dabbling in Greek…

Now Greek is a fun language, first of all because of that unreadable αλφάβητ. And then you also have modern greek vs. ancient greek (and the two ways of pronouncing the latter). I personally chose Ancient Greek (and Im going for the trickier, Ph = P + H and not F pronunciation), because I hope to one day read Aristotle’s Organon in the original (I think I dabble a bit too much to get that far, but one lives in hope!)

Side Note: If you are interested (or want to become interested) in languages, I highly recommend the NativLang Youtube Channel, in particular their long video on the history of scripts. I found it absolutely fascinating! As a result, I started to dabble a bit in The Hiragana and Kanji, and of course the beautifully elegant Korean Hangul (which I was happy to find was printed on my Go Stone Box):

Recently, I’ve also got a better handle on Toki Pona’s grammar (the 120 word langauge), which I tried memorising (on Memrise) a while back, but gave up because I couldn’t get past the grammar. My first (IRC) conversation also wasn’t very promising due to this fact. Though, I must admit, whilst I love the concept building in Toki Pona, I do not like the sound of the language (to be honest, I think it sounds very silly), nor the philosophically shallow foundations (imagine if it was built around Aristotle’s metaphysics!).

Side note: Yes, I had a look at Elvish, but the writing system (although beautiful) frustrated me, and writing system tends to play a big part in language for me!

Now, whilst I don’t think learning constructed languages (Sindarin/Elvish, Esperanto, Ithkuil) are the most practical thing in the world, it is a lot of fun, and its also fascinating to see how much one can mess with grammatical systems, but still remain a usable language. For example, Lojban doesn’t even have verbs, but these strange constructs called “brivla“. Now that is one language I actively avoided before, but after learning about how elegant their system is, I can see myself being drawn in (I had a similar impression of Esperanto after reading this page).

I know this article has been a bit disjointed, but if you want to take something from it, it’s this: Languages (real and fake) are hugely complex, extremely diverse, and therefore endlessly fascinating!

TED: Re imagining School

In line with my recent interest in education, I’ve been slowly going through this playlist of TED talks: Re-imagining School, and I would like to write down a few of my thoughts on each one.

Ken Robinson

This one is the classic ted talk, and I think even ten years later, it’s very good. I did watch it a while back (2008 maybe) but I didn’t buy into how much this guy is saying. First of all, he’s a very engaging, funny, speaker. His idea basically comes down to incorporating creativity in schools. To be honest, I don’t know if this is the best idea yet, but this video offered a lot of food for thought! I might add that if you want more of his comedic style, a lot more videos have come out since.

Khan Academy

I like Khan Academy. Every so often I go back to it and binge on Sal’s videos (I would note that I only watch the Sal ones, as I personally find the other speakers annoying). But I’m leaning away from his idea of turning the classroom around, simply because I don’t feel that technology is actually the solution. I personally suffer from eye problems from using the computer too much in my secondary education, and I think this is a very big obstacle to technology being the best idea (yet!)… However, his points about 1-on-1 help, the value of more social teaching (especially in primary and secondary) do seem to ring true.

12 year old poor Indian Biochemists

This one made me think about a simpler kid of learning… thinking about education as more of a challenge or game. The idea of asking the question before the kid knows the answer is really weird, but interesting.

Japanese Kindergarten

This was more of an architectural approach, which I thought was fun and helpful, but I also felt it was probably a small blip on the radar (though I’m happy to be proven wrong!)

Coursera

Whilst I didn’t think this lady was the best speaker (n.b. I can’t talk), I thought the online service she talked about was really good, and well done. Also the idea of fellow students marking work (and the correlation to show it’s effectiveness) was very very interesting. It made me sign up for (the similar) FutureLearn straight away, and now I’m doing the science of nutrition and Spanish!

Studio Schools

I don’t really have much to say about this… a practical, hands on, cooperative, pragmatic school :D

Once Upon a School

The reason I find this one exceptional (in comparison) is that it’s about a particular institution doing something specific in a real part of the world. They made it effective and fun, and it hits me on a much more human level!

There were a couple more… but they felt like more of the same (good, but repetition). If you have any additional thoughts, feel free to comment and we can have a discussion about them!

Nomic Lite – A Lighter Variant of a Meta-Game

In case you haven’t heard of nomic, I recommend you read the original article that introduced the game. In short: It’s a kind of game where the rules change as the game continues. It has a base ruleset, which is a basic “democratic” system and a few basic win conditions, but essentially establishes a base on which to build whatever kind of rule system one wants.

As of yet, i have played two games of nomic (in real life) and although they are entirely different, we ended up spending a lot of time in both of them simply pruning unnecessary rules. Therefore, I would like to propose a lighter version, which we will certainly use from now on:

101. All players must always abide by all the rules then in effect, in the form in which they are then in effect.

102. The game should be commenced with the youngest player’s turn.
Players shall continue to take turns in clockwise order.

103. One turn consists of proposing one rule-change and having it voted on.

104. A rule change is the enactment, repeal or amendment of a rule. It will be adopted if and only if they receive unanimous approval.

105. Every player is an eligible voter, receives exactly one vote and must participate in every vote on rule-changes.

106. All proposed rule-changes should be clearly stated before they are voted on. If they are adopted, they shall be added/edited to the current rules, and take full effect immediately form in which they were voted on.

107. A player always has the option to forfeit the game rather than continue to play or incur a game penalty. No penalty worse than losing, in the judgment of the player to incur it, may be imposed.

108. If the rules are changed so that further play is impossible, or if the legality of a move cannot be determined with finality, or if a move appears equally legal and illegal, then the first player unable to complete a turn is the winner.

This rule takes precedence over every other rule determining the winner.

If you are a Nomic player, do tell me what you think. To be fair, I realised that this version is a more light-hearted style of nomic, and is not as foolproof as the original, but to be honest, the appeal of nomic to me is more in the game design potential, rather than the lawyery thing.