Problem 48 - Quickly done in C

I am supposed to be writing a paper for a class. I got about 3 sentences done of it, so it seemed like a good time to take a break and solve a project Euler problem. This problem was quite easy, and I used C for the sake of expediency and ease, but I would not be too surprised if I come back soon and redo this problem in a pretty crazy language - 64 bit integers, modulus, multiplication, and control structures are really all that is needed to solve this problem in the blink of an eye. (well, 16ms, which I imagine is less than the time it takes to blink an eye).

#include <stdio.h>

int main(int argc, char** argv) {
    const unsigned long long BIG  = 10000000000;
    unsigned long long ans       = 0;
    unsigned long long summand   = 0;
    unsigned long long i;
    unsigned long long j;
    for (i = 1; i <= 1000; ++i) {
        summand = i;
        for (j = 1; j < i; ++ j) {
            summand *= i;
            summand %= BIG;
        }
        ans += summand;
        ans %= BIG;
    }
    printf("%lld\n",ans);
}

Problem 47 - x86 assembly

Yesterday I wrote my first x86 assembly code for one of my cs classes, and after finishing the assignment, rather than being exhausted from the effort or frustration or anything else, I had a feeling of satisfaction, having found working in assembly somewhat fun (at least at the relatively small scales I am still working at). So, as not to let that fun end, I decided to use x86 assembly on a Project Euler problem, and, as luck would have it, the problem I was up to, problem 47, was one that was not particular hard (for me, at least) to write in assembly - no need for copious variables, arrays, or any other sort of high-level language features that I would not be able to deal with. I am starting to think that all the drudgery with esoteric and otherwise dumb languages that I have had to put up with in the last month has made me immune to frustrations with programming languages or having too many difficulties switching between modes of computation - after learning how to write whitespace well, assembly is hardly a challenge, even if imul is implemented in a really stupid manner. Anyway, without further ado, here is my code, which runs in about .6s (to see the answer, I call e47 and use printf from a C program - the extra linking, etc that would be required to do this without touching C seemed unnecessary).

    .text
    .globl  isPrime
    .type   isPrime,@function
isPrime:
    pushq   %rbx
    pushq   %r12
    pushq   %r13
    pushq   %r14
    pushq   %r15
    movl    %edi,%ebx   # ebx = n
    cmpl    $2,%ebx     # n < 2
    jl      finif       # return 0
    movl    %ebx,%eax   # temp = 2
    andl    $1,%eax     # temp&= 1
    cmpl    $0,%eax     # n % 2 == 0
    je      finic       # return n == 2
    movl    $3,%r12d    # i = 3
loop:
    movq    $0,%rdx     # clear rdx for mul
    movl    %r12d,%eax  # put i in eax for mul
    imull   %r12d       # eax = i * i
    cmpl    %ebx,%eax   # i * i <= n
    jg      overloop
    movq    $0,%rdx     # clear rdx for div
    movl    %ebx,%eax   # put n in eax for div
    idivl   %r12d       # edx = n % i
    cmpl    $0,%edx     # n % i == 0
    je      finif       # return 0
    addl    $2,%r12d    # i+=2
    jmp     loop
overloop:
    movq    $1,%rax     # return 1
    jmp     fini
finif:
    movq    $0,%rax     # return 0
    jmp     fini
finic:
    cmpl    $2,%ebx     # n == 2
    jne     finif
    movq    $1,%rax     # return 1
fini:
    popq    %r15
    popq    %r14
    popq    %r13
    popq    %r12
    popq    %rbx   
    ret
    .size   isPrime,.-isPrime

    .text
    .globl  pfc
    .type   pfc,@function
pfc:
    pushq   %rbx
    pushq   %r12
    pushq   %r13
    pushq   %r14
    pushq   %r15
    movl    %edi,%ebx   # ebx = n
    movl    $0,%r13d    # fc  = 0
    movl    $2,%r12d    # i = 2
loop2:
    movl    %ebx,%edi   # n is param 1
    call    isPrime     # isPrime(n)
    cmpl    $1,%eax     # if true
    je      finish
    cmpl    $3,%r13d    # if fc is 3 and not prime, return false
    je      finishFalse
    movq    $0,%rdx     # clear rdx for div
    movl    %ebx,%eax   # put n in eax for div
    idivl   %r12d       # eax: n%i, edx: n/i
    cmpl    $0,%edx     # n%i == 0
    jne     overif
    movl    %eax,%ebx   # n /= i
    incl    %r13d       # fc++
