# 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[edit]

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])

## Problem 2[edit]

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])

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

## Problem 3[edit]

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.

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>

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[edit]

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[edit]

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)

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)