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
loc{ add1 nr add2 flag }
nr 2/ 0
do add1 i + c@
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.