divloop:                # perform extra divisions of the factor
    movq    $0,%rdx     # clear rdx for division
    movl    %ebx,%eax   # put n in eax for div
    idivl   %r12d       # compute division again
    cmpl    $0,%edx     # n%i == 0
    jne     overdivloop
    movl    %eax,%ebx   # n /= i
    movl    %ebx,%edi   # n is param 1
    call    isPrime     # we must recheck primality here
    cmpl    $1,%eax     # if isPrime
    je      finish
    cmpl    $1,%ebx     # if 1
    je      finish
    jmp     divloop
overdivloop:
overif:
    incl    %r12d       # i++
    jmp     loop2
overloop2:
finish:
    cmpl    $3,%r13d    # fc == 3
    je      finishTrue
finishFalse:
    movq    $0,%rax  
    jmp     veryend
finishTrue:
    movq    $1,%rax
veryend:
    popq    %r15
    popq    %r14
    popq    %r13
    popq    %r12
    popq    %rbx   
    ret
    .size pfc,.-pfc
    
    .text
    .globl  e47
    .type   e47,@function
e47:
    pushq   %rbx
    pushq   %r12
    pushq   %r13
    pushq   %r14
    pushq   %r15
    movl    $210,%ebx   # N = 210 (lowest possible num)
    movl    $0,%r12d    # count = 0
loop3:
    movl    %ebx,%edi   # N is param 1
    call    pfc
    cmpl    $1,%eax     # pfc(N) == 1
    jne     elsepart
    incl    %r12d       # count++
    cmpl    $1,%r12d    # count == 1
    jne     overif2
    movl    %ebx,%r13d  # r13d = first in seq
overif2:
    cmpl    $4,%r12d    # count == 4
    je      thefinish   # we are done
    jmp     overif3
elsepart:
    movl    $0,%r12d    # clear the count
overif3:
    incl    %ebx
    jmp     loop3
thefinish:
    movl    %r13d,%eax
    popq    %r15
    popq    %r14
    popq    %r13
    popq    %r12
    popq    %rbx   
    ret
    
    .size e47,.-e47

Problem 46 - Julia

I haven't solved a problem in a esoteric language too recently - rest assured, I am sure I will move back to esolangs soon, INTERCAL beckons. For now, however, there are still some entirely reasonable languages left for me to take advantage of. Most recently, I have used Julia - a language apparently designed like MATLAB and R with mathematical computation in mind, and like so many other languages I have used recently (especially with the stark contrast from things like Whitespace not too long ago), it was a very easy language to pick up and use for something not too bad like this. This problem involved Goldbach's "other" conjecture which conjectured that every odd composite was the sum of a prime and two times a square; this program disproves that conjecture in a handful of seconds.

function isPrime(x)
    if x < 2 || x % 2 == 0
        return x == 2
    end
    i = 3
    while i * i <= x
        if x % i == 0
            return false
        end
        i += 1
    end
    return true
end

primes = [2]
for i = 3:10000
    if isPrime(i)
        primes = [primes..., i]
    end
end

squares = [0]
for i = 1:1000
    squares = [squares..., i * i]
end

x = 7
while true
    gotans = false
    for p in primes
        done = false
        if p > x
            println(x)
            gotans = true
            break
        end
        for s in squares
            if x == p + 2*s
                done = true
                break
            end
            if p + 2*s > x
                break
            end
        end
        if done
            break
        end
    end
    if gotans
        break
    end
    x += 2
end

Problem 45 - R

Believe it or not, there are still real programming languages that I have yet to use, and among them was R, a language specifically designed for mathematical/statistical analysis, and thus a language that is pretty well suited to Project Euler. Didn't have too many problems with this one - the biggest issue was having to realize that a "double" is a double-precision integer (like a long in C), because I needed those for this.

hex <- function(n) n*(2*n-1)

isPent <- function(p) {
    root <- as.double(sqrt(24*p + 1))
    (root * root == 24*p + 1) && ((root + 1) %% 6 == 0)
}

for (i in 144:30000) {
    h <- hex(i)
    if (isPent(h)) {
        print(h)
        break
    }
}

Problem 44 - Scala

I solved problem 44 in Scala, after just having freed it up with Prolog. This problem was relatively easy, so I didn't really need to bring in Scala, which is relatively one of the "big guns" (being a language that I am pretty familiar with), but I wanted to get another problem done and move as quickly as possible towards number 50. This solution very well may be replaced by a solution in a more difficult language soon.

object e44 {
  def min(x : Int, y : Int) : Int = if (x < y) x else y

  def isPent(p : Int) : Boolean = {
    val root =  math.sqrt(24 * p + 1).asInstanceOf[Int]
    return (root * root == 24*p + 1) && ((root + 1)% 6 == 0)
  }

  def pent(n : Int) : Int = n * (3 * n - 1) / 2

