XQuery/Project Euler

Project Euler is a collection of mathematical problems. Currently there are 166 so it may take some time to get through them all :-).

Problem 1

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

sum ((1 to 999)[. mod 3 = 0 or . mod 5 = 0]) 

Run

Problem 2

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

declare function local:fib($fibs,$max) {
  let $next := $fibs[1] + $fibs[2]
  return 
    if ($next > $max)
    then $fibs
    else local:fib(($next,$fibs),$max)
};
 sum( local:fib((2,1),1000000)[. mod 2 = 0])
  

Run

This brute-force approach recursively builds the Fibonacci sequence (in reverse) up to the maximum, then filters and sums the result.

Problem 3

What is the largest prime factor of the number 317584931803?

First we need to get a list of primes. The algorithm known as the Sieve of Eratosthenes is directly expressible in XQuery:

declare function local:sieve($primes as xs:integer*,$nums as xs:integer* )  as xs:integer*  {
   if (exists($nums))
   then  
        let $prime :=  $nums[1]
        return local:sieve(($primes,$prime), $nums[. mod $prime !=  0])
   else $primes
};

<result>
   { local:sieve( (), 2 to 1000 ) }
</result>

The list of primes starts off empty, the list of numbers starts off with the integers. Each recursive call of local:sieve takes the first of the remaining integers as a new prime and reduces the list of integers to those not divisible by the prime. When the list of integers is exhausted, the list of primes is returned.

Primes less than 1000

Factorization of a number N is also easily expressed as the subset of primes which divide N:

declare function local:factor($n as xs:integer ,$primes as xs:integer*) as xs:integer* {
      $primes[ $n mod . = 0]
};

Hence

let $n:=  xs:integer(request:get-parameter("n",100))
let $max :=  xs:integer(ceiling($n div 2))
let $primes := local:sieve((),2 to $max)
return 
 <result>
   { local:factor($n,$primes) }
 </result>

Factors of 666

And the largest is

  max (local:factor($n,$primes))

Sadly this elegant method runs out of space and time for integers as large as that in the problem.

Problem 4

Find the largest palindrome made from the product of two 3-digit numbers.

declare function local:palindromic($n as xs:integer) as xs:boolean {
  let $s := xs:string($n)
  let $sc := string-to-codepoints($s)
  let $sr := reverse ($sc)
  let $r := codepoints-to-string($sr)
  return $s = $r 
};

max(
(for $i in (100 to 999)
 for $j in (100 to 999)
 return $i * $j)
 [local:palindromic(.)]
)

Run [ takes 20 seconds]

Problem 5

What is the difference between the sum of the squares and the square of the sums for integers from 1 to 100?

 declare function local:diff-sum($n as xs:integer) as xs:integer) {
     sum (1 to $n) * sum(1 to $n)
      - sum( for $i in 1 to $n  return $i * $i )
 };
 local:diff-sum(100) 

Run

This nasty brute-force method can be replaced by an explicit expression using familiar formula:

 declare function local:diff-sum($n as xs:integer) as xs:integer {
  let $sum := $n * ($n + 1) div 2
  let $sumsq :=( $n * ($n+1) * (2 * $n +1) ) div 6
  return $sum * $sum - $sumsq
};

 local:diff-sum(100)   

Run