As of May 4 2007 the scripts will autodetect your timezone settings. Nothing here has to be changed, but there are a few things

Please follow this blog

Search this blog

Showing posts with label Project Euler. Show all posts
Showing posts with label Project Euler. Show all posts

Sunday, July 31, 2011

The K programming language

Question

The decimal number, $585 = 10010010012_2$ (binary), is palindromic in both bases. Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

Problem 36  - Project Euler

Answer

+/&(&/{x~|x}'2 10_vs\:)'!_1e6

That is, in the K programming language. If Java is verbose then I would say that K is autistic. It has been estimated that there are not more than 1000 professional K-programmers. Most of them highly paid and employed in the high-end financial sector ( London, New York ).

Another example.

Question

The nth term of the sequence of triangle numbers is given by $t(n) = \frac{n (n+1) }{2}$, so the first ten triangle numbers are $1, 3, 6, 10, 15, 21, 28, 36, 45, 55$. By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is $19 + 11 + 25 = 55 = t(10)$. If the word value is a triangle number then we shall call the word a triangle word. Using words.txt, a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Problem 42  - Project Euler

Answer

+/((+/-64+6h$.:)'","\:*0:`words.txt)in{_.5*x*1+x}@!99

Again, in the K programming language. ( I used 4 lines in Mathematica, it would take 20+ lines in Java. )

Friday, July 29, 2011

Mathematica is self-documenting.

( *** WARNING: CONTAINS SPOILERS FOR EULER 22 *** )

Mathematica is self-documenting. ( That is if you use a mild form of Literary Programming. ) Anyway let me try to prove my point by looking at some code and compare it with two other languages.

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 53 = 49714.

What is the total of all the name scores in the file?

Source: Euler 22

My solution was:

file = ToFileName[{"C:", "My Dropbox", "Mathematica", "Project Euler"}, "names.txt"];
dta = Sort[ReadList[file, Word, WordSeparators -> { ",", "\",\""}]];
Timing[Sum[ k*Plus @@ (ToCharacterCode[#] - 64 &) /@ Characters[dta[[k]]], {k, 1, Length[dta]}]]


Do you really need the following comments to get an idea what the program does?
Line 1. Address file.
Line 2. Read and parse data
Line 3. Process ( time and present ) data ( ToCharacterCode[] assigns 65 to A and so forth, the file contains names in all uppercase. ) Timing shows the time it took the computer to process line 3. Alternatives for @@ and /@ are the usage of Map and Apply.

Compare this to a solution in Java:

import java.io.*;
import java.util.*;
 
public class Problem22 {
    public static void main(String[] args) throws Exception {
 
	BufferedReader br = new BufferedReader(new FileReader(new File(\"names.txt\")));
	String[] names = br.readLine().split(\",\");
	Arrays.sort(names);
	long sum = 0;
	long count = 1;
	for (int i = 0; i < names.length; i++) {
	    sum += count++ * sum(names[i]);

	}
	System.out.println(\"The sum is: \" + sum);
    }
 
    static long sum(String name) {
	char[] letters = name.toLowerCase().toCharArray();
	long sum = 0;
	for (int i = 1; i < letters.length - 1; i++) {
	    sum += letters[i] - 96;
	}
	return sum;
    }
}
Java is known to be verbose, but therefore very readable as well.

Some people get high from coding Haskell... ( I can't guarantee this code works, Haskell is not my thing. No thanks. )

import Control.Monad
import Data.List
import Char
import Control.Applicative
 
main = (read :: String -> [String]) `liftM` readFile "problem22.data" >>= \list -> putStrLn $ show $ sum $ zipWith (*) [1..] $ sum . map (\x->ord x - ord 'A' + 1) <$> sort list

I tried to show that Mathematica is self-documenting. Not that any other language is bad or otherwise inferior.

Saturday, July 16, 2011

Collatz sequence - Revisited

This following Mathematica code prints the Collatz sequence for n to 1.
g[n_]:=NestWhileList[Piecewise[{{3#+1,OddQ[#]},{#/2,EvenQ[#]}}]&,n,#>1&]

For example
g[23]={23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1}


Problem 14 of the Euler Project is about the Collatz sequence. Officially it is a conjecture that every sequence starting with n ends in 1.

I spend so much time on 3x+1.... My first blog post in 2005 was on the Collatz sequence. I am able to generate sequences of any length ( thus including very large lengths ) but they end with 1 by definition. It's sort of a paradox.

Sunday, July 10, 2011

Project Euler - Revisited

In order of difficulty I have now solved the first 12 least difficult problems, of the 300+ total problems. I am still in the zone of the not so difficult stuff because I haven't reached a level yet.

A Pythagorean triplet is a set of three natural numbers, $a, b, c$, for which, $a^2 + b^2 = c2$ For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

Project Euler - Problem 9. This problem has been solved by 75913 people, ( problem 1 by 159750 people ).

When you have solved a problem you get access to the answer book. It then becomes clear what a difference it makes if you are somewhat literate in a tool like Mathematica. I have solved most problems so far, if not all. with one line of functional Mathematica code while the model answer is a three or four page pdf full of procedural code. - For a while I had the feeling I was cheating by using Mathematica, but the goal is clear. Solve. no matter what. I am not sure but I think Euler is mainly geared for computer geeks, although the problems so far could have been solved by intelligent programming alone, knowledge of mathematics makes a difference. Take this problem for example.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Project Euler - Problem 5.

Solved this one without using my computer, thus simple. Because I have done an introductory course in Number Theory of course. Maybe it is not so simple otherwise, I don't think so actually.

If you are ever enjoying leisure time on Sudoku's, Euler is worth considering. More fun!

P.S.
Watched the movie Source code yesterday. Liked it so much that I will give Proof ( Jake Gyllenhaal has a part in it ) a second chance. Proof is not an action movie, it is more in the line of A Beautiful Mind. An attempt to answer "Where does genius end before it turns into undeniable insanity?"

Monday, June 6, 2011

Project Euler

If you like programming, mathematics and you want to rank yourself among peers then Project Euler may be an option for you. It's not for me ( yet ), my game is mathematics at the Open University but who knows, I might not be able to resist the problems. Although some look simple, once you have solved a problem you get access to a database of how others solved the problem. That may be very illuminating.

Add all the natural numbers below one thousand that are multiples of 3 or 5.

Problem #1.

What is the first term in the Fibonacci sequence to contain 1000 digits?

Problem #25.

And so on... with an ever increasing complexity. Knowing some Elementary Number Theory might help, I suppose.

Link: Project Euler

Happy Coding!

Popular Posts

Welcome to The Bridge

Mathematics: is it the fabric of MEST?
This is my voyage
My continuous mission
To uncover hidden structures
To create new theorems and proofs
To boldly go where no man has gone before




(Raumpatrouille – Die phantastischen Abenteuer des Raumschiffes Orion, colloquially aka Raumpatrouille Orion was the first German science fiction television series. Its seven episodes were broadcast by ARD beginning September 17, 1966. The series has since acquired cult status in Germany. Broadcast six years before Star Trek first aired in West Germany (in 1972), it became a huge success.)