  def main(args: Array[String]) {
    var D = 1000000000
    var p1 = 0
    var p2 = 0
    for (i <- 1 to 10000) {
      for (j <- (i+1) to 10000) {
        p1 = pent(i)
        p2 = pent(j)
        if (isPent(p1 + p2) && isPent(p2 - p1)) {
          D = min(D, p2 - p1)
        }
      }
    }
    println(D)
  }
}

Introduction

I am Sam Donow, a Sophomore at Williams College, and this is my blog for a language challenge of mine related to Project Euler.

There are now 50 posts on this blog, and the introductory post explaining what I am doing is way at the bottom, so I feel as though I ought to restate what I am doing.

Project Euler is a collection of increasingly difficult mathematical problems which are expected to require computers to solve. People are drawn to Project Euler for various reasons - mental stimulation, interest in the mathematics of the problems, a wish for something to do when learning a new programming language, etc. My goal is to solve as many of the problems in as many different languages as possible. At the time of this writing, I have solved 43 problems in almost as many language (why "almost as many" will be explained below). I plan on going for as long as I can - there are a LOT of programming languages out there, and whenever it seems like I might be running out of reasonable new languages to use, something that I had forgotten before springs up.

The challenge began as part of a 24-hackathon, where I attempted to and succeeded at solving 20 problems in 20 different languages. Since then, it has continued for over a month of non-continuous work. Below are some of the formal rules I have set down for myself, in the form that I am currently following.

• In order to make the challenge well-defined, I must have a well-defined metric of difference for languages. For this metric, I consider different revisions of a language to all be the same - so Fortran 95 is the same as Fortran 77, Java 7 is the same as Java 5, etc. In the past I have considered other languages, like C and C++ as the same for my purposes, but I will likely reverse that soon due to them being no more similar than some other language pairs.
• I can re-solve problems I have already solved in a different language, and reuse the language that I originally used to solve the first problem. The reason for this rule is to promote me solving problems frequently - If I think I may eventually solve problem 44 in INTERCAL, then  without this rule I would have to wait until I had the time to learn and use INTERCAL, but with this language, I can solve numerous problems in relatively easy languages frequently, and then every once and a while go back and use a crazy language.

And those are basically the rules. I am still going through the problems, and still having tons of fun discovering and using new/old/crazy languages. Just today I solved a problem in Prolog, and now I am only 7 problems away from having solved 50, which would bring my profile to level 2 and put it in the 92nd percentile of Project Euler users, despite the fact that most (all?) of the other users have not solved problems under the crazy restrictions I am solving them under.

Progress

This table records all of the languages I have used on this challenge, along with which problems have been solved in which challenge. The statement of the problems can all be found on Project Euler, and my solutions are described in this blog, as well as being linked to from the table below. This table keeps growing, and keeps getting pushed lower and lower in the blog, so I keep reprinting it.

BrainFuck	1
Haskell	2*,37
J	3*,24*,35
Ruby	4*,30
Whenever	2,5*
Ook!	6
Racket	7*,26
K	8*
Javascript	9*,31
sML	10*,42
PHP	11
Go	12*,32
cLisp	13
C/C++	14*,48*,50
Fortran95	3,15*
Python	16*,24*,39

ELM	17*,48
Scala	18*,44
Perl	19
Java	20
FALSE	4
Squirrel	21
D	22
Ceylon	23
Postscript	7
Befunge	27
Boo	29
Frink	16
Forth	9
Shakespeare	12
Bash	33
Batch	34

Whitespace	36
LOLCODE	10
Lua	38
Erlang	24
Rust	40
Ada	41
Clojure	14
Coffeescript	43
Prolog	18
R	45
Julia	46
x86	47
INTERCAL	17
OCaml	49
Analytic	5,8,15
Analytic	25,28

Problem 18 redo - Prolog

I used Prolog briefly a long time ago, around the time that I first got into Project Euler and solved programs in Scheme, but it has been a very long time, and I never did anything vaguely useful with it. So, now I decided to use it for a Project Euler problem. I didn't have very fond memories of my brief foray into Prolog, but after solving this problem in Prolog, I have found that it can actually be a pretty nice language, and I may want to use it for some future problems. It is certainly very different from most other languages, being a logical language and all, calculating through inferences on and trees and such, but it worked out in the end.

My first solution to this problem in Prolog accidentally ended up having exponential complexity and took a couple minutes to run, but this solution below runs in less than a milisecond (it requires Prolog to perform only 799 inferences). Solving this problem in Prolog freed up Scala, but now I would not be surprised if some time down the line I use some sillier language for this problem and recover Prolog.

