## Monday, April 11, 2016

### Tutorial 2: Euler project 1 - 5

https://projecteuler.net/problem=1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

: multiple-of-3  3 mod 0= ;
: multiple-of-5  5 mod 0= ;

: setsum \ -- n | s --
0 foreach do zst> + loop ;

{ 1 1000 | multiple-of-3 } { 1 1000 | multiple-of-5 } union setsum .

or

: multiple-of-3-or-5  dup multiple-of-3 swap multiple-of-5 or ;

{ 1 1000 | multiple-of-3-or-5 } setsum .

https://projecteuler.net/problem=2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

: next-fib-pair \ m n -- n m+n
tuck + ;

: euler2 \ -- sum
0 loc{ sum } 1 2
begin dup 1 and 0=
if dup sum + to sum
then next-fib-pair dup 4000000 >
until 2drop sum ;

euler2 .

https://projecteuler.net/problem=3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

600851475143 pollard# sort over . drops

https://projecteuler.net/problem=4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

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

: palindrome \ n -- flag
s>d <# #s #> 2dup + 1- true
nr 2/ 0
add2 i - c@ = 0=
if false to flag leave then
loop flag ;

Just for curiosity:

{ 10000 1000000 | palindrome } cardinality . 1800  ok

: split-fact \ n -- i j where ij=n and i+j is minimal
dup sqrtf
begin 2dup mod
while 1-
repeat tuck / ;

: euler4 \ -- n
10000 999999
do i palindrome
if i split-fact
100 1000 within swap
100 1000 within and
if i leave then
then -1
+loop ;

euler4 .

https://projecteuler.net/problem=5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

: divisible20 \ m -- flag
true loc{ m flag } 21 1
do m i mod
if false to flag leave then
loop flag ;

: euler5 \  -- n
-1 1
do i divisible20
if i leave then
loop ;

utime euler5 . utime d- d. xxxxxxxxx -36728698  ok

That takes more than 36.7 seconds. However, the wanted number is the product of all numbers in the intervall 1...20 that are of the form p^n, where p is a prime and p^n<=20<p^(n+1).

20 value numb
: pn \ m -- flag
dup uniprime 0= if drop false exit then
dup pollard# over >r drops r> * numb > ;

: setmul \ -- n | s --
1 foreach do zst> * loop ;

utime { 2 21 | pn } setmul . utime d- d.  xxxxxxxxx -190  ok

which takes 190 micro seconds.