Last modified on 1 July 2008, at 22:26

# 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 1Edit

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

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

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(round(math:sqrt(\$n)))
let \$primes := local:sieve((),2 to \$max)
return
<result>
{ local:factor(\$n,\$primes) }
</result>
```

Factors of 13195

And the largest is

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

Largest factor of 13195

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

## Problem 4Edit

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

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