getRow(R, Row) :-
nth0(R, [[75],
 [95,64],
 [17,47,82],
 [18,35,87,10],
 [20,4,82,47,65],
 [19,1,23,75,3,34],
 [88,2,77,73,7,63,67],
 [99,65,4,28,6,16,70,92],
 [41,41,26,56,83,40,80,70,33],
 [41,48,72,33,47,32,37,16,94,29],
 [53,71,44,65,25,43,91,52,97,51,14],
 [70,11,33,28,77,73,17,78,39,68,17,57],
 [91,71,52,38,17,14,91,43,58,50,27,29,48],
 [63,66,4,68,89,53,67,30,73,16,69,87,40,31],
 [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]], Row).

max(X, Y, Y) :- Y >= X.
max(X, Y, X) :- X >= Y.

prepend([], Z, [Z]).
prepend([X|Y], Z, [Z,X|Y]).

combineRows([X, Y], [Z], Row) :-
    XZ is X + Z,
    YZ is Y + Z,
    max(XZ, YZ, N),
    prepend([], N, Row).

combineRows([X,Y|T1], [Z|T2], Row) :-
    XZ is X + Z,
    YZ is Y + Z,
    max(XZ, YZ, N),
    combineRows([Y|T1], T2, Tail),
    prepend(Tail, N, Row).

ans(14, W) :- getRow(14, W).
ans(N, W)  :-
    N1 is N + 1,
    getRow(N, Top),
    ans(N1, Bottom),
    combineRows(Bottom, Top, W).

%% Command to Find the Answer:
e18(W) :- ans(0, List),
    nth0(0, List, W).

Problem 43 - Coffeescript

Another language that falls in the "fairly boring" category. I can tell that there are nicer ways to do this problem, but most nice ways are a lot harder than the easy way, but the easy way is only easy in a language with nice features like arrays. So, as it is the middle of the week and I should probably spend most of my time on classwork, I decided to go the easy way on this problem - maybe I will go the hard way some time later. I used Coffeescript for this problem, a language that compiles to javascript but which is in some ways nicer for some things according to its proponents - it wasn't too hard a language to use, even if it does have some strange features.

Anyway, here is the coffeescript code (oh what a creative name that was...)

concatDigits = (digits) ->
    sum = 0
    for i in digits
        do(i) ->
            sum = sum*10 + i
    return sum


hasProperty = (digits) ->
    if (concatDigits(digits[1..3]) % 2 is 0 and 
       concatDigits(digits[2..4]) % 3 is 0 and
       concatDigits(digits[3..5]) % 5 is 0 and
       concatDigits(digits[4..6]) % 7 is 0 and
       concatDigits(digits[5..7]) % 11 is 0 and
       concatDigits(digits[6..8]) % 13 is 0 and
       concatDigits(digits[7..])  % 17 is 0)
        concatDigits(digits)
    else
        0
    
fac = (x) => if x < 2 then 1 else x * fac(x - 1)
NthLP = (N, p, rem) ->
    if rem.length == 1 then return p.concat(rem)
    k = fac(rem.length - 1)
    index = Math.floor(N / k)
    p.push(rem[index])
    rem = if index is 0
            rem[1..]
          else if index is rem.length - 1
            rem[..-2]
          else 
            rem[..index-1].concat(rem[index+1..])
    return NthLP(N % k, p, rem)

sum = 0
i = 0
while i < fac(10)
    digits = NthLP(i, [], j for j in [0..9])
    sum += hasProperty(digits)
    i += 1
console.log(sum)

Problem 14 redo - Clojure

Given the fact that I can mostly only find time to solve Euler problems on weekends, I thought it would be a shame to have only done two problems this weekend, so I squeezed in another. Problem 43 looks a little bit daunting to jump into with a hard-to-use language, so I decided to free up a nice language from a while ago that I may or may not use directly for problem 43, but which will certainly be useful to have free - C (or C++, I have been considering them "the same" for my purposes, but now that I am expanding this challenge out so far..maybe I will allow the two to be used separately).

Anyway, I used C back in the initial 24 hour hackathon stage of this challenge for a rather easy problem involving collatz sequences - I used it during the "home stretch" when I had about as many language I knew left as problems left to solve. I decided to noq resolve this problem in clojure. Clojure turns out to be a pretty nice functional language...for whatever reason I had difficulties starting with it before, but now that I know that it is not too different from most lisps/schemes, I may eventually reclaim and reuse it. But anyway, here is my solution to problem 14 in Clojure (runs in about 15s...but Clojure runs in the JVM and does not seem to be fast by any stretch of the imagination).

(defn collatz-count [n c]
    (if (= 1 n) (+ c 1)
        (if (= 0 (mod n 2)) (collatz-count (/ n 2) (+ c 1))
            (collatz-count (+ (* 3 n) 1) (+ c 1)))))

(defn mmax [x y] (if (< (first x) (first y)) y x))

(println (second (reduce mmax (map #(list (collatz-count % 0) %) (range 1 1000000)))))