Project Euler Problem 1 - 10

	#lang racket
	(require srfi/1 srfi/13 srfi/41 srfi/42 (only-in math/number-theory
	coprime?
	prime?
	factorize
	defactorize))
	;;;10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の
	;;;4つがあり, これらの合計は 23 になる.
	;;;
	;;;同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.
	(define (problem1 n)
	(stream-fold + 0
	(stream-filter
	(lambda (x)
	(or (zero? (modulo x 3)) (zero? (modulo x 5))))
	(stream-range 1 n))))
	(problem1 1000)
	;;;フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば,
	;;;最初の10項は以下の通りである.
	;;;1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
	;;;
	;;;数列の項の値が400万以下の, 偶数値の項の総和を求めよ.
	;;;
	;;;Note:この問題は最近更新されました.
	;;;お使いのパラメータが正しいかどうか確認してください.
	(define (problem2 n)
	(define fib (stream-cons 1
	(stream-cons 2
	(stream-map + fib (stream-cdr fib)))))
	(stream-fold + 0
	(stream-filter even?
	(stream-take-while (lambda (x)
	(<= x n)) fib))))
	(problem2 40000)
	;;;13195 の素因数は 5, 7, 13, 29 である.
	;;;
	;;;600851475143 の素因数のうち最大のものを求めよ.
	(define (problem3 n)
	(let ((ls (map car (factorize n))))
	(apply max ls)))
	(problem3 600851475143)
	;;;左右どちらから読んでも同じ値になる数を回文数という.
	;;;2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
	;;;
	;;;では, 3桁の数の積で表される回文数の最大値を求めよ.
	(define (problem4 n)
	(define (gen)
	(let ((k (expt 10 (- n 1))))
	(iota (* 9 k) k)))
	(define (parindrome? x)
	(let ((str (number->string x)))
	(string=? str (string-reverse str))))
	(let ((ls (gen)))
	(apply max (filter parindrome? (list-ec (: i ls) (: j ls) (* i j))))))
	(problem4 3)
	;;;2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり,
	;;;そのような数字の中では最小の値である.
	;;;
	;;;では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
	(define (problem5 n)
	(let ((primes (stream-filter prime? (stream-from 2))))
	(let ((s (stream->list (stream-take-while (lambda (x)
	(< x (+ n 1))) primes))))
	(define (proc x)
	(let loop ((k 2))
	(if (> (expt x k) n)
	`(,x ,(- k 1))
	(loop (+ k 1)))))
	(defactorize (map proc s)))))
	(problem5 20)
	;;;最初の10個の自然数について, その二乗の和は,
	;;;12 + 22 + ... + 102 = 385
	;;;
	;;;最初の10個の自然数について, その和の二乗は,
	;;;(1 + 2 + ... + 10)2 = 3025
	;;;
	;;;これらの数の差は 3025 - 385 = 2640 となる.
	;;;
	;;;同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.
	(define (problem6 n)
	(let ((s (stream-from 1)))
	(let ((s1 (stream-fold + 0 (stream-map (lambda (x)
	(expt x 2))
	(stream-take n s))))
	(s2 (expt (stream-fold + 0 (stream-take n s)) 2)))
	(- s2 s1))))
	;;;素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である.
	;;;
	;;;10 001 番目の素数を求めよ.
	(define (problem7 n)
	(let ((primes (stream-filter prime? (stream-from 2))))
	(stream-ref primes (- n 1))))
	(problem7 10001)
	;;;次の1000桁の数字のうち, 隣接する4つの数字の総乗の中で,
	;;;最大となる値は, 9 × 9 × 8 × 9 = 5832である.
	;;;73167176531330624919225119674426574742355349194934
	;;;96983520312774506326239578318016984801869478851843
	;;;85861560789112949495459501737958331952853208805511
	;;;12540698747158523863050715693290963295227443043557
	;;;66896648950445244523161731856403098711121722383113
	;;;62229893423380308135336276614282806444486645238749
	;;;30358907296290491560440772390713810515859307960866
	;;;70172427121883998797908792274921901699720888093776
	;;;65727333001053367881220235421809751254540594752243
	;;;52584907711670556013604839586446706324415722155397
	;;;53697817977846174064955149290862569321978468622482
	;;;83972241375657056057490261407972968652414535100474
	;;;82166370484403199890008895243450658541227588666881
	;;;16427171479924442928230863465674813919123162824586
	;;;17866458359124566529476545682848912883142607690042
	;;;24219022671055626321111109370544217506941658960408
	;;;07198403850962455444362981230987879927244284909188
	;;;84580156166097919133875499200524063689912560717606
	;;;05886116467109405077541002256983155200055935729725
	;;;71636269561882670428252483600823257530420752963450
	;;;
	;;;この1000桁の数字から13個の連続する数字を取り出して,
	;;;それらの総乗を計算する. では、それら総乗のうち、最大となる値はいくらか.
	;;;
	;;;EX 6桁の数123789から5個の連続する数字を取り出す場合,
	;;;1*2*3*7*8と2*3*7*8*9の二通りとなり, 後者の2*3*7*8*9=3024が最大の総乗となる.
	(define (problem8 n)
	(let ((v (list->vector
	(map (lambda (x)
	(- (char->integer x)
	(char->integer #\0)))
	(filter (lambda (x)
	(not (char=? x #\newline)))
	(string->list
	"73167176531330624919225119674426574742355349194934
	96983520312774506326239578318016984801869478851843
	85861560789112949495459501737958331952853208805511
	12540698747158523863050715693290963295227443043557
	66896648950445244523161731856403098711121722383113
	62229893423380308135336276614282806444486645238749
	30358907296290491560440772390713810515859307960866
	70172427121883998797908792274921901699720888093776
	65727333001053367881220235421809751254540594752243
	52584907711670556013604839586446706324415722155397
	53697817977846174064955149290862569321978468622482
	83972241375657056057490261407972968652414535100474
	82166370484403199890008895243450658541227588666881
	16427171479924442928230863465674813919123162824586
	17866458359124566529476545682848912883142607690042
	24219022671055626321111109370544217506941658960408
	07198403850962455444362981230987879927244284909188
	84580156166097919133875499200524063689912560717606
	05886116467109405077541002256983155200055935729725
	71636269561882670428252483600823257530420752963450"))))))
	(let loop ((start 0) (end n) (acc 0))
	(if (> end (vector-length v))
	acc
	(let ((ls (vector->list (vector-copy v start end))))
	(loop (+ start 1) (+ end 1) (if (memv 0 ls)
	acc
	(max acc (apply * ls)))))))))
	(problem8 13)
	;;;ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a < b < c で
	;;;以下の式を満たす数の組である.
	;;;a2 + b2 = c2
	;;;
	;;;例えば, 32 + 42 = 9 + 16 = 25 = 52 である.
	;;;
	;;;a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する.
	;;;これらの積 abc を計算しなさい.
	(define (problem9 x)
	(let ((pythagorean (stream-filter
	(lambda (x)
	(apply coprime? x)
	(odd? (apply - x)))
	(list->stream (list-ec (: m 2 x) (: n 1 m) `(,m ,n))))))
	(let loop ((k 0) (a 0) (b 0) (c 0))
	(if (= (+ a b c) x)
	(* a b c)
	(let-values (((m n) (apply values (stream-ref pythagorean k))))
	(loop (+ k 1) (* 2 m n)
	(- (expt m 2) (expt n 2))
	(+ (expt m 2) (expt n 2))))))))
	(problem9 1000)
	;;;10以下の素数の和は 2 + 3 + 5 + 7 = 17 である.
	;;;
	;;;200万以下の全ての素数の和を求めよ.
	(define (problem10 n)
	(let ((primes (stream-filter prime? (stream-from 2))))
	(let ((s (stream-take-while (lambda (x)
	(<= x n)) primes)))
	(stream-fold + 0 s))))
	(problem10 2000000)

view raw projectEuler1-10.rkt hosted with ❤ by GitHub