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

## 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 + \$fibs
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

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

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

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)

```