! Copyright (c) 2007-2009 Aaron Schaefer, Slava Pestov.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math math.functions ranges project-euler.common sequences
- sets ;
+USING: kernel math math.functions ranges project-euler.common
+sequences sets ;
IN: project-euler.001
-! https://projecteuler.net/index.php?section=problems&id=1
+! https://projecteuler.net/problem=1
! DESCRIPTION
! -----------
-! 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.
+! 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.
USING: kernel math sequences project-euler.common ;
IN: project-euler.002
-! https://projecteuler.net/index.php?section=problems&id=2
+! https://projecteuler.net/problem=2
! DESCRIPTION
! -----------
-! 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:
+! 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, ...
-! Find the sum of all the even-valued terms in the sequence which do not exceed
-! four million.
+! Find the sum of all the even-valued terms in the sequence
+! which do not exceed four million.
! SOLUTION
USING: math.primes.factors sequences project-euler.common ;
IN: project-euler.003
-! https://projecteuler.net/index.php?section=problems&id=3
+! https://projecteuler.net/problem=3
! DESCRIPTION
! -----------
sequences sets sorting ;
IN: project-euler.004
-! https://projecteuler.net/index.php?section=problems&id=4
+! https://projecteuler.net/problem=4
! DESCRIPTION
! -----------
-! A palindromic number reads the same both ways. The largest palindrome made
-! from the product of two 2-digit numbers is 9009 = 91 * 99.
+! 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.
+! Find the largest palindrome made from the product of two
+! 3-digit numbers.
! SOLUTION
USING: math project-euler.common ranges sequences ;
IN: project-euler.005
-! https://projecteuler.net/index.php?section=problems&id=5
+! https://projecteuler.net/problem=5
! DESCRIPTION
! -----------
-! 2520 is the smallest number that can be divided by each of the numbers from 1
-! to 10 without any remainder.
+! 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 number that is evenly divisible by all of the numbers from 1 to 20?
+! What is the smallest number that is evenly divisible by all of
+! the numbers from 1 to 20?
! SOLUTION
USING: kernel math ranges sequences project-euler.common ;
IN: project-euler.006
-! https://projecteuler.net/index.php?section=problems&id=6
+! https://projecteuler.net/problem=6
! DESCRIPTION
! -----------
! The square of the sum of the first ten natural numbers is,
! (1 + 2 + ... + 10)² = 55² = 3025
-! Hence the difference between the sum of the squares of the first ten natural
-! numbers and the square of the sum is 3025 - 385 = 2640.
+! Hence the difference between the sum of the squares of the
+! first ten natural numbers and the square of the sum is 3025 -
+! 385 = 2640.
-! Find the difference between the sum of the squares of the first one hundred
-! natural numbers and the square of the sum.
+! Find the difference between the sum of the squares of the
+! first one hundred natural numbers and the square of the sum.
! SOLUTION
USING: project-euler.common ;
IN: project-euler.007
-! https://projecteuler.net/index.php?section=problems&id=7
+! https://projecteuler.net/problem=7
! DESCRIPTION
! -----------
-! By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see
-! that the 6th prime is 13.
+! By listing the first six prime numbers: 2, 3, 5, 7, 11, and
+! 13, we can see that the 6th prime is 13.
! What is the 10001st prime number?
! Copyright (c) 2007, 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: grouping math.order math.parser sequences project-euler.common ;
+USING: grouping math.order math.parser sequences
+project-euler.common ;
IN: project-euler.008
-! https://projecteuler.net/index.php?section=problems&id=8
+! https://projecteuler.net/problem=8
! DESCRIPTION
! -----------
-! Find the greatest product of five consecutive digits in the 1000-digit number.
+! Find the greatest product of five consecutive digits in the
+! 1000-digit number.
! 73167176531330624919225119674426574742355349194934
! 96983520312774506326239578318016984801869478851843
USING: kernel make math sequences sorting project-euler.common ;
IN: project-euler.009
-! https://projecteuler.net/index.php?section=problems&id=9
+! https://projecteuler.net/problem=9
! DESCRIPTION
! -----------
-! A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
+! A Pythagorean triplet is a set of three natural numbers, a < b
+! < c, for which,
! a² + b² = c²
! For example, 3² + 4² = 9 + 16 = 25 = 5².
-! There exists exactly one Pythagorean triplet for which a + b + c = 1000.
-! Find the product abc.
+! There exists exactly one Pythagorean triplet for which a + b +
+! c = 1000. Find the product abc.
! SOLUTION
USING: math.primes sequences project-euler.common ;
IN: project-euler.010
-! https://projecteuler.net/index.php?section=problems&id=10
+! https://projecteuler.net/problem=10
! DESCRIPTION
! -----------
! Copyright (c) 2007, 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: grouping kernel make math.order sequences project-euler.common ;
+USING: grouping kernel make math.order sequences
+project-euler.common ;
IN: project-euler.011
-! https://projecteuler.net/index.php?section=problems&id=11
+! https://projecteuler.net/problem=11
! DESCRIPTION
! -----------
-! In the 20x20 grid below, four numbers along a diagonal line have been marked
-! in red.
+! In the 20x20 grid below, four numbers along a diagonal line
+! have been marked in red.
! 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
! 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
USING: kernel math project-euler.common ;
IN: project-euler.012
-! https://projecteuler.net/index.php?section=problems&id=12
+! https://projecteuler.net/problem=12
! DESCRIPTION
! -----------
-! The sequence of triangle numbers is generated by adding the natural numbers.
-! So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first
-! ten terms would be:
+! The sequence of triangle numbers is generated by adding the
+! natural numbers. So the 7th triangle number would be 1 + 2 + 3
+! + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
! 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
! 21: 1,3,7,21
! 28: 1,2,4,7,14,28
-! We can see that the 7th triangle number, 28, is the first triangle number to
-! have over five divisors.
+! We can see that the 7th triangle number, 28, is the first
+! triangle number to have over five divisors.
-! Which is the first triangle number to have over five-hundred divisors?
+! Which is the first triangle number to have over five-hundred
+! divisors?
! SOLUTION
USING: math.parser sequences project-euler.common ;
IN: project-euler.013
-! https://projecteuler.net/index.php?section=problems&id=13
+! https://projecteuler.net/problem=13
! DESCRIPTION
! -----------
-! Work out the first ten digits of the sum of the following one-hundred
-! 50-digit numbers.
+! Work out the first ten digits of the sum of the following
+! one-hundred 50-digit numbers.
! 37107287533902102798797998220837590246510135740250
! 46376937677490009712648124896970078050417018260538
! Copyright (c) 2007 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: combinators.short-circuit kernel make math math.functions ranges
- sequences project-euler.common ;
+USING: combinators.short-circuit kernel make math math.functions
+ranges sequences project-euler.common ;
IN: project-euler.014
-! https://projecteuler.net/index.php?section=problems&id=14
+! https://projecteuler.net/problem=14
! DESCRIPTION
! -----------
-! The following iterative sequence is defined for the set of positive integers:
+! The following iterative sequence is defined for the set of
+! positive integers:
! n -> n / 2 (n is even)
! n -> 3n + 1 (n is odd)
-! Using the rule above and starting with 13, we generate the following
-! sequence:
+! Using the rule above and starting with 13, we generate the
+! following sequence:
! 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
-! It can be seen that this sequence (starting at 13 and finishing at 1)
-! contains 10 terms. Although it has not been proved yet (Collatz Problem), it
-! is thought that all starting numbers finish at 1.
+! It can be seen that this sequence (starting at 13 and
+! finishing at 1) contains 10 terms. Although it has not been
+! proved yet (Collatz Problem), it is thought that all starting
+! numbers finish at 1.
-! Which starting number, under one million, produces the longest chain?
+! Which starting number, under one million, produces the longest
+! chain?
-! NOTE: Once the chain starts the terms are allowed to go above one million.
+! NOTE: Once the chain starts the terms are allowed to go above
+! one million.
! SOLUTION
USING: kernel math math.combinatorics project-euler.common ;
IN: project-euler.015
-! https://projecteuler.net/index.php?section=problems&id=15
+! https://projecteuler.net/problem=15
! DESCRIPTION
! -----------
-! Starting in the top left corner of a 2x2 grid, there are 6 routes (without
-! backtracking) to the bottom right corner.
+! Starting in the top left corner of a 2x2 grid, there are 6
+! routes (without backtracking) to the bottom right corner.
! How many routes are there through a 20x20 grid?
USING: math.functions project-euler.common sequences ;
IN: project-euler.016
-! https://projecteuler.net/index.php?section=problems&id=16
+! https://projecteuler.net/problem=16
! DESCRIPTION
! -----------
-! 2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
+! 2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 =
+! 26.
! What is the sum of the digits of the number 2^1000?
project-euler.common ;
IN: project-euler.017
-! https://projecteuler.net/index.php?section=problems&id=17
+! https://projecteuler.net/problem=17
! DESCRIPTION
! -----------
-! If the numbers 1 to 5 are written out in words: one, two, three, four, five;
-! there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
+! If the numbers 1 to 5 are written out in words: one, two,
+! three, four, five; there are 3 + 3 + 5 + 4 + 4 = 19 letters
+! used in total.
-! If all the numbers from 1 to 1000 (one thousand) inclusive were written out
-! in words, how many letters would be used?
+! If all the numbers from 1 to 1000 (one thousand) inclusive
+! were written out in words, how many letters would be used?
-! NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and
-! forty-two) contains 23 letters and 115 (one hundred and fifteen) contains
-! 20 letters.
+! NOTE: Do not count spaces or hyphens. For example, 342 (three
+! hundred and forty-two) contains 23 letters and 115 (one
+! hundred and fifteen) contains 20 letters.
! SOLUTION
! --------
: euler017 ( -- answer )
- 1000 [1..b] SBUF" " clone [ number>text append! ] reduce [ Letter? ] count ;
+ 1000 [1..b] SBUF" " clone [ number>text append! ] reduce
+ [ Letter? ] count ;
! [ euler017 ] 100 ave-time
! 15 ms ave run time - 1.71 SD (100 trials)
USING: kernel project-euler.common ranges sequences ;
IN: project-euler.018
-! https://projecteuler.net/index.php?section=problems&id=18
+! https://projecteuler.net/problem=18
! DESCRIPTION
! -----------
sequences ;
IN: project-euler.019
-! https://projecteuler.net/index.php?section=problems&id=19
+! https://projecteuler.net/problem=19
! DESCRIPTION
! -----------
-! You are given the following information, but you may prefer to do some
-! research for yourself.
+! You are given the following information, but you may prefer to
+! do some research for yourself.
! * 1 Jan 1900 was a Monday.
-! * Thirty days has September, April, June and November. All the rest have
-! thirty-one, Saving February alone, Which has twenty-eight, rain or
-! shine. And on leap years, twenty-nine.
-! * A leap year occurs on any year evenly divisible by 4, but not on a
-! century unless it is divisible by 400.
+! * Thirty days has September, April, June and November.
+! All the rest have thirty-one, Saving February alone, Which
+! has twenty-eight, rain or shine. And on leap years,
+! twenty-nine.
+! * A leap year occurs on any year evenly divisible by 4,
+! but not on a century unless it is divisible by 400.
-! How many Sundays fell on the first of the month during the twentieth century
-! (1 Jan 1901 to 31 Dec 2000)?
+! How many Sundays fell on the first of the month during the
+! twentieth century (1 Jan 1901 to 31 Dec 2000)?
! SOLUTION
! --------
-! Use Zeller congruence, which is implemented in the "calendar" module
-! already, as "(day-of-week) ( year month day -- n )" where n is
-! the day of the week (Sunday is 0).
+! Use Zeller congruence, which is implemented in the "calendar"
+! module already, as "(day-of-week) ( year month day -- n )"
+! where n is the day of the week (Sunday is 0).
: euler019 ( -- answer )
1901 2000 [a..b] [
USING: math.combinatorics project-euler.common sequences ;
IN: project-euler.020
-! https://projecteuler.net/index.php?section=problems&id=20
+! https://projecteuler.net/problem=20
! DESCRIPTION
! -----------
ranges sequences ;
IN: project-euler.021
-! https://projecteuler.net/index.php?section=problems&id=21
+! https://projecteuler.net/problem=21
! DESCRIPTION
! -----------
-! Let d(n) be defined as the sum of proper divisors of n (numbers less than n
-! which divide evenly into n).
+! Let d(n) be defined as the sum of proper divisors of n
+! (numbers less than n which divide evenly into n).
-! If d(a) = b and d(b) = a, where a != b, then a and b are an amicable pair and
-! each of a and b are called amicable numbers.
+! If d(a) = b and d(b) = a, where a != b, then a and b are an
+! amicable pair and each of a and b are called amicable numbers.
-! For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44,
-! 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4,
-! 71 and 142; so d(284) = 220.
+! For example, the proper divisors of 220 are 1, 2, 4, 5, 10,
+! 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper
+! divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
! Evaluate the sum of all the amicable numbers under 10000.
project-euler.common sequences sorting splitting ;
IN: project-euler.022
-! https://projecteuler.net/index.php?section=problems&id=22
+! https://projecteuler.net/problem=22
! DESCRIPTION
! -----------
-! Using names.txt (right click and 'Save Link/Target As...'), a 46K text file
-! containing over five-thousand first names, begin by sorting it into
-! alphabetical order. Then working out the alphabetical value for each name,
-! multiply this value by its alphabetical position in the list to obtain a name
-! score.
+! Using names.txt (right click and 'Save Link/Target As...'), a
+! 46K text file containing over five-thousand first names, begin
+! by sorting it into alphabetical order. Then working out the
+! alphabetical value for each name, multiply this value by its
+! alphabetical position in the list to obtain a name score.
-! For example, when the list is sorted into alphabetical order, COLIN, which is
-! worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN
-! would obtain a score of 938 * 53 = 49714.
+! For example, when the list is sorted into alphabetical order,
+! COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th
+! name in the list. So, COLIN would obtain a score of 938 * 53 =
+! 49714.
! What is the total of all the name scores in the file?
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math ranges project-euler.common
-sequences sets ;
+USING: kernel math ranges project-euler.common sequences sets ;
IN: project-euler.023
-! https://projecteuler.net/index.php?section=problems&id=23
+! https://projecteuler.net/problem=23
! DESCRIPTION
! -----------
-! A perfect number is a number for which the sum of its proper divisors is
-! exactly equal to the number. For example, the sum of the proper divisors of
-! 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
+! A perfect number is a number for which the sum of its proper
+! divisors is exactly equal to the number. For example, the sum
+! of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28,
+! which means that 28 is a perfect number.
-! A number whose proper divisors are less than the number is called deficient
-! and a number whose proper divisors exceed the number is called abundant.
+! A number whose proper divisors are less than the number is
+! called deficient and a number whose proper divisors exceed the
+! number is called abundant.
-! As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest
-! number that can be written as the sum of two abundant numbers is 24. By
-! mathematical analysis, it can be shown that all integers greater than 28123
-! can be written as the sum of two abundant numbers. However, this upper limit
-! cannot be reduced any further by analysis even though it is known that the
-! greatest number that cannot be expressed as the sum of two abundant numbers
-! is less than this limit.
+! As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16,
+! the smallest number that can be written as the sum of two
+! abundant numbers is 24. By mathematical analysis, it can be
+! shown that all integers greater than 28123 can be written as
+! the sum of two abundant numbers. However, this upper limit
+! cannot be reduced any further by analysis even though it is
+! known that the greatest number that cannot be expressed as the
+! sum of two abundant numbers is less than this limit.
-! Find the sum of all the positive integers which cannot be written as the sum
-! of two abundant numbers.
+! Find the sum of all the positive integers which cannot be
+! written as the sum of two abundant numbers.
! SOLUTION
! --------
-! The upper limit can be dropped to 20161 which reduces our search space
-! and every even number > 46 can be expressed as a sum of two abundants
+! The upper limit can be dropped to 20161 which reduces our
+! search space and every even number > 46 can be expressed as a
+! sum of two abundants
<PRIVATE
USING: math.combinatorics project-euler.common sequences ;
IN: project-euler.024
-! https://projecteuler.net/index.php?section=problems&id=24
+! https://projecteuler.net/problem=24
! DESCRIPTION
! -----------
-! A permutation is an ordered arrangement of objects. For example, 3124 is one
-! possible permutation of the digits 1, 2, 3 and 4. If all of the permutations
-! are listed numerically or alphabetically, we call it lexicographic order. The
+! A permutation is an ordered arrangement of objects. For
+! example, 3124 is one possible permutation of the digits 1, 2,
+! 3 and 4. If all of the permutations are listed numerically or
+! alphabetically, we call it lexicographic order. The
! lexicographic permutations of 0, 1 and 2 are:
! 012 021 102 120 201 210
-! What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4,
-! 5, 6, 7, 8 and 9?
+! What is the millionth lexicographic permutation of the digits
+! 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
! SOLUTION
project-euler.common sequences ;
IN: project-euler.025
-! https://projecteuler.net/index.php?section=problems&id=25
+! https://projecteuler.net/problem=25
! DESCRIPTION
! -----------
! The 12th term, F12, is the first term to contain three digits.
-! What is the first term in the Fibonacci sequence to contain 1000 digits?
+! What is the first term in the Fibonacci sequence to contain
+! 1000 digits?
! SOLUTION
project-euler.common sequences ;
IN: project-euler.026
-! https://projecteuler.net/index.php?section=problems&id=26
+! https://projecteuler.net/problem=26
! DESCRIPTION
! -----------
-! A unit fraction contains 1 in the numerator. The decimal representation of
-! the unit fractions with denominators 2 to 10 are given:
+! A unit fraction contains 1 in the numerator. The decimal
+! representation of the unit fractions with denominators 2 to 10
+! are given:
! 1/2 = 0.5
! 1/3 = 0.(3)
! 1/9 = 0.(1)
! 1/10 = 0.1
-! Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be
-! seen that 1/7 has a 6-digit recurring cycle.
+! Where 0.1(6) means 0.166666..., and has a 1-digit recurring
+! cycle. It can be seen that 1/7 has a 6-digit recurring cycle.
-! Find the value of d < 1000 for which 1/d contains the longest recurring cycle
-! in its decimal fraction part.
+! Find the value of d < 1000 for which 1/d contains the longest
+! recurring cycle in its decimal fraction part.
! SOLUTION
swap 1 (mult-order) ;
: period-length ( a/b -- n )
- dup recurring-period? [ denominator 10 swap mult-order ] [ drop 0 ] if ;
+ dup recurring-period?
+ [ denominator 10 swap mult-order ] [ drop 0 ] if ;
<PRIVATE
USING: kernel math math.primes project-euler.common sequences ;
IN: project-euler.027
-! https://projecteuler.net/index.php?section=problems&id=27
+! https://projecteuler.net/problem=27
! DESCRIPTION
! -----------
! n² + n + 41
-! It turns out that the formula will produce 40 primes for the consecutive
-! values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is
-! divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly
-! divisible by 41.
+! It turns out that the formula will produce 40 primes for the
+! consecutive values n = 0 to 39. However, when n = 40, 402 + 40
+! + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when
+! n = 41, 41² + 41 + 41 is clearly divisible by 41.
-! Using computers, the incredible formula n² - 79n + 1601 was discovered, which
-! produces 80 primes for the consecutive values n = 0 to 79. The product of the
-! coefficients, -79 and 1601, is -126479.
+! Using computers, the incredible formula n² - 79n + 1601 was
+! discovered, which produces 80 primes for the consecutive
+! values n = 0 to 79. The product of the coefficients, -79 and
+! 1601, is -126479.
! Considering quadratics of the form:
! where |n| is the modulus/absolute value of n
! e.g. |11| = 11 and |-4| = 4
-! Find the product of the coefficients, a and b, for the quadratic expression
-! that produces the maximum number of primes for consecutive values of n,
-! starting with n = 0.
+! Find the product of the coefficients, a and b, for the
+! quadratic expression that produces the maximum number of
+! primes for consecutive values of n, starting with n = 0.
! SOLUTION
USING: kernel math ranges sequences project-euler.common ;
IN: project-euler.028
-! https://projecteuler.net/index.php?section=problems&id=28
+! https://projecteuler.net/problem=28
! DESCRIPTION
! -----------
-! Starting with the number 1 and moving to the right in a clockwise direction a
-! 5 by 5 spiral is formed as follows:
+! Starting with the number 1 and moving to the right in a
+! clockwise direction a 5 by 5 spiral is formed as follows:
! 21 22 23 24 25
! 20 7 8 9 10
! It can be verified that the sum of both diagonals is 101.
-! What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?
+! What is the sum of both diagonals in a 1001 by 1001 spiral
+! formed in the same way?
! SOLUTION
sequences sets ;
IN: project-euler.029
-! https://projecteuler.net/index.php?section=problems&id=29
+! https://projecteuler.net/problem=29
! DESCRIPTION
! -----------
-! Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
+! Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and
+! 2 ≤ b ≤ 5:
! 2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32
! 3^2 = 9, 3^3 = 27, 3^4 = 81, 3^5 = 243
! 4^2 = 16, 4^3 = 64, 4^4 = 256, 4^5 = 1024
! 5^2 = 25, 5^3 = 125, 5^4 = 625, 5^5 = 3125
-! If they are then placed in numerical order, with any repeats removed, we get
-! the following sequence of 15 distinct terms:
+! If they are then placed in numerical order, with any repeats
+! removed, we get the following sequence of 15 distinct terms:
-! 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
+! 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024,
+! 3125
-! How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100
-! and 2 ≤ b ≤ 100?
+! How many distinct terms are in the sequence generated by a^b
+! for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
! SOLUTION
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math math.functions project-euler.common sequences ;
+USING: kernel math math.functions project-euler.common sequences
+;
IN: project-euler.030
-! https://projecteuler.net/index.php?section=problems&id=30
+! https://projecteuler.net/problem=30
! DESCRIPTION
! -----------
-! Surprisingly there are only three numbers that can be written as the sum of
-! fourth powers of their digits:
+! Surprisingly there are only three numbers that can be written
+! as the sum of fourth powers of their digits:
! 1634 = 1^4 + 6^4 + 3^4 + 4^4
! 8208 = 8^4 + 2^4 + 0^4 + 8^4
! The sum of these numbers is 1634 + 8208 + 9474 = 19316.
-! Find the sum of all the numbers that can be written as the sum of fifth
-! powers of their digits.
+! Find the sum of all the numbers that can be written as the sum
+! of fifth powers of their digits.
! SOLUTION
USING: kernel math project-euler.common ;
IN: project-euler.031
-! https://projecteuler.net/index.php?section=problems&id=31
+! https://projecteuler.net/problem=31
! DESCRIPTION
! -----------
-! In England the currency is made up of pound, £, and pence, p, and there are
-! eight coins in general circulation:
+! In England the currency is made up of pound, £, and pence, p,
+! and there are eight coins in general circulation:
! 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
! 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
-! How many different ways can £2 be made using any number of coins?
+! How many different ways can £2 be made using any number of
+! coins?
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math math.combinatorics math.functions math.parser ranges
- project-euler.common sequences sets ;
+USING: kernel math math.combinatorics math.functions math.parser
+ranges project-euler.common sequences sets ;
IN: project-euler.032
-! https://projecteuler.net/index.php?section=problems&id=32
+! https://projecteuler.net/problem=32
! DESCRIPTION
! -----------
-! The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing
-! multiplicand, multiplier, and product is 1 through 9 pandigital.
+! The product 7254 is unusual, as the identity, 39 × 186 = 7254,
+! containing multiplicand, multiplier, and product is 1 through
+! 9 pandigital.
-! Find the sum of all products whose multiplicand/multiplier/product identity
-! can be written as a 1 through 9 pandigital.
+! Find the sum of all products whose
+! multiplicand/multiplier/product identity can be written as a 1
+! through 9 pandigital.
-! HINT: Some products can be obtained in more than one way so be sure to only
-! include it once in your sum.
+! HINT: Some products can be obtained in more than one way so be
+! sure to only include it once in your sum.
! SOLUTION
! --------
-! Generate all pandigital numbers and then check if they fit the identity
+! Generate all pandigital numbers and then check if they fit the
+! identity
<PRIVATE
USING: kernel math ranges project-euler.common sequences ;
IN: project-euler.033
-! https://projecteuler.net/index.php?section=problems&id=33
+! https://projecteuler.net/problem=33
! DESCRIPTION
! -----------
-! The fraction 49/98 is a curious fraction, as an inexperienced mathematician
-! in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which
-! is correct, is obtained by cancelling the 9s.
+! The fraction 49/98 is a curious fraction, as an inexperienced
+! mathematician in attempting to simplify it may incorrectly
+! believe that 49/98 = 4/8, which is correct, is obtained by
+! cancelling the 9s.
-! We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
+! We shall consider fractions like, 30/50 = 3/5, to be trivial
+! examples.
-! There are exactly four non-trivial examples of this type of fraction, less
-! than one in value, and containing two digits in the numerator and
-! denominator.
+! There are exactly four non-trivial examples of this type of
+! fraction, less than one in value, and containing two digits in
+! the numerator and denominator.
-! If the product of these four fractions is given in its lowest common terms,
-! find the value of the denominator.
+! If the product of these four fractions is given in its lowest
+! common terms, find the value of the denominator.
! SOLUTION
! --------
-! Through analysis, you only need to check fractions fitting the pattern ax/xb
+! Through analysis, you only need to check fractions fitting the
+! pattern ax/xb
<PRIVATE
USING: kernel ranges project-euler.common sequences ;
IN: project-euler.034
-! https://projecteuler.net/index.php?section=problems&id=34
+! https://projecteuler.net/problem=34
! DESCRIPTION
! -----------
! 145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
-! Find the sum of all numbers which are equal to the sum of the factorial of
-! their digits.
+! Find the sum of all numbers which are equal to the sum of the
+! factorial of their digits.
! Note: as 1! = 1 and 2! = 2 are not sums they are not included.
! SOLUTION
! --------
-! We can reduce the upper bound a little by calculating 7 * 9! = 2540160, and
-! then reducing one of the 9! to 2! (since the 7th digit cannot exceed 2), so we
-! get 2! + 6 * 9! = 2177282 as an upper bound.
+! We can reduce the upper bound a little by calculating 7 * 9! =
+! 2540160, and then reducing one of the 9! to 2! (since the 7th
+! digit cannot exceed 2), so we get 2! + 6 * 9! = 2177282 as an
+! upper bound.
-! We can then take that one more step, and notice that the largest factorial
-! sum a 7 digit number starting with 21 or 20 is 2! + 1! + 5 * 9! or 1814403.
-! So there can't be any 7 digit solutions starting with 21 or 20, and therefore
-! our numbers must be less that 2000000.
+! We can then take that one more step, and notice that the
+! largest factorial sum a 7 digit number starting with 21 or 20
+! is 2! + 1! + 5 * 9! or 1814403. So there can't be any 7 digit
+! solutions starting with 21 or 20, and therefore our numbers
+! must be less that 2000000.
<PRIVATE
USING: kernel math math.primes project-euler.common sequences ;
IN: project-euler.035
-! https://projecteuler.net/index.php?section=problems&id=35
+! https://projecteuler.net/problem=35
! DESCRIPTION
! -----------
-! The number, 197, is called a circular prime because all rotations of the
-! digits: 197, 971, and 719, are themselves prime.
+! The number, 197, is called a circular prime because all
+! rotations of the digits: 197, 971, and 719, are themselves
+! prime.
! There are thirteen such primes below 100:
! 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
USING: combinators.short-circuit kernel math.parser ranges
- project-euler.common sequences ;
+project-euler.common sequences ;
IN: project-euler.036
-! https://projecteuler.net/index.php?section=problems&id=36
+! https://projecteuler.net/problem=36
! DESCRIPTION
! -----------
-! The decimal number, 585 = 1001001001 (binary), is palindromic in both bases.
+! The decimal number, 585 = 1001001001 (binary), is palindromic
+! in both bases.
-! Find the sum of all numbers, less than one million, which are palindromic in
-! base 10 and base 2.
+! Find the sum of all numbers, less than one million, which are
+! palindromic in base 10 and base 2.
-! (Please note that the palindromic number, in either base, may not include
-! leading zeros.)
+! (Please note that the palindromic number, in either base, may
+! not include leading zeros.)
! SOLUTION
! --------
-! Only check odd numbers since the binary number must begin and end with 1
+! Only check odd numbers since the binary number must begin and
+! end with 1
<PRIVATE
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math math.parser math.primes sequences project-euler.common ;
+USING: kernel math math.parser math.primes sequences
+project-euler.common ;
IN: project-euler.037
-! https://projecteuler.net/index.php?section=problems&id=37
+! https://projecteuler.net/problem=37
! DESCRIPTION
! -----------
-! The number 3797 has an interesting property. Being prime itself, it is
-! possible to continuously remove digits from left to right, and remain prime
-! at each stage: 3797, 797, 97, and 7. Similarly we can work from right to
-! left: 3797, 379, 37, and 3.
+! The number 3797 has an interesting property. Being prime
+! itself, it is possible to continuously remove digits from left
+! to right, and remain prime at each stage: 3797, 797, 97, and
+! 7. Similarly we can work from right to left: 3797, 379, 37,
+! and 3.
-! Find the sum of the only eleven primes that are both truncatable from left to
-! right and right to left.
+! Find the sum of the only eleven primes that are both
+! truncatable from left to right and right to left.
-! NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
+! NOTE: 2, 3, 5, and 7 are not considered to be truncatable
+! primes.
! SOLUTION
USING: kernel math ranges project-euler.common sequences ;
IN: project-euler.038
-! https://projecteuler.net/index.php?section=problems&id=38
+! https://projecteuler.net/problem=38
! DESCRIPTION
! -----------
! 192 × 2 = 384
! 192 × 3 = 576
-! By concatenating each product we get the 1 to 9 pandigital, 192384576. We
-! will call 192384576 the concatenated product of 192 and (1,2,3)
+! By concatenating each product we get the 1 to 9 pandigital,
+! 192384576. We will call 192384576 the concatenated product of
+! 192 and (1,2,3)
-! The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4,
-! and 5, giving the pandigital, 918273645, which is the concatenated product of
-! 9 and (1,2,3,4,5).
+! The same can be achieved by starting with 9 and multiplying by
+! 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is
+! the concatenated product of 9 and (1,2,3,4,5).
-! What is the largest 1 to 9 pandigital 9-digit number that can be formed as
-! the concatenated product of an integer with (1,2, ... , n) where n > 1?
+! What is the largest 1 to 9 pandigital 9-digit number that can
+! be formed as the concatenated product of an integer with
+! (1,2, ..., n) where n > 1?
! SOLUTION
! --------
-! Only need to search 4-digit numbers starting with 9 since a 2-digit number
-! starting with 9 would produce 8 or 11 digits, and a 3-digit number starting
-! with 9 would produce 7 or 11 digits.
+! Only need to search 4-digit numbers starting with 9 since a
+! 2-digit number starting with 9 would produce 8 or 11 digits,
+! and a 3-digit number starting with 9 would produce 7 or 11
+! digits.
<PRIVATE
sequences sequences.extras ;
IN: project-euler.039
-! https://projecteuler.net/index.php?section=problems&id=39
+! https://projecteuler.net/problem=39
! DESCRIPTION
! -----------
-! If p is the perimeter of a right angle triangle with integral length sides,
-! {a,b,c}, there are exactly three solutions for p = 120.
+! If p is the perimeter of a right angle triangle with integral
+! length sides, {a,b,c}, there are exactly three solutions for p
+! = 120.
! {20,48,52}, {24,45,51}, {30,40,50}
-! For which value of p < 1000, is the number of solutions maximized?
+! For which value of p < 1000, is the number of solutions
+! maximized?
! SOLUTION
! --------
-! Algorithm adapted from https://mathworld.wolfram.com/PythagoreanTriple.html
+! Algorithm adapted from
+! https://mathworld.wolfram.com/PythagoreanTriple.html
! Identical implementation as problem #75
-! Basically, this makes an array of 1000 zeros, recursively creates primitive
-! triples using the three transforms and then increments the array at index
-! [a+b+c] by one for each triple's sum AND its multiples under 1000 (to account
-! for non-primitive triples). The answer is just the index that has the highest
+! Basically, this makes an array of 1000 zeros, recursively
+! creates primitive triples using the three transforms and then
+! increments the array at index [a+b+c] by one for each triple's
+! sum AND its multiples under 1000 (to account for non-primitive
+! triples). The answer is just the index that has the highest
! number.
SYMBOL: p-count
USING: kernel math math.parser sequences project-euler.common ;
IN: project-euler.040
-! https://projecteuler.net/index.php?section=problems&id=40
+! https://projecteuler.net/problem=40
! DESCRIPTION
! -----------
-! An irrational decimal fraction is created by concatenating the positive
-! integers:
+! An irrational decimal fraction is created by concatenating the
+! positive integers:
! 0.123456789101112131415161718192021...
-! It can be seen that the 12th digit of the fractional part is 1.
+! It can be seen that the 12th digit of the fractional part is
+! 1.
-! If dn represents the nth digit of the fractional part, find the value of the
-! following expression.
+! If dn represents the nth digit of the fractional part, find
+! the value of the following expression.
! d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math.combinatorics math.primes sequences project-euler.common ;
+USING: kernel math.combinatorics math.primes sequences
+project-euler.common ;
IN: project-euler.041
-! https://projecteuler.net/index.php?section=problems&id=41
+! https://projecteuler.net/problem=41
! DESCRIPTION
! -----------
-! We shall say that an n-digit number is pandigital if it makes use of all the
-! digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is
-! also prime.
+! We shall say that an n-digit number is pandigital if it makes
+! use of all the digits 1 to n exactly once. For example, 2143
+! is a 4-digit pandigital and is also prime.
! What is the largest n-digit pandigital prime that exists?
! SOLUTION
! --------
-! Check 7-digit pandigitals because if the sum of the digits in any number add
-! up to a multiple of three, then it is a multiple of three and can't be prime.
-! I assumed there would be a 7-digit answer, but technically a higher 4-digit
-! pandigital than the one given in the description was also possible.
+! Check 7-digit pandigitals because if the sum of the digits in
+! any number add up to a multiple of three, then it is a
+! multiple of three and can't be prime. I assumed there would be
+! a 7-digit answer, but technically a higher 4-digit pandigital
+! than the one given in the description was also possible.
! 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
! 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: ascii io.encodings.ascii io.files kernel make math math.functions
-project-euler.common sequences splitting ;
+USING: ascii io.encodings.ascii io.files kernel make math
+math.functions project-euler.common sequences splitting ;
IN: project-euler.042
-! https://projecteuler.net/index.php?section=problems&id=42
+! https://projecteuler.net/problem=42
! DESCRIPTION
! -----------
! 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
-! By converting each letter in a word to a number corresponding to its
-! alphabetical position and adding these values we form a word value. For
-! example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value
-! is a triangle number then we shall call the word a triangle word.
+! By converting each letter in a word to a number corresponding
+! to its alphabetical position and adding these values we form a
+! word value. For example, the word value for SKY is 19 + 11 +
+! 25 = 55 = t10. If the word value is a triangle number then we
+! shall call the word a triangle word.
-! Using words.txt (right click and 'Save Link/Target As...'), a 16K text file
-! containing nearly two-thousand common English words, how many are triangle
-! words?
+! Using words.txt (right click and 'Save Link/Target As...'), a
+! 16K text file containing nearly two-thousand common English
+! words, how many are triangle words?
! SOLUTION
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: combinators.short-circuit kernel math math.functions math.combinatorics
- ranges project-euler.common sequences sets sorting ;
+USING: combinators.short-circuit kernel math math.functions
+math.combinatorics ranges project-euler.common sequences sets
+sorting ;
IN: project-euler.043
-! https://projecteuler.net/index.php?section=problems&id=43
+! https://projecteuler.net/problem=43
! DESCRIPTION
! -----------
-! The number, 1406357289, is a 0 to 9 pandigital number because it is made up
-! of each of the digits 0 to 9 in some order, but it also has a rather
-! interesting sub-string divisibility property.
+! The number, 1406357289, is a 0 to 9 pandigital number because
+! it is made up of each of the digits 0 to 9 in some order, but
+! it also has a rather interesting sub-string divisibility
+! property.
-! Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note
-! the following:
+! Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In
+! this way, we note the following:
! * d2d3d4 = 406 is divisible by 2
! * d3d4d5 = 063 is divisible by 3
! * d7d8d9 = 728 is divisible by 13
! * d8d9d10 = 289 is divisible by 17
-! Find the sum of all 0 to 9 pandigital numbers with this property.
+! Find the sum of all 0 to 9 pandigital numbers with this
+! property.
! SOLUTION
! --------
-! Brute force generating all the pandigitals then checking 3-digit divisiblity
-! properties...this is very slow!
+! Brute force generating all the pandigitals then checking
+! 3-digit divisiblity properties...this is very slow!
<PRIVATE
sequences layouts ;
IN: project-euler.044
-! https://projecteuler.net/index.php?section=problems&id=44
+! https://projecteuler.net/problem=44
! DESCRIPTION
! -----------
-! Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten
-! pentagonal numbers are:
+! Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2.
+! The first ten pentagonal numbers are:
! 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
-! It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference,
-! 70 − 22 = 48, is not pentagonal.
+! It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However,
+! their difference, 70 − 22 = 48, is not pentagonal.
-! Find the pair of pentagonal numbers, Pj and Pk, for which their sum and
-! difference is pentagonal and D = |Pk − Pj| is minimised; what is the value of D?
+! Find the pair of pentagonal numbers, Pj and Pk, for which
+! their sum and difference is pentagonal and D = |Pk − Pj| is
+! minimised; what is the value of D?
! SOLUTION
! --------
-! Brute force using a cartesian product and an arbitrarily chosen limit.
+! Brute force using a cartesian product and an arbitrarily
+! chosen limit.
<PRIVATE
USING: kernel math project-euler.common ;
IN: project-euler.045
-! https://projecteuler.net/index.php?section=problems&id=45
+! https://projecteuler.net/problem=45
! DESCRIPTION
! -----------
-! Triangle, pentagonal, and hexagonal numbers are generated by the following
-! formulae:
+! Triangle, pentagonal, and hexagonal numbers are generated by
+! the following formulae:
! Triangle Tn = n(n + 1) / 2 1, 3, 6, 10, 15, ...
! Pentagonal Pn = n(3n − 1) / 2 1, 5, 12, 22, 35, ...
! Hexagonal Hn = n(2n − 1) 1, 6, 15, 28, 45, ...
! It can be verified that T285 = P165 = H143 = 40755.
-! Find the next triangle number that is also pentagonal and hexagonal.
+! Find the next triangle number that is also pentagonal and
+! hexagonal.
! SOLUTION
! --------
-! All hexagonal numbers are also triangle numbers, so iterate through hexagonal
-! numbers until you find one that is pentagonal as well.
+! All hexagonal numbers are also triangle numbers, so iterate
+! through hexagonal numbers until you find one that is
+! pentagonal as well.
<PRIVATE
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math math.functions math.primes ranges
-sequences project-euler.common ;
+USING: kernel math math.functions math.primes ranges sequences
+project-euler.common ;
IN: project-euler.046
-! https://projecteuler.net/index.php?section=problems&id=46
+! https://projecteuler.net/problem=46
! DESCRIPTION
! -----------
-! It was proposed by Christian Goldbach that every odd composite number can be
-! written as the sum of a prime and twice a square.
+! It was proposed by Christian Goldbach that every odd composite
+! number can be written as the sum of a prime and twice a
+! square.
! 9 = 7 + 2 * 1^2
! 15 = 7 + 2 * 2^2
! It turns out that the conjecture was false.
-! What is the smallest odd composite that cannot be written as the sum of a
-! prime and twice a square?
+! What is the smallest odd composite that cannot be written as
+! the sum of a prime and twice a square?
! SOLUTION
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: arrays kernel math math.primes math.primes.factors
- ranges namespaces sequences project-euler.common ;
+USING: arrays kernel math math.primes math.primes.factors ranges
+namespaces sequences project-euler.common ;
IN: project-euler.047
-! https://projecteuler.net/index.php?section=problems&id=47
+! https://projecteuler.net/problem=47
! DESCRIPTION
! -----------
-! The first two consecutive numbers to have two distinct prime factors are:
+! The first two consecutive numbers to have two distinct prime
+! factors are:
! 14 = 2 * 7
! 15 = 3 * 5
-! The first three consecutive numbers to have three distinct prime factors are:
+! The first three consecutive numbers to have three distinct
+! prime factors are:
! 644 = 2² * 7 * 23
! 645 = 3 * 5 * 43
! 646 = 2 * 17 * 19.
-! Find the first four consecutive integers to have four distinct primes
-! factors. What is the first of these numbers?
+! Find the first four consecutive integers to have four distinct
+! primes factors. What is the first of these numbers?
! SOLUTION
! --------
-! Brute force, not sure why it's incredibly slow compared to other languages
+! Brute force, not sure why it's incredibly slow compared to
+! other languages
<PRIVATE
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math math.functions ranges
-project-euler.common sequences ;
+USING: kernel math math.functions ranges project-euler.common
+sequences ;
IN: project-euler.048
-! https://projecteuler.net/index.php?section=problems&id=48
+! https://projecteuler.net/problem=48
! DESCRIPTION
! -----------
! The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.
-! Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.
+! Find the last ten digits of the series,
+! 1^1 + 2^2 + 3^3 + ... + 1000^1000.
! SOLUTION
FROM: project-euler.common => permutations? ;
IN: project-euler.049
-! https://projecteuler.net/index.php?section=problems&id=49
+! https://projecteuler.net/problem=49
! DESCRIPTION
! -----------
-! The arithmetic sequence, 1487, 4817, 8147, in which each of the terms
-! increases by 3330, is unusual in two ways: (i) each of the three terms are
-! prime, and, (ii) each of the 4-digit numbers are permutations of one another.
+! The arithmetic sequence, 1487, 4817, 8147, in which each of
+! the terms increases by 3330, is unusual in two ways: (i) each
+! of the three terms are prime, and, (ii) each of the 4-digit
+! numbers are permutations of one another.
-! There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes,
-! exhibiting this property, but there is one other 4-digit increasing sequence.
+! There are no arithmetic sequences made up of three 1-, 2-, or
+! 3-digit primes, exhibiting this property, but there is one
+! other 4-digit increasing sequence.
-! What 12-digit number do you form by concatenating the three terms in this
-! sequence?
+! What 12-digit number do you form by concatenating the three
+! terms in this sequence?
! SOLUTION
project-euler.common sequences ;
IN: project-euler.050
-! https://projecteuler.net/index.php?section=problems&id=50
+! https://projecteuler.net/problem=50
! DESCRIPTION
! -----------
-! The prime 41, can be written as the sum of six consecutive primes:
+! The prime 41, can be written as the sum of six consecutive
+! primes:
! 41 = 2 + 3 + 5 + 7 + 11 + 13
-! This is the longest sum of consecutive primes that adds to a prime below
-! one-hundred.
+! This is the longest sum of consecutive primes that adds to a
+! prime below one-hundred.
-! The longest sum of consecutive primes below one-thousand that adds to a
-! prime, contains 21 terms, and is equal to 953.
+! The longest sum of consecutive primes below one-thousand that
+! adds to a prime, contains 21 terms, and is equal to 953.
-! Which prime, below one-million, can be written as the sum of the most
-! consecutive primes?
+! Which prime, below one-million, can be written as the sum of
+! the most consecutive primes?
! SOLUTION
! --------
! 1) Create an sequence of all primes under 1000000.
-! 2) Start summing elements in the sequence until the next number would put you
-! over 1000000.
-! 3) Check if that sum is prime, if not, subtract the last number added.
-! 4) Repeat step 3 until you get a prime number, and store it along with the
-! how many consecutive numbers from the original sequence it took to get there.
-! 5) Drop the first number from the sequence of primes, and do steps 2-4 again
-! 6) Compare the longest chain from the first run with the second run, and store
-! the longer of the two.
-! 7) If the sequence of primes is still longer than the longest chain, then
-! repeat steps 5-7...otherwise, you've found the longest sum of consecutive
-! primes!
+! 2) Start summing elements in the sequence until the next
+! number would put you over 1000000.
+! 3) Check if that sum is prime, if not, subtract the last
+! number added.
+! 4) Repeat step 3 until you get a prime number, and store it
+! along with the how many consecutive numbers from the
+! original sequence it took to get there.
+! 5) Drop the first number from the sequence of primes, and do
+! steps 2-4 again
+! 6) Compare the longest chain from the first run with the
+! second run, and store the longer of the two.
+! 7) If the sequence of primes is still longer than the longest
+! chain, then repeat steps 5-7...otherwise, you've found the
+! longest sum of consecutive primes!
<PRIVATE
! Copyright (C) 2009 Jon Harper.
! See https://factorcode.org/license.txt for BSD license.
+USING: assocs kernel math math.combinatorics math.functions
+math.order math.parser math.primes ranges namespaces
+project-euler.common sequences sets ;
+IN: project-euler.051
-! https://projecteuler.net/index.php?section=problems&id=1
+! https://projecteuler.net/problem=51
! DESCRIPTION
! -----------
-
-! By replacing the first digit of *3, it turns out that
-! six of the nine possible values:
-! 13, 23, 43, 53, 73, and 83, are all prime.
-! By replacing the third and fourth digits of 56**3 with the same digit,
-! this 5-digit number is the first example having seven primes among
-! the ten generated numbers, yielding the family:
-! 56003, 56113, 56333, 56443, 56663, 56773, and 56993.
-! Consequently 56003, being the first member of this family,
-! is the smallest prime with this property.
+! By replacing the first digit of *3, it turns out that six of
+! the nine possible values: 13, 23, 43, 53, 73, and 83, are all
+! prime. By replacing the third and fourth digits of 56**3 with
+! the same digit, this 5-digit number is the first example
+! having seven primes among the ten generated numbers, yielding
+! the family: 56003, 56113, 56333, 56443, 56663, 56773, and
+! 56993. Consequently 56003, being the first member of this
+! family, is the smallest prime with this property.
!
! Find the smallest prime which, by replacing part of the number
-! (not necessarily adjacent digits) with the same digit,
-! is part of an eight prime value family.
+! (not necessarily adjacent digits) with the same digit, is part
+! of an eight prime value family.
! SOLUTION
! --------
-! for each prime number, count the families it belongs to. When one reaches count of 8, stop, and get the smallest number by replacing * with ones.
+! for each prime number, count the families it belongs to. When
+! one reaches count of 8, stop, and get the smallest number by
+! replacing * with ones.
-USING: assocs kernel math math.combinatorics math.functions
-math.order math.parser math.primes ranges namespaces
-project-euler.common sequences sets ;
-IN: project-euler.051
<PRIVATE
SYMBOL: family-count
SYMBOL: large-families
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
USING: combinators.short-circuit kernel math math.functions
- project-euler.common sequences sorting grouping ;
+project-euler.common sequences sorting grouping ;
IN: project-euler.052
-! https://projecteuler.net/index.php?section=problems&id=52
+! https://projecteuler.net/problem=52
! DESCRIPTION
! -----------
-! It can be seen that the number, 125874, and its double, 251748, contain
-! exactly the same digits, but in a different order.
+! It can be seen that the number, 125874, and its double,
+! 251748, contain exactly the same digits, but in a different
+! order.
-! Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x,
-! contain the same digits.
+! Find the smallest positive integer, x, such that 2x, 3x, 4x,
+! 5x, and 6x, contain the same digits.
! SOLUTION
! --------
-! Analysis shows the number must be odd, divisible by 3, and larger than 123456
+! Analysis shows the number must be odd, divisible by 3, and
+! larger than 123456
<PRIVATE
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math math.combinatorics ranges sequences project-euler.common ;
+USING: kernel math math.combinatorics ranges sequences
+project-euler.common ;
IN: project-euler.053
-! https://projecteuler.net/index.php?section=problems&id=53
+! https://projecteuler.net/problem=53
! DESCRIPTION
! -----------
-! There are exactly ten ways of selecting three from five, 12345:
+! There are exactly ten ways of selecting three from five,
+! 12345:
! 123, 124, 125, 134, 135, 145, 234, 235, 245, and 345
! nCr = n! / r! * (n - r)!
! where r ≤ n, n! = n * (n − 1) * ... * 3 * 2 * 1, and 0! = 1.
-! It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.
+! It is not until n = 23, that a value exceeds one-million:
+! 23C10 = 1144066.
-! How many values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?
+! How many values of nCr, for 1 ≤ n ≤ 100, are greater than
+! one-million?
! SOLUTION
! Copyright (c) 2009 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: arrays io.encodings.ascii io.files kernel math.order poker
- project-euler.common sequences ;
+USING: arrays io.encodings.ascii io.files kernel math.order
+poker project-euler.common sequences ;
IN: project-euler.054
-! https://projecteuler.net/index.php?section=problems&id=54
+! https://projecteuler.net/problem=54
! DESCRIPTION
! -----------
-! In the card game poker, a hand consists of five cards and are ranked, from
-! lowest to highest, in the following way:
+! In the card game poker, a hand consists of five cards and are
+! ranked, from lowest to highest, in the following way:
! * High Card: Highest value card.
! * One Pair: Two cards of the same value.
! * Flush: All cards of the same suit.
! * Full House: Three of a kind and a pair.
! * Four of a Kind: Four cards of the same value.
-! * Straight Flush: All cards are consecutive values of same suit.
+! * Straight Flush: All cards are consecutive values of same
+! suit.
! * Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.
! The cards are valued in the order:
! 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.
-! If two players have the same ranked hands then the rank made up of the
-! highest value wins; for example, a pair of eights beats a pair of fives (see
-! example 1 below). But if two ranks tie, for example, both players have a pair
-! of queens, then highest cards in each hand are compared (see example 4
-! below); if the highest cards tie then the next highest cards are compared,
-! and so on.
+! If two players have the same ranked hands then the rank made
+! up of the highest value wins; for example, a pair of eights
+! beats a pair of fives (see example 1 below). But if two ranks
+! tie, for example, both players have a pair of queens, then
+! highest cards in each hand are compared (see example 4 below);
+! if the highest cards tie then the next highest cards are
+! compared, and so on.
! Consider the following five hands dealt to two players:
! Full House Full House
! With Three Fours With Three Threes Player 1
-! The file, poker.txt, contains one-thousand random hands dealt to two players.
-! Each line of the file contains ten cards (separated by a single space): the
-! first five are Player 1's cards and the last five are Player 2's cards. You
-! can assume that all hands are valid (no invalid characters or repeated
-! cards), each player's hand is in no specific order, and in each hand there is
-! a clear winner.
+! The file, poker.txt, contains one-thousand random hands dealt
+! to two players. Each line of the file contains ten cards
+! (separated by a single space): the first five are Player 1's
+! cards and the last five are Player 2's cards. You can assume
+! that all hands are valid (no invalid characters or repeated
+! cards), each player's hand is in no specific order, and in
+! each hand there is a clear winner.
! How many hands does Player 1 win?
USING: kernel math project-euler.common sequences ;
IN: project-euler.055
-! https://projecteuler.net/index.php?section=problems&id=55
+! https://projecteuler.net/problem=55
! DESCRIPTION
! -----------
-! If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
+! If we take 47, reverse and add, 47 + 74 = 121, which is
+! palindromic.
! Not all numbers produce palindromes so quickly. For example,
! That is, 349 took three iterations to arrive at a palindrome.
-! Although no one has proved it yet, it is thought that some numbers, like 196,
-! never produce a palindrome. A number that never forms a palindrome through
-! the reverse and add process is called a Lychrel number. Due to the
-! theoretical nature of these numbers, and for the purpose of this problem, we
-! shall assume that a number is Lychrel until proven otherwise. In addition you
-! are given that for every number below ten-thousand, it will either (i) become a
-! palindrome in less than fifty iterations, or, (ii) no one, with all the
-! computing power that exists, has managed so far to map it to a palindrome. In
-! fact, 10677 is the first number to be shown to require over fifty iterations
-! before producing a palindrome: 4668731596684224866951378664 (53 iterations,
-! 28-digits).
-
-! Surprisingly, there are palindromic numbers that are themselves Lychrel
-! numbers; the first example is 4994.
+! Although no one has proved it yet, it is thought that some
+! numbers, like 196, never produce a palindrome. A number that
+! never forms a palindrome through the reverse and add process
+! is called a Lychrel number. Due to the theoretical nature of
+! these numbers, and for the purpose of this problem, we shall
+! assume that a number is Lychrel until proven otherwise. In
+! addition you are given that for every number below
+! ten-thousand, it will either (i) become a palindrome in less
+! than fifty iterations, or, (ii) no one, with all the computing
+! power that exists, has managed so far to map it to a
+! palindrome. In fact, 10677 is the first number to be shown to
+! require over fifty iterations before producing a palindrome:
+! 4668731596684224866951378664 (53 iterations, 28-digits).
+
+! Surprisingly, there are palindromic numbers that are
+! themselves Lychrel numbers; the first example is 4994.
! How many Lychrel numbers are there below ten-thousand?
-! NOTE: Wording was modified slightly on 24 April 2007 to emphasise the
-! theoretical nature of Lychrel numbers.
+! NOTE: Wording was modified slightly on 24 April 2007 to
+! emphasise the theoretical nature of Lychrel numbers.
! SOLUTION
sequences math.order ;
IN: project-euler.056
-! https://projecteuler.net/index.php?section=problems&id=56
+! https://projecteuler.net/problem=56
! DESCRIPTION
! -----------
-! A googol (10^100) is a massive number: one followed by one-hundred zeros;
-! 100^100 is almost unimaginably large: one followed by two-hundred zeros.
-! Despite their size, the sum of the digits in each number is only 1.
+! A googol (10^100) is a massive number: one followed by
+! one-hundred zeros; 100^100 is almost unimaginably large: one
+! followed by two-hundred zeros. Despite their size, the sum of
+! the digits in each number is only 1.
-! Considering natural numbers of the form, a^b, where a, b < 100, what is the
-! maximum digital sum?
+! Considering natural numbers of the form, a^b, where a, b <
+! 100, what is the maximum digital sum?
! SOLUTION
USING: kernel math math.parser project-euler.common sequences ;
IN: project-euler.057
-! https://projecteuler.net/index.php?section=problems&id=57
+! https://projecteuler.net/problem=57
! DESCRIPTION
! -----------
-! It is possible to show that the square root of two can be expressed
-! as an infinite continued fraction.
+! It is possible to show that the square root of two can be
+! expressed as an infinite continued fraction.
! √ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
! 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
! 1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
-! The next three expansions are 99/70, 239/169, and 577/408, but the
-! eighth expansion, 1393/985, is the first example where the number of
-! digits in the numerator exceeds the number of digits in the
-! denominator.
+! The next three expansions are 99/70, 239/169, and 577/408, but
+! the eighth expansion, 1393/985, is the first example where the
+! number of digits in the numerator exceeds the number of digits
+! in the denominator.
-! In the first one-thousand expansions, how many fractions contain a
-! numerator with more digits than denominator?
+! In the first one-thousand expansions, how many fractions
+! contain a numerator with more digits than denominator?
! SOLUTION
! --------
sequences ;
IN: project-euler.058
-! https://projecteuler.net/index.php?section=problems&id=58
+! https://projecteuler.net/problem=58
! DESCRIPTION
! -----------
-! Starting with 1 and solveling anticlockwise in the following way, a square
-! solve with side length 7 is formed.
+! Starting with 1 and solveling anticlockwise in the following
+! way, a square solve with side length 7 is formed.
! 37 36 35 34 33 32 31
! 38 17 16 15 14 13 30
! 42 21 22 23 24 25 26
! 43 44 45 46 47 48 49
-! It is interesting to note that the odd squares lie along the bottom right
-! diagonal, but what is more interesting is that 8 out of the 13 numbers lying
-! along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.
+! It is interesting to note that the odd squares lie along the
+! bottom right diagonal, but what is more interesting is that 8
+! out of the 13 numbers lying along both diagonals are prime;
+! that is, a ratio of 8/13 ≈ 62%.
-! If one complete new layer is wrapped around the solve above, a square solve
-! with side length 9 will be formed. If this process is continued, what is the
-! side length of the square solve for which the ratio of primes along both
-! diagonals first falls below 10%?
+! If one complete new layer is wrapped around the solve above, a
+! square solve with side length 9 will be formed. If this
+! process is continued, what is the side length of the square
+! solve for which the ratio of primes along both diagonals first
+! falls below 10%?
! SOLUTION
sequences sequences.private sets sorting splitting ;
IN: project-euler.059
-! https://projecteuler.net/index.php?section=problems&id=59
+! https://projecteuler.net/problem=59
! DESCRIPTION
! -----------
-! Each character on a computer is assigned a unique code and the preferred
-! standard is ASCII (American Standard Code for Information Interchange). For
-! example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.
-
-! A modern encryption method is to take a text file, convert the bytes to
-! ASCII, then XOR each byte with a given value, taken from a secret key. The
-! advantage with the XOR function is that using the same encryption key on the
-! cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107
-! XOR 42 = 65.
-
-! For unbreakable encryption, the key is the same length as the plain text
-! message, and the key is made up of random bytes. The user would keep the
-! encrypted message and the encryption key in different locations, and without
-! both "halves", it is impossible to decrypt the message.
-
-! Unfortunately, this method is impractical for most users, so the modified
-! method is to use a password as a key. If the password is shorter than the
-! message, which is likely, the key is repeated cyclically throughout the
-! message. The balance for this method is using a sufficiently long password
-! key for security, but short enough to be memorable.
-
-! Your task has been made easy, as the encryption key consists of three lower
-! case characters. Using cipher1.txt (right click and 'Save Link/Target
-! As...'), a file containing the encrypted ASCII codes, and the knowledge that
-! the plain text must contain common English words, decrypt the message and
-! find the sum of the ASCII values in the original text.
+! Each character on a computer is assigned a unique code and the
+! preferred standard is ASCII (American Standard Code for
+! Information Interchange). For example, uppercase A = 65,
+! asterisk (*) = 42, and lowercase k = 107.
+
+! A modern encryption method is to take a text file, convert the
+! bytes to ASCII, then XOR each byte with a given value, taken
+! from a secret key. The advantage with the XOR function is that
+! using the same encryption key on the cipher text, restores the
+! plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 =
+! 65.
+
+! For unbreakable encryption, the key is the same length as the
+! plain text message, and the key is made up of random bytes.
+! The user would keep the encrypted message and the encryption
+! key in different locations, and without both "halves", it is
+! impossible to decrypt the message.
+
+! Unfortunately, this method is impractical for most users, so
+! the modified method is to use a password as a key. If the
+! password is shorter than the message, which is likely, the key
+! is repeated cyclically throughout the message. The balance for
+! this method is using a sufficiently long password key for
+! security, but short enough to be memorable.
+
+! Your task has been made easy, as the encryption key consists
+! of three lower case characters. Using cipher1.txt (right click
+! and 'Save Link/Target As...'), a file containing the encrypted
+! ASCII codes, and the knowledge that the plain text must
+! contain common English words, decrypt the message and find the
+! sum of the ASCII values in the original text.
! SOLUTION
! --------
-! Assume that the space character will be the most common, so XOR the input
-! text with a space character then group the text into three "columns" since
-! that's how long our key is. Then do frequency analysis on each column to
-! find out what the most likely candidate is for the key.
+! Assume that the space character will be the most common, so
+! XOR the input text with a space character then group the text
+! into three "columns" since that's how long our key is. Then
+! do frequency analysis on each column to find out what the most
+! likely candidate is for the key.
-! NOTE: This technique would probably not work well in all cases, but luckily
-! it did for this particular problem.
+! NOTE: This technique would probably not work well in all
+! cases, but luckily it did for this particular problem.
<PRIVATE
-! Copyright (C) 2018 John Benediktsson
+! Copyright (C) 2018 John Benediktsson.
! See https://factorcode.org/license.txt for BSD license
-
USING: backtrack backtrack.private combinators.short-circuit
kernel math math.functions math.primes
project-euler.common sequences ;
-
IN: project-euler.060
! https://projecteuler.net/problem=60
-! Copyright (C) 2023 Giftpflanze
+! Copyright (C) 2023 Giftpflanze.
! See https://factorcode.org/license.txt for BSD license
-
USING: arrays assocs assocs.extras grouping kernel math
project-euler.common ranges sequences sequences.extras ;
-
IN: project-euler.061
! https://projecteuler.net/problem=61
--- /dev/null
+Giftpflanze
project-euler.common sequences sorting ;
IN: project-euler.062
-! https://projecteuler.net/index.php?section=problems&id=062
+! https://projecteuler.net/problem=62
! DESCRIPTION
! -----------
! Copyright (c) 2009 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math math.functions ranges project-euler.common sequences ;
+USING: kernel math math.functions ranges project-euler.common
+sequences ;
IN: project-euler.063
-! https://projecteuler.net/index.php?section=problems&id=63
+! https://projecteuler.net/problem=63
! DESCRIPTION
! -----------
-! The 5-digit number, 16807 = 7^5, is also a fifth power. Similarly, the
-! 9-digit number, 134217728 = 8^9, is a ninth power.
+! The 5-digit number, 16807 = 7^5, is also a fifth power.
+! Similarly, the 9-digit number, 134217728 = 8^9, is a ninth
+! power.
-! How many n-digit positive integers exist which are also an nth power?
+! How many n-digit positive integers exist which are also an nth
+! power?
! SOLUTION
! --------
-! Only have to check from 1 to 9 because 10^n already has too many digits.
-! In general, x^n has n digits when:
+! Only have to check from 1 to 9 because 10^n already has too
+! many digits. In general, x^n has n digits when:
! 10^(n-1) <= x^n < 10^n
-! ...take the left side of that equation, solve for n to see where they meet:
+! ...take the left side of that equation, solve for n to see
+! where they meet:
! n = log(10) / [ log(10) - log(x) ]
-! Round down since we already know that particular value of n is no good.
+! Round down since we already know that particular value of n is
+! no good.
: euler063 ( -- answer )
9 [1..b] [ log [ 10 log dup ] dip - /i ] map-sum ;
--- /dev/null
+! Copyright (C) 2023 Giftpflanze.
+! See https://factorcode.org/license.txt for BSD license.
+USING: tools.test project-euler.064 ;
+IN: project-euler.064.tests
+
+{ 1322 } [ euler064b ] unit-test
+! Copyright (C) 2009 Kye W. Shi.
+! See https://factorcode.org/license.txt for BSD license.
USING: accessors classes.tuple kernel math math.functions
project-euler.common ranges sequences ;
IN: project-euler.064
-! http://projecteuler.net/index.php?section=problems&id=64
+! http://projecteuler.net/problem=64
! DESCRIPTION
! -----------
--- /dev/null
+Kye W. Shi
! Copyright (c) 2009 Guillaume Nargeot.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math lists lists.lazy project-euler.common sequences ;
+USING: kernel math lists lists.lazy project-euler.common
+sequences ;
IN: project-euler.065
-! https://projecteuler.net/index.php?section=problems&id=065
+! https://projecteuler.net/problem=65
! DESCRIPTION
! -----------
-! The square root of 2 can be written as an infinite continued fraction.
+! The square root of 2 can be written as an infinite continued
+! fraction.
! 1
! √2 = 1 + -------------------------
! 2 + -------------
! 2 + ...
-! The infinite continued fraction can be written, √2 = [1;(2)], (2) indicates
-! that 2 repeats ad infinitum. In a similar way, √23 = [4;(1,3,1,8)].
+! The infinite continued fraction can be written, √2 = [1;(2)],
+! (2) indicates that 2 repeats ad infinitum. In a similar way,
+! √23 = [4;(1,3,1,8)].
-! It turns out that the sequence of partial values of continued fractions for
-! square roots provide the best rational approximations. Let us consider the
-! convergents for √2.
+! It turns out that the sequence of partial values of continued
+! fractions for square roots provide the best rational
+! approximations. Let us consider the convergents for √2.
! 1 3 1 7 1 17 1 41
! 1 + - = - ; 1 + ----- = - ; 1 + --------- = -- ; 1 + ------------- = --
! 2 + -
! 2
-! Hence the sequence of the first ten convergents for √2 are:
-! 1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...
+! Hence the sequence of the first ten convergents for √2 are: 1,
+! 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985,
+! 3363/2378, ...
-! What is most surprising is that the important mathematical constant,
-! e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].
+! What is most surprising is that the important mathematical
+! constant, e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].
! The first ten terms in the sequence of convergents for e are:
-! 2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...
+! 2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465,
+! 1457/536, ...
-! The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.
+! The sum of digits in the numerator of the 10th convergent is
+! 1+4+5+7=17.
-! Find the sum of digits in the numerator of the 100th convergent of the
-! continued fraction for e.
+! Find the sum of digits in the numerator of the 100th
+! convergent of the continued fraction for e.
! SOLUTION
io.encodings.ascii sequences splitting ;
IN: project-euler.067
-! https://projecteuler.net/index.php?section=problems&id=67
+! https://projecteuler.net/problem=67
! DESCRIPTION
! -----------
-! By starting at the top of the triangle below and moving to adjacent numbers
-! on the row below, the maximum total from top to bottom is 23.
+! By starting at the top of the triangle below and moving to
+! adjacent numbers on the row below, the maximum total from top
+! to bottom is 23.
! 3
! 7 5
! That is, 3 + 7 + 4 + 9 = 23.
-! Find the maximum total from top to bottom in triangle.txt (right click and
-! 'Save Link/Target As...'), a 15K text file containing a triangle with
-! one-hundred rows.
+! Find the maximum total from top to bottom in triangle.txt
+! (right click and 'Save Link/Target As...'), a 15K text file
+! containing a triangle with one-hundred rows.
-! NOTE: This is a much more difficult version of Problem 18. It is not possible
-! to try every route to solve this problem, as there are 2^99 altogether! If you
-! could check one trillion (10^12) routes every second it would take over twenty
-! billion years to check them all. There is an efficient algorithm to solve it. ;o)
+! NOTE: This is a much more difficult version of Problem 18. It
+! is not possible to try every route to solve this problem, as
+! there are 2^99 altogether! If you could check one trillion
+! (10^12) routes every second it would take over twenty billion
+! years to check them all. There is an efficient algorithm to
+! solve it. ;o)
! SOLUTION
! --------
-! Propagate from bottom to top the longest cumulative path as is done in
-! problem 18.
+! Propagate from bottom to top the longest cumulative path as is
+! done in problem 18.
<PRIVATE
ranges project-euler.common sequences sequences.extras ;
IN: project-euler.069
-! https://projecteuler.net/index.php?section=problems&id=69
+! https://projecteuler.net/problem=69
! DESCRIPTION
! -----------
-! Euler's Totient function, φ(n) [sometimes called the phi function], is used
-! to determine the number of numbers less than n which are relatively prime to
-! n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and
-! relatively prime to nine, φ(9)=6.
+! Euler's Totient function, φ(n) [sometimes called the phi
+! function], is used to determine the number of numbers less
+! than n which are relatively prime to n. For example, as 1, 2,
+! 4, 5, 7, and 8, are all less than nine and relatively prime to
+! nine, φ(9)=6.
! +----+------------------+------+-----------+
! | n | Relatively Prime | φ(n) | n / φ(n) |
! | 10 | 1,3,7,9 | 4 | 2.5 |
! +----+------------------+------+-----------+
-! It can be seen that n = 6 produces a maximum n / φ(n) for n ≤ 10.
+! It can be seen that n = 6 produces a maximum n / φ(n) for n ≤
+! 10.
-! Find the value of n ≤ 1,000,000 for which n / φ(n) is a maximum.
+! Find the value of n ≤ 1,000,000 for which n / φ(n) is a
+! maximum.
! SOLUTION
-! Copyright (c) 2010 Aaron Schaefer. All rights reserved.
-! The contents of this file are licensed under the Simplified BSD License
-! A copy of the license is available at https://factorcode.org/license.txt
-USING: arrays combinators.short-circuit kernel math math.combinatorics
-math.functions math.primes project-euler.common sequences
-sequences.extras ;
+! Copyright (c) 2010 Aaron Schaefer.
+! See https://factorcode.org/license.txt for BSD license.
+USING: arrays combinators.short-circuit kernel math
+math.combinatorics math.functions math.primes
+project-euler.common sequences sequences.extras ;
FROM: project-euler.common => permutations? ;
IN: project-euler.070
-! https://projecteuler.net/index.php?section=problems&id=70
+! https://projecteuler.net/problem=70
! DESCRIPTION
! -----------
-! Euler's Totient function, φ(n) [sometimes called the phi function], is used
-! to determine the number of positive numbers less than or equal to n which are
-! relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less
-! than nine and relatively prime to nine, φ(9)=6. The number 1 is considered to
-! be relatively prime to every positive number, so φ(1)=1.
+! Euler's Totient function, φ(n) [sometimes called the phi
+! function], is used to determine the number of positive numbers
+! less than or equal to n which are relatively prime to n. For
+! example, as 1, 2, 4, 5, 7, and 8, are all less than nine and
+! relatively prime to nine, φ(9)=6. The number 1 is considered
+! to be relatively prime to every positive number, so φ(1)=1.
-! Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation
-! of 79180.
+! Interestingly, φ(87109)=79180, and it can be seen that 87109
+! is a permutation of 79180.
-! Find the value of n, 1 < n < 10^(7), for which φ(n) is a permutation of n and
-! the ratio n/φ(n) produces a minimum.
+! Find the value of n, 1 < n < 10^(7), for which φ(n) is a
+! permutation of n and the ratio n/φ(n) produces a minimum.
! SOLUTION
! --------
-! For n/φ(n) to be minimised, φ(n) must be as close to n as possible; that is,
-! we want to maximize φ(n). The minimal solution for n/φ(n) would be if n was
-! prime giving n/(n-1) but since n-1 never is a permutation of n it cannot be
-! prime.
+! For n/φ(n) to be minimised, φ(n) must be as close to n as
+! possible; that is, we want to maximize φ(n). The minimal
+! solution for n/φ(n) would be if n was prime giving n/(n-1) but
+! since n-1 never is a permutation of n it cannot be prime.
-! The next best thing would be if n only consisted of 2 prime factors close to
-! (in this case) sqrt(10000000). Hence n = p1*p2 and we only need to search
-! through a list of known prime pairs. In addition:
+! The next best thing would be if n only consisted of 2 prime
+! factors close to (in this case) sqrt(10000000). Hence n =
+! p1*p2 and we only need to search through a list of known prime
+! pairs. In addition:
! φ(p1*p2) = p1*p2*(1-1/p1)(1-1/p2) = (p1-1)(p2-1)
USING: kernel math project-euler.common sequences ;
IN: project-euler.071
-! https://projecteuler.net/index.php?section=problems&id=71
+! https://projecteuler.net/problem=71
! DESCRIPTION
! -----------
-! Consider the fraction, n/d, where n and d are positive integers. If n<d and
-! HCF(n,d) = 1, it is called a reduced proper fraction.
+! Consider the fraction, n/d, where n and d are positive
+! integers. If n<d and HCF(n,d) = 1, it is called a reduced
+! proper fraction.
-! If we list the set of reduced proper fractions for d <= 8 in ascending order of
-! size, we get:
+! If we list the set of reduced proper fractions for d <= 8 in
+! ascending order of size, we get:
! 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8,
! 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
-! It can be seen that 2/5 is the fraction immediately to the left of 3/7.
-
-! By listing the set of reduced proper fractions for d <= 1,000,000 in
-! ascending order of size, find the numerator of the fraction immediately to the
+! It can be seen that 2/5 is the fraction immediately to the
! left of 3/7.
+! By listing the set of reduced proper fractions for d <=
+! 1,000,000 in ascending order of size, find the numerator of
+! the fraction immediately to the left of 3/7.
+
! SOLUTION
! --------
-! Use the properties of a Farey sequence by setting an upper bound of 3/7 and
-! then taking the mediant of that fraction and the one to its immediate left
-! repeatedly until the denominator is as close to 1000000 as possible without
-! going over.
+! Use the properties of a Farey sequence by setting an upper
+! bound of 3/7 and then taking the mediant of that fraction and
+! the one to its immediate left repeatedly until the denominator
+! is as close to 1000000 as possible without going over.
: euler071 ( -- answer )
2/5 [ dup denominator 1000000 <= ] [ 3/7 mediant dup ] produce
! Copyright (c) 2009 Guillaume Nargeot.
! See https://factorcode.org/license.txt for BSD license.
-USING: math.primes.factors project-euler.common ranges sequences ;
+USING: math.primes.factors project-euler.common ranges sequences
+;
IN: project-euler.072
-! https://projecteuler.net/index.php?section=problems&id=072
+! https://projecteuler.net/problem=72
! DESCRIPTION
! -----------
-! Consider the fraction, n/d, where n and d are positive integers.
-! If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
+! Consider the fraction, n/d, where n and d are positive
+! integers. If n<d and HCF(n,d)=1, it is called a reduced proper
+! fraction.
-! If we list the set of reduced proper fractions for d ≤ 8 in ascending order
-! of size, we get:
+! If we list the set of reduced proper fractions for d ≤ 8 in
+! ascending order of size, we get:
-! 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3,
-! 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
+! 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7,
+! 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
! It can be seen that there are 21 elements in this set.
-! How many elements would be contained in the set of reduced proper fractions
-! for d ≤ 1,000,000?
+! How many elements would be contained in the set of reduced
+! proper fractions for d ≤ 1,000,000?
! SOLUTION
USING: kernel math project-euler.common ;
IN: project-euler.073
-! https://projecteuler.net/index.php?section=problems&id=73
+! https://projecteuler.net/problem=73
! DESCRIPTION
! -----------
-! Consider the fraction, n/d, where n and d are positive integers. If n<d and
-! HCF(n,d) = 1, it is called a reduced proper fraction.
+! Consider the fraction, n/d, where n and d are positive
+! integers. If n<d and HCF(n,d) = 1, it is called a reduced
+! proper fraction.
-! If we list the set of reduced proper fractions for d <= 8 in ascending order of
-! size, we get:
+! If we list the set of reduced proper fractions for d <= 8 in
+! ascending order of size, we get:
-! 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8,
-! 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
+! 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2,
+! 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
! It can be seen that there are 3 fractions between 1/3 and 1/2.
-! How many fractions lie between 1/3 and 1/2 in the sorted set of reduced
-! proper fractions for d <= 10,000?
+! How many fractions lie between 1/3 and 1/2 in the sorted set
+! of reduced proper fractions for d <= 10,000?
! SOLUTION
! --------
-! Use the properties of a Farey sequence and mediants to recursively generate
-! the next fraction until the denominator is as close to 1000000 as possible
-! without going over.
+! Use the properties of a Farey sequence and mediants to
+! recursively generate the next fraction until the denominator
+! is as close to 1000000 as possible without going over.
<PRIVATE
sequences sets ;
IN: project-euler.074
-! https://projecteuler.net/index.php?section=problems&id=074
+! https://projecteuler.net/problem=74
! DESCRIPTION
! -----------
-! The number 145 is well known for the property that the sum of the factorial
-! of its digits is equal to 145:
+! The number 145 is well known for the property that the sum of
+! the factorial of its digits is equal to 145:
! 1! + 4! + 5! = 1 + 24 + 120 = 145
-! Perhaps less well known is 169, in that it produces the longest chain of
-! numbers that link back to 169; it turns out that there are only three such
-! loops that exist:
+! Perhaps less well known is 169, in that it produces the
+! longest chain of numbers that link back to 169; it turns out
+! that there are only three such loops that exist:
! 169 → 363601 → 1454 → 169
! 871 → 45361 → 871
! 872 → 45362 → 872
-! It is not difficult to prove that EVERY starting number will eventually get
-! stuck in a loop. For example,
+! It is not difficult to prove that EVERY starting number will
+! eventually get stuck in a loop. For example,
! 69 → 363600 → 1454 → 169 → 363601 (→ 1454)
! 78 → 45360 → 871 → 45361 (→ 871)
! 540 → 145 (→ 145)
-! Starting with 69 produces a chain of five non-repeating terms, but the
-! longest non-repeating chain with a starting number below one million is sixty
-! terms.
+! Starting with 69 produces a chain of five non-repeating terms,
+! but the longest non-repeating chain with a starting number
+! below one million is sixty terms.
-! How many chains, with a starting number below one million, contain exactly
-! sixty non-repeating terms?
+! How many chains, with a starting number below one million,
+! contain exactly sixty non-repeating terms?
! SOLUTION
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
-USING: arrays kernel math ranges
- namespaces project-euler.common sequences ;
+USING: arrays kernel math ranges namespaces project-euler.common
+sequences ;
IN: project-euler.075
-! https://projecteuler.net/index.php?section=problems&id=75
+! https://projecteuler.net/problem=75
! DESCRIPTION
! -----------
-! It turns out that 12 cm is the smallest length of wire can be bent to form a
-! right angle triangle in exactly one way, but there are many more examples.
+! It turns out that 12 cm is the smallest length of wire can be
+! bent to form a right angle triangle in exactly one way, but
+! there are many more examples.
! 12 cm: (3,4,5)
! 24 cm: (6,8,10)
! 40 cm: (8,15,17)
! 48 cm: (12,16,20)
-! In contrast, some lengths of wire, like 20 cm, cannot be bent to form a right
-! angle triangle, and other lengths allow more than one solution to be found;
-! for example, using 120 cm it is possible to form exactly three different
-! right angle triangles.
+! In contrast, some lengths of wire, like 20 cm, cannot be bent
+! to form a right angle triangle, and other lengths allow more
+! than one solution to be found; for example, using 120 cm it is
+! possible to form exactly three different right angle
+! triangles.
! 120 cm: (30,40,50), (20,48,52), (24,45,51)
-! Given that L is the length of the wire, for how many values of L ≤ 2,000,000
-! can exactly one right angle triangle be formed?
+! Given that L is the length of the wire, for how many values of
+! L ≤ 2,000,000 can exactly one right angle triangle be formed?
! SOLUTION
! --------
-! Algorithm adapted from https://mathworld.wolfram.com/PythagoreanTriple.html
+! Algorithm adapted from
+! https://mathworld.wolfram.com/PythagoreanTriple.html
! Identical implementation as problem #39
-! Basically, this makes an array of 2000000 zeros, recursively creates
-! primitive triples using the three transforms and then increments the array at
-! index [a+b+c] by one for each triple's sum AND its multiples under 2000000
-! (to account for non-primitive triples). The answer is just the total number
-! of indexes that are equal to one.
+! Basically, this makes an array of 2000000 zeros, recursively
+! creates primitive triples using the three transforms and then
+! increments the array at index [a+b+c] by one for each triple's
+! sum AND its multiples under 2000000 (to account for
+! non-primitive triples). The answer is just the total number of
+! indexes that are equal to one.
SYMBOL: p-count
! Copyright (c) 2008 Eric Mertens.
! See https://factorcode.org/license.txt for BSD license.
-USING: arrays assocs kernel math math.order ranges sequences project-euler.common ;
+USING: arrays assocs kernel math math.order ranges sequences
+project-euler.common ;
IN: project-euler.076
-! https://projecteuler.net/index.php?section=problems&id=76
+! https://projecteuler.net/problem=76
! DESCRIPTION
! -----------
! Copyright (c) 2008 Aaron Schaefer.
! See https://factorcode.org/license.txt for BSD license.
USING: assocs io.encodings.ascii io.files kernel make math
- math.parser sequences sets project-euler.common ;
+math.parser sequences sets project-euler.common ;
IN: project-euler.079
-! https://projecteuler.net/index.php?section=problems&id=79
+! https://projecteuler.net/problem=79
! DESCRIPTION
! -----------
-! A common security method used for online banking is to ask the user for three
-! random characters from a passcode. For example, if the passcode was 531278,
-! they may asked for the 2nd, 3rd, and 5th characters; the expected reply would
-! be: 317.
+! A common security method used for online banking is to ask the
+! user for three random characters from a passcode. For example,
+! if the passcode was 531278, they may asked for the 2nd, 3rd,
+! and 5th characters; the expected reply would be: 317.
-! The text file, keylog.txt, contains fifty successful login attempts.
+! The text file, keylog.txt, contains fifty successful login
+! attempts.
-! Given that the three characters are always asked for in order, analyse the
-! file so as to determine the shortest possible secret passcode of unknown
-! length.
+! Given that the three characters are always asked for in order,
+! analyse the file so as to determine the shortest possible
+! secret passcode of unknown length.
! SOLUTION
math.parser project-euler.common sequences splitting ;
IN: project-euler.081
-! https://projecteuler.net/index.php?section=problems&id=081
+! https://projecteuler.net/problem=81
! DESCRIPTION
! -----------
sequences ;
IN: project-euler.085
-! https://projecteuler.net/index.php?section=problems&id=85
+! https://projecteuler.net/problem=85
! DESCRIPTION
! -----------
-! By counting carefully it can be seen that a rectangular grid measuring
-! 3 by 2 contains eighteen rectangles.
+! By counting carefully it can be seen that a rectangular grid
+! measuring 3 by 2 contains eighteen rectangles.
-! Although there exists no rectangular grid that contains exactly two million
-! rectangles, find the area of the grid with the nearest solution.
+! Although there exists no rectangular grid that contains
+! exactly two million rectangles, find the area of the grid with
+! the nearest solution.
! SOLUTION
! --------
-! A grid measuring x by y contains x * (x + 1) * y * (x + 1) / 4 rectangles.
+! A grid measuring x by y contains x * (x + 1) * y * (x + 1) / 4
+! rectangles.
<PRIVATE
--- /dev/null
+! Copyright (C) 2023 Giftpflanze.
+! See https://factorcode.org/license.txt for BSD license.
+USING: tools.test project-euler.087 ;
+IN: project-euler.087.tests
+
+{ 1097343 } [ euler087 ] unit-test
-USING: math math.functions math.primes
-project-euler.common sequences sets ;
-
+! Copyright (C) 2009 Kye W. Shi.
+! See https://factorcode.org/license.txt for BSD license.
+USING: math math.functions math.primes project-euler.common
+sequences sets ;
IN: project-euler.087
-! https://projecteuler.net/index.php?section=problems&id=87
+! https://projecteuler.net/problem=87
! DESCRIPTION
! -----------
--- /dev/null
+Kye W. Shi
project-euler.common roman sequences ;
IN: project-euler.089
-! https://projecteuler.net/index.php?section=problems&id=089
+! https://projecteuler.net/problem=89
! DESCRIPTION
! -----------
-! The rules for writing Roman numerals allow for many ways of writing
-! each number (see FAQ: Roman Numerals). However, there is always a
-! "best" way of writing a particular number.
+! The rules for writing Roman numerals allow for many ways of
+! writing each number (see FAQ: Roman Numerals). However, there
+! is always a "best" way of writing a particular number.
-! For example, the following represent all of the legitimate ways of
-! writing the number sixteen:
+! For example, the following represent all of the legitimate
+! ways of writing the number sixteen:
! IIIIIIIIIIIIIIII
! VIIIIIIIIIII
! VVVI
! XVI
-! The last example being considered the most efficient, as it uses
-! the least number of numerals.
+! The last example being considered the most efficient, as it
+! uses the least number of numerals.
-! The 11K text file, roman.txt (right click and 'Save Link/Target As...'),
-! contains one thousand numbers written in valid, but not necessarily
-! minimal, Roman numerals; that is, they are arranged in descending units
-! and obey the subtractive pair rule (see FAQ for the definitive rules
-! for this problem).
+! The 11K text file, roman.txt (right click and 'Save
+! Link/Target As...'), contains one thousand numbers written in
+! valid, but not necessarily minimal, Roman numerals; that is,
+! they are arranged in descending units and obey the subtractive
+! pair rule (see FAQ for the definitive rules for this problem).
-! Find the number of characters saved by writing each of these in their minimal form.
+! Find the number of characters saved by writing each of these
+! in their minimal form.
! SOLUTION
! --------
USING: kernel math ranges project-euler.common sequences ;
IN: project-euler.092
-! https://projecteuler.net/index.php?section=problems&id=92
+! https://projecteuler.net/problem=92
! DESCRIPTION
! -----------
-! A number chain is created by continuously adding the square of the digits in
-! a number to form a new number until it has been seen before.
+! A number chain is created by continuously adding the square of
+! the digits in a number to form a new number until it has been
+! seen before.
! For example,
! 44 -> 32 -> 13 -> 10 -> 1 -> 1
! 85 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89
-! Therefore any chain that arrives at 1 or 89 will become stuck in an endless
-! loop. What is most amazing is that EVERY starting number will eventually
-! arrive at 1 or 89.
+! Therefore any chain that arrives at 1 or 89 will become stuck
+! in an endless loop. What is most amazing is that EVERY
+! starting number will eventually arrive at 1 or 89.
! How many starting numbers below ten million will arrive at 89?
USING: math math.functions project-euler.common ;
IN: project-euler.097
-! https://projecteuler.net/index.php?section=problems&id=97
+! https://projecteuler.net/problem=97
! DESCRIPTION
! -----------
-! The first known prime found to exceed one million digits was discovered in
-! 1999, and is a Mersenne prime of the form 2^6972593 − 1; it contains exactly
-! 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p − 1,
-! have been found which contain more digits.
+! The first known prime found to exceed one million digits was
+! discovered in 1999, and is a Mersenne prime of the form
+! 2^6972593 − 1; it contains exactly 2,098,960 digits.
+! Subsequently other Mersenne primes, of the form 2p − 1, have
+! been found which contain more digits.
-! However, in 2004 there was found a massive non-Mersenne prime which contains
-! 2,357,207 digits: 28433 * 2^7830457 + 1.
+! However, in 2004 there was found a massive non-Mersenne prime
+! which contains 2,357,207 digits: 28433 * 2^7830457 + 1.
! Find the last ten digits of this prime number.
sequences.extras splitting ;
IN: project-euler.099
-! https://projecteuler.net/index.php?section=problems&id=99
+! https://projecteuler.net/problem=99
! DESCRIPTION
! -----------
-! Comparing two numbers written in index form like 2^11 and 3^7 is not difficult,
-! as any calculator would confirm that 2^11 = 2048 < 3^7 = 2187.
+! Comparing two numbers written in index form like 2^11 and 3^7
+! is not difficult, as any calculator would confirm that 2^11 =
+! 2048 < 3^7 = 2187.
-! However, confirming that 632382^518061 519432^525806 would be much more
-! difficult, as both numbers contain over three million digits.
+! However, confirming that 632382^518061 519432^525806 would be
+! much more difficult, as both numbers contain over three
+! million digits.
-! Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text
-! file containing one thousand lines with a base/exponent pair on each line,
-! determine which line number has the greatest numerical value.
+! Using base_exp.txt (right click and 'Save Link/Target As...'),
+! a 22K text file containing one thousand lines with a
+! base/exponent pair on each line, determine which line number
+! has the greatest numerical value.
-! NOTE: The first two lines in the file represent the numbers in the example
-! given above.
+! NOTE: The first two lines in the file represent the numbers in
+! the example given above.
! SOLUTION
! --------
-! Use logarithms to make the calculations necessary more manageable.
+! Use logarithms to make the calculations necessary more
+! manageable.
<PRIVATE
USING: kernel math math.functions project-euler.common ;
IN: project-euler.100
-! https://projecteuler.net/index.php?section=problems&id=100
+! https://projecteuler.net/problem=100
-! DESCRIPTION ! -----------
+! DESCRIPTION
+! -----------
-! If a box contains twenty-one colored discs, composed of fifteen blue discs
-! and six red discs, and two discs were taken at random, it can be seen that
-! the probability of taking two blue discs, P(BB) = (15/21)*(14/20) = 1/2.
+! If a box contains twenty-one colored discs, composed of
+! fifteen blue discs and six red discs, and two discs were taken
+! at random, it can be seen that the probability of taking two
+! blue discs, P(BB) = (15/21)*(14/20) = 1/2.
-! The next such arrangement, for which there is exactly 50% chance of taking
-! two blue discs at random, is a box containing eighty-five blue discs and
-! thirty-five red discs.
+! The next such arrangement, for which there is exactly 50%
+! chance of taking two blue discs at random, is a box containing
+! eighty-five blue discs and thirty-five red discs.
-! By finding the first arrangement to contain over 10^12 = 1,000,000,000,000
-! discs in total, determine the number of blue discs that the box would contain.
+! By finding the first arrangement to contain over 10^12 =
+! 1,000,000,000,000 discs in total, determine the number of blue
+! discs that the box would contain.
! SOLUTION
math.parser sequences splitting project-euler.common ;
IN: project-euler.102
-! https://projecteuler.net/index.php?section=problems&id=102
+! https://projecteuler.net/problem=102
! DESCRIPTION
! -----------
-! Three distinct points are plotted at random on a Cartesian plane, for which
-! -1000 ≤ x, y ≤ 1000, such that a triangle is formed.
+! Three distinct points are plotted at random on a Cartesian
+! plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is
+! formed.
! Consider the following two triangles:
! A(-340,495), B(-153,-910), C(835,-947)
! X(-175,41), Y(-421,-714), Z(574,-645)
-! It can be verified that triangle ABC contains the origin, whereas triangle
-! XYZ does not.
+! It can be verified that triangle ABC contains the origin,
+! whereas triangle XYZ does not.
-! Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text
-! file containing the coordinates of one thousand "random" triangles, find the
-! number of triangles for which the interior contains the origin.
+! Using triangles.txt (right click and 'Save Link/Target
+! As...'), a 27K text file containing the coordinates of one
+! thousand "random" triangles, find the number of triangles for
+! which the interior contains the origin.
-! NOTE: The first two examples in the file represent the triangles in the
-! example given above.
+! NOTE: The first two examples in the file represent the
+! triangles in the example given above.
! SOLUTION
USING: kernel math project-euler.common sequences sorting ;
IN: project-euler.112
-! https://projecteuler.net/index.php?section=problems&id=112
+! https://projecteuler.net/problem=112
! DESCRIPTION
! -----------
-! Working from left-to-right if no digit is exceeded by the digit to its left
-! it is called an increasing number; for example, 134468.
+! Working from left-to-right if no digit is exceeded by the
+! digit to its left it is called an increasing number; for
+! example, 134468.
-! Similarly if no digit is exceeded by the digit to its right it is called a
-! decreasing number; for example, 66420.
+! Similarly if no digit is exceeded by the digit to its right it
+! is called a decreasing number; for example, 66420.
-! We shall call a positive integer that is neither increasing nor decreasing a
-! "bouncy" number; for example, 155349.
+! We shall call a positive integer that is neither increasing
+! nor decreasing a "bouncy" number; for example, 155349.
-! Clearly there cannot be any bouncy numbers below one-hundred, but just over
-! half of the numbers below one-thousand (525) are bouncy. In fact, the least
-! number for which the proportion of bouncy numbers first reaches 50% is 538.
+! Clearly there cannot be any bouncy numbers below one-hundred,
+! but just over half of the numbers below one-thousand (525) are
+! bouncy. In fact, the least number for which the proportion of
+! bouncy numbers first reaches 50% is 538.
-! Surprisingly, bouncy numbers become more and more common and by the time we
-! reach 21780 the proportion of bouncy numbers is equal to 90%.
+! Surprisingly, bouncy numbers become more and more common and
+! by the time we reach 21780 the proportion of bouncy numbers is
+! equal to 90%.
-! Find the least number for which the proportion of bouncy numbers is exactly
-! 99%.
+! Find the least number for which the proportion of bouncy
+! numbers is exactly 99%.
! SOLUTION
USING: kernel math ranges sequences project-euler.common ;
IN: project-euler.116
-! https://projecteuler.net/index.php?section=problems&id=116
+! https://projecteuler.net/problem=116
! DESCRIPTION
! -----------
-! A row of five black square tiles is to have a number of its tiles replaced
-! with colored oblong tiles chosen from red (length two), green (length
-! three), or blue (length four).
+! A row of five black square tiles is to have a number of its
+! tiles replaced with colored oblong tiles chosen from red
+! (length two), green (length three), or blue (length four).
-! If red tiles are chosen there are exactly seven ways this can be done.
-! If green tiles are chosen there are three ways.
-! And if blue tiles are chosen there are two ways.
+! If red tiles are chosen there are exactly seven ways this can
+! be done. If green tiles are chosen there are three ways. And
+! if blue tiles are chosen there are two ways.
-! Assuming that colors cannot be mixed there are 7 + 3 + 2 = 12 ways of
-! replacing the black tiles in a row measuring five units in length.
+! Assuming that colors cannot be mixed there are 7 + 3 + 2 = 12
+! ways of replacing the black tiles in a row measuring five
+! units in length.
-! How many different ways can the black tiles in a row measuring fifty units in
-! length be replaced if colors cannot be mixed and at least one colored tile
-! must be used?
+! How many different ways can the black tiles in a row measuring
+! fifty units in length be replaced if colors cannot be mixed
+! and at least one colored tile must be used?
! SOLUTION
! --------
-! This solution uses a simple dynamic programming approach using the
-! following recurence relation
+! This solution uses a simple dynamic programming approach using
+! the following recurence relation
! ways(n,_) = 0 | n < 0
! ways(0,_) = 1
USING: kernel math project-euler.common sequences ;
IN: project-euler.117
-! https://projecteuler.net/index.php?section=problems&id=117
+! https://projecteuler.net/problem=117
! DESCRIPTION
! -----------
-! Using a combination of black square tiles and oblong tiles chosen
-! from: red tiles measuring two units, green tiles measuring three
-! units, and blue tiles measuring four units, it is possible to tile a
-! row measuring five units in length in exactly fifteen different ways.
+! Using a combination of black square tiles and oblong tiles
+! chosen from: red tiles measuring two units, green tiles
+! measuring three units, and blue tiles measuring four units, it
+! is possible to tile a row measuring five units in length in
+! exactly fifteen different ways.
-! How many ways can a row measuring fifty units in length be tiled?
+! How many ways can a row measuring fifty units in length be
+! tiled?
! SOLUTION
! --------
-! This solution uses a simple dynamic programming approach using the
-! following recurence relation
+! This solution uses a simple dynamic programming approach using
+! the following recurence relation
! ways(i) = 1 | i <= 0
! ways(i) = ways(i-4) + ways(i-3) + ways(i-2) + ways(i-1)
! Copyright (c) 2009 Guillaume Nargeot.
! See https://factorcode.org/license.txt for BSD license.
-USING: arrays kernel math.primes.factors
-ranges project-euler.common sequences sorting ;
+USING: arrays kernel math.primes.factors ranges
+project-euler.common sequences sorting ;
IN: project-euler.124
-! https://projecteuler.net/index.php?section=problems&id=124
+! https://projecteuler.net/problem=124
! DESCRIPTION
! -----------
-! The radical of n, rad(n), is the product of distinct prime factors of n.
-! For example, 504 = 2^3 × 3^2 × 7, so rad(504) = 2 × 3 × 7 = 42.
+! The radical of n, rad(n), is the product of distinct prime
+! factors of n. For example, 504 = 2^3 × 3^2 × 7, so rad(504) =
+! 2 × 3 × 7 = 42.
-! If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n),
-! and sorting on n if the radical values are equal, we get:
+! If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on
+! rad(n), and sorting on n if the radical values are equal, we
+! get:
! Unsorted Sorted
! n rad(n) n rad(n) k
! 9 3 7 7 9
! 10 10 10 10 10
-! Let E(k) be the kth element in the sorted n column; for example,
-! E(4) = 8 and E(6) = 9.
+! Let E(k) be the kth element in the sorted n column; for
+! example, E(4) = 8 and E(6) = 9.
! If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).
math.functions math.primes.lists project-euler.common ;
IN: project-euler.134
-! https://projecteuler.net/index.php?section=problems&id=134
+! https://projecteuler.net/problem=134
! DESCRIPTION
! -----------
-! Consider the consecutive primes p1 = 19 and p2 = 23. It can be verified that
-! 1219 is the smallest number such that the last digits are formed by p1 whilst
-! also being divisible by p2.
+! Consider the consecutive primes p1 = 19 and p2 = 23. It can be
+! verified that 1219 is the smallest number such that the last
+! digits are formed by p1 whilst also being divisible by p2.
-! In fact, with the exception of p1 = 3 and p2 = 5, for every pair of
-! consecutive primes, p2 p1, there exist values of n for which the last digits
-! are formed by p1 and n is divisible by p2. Let S be the smallest of these
-! values of n.
+! In fact, with the exception of p1 = 3 and p2 = 5, for every
+! pair of consecutive primes, p2 p1, there exist values of n for
+! which the last digits are formed by p1 and n is divisible by
+! p2. Let S be the smallest of these values of n.
! Find S for every pair of consecutive primes with 5 p1 1000000.
<PRIVATE
-! Compute S for a given pair (p1, p2) -- that is the smallest positive
-! number such that X = p1 [npt] and X = 0 [p2] (npt being the smallest
-! power of 10 above p1)
+! Compute S for a given pair (p1, p2) -- that is the smallest
+! positive number such that X = p1 [npt] and X = 0 [p2] (npt
+! being the smallest power of 10 above p1)
: s ( p1 p2 -- s )
over 0 2array rot next-power-of-10 rot 2array chinese-remainder ;
! Copyright (c) 2008 Eric Mertens.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math math.functions sequences project-euler.common ;
+USING: kernel math math.functions sequences project-euler.common
+;
IN: project-euler.148
-! https://projecteuler.net/index.php?section=problems&id=148
+! https://projecteuler.net/problem=148
! DESCRIPTION
! -----------
-! We can easily verify that none of the entries in the first seven rows of
-! Pascal's triangle are divisible by 7:
+! We can easily verify that none of the entries in the first
+! seven rows of Pascal's triangle are divisible by 7:
! 1
! 1 1
! 1 5 10 10 5 1
! 1 6 15 20 15 6 1
-! However, if we check the first one hundred rows, we will find that only 2361
-! of the 5050 entries are not divisible by 7.
+! However, if we check the first one hundred rows, we will find
+! that only 2361 of the 5050 entries are not divisible by 7.
-! Find the number of entries which are not divisible by 7 in the first one
-! billion (10^9) rows of Pascal's triangle.
+! Find the number of entries which are not divisible by 7 in the
+! first one billion (10^9) rows of Pascal's triangle.
! SOLUTION
project-euler.common sequences sequences.private ;
IN: project-euler.150
-! https://projecteuler.net/index.php?section=problems&id=150
+! https://projecteuler.net/problem=150
! DESCRIPTION
! -----------
-! In a triangular array of positive and negative integers, we wish to find a
-! sub-triangle such that the sum of the numbers it contains is the smallest
-! possible.
+! In a triangular array of positive and negative integers, we
+! wish to find a sub-triangle such that the sum of the numbers
+! it contains is the smallest possible.
-! In the example below, it can be easily verified that the marked triangle
-! satisfies this condition having a sum of -42.
+! In the example below, it can be easily verified that the
+! marked triangle satisfies this condition having a sum of -42.
-! We wish to make such a triangular array with one thousand rows, so we
-! generate 500500 pseudo-random numbers sk in the range +/-2^19, using a type of
-! random number generator (known as a Linear Congruential Generator) as
-! follows:
+! We wish to make such a triangular array with one thousand
+! rows, so we generate 500500 pseudo-random numbers sk in the
+! range +/-2^19, using a type of random number generator (known
+! as a Linear Congruential Generator) as follows:
! ...
! Copyright (c) 2008 Eric Mertens.
! See https://factorcode.org/license.txt for BSD license.
-USING: assocs combinators kernel math math.order namespaces sequences project-euler.common ;
+USING: assocs combinators kernel math math.order namespaces
+sequences project-euler.common ;
IN: project-euler.151
-! https://projecteuler.net/index.php?section=problems&id=151
+! https://projecteuler.net/problem=151
! DESCRIPTION
! -----------
-! A printing shop runs 16 batches (jobs) every week and each batch requires a
-! sheet of special color-proofing paper of size A5.
+! A printing shop runs 16 batches (jobs) every week and each
+! batch requires a sheet of special color-proofing paper of size
+! A5.
-! Every Monday morning, the foreman opens a new envelope, containing a large
-! sheet of the special paper with size A1.
+! Every Monday morning, the foreman opens a new envelope,
+! containing a large sheet of the special paper with size A1.
-! He proceeds to cut it in half, thus getting two sheets of size A2. Then he
-! cuts one of them in half to get two sheets of size A3 and so on until he
-! obtains the A5-size sheet needed for the first batch of the week.
+! He proceeds to cut it in half, thus getting two sheets of size
+! A2. Then he cuts one of them in half to get two sheets of size
+! A3 and so on until he obtains the A5-size sheet needed for the
+! first batch of the week.
! All the unused sheets are placed back in the envelope.
-! At the beginning of each subsequent batch, he takes from the envelope one
-! sheet of paper at random. If it is of size A5, he uses it. If it is larger,
-! he repeats the 'cut-in-half' procedure until he has what he needs and any
-! remaining sheets are always placed back in the envelope.
+! At the beginning of each subsequent batch, he takes from the
+! envelope one sheet of paper at random. If it is of size A5, he
+! uses it. If it is larger, he repeats the 'cut-in-half'
+! procedure until he has what he needs and any remaining sheets
+! are always placed back in the envelope.
-! Excluding the first and last batch of the week, find the expected number of
-! times (during each week) that the foreman finds a single sheet of paper in
-! the envelope.
+! Excluding the first and last batch of the week, find the
+! expected number of times (during each week) that the foreman
+! finds a single sheet of paper in the envelope.
-! Give your answer rounded to six decimal places using the format x.xxxxxx .
+! Give your answer rounded to six decimal places using the
+! format x.xxxxxx .
! SOLUTION
! Copyright (c) 2008 Eric Mertens.
! See https://factorcode.org/license.txt for BSD license.
-USING: arrays assocs kernel math ranges sequences project-euler.common ;
+USING: arrays assocs kernel math ranges sequences
+project-euler.common ;
IN: project-euler.164
-! https://projecteuler.net/index.php?section=problems&id=164
+! https://projecteuler.net/problem=164
! DESCRIPTION
! -----------
-! How many 20 digit numbers n (without any leading zero) exist such
-! that no three consecutive digits of n have a sum greater than 9?
+! How many 20 digit numbers n (without any leading zero) exist
+! such that no three consecutive digits of n have a sum greater
+! than 9?
! SOLUTION
! Copyright (c) 2007 Samuel Tardieu.
! See https://factorcode.org/license.txt for BSD license.
+USING: combinators kernel math math.functions
+project-euler.common ;
IN: project-euler.169
-USING: combinators kernel math math.functions project-euler.common ;
-! https://projecteuler.net/index.php?section=problems&id=169
+! https://projecteuler.net/problem=169
! DESCRIPTION
! -----------
-! Define f(0) = 1 and f(n) to be the number of different ways n can be
-! expressed as a sum of integer powers of 2 using each power no more than
-! twice.
+! Define f(0) = 1 and f(n) to be the number of different ways n
+! can be expressed as a sum of integer powers of 2 using each
+! power no more than twice.
-! For example, f(10) = 5 since there are five different ways to express 10:
+! For example, f(10) = 5 since there are five different ways to
+! express 10:
! 1 + 1 + 8
! 1 + 1 + 4 + 4
! Copyright (c) 2007 Samuel Tardieu.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math math.functions ranges sequences project-euler.common ;
+USING: kernel math math.functions ranges sequences
+project-euler.common ;
IN: project-euler.173
-! https://projecteuler.net/index.php?section=problems&id=173
+! https://projecteuler.net/problem=173
! DESCRIPTION
! -----------
-! We shall define a square lamina to be a square outline with a square "hole"
-! so that the shape possesses vertical and horizontal symmetry. For example,
-! using exactly thirty-two square tiles we can form two different square
-! laminae: [see URL for figure]
+! We shall define a square lamina to be a square outline with a
+! square "hole" so that the shape possesses vertical and
+! horizontal symmetry. For example, using exactly thirty-two
+! square tiles we can form two different square laminae: [see
+! URL for figure]
-! With one-hundred tiles, and not necessarily using all of the tiles at one
-! time, it is possible to form forty-one different square laminae.
+! With one-hundred tiles, and not necessarily using all of the
+! tiles at one time, it is possible to form forty-one different
+! square laminae.
-! Using up to one million tiles how many different square laminae can be formed?
+! Using up to one million tiles how many different square
+! laminae can be formed?
! SOLUTION
sequences ;
IN: project-euler.175
-! https://projecteuler.net/index.php?section=problems&id=175
+! https://projecteuler.net/problem=175
! DESCRIPTION
! -----------
-! Define f(0) = 1 and f(n) to be the number of ways to write n as a sum of
-! powers of 2 where no power occurs more than twice.
+! Define f(0) = 1 and f(n) to be the number of ways to write n
+! as a sum of powers of 2 where no power occurs more than twice.
-! For example, f(10) = 5 since there are five different ways to express
-! 10: 10 = 8+2 = 8+1+1 = 4+4+2 = 4+2+2+1+1 = 4+4+1+1
+! For example, f(10) = 5 since there are five different ways to
+! express 10: 10 = 8+2 = 8+1+1 = 4+4+2 = 4+2+2+1+1 = 4+4+1+1
-! It can be shown that for every fraction p/q (p0, q0) there exists at least
-! one integer n such that f(n) / f(n-1) = p/q.
+! It can be shown that for every fraction p/q (p0, q0) there
+! exists at least one integer n such that f(n) / f(n-1) = p/q.
-! For instance, the smallest n for which f(n) / f(n-1) = 13/17 is 241. The
-! binary expansion of 241 is 11110001. Reading this binary number from the most
-! significant bit to the least significant bit there are 4 one's, 3 zeroes and
-! 1 one. We shall call the string 4,3,1 the Shortened Binary Expansion of 241.
+! For instance, the smallest n for which f(n) / f(n-1) = 13/17
+! is 241. The binary expansion of 241 is 11110001. Reading this
+! binary number from the most significant bit to the least
+! significant bit there are 4 one's, 3 zeroes and 1 one. We
+! shall call the string 4,3,1 the Shortened Binary Expansion of
+! 241.
-! Find the Shortened Binary Expansion of the smallest n for which
-! f(n) / f(n-1) = 123456789/987654321.
+! Find the Shortened Binary Expansion of the smallest n for
+! which f(n) / f(n-1) = 123456789/987654321.
-! Give your answer as comma separated integers, without any whitespaces.
+! Give your answer as comma separated integers, without any
+! whitespaces.
! SOLUTION
! Copyright (c) 2008 Eric Mertens.
! See https://factorcode.org/license.txt for BSD license.
-USING: circular disjoint-sets kernel math ranges sequences project-euler.common ;
+USING: circular disjoint-sets kernel math ranges sequences
+project-euler.common ;
IN: project-euler.186
-! https://projecteuler.net/index.php?section=problems&id=186
+! https://projecteuler.net/problem=186
! DESCRIPTION
! -----------
-! Here are the records from a busy telephone system with one million users:
+! Here are the records from a busy telephone system with one
+! million users:
! RecNr Caller Called
! 1 200007 100053
! 3 600863 701497
! ... ... ...
-! The telephone number of the caller and the called number in record n are
-! Caller(n) = S2n-1 and Called(n) = S2n where S1,2,3,... come from the "Lagged
-! Fibonacci Generator":
+! The telephone number of the caller and the called number in
+! record n are Caller(n) = S2n-1 and Called(n) = S2n where
+! S1,2,3,... come from the "Lagged Fibonacci Generator":
-! For 1 <= k <= 55, Sk = [100003 - 200003k + 300007k^3] (modulo 1000000)
+! For 1 <= k <= 55, Sk = [100003 - 200003k + 300007k^3] (modulo
+! 1000000)
! For 56 <= k, Sk = [Sk-24 + Sk-55] (modulo 1000000)
-! If Caller(n) = Called(n) then the user is assumed to have misdialled and the
-! call fails; otherwise the call is successful.
+! If Caller(n) = Called(n) then the user is assumed to have
+! misdialled and the call fails; otherwise the call is
+! successful.
-! From the start of the records, we say that any pair of users X and Y are
-! friends if X calls Y or vice-versa. Similarly, X is a friend of a friend of Z
-! if X is a friend of Y and Y is a friend of Z; and so on for longer chains.
+! From the start of the records, we say that any pair of users X
+! and Y are friends if X calls Y or vice-versa. Similarly, X is
+! a friend of a friend of Z if X is a friend of Y and Y is a
+! friend of Z; and so on for longer chains.
-! The Prime Minister's phone number is 524287. After how many successful calls,
-! not counting misdials, will 99% of the users (including the PM) be a friend,
-! or a friend of a friend etc., of the Prime Minister?
+! The Prime Minister's phone number is 524287. After how many
+! successful calls, not counting misdials, will 99% of the users
+! (including the PM) be a friend, or a friend of a friend etc.,
+! of the Prime Minister?
! SOLUTION
USING: kernel math math.functions project-euler.common ;
IN: project-euler.188
-! https://projecteuler.net/index.php?section=problems&id=188
+! https://projecteuler.net/problem=188
! DESCRIPTION
! -----------
-! The hyperexponentiation or tetration of a number a by a positive integer b,
-! denoted by a↑↑b or ^(b)a, is recursively defined by:
+! The hyperexponentiation or tetration of a number a by a
+! positive integer b, denoted by a↑↑b or ^(b)a, is recursively
+! defined by:
! a↑↑1 = a,
! a↑↑(k+1) = a^(a↑↑k).
! Copyright (c) 2008 Eric Mertens.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel sequences math math.functions ranges project-euler.common ;
+USING: kernel sequences math math.functions ranges
+project-euler.common ;
IN: project-euler.190
-! https://projecteuler.net/index.php?section=problems&id=190
+! https://projecteuler.net/problem=190
! DESCRIPTION
! -----------
-! Let Sm = (x1, x2, ... , xm) be the m-tuple of positive real numbers
-! with x1 + x2 + ... + xm = m for which Pm = x1 * x22 * ... * xmm is
-! maximized.
+! Let Sm = (x1, x2, ... , xm) be the m-tuple of positive real
+! numbers with x1 + x2 + ... + xm = m for which Pm = x1 * x22 *
+! ... * xmm is maximized.
-! For example, it can be verified that [P10] = 4112 ([ ] is the integer
-! part function).
+! For example, it can be verified that [P10] = 4112 ([ ] is the
+! integer part function).
! Find Σ[Pm] for 2 ≤ m ≤ 15.
! Copyright (c) 2008 Eric Mertens.
! See https://factorcode.org/license.txt for BSD license.
-USING: kernel math math.primes.factors math.vectors sequences sets
-project-euler.common ;
+USING: kernel math math.primes.factors math.vectors sequences
+sets project-euler.common ;
IN: project-euler.203
-! https://projecteuler.net/index.php?section=problems&id=203
+! https://projecteuler.net/problem=203
! DESCRIPTION
! -----------
-! The binomial coefficients nCk can be arranged in triangular form, Pascal's
-! triangle, like this:
+! The binomial coefficients nCk can be arranged in triangular
+! form, Pascal's triangle, like this:
! 1
! 1 1
! 1 7 21 35 35 21 7 1
! .........
-! It can be seen that the first eight rows of Pascal's triangle contain twelve
-! distinct numbers: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 and 35.
+! It can be seen that the first eight rows of Pascal's triangle
+! contain twelve distinct numbers: 1, 2, 3, 4, 5, 6, 7, 10, 15,
+! 20, 21 and 35.
-! A positive integer n is called squarefree if no square of a prime divides n.
-! Of the twelve distinct numbers in the first eight rows of Pascal's triangle,
-! all except 4 and 20 are squarefree. The sum of the distinct squarefree numbers
-! in the first eight rows is 105.
+! A positive integer n is called squarefree if no square of a
+! prime divides n. Of the twelve distinct numbers in the first
+! eight rows of Pascal's triangle, all except 4 and 20 are
+! squarefree. The sum of the distinct squarefree numbers in the
+! first eight rows is 105.
-! Find the sum of the distinct squarefree numbers in the first 51 rows of
-! Pascal's triangle.
+! Find the sum of the distinct squarefree numbers in the first
+! 51 rows of Pascal's triangle.
! SOLUTION
-! Copyright (c) 2010 Aaron Schaefer. All rights reserved.
-! The contents of this file are licensed under the Simplified BSD License
-! A copy of the license is available at https://factorcode.org/license.txt
+! Copyright (c) 2010 Aaron Schaefer.
+! See https://factorcode.org/license.txt for BSD license.
USING: grouping kernel math project-euler.common ranges
sequences sequences.cords ;
IN: project-euler.206
-! https://projecteuler.net/index.php?section=problems&id=206
+! https://projecteuler.net/problem=206
! DESCRIPTION
! -----------
! SOLUTION
! --------
-! Through mathematical analysis, we know that the number must end in 00, and
-! the only way to get the last digits to be 900, is for our answer to end in
-! 30 or 70.
+! Through mathematical analysis, we know that the number must
+! end in 00, and the only way to get the last digits to be 900,
+! is for our answer to end in 30 or 70.
<PRIVATE
USING: accessors kernel math project-euler.common ;
IN: project-euler.215
-! https://projecteuler.net/index.php?section=problems&id=215
+! https://projecteuler.net/problem=215
! DESCRIPTION
! -----------
-! Consider the problem of building a wall out of 2x1 and 3x1 bricks
-! (horizontal x vertical dimensions) such that, for extra strength, the gaps
-! between horizontally-adjacent bricks never line up in consecutive layers,
-! i.e. never form a "running crack".
+! Consider the problem of building a wall out of 2x1 and 3x1
+! bricks (horizontal x vertical dimensions) such that, for extra
+! strength, the gaps between horizontally-adjacent bricks never
+! line up in consecutive layers, i.e. never form a "running
+! crack".
-! For example, the following 93 wall is not acceptable due to the running crack
-! shown in red:
+! For example, the following 93 wall is not acceptable due to
+! the running crack shown in red:
! See problem site for image...
-! There are eight ways of forming a crack-free 9x3 wall, written W(9,3) = 8.
+! There are eight ways of forming a crack-free 9x3 wall, written
+! W(9,3) = 8.
! Calculate W(32,10).
USING: kernel math math.functions project-euler.common ;
IN: project-euler.255
-! https://projecteuler.net/index.php?section=problems&id=255
+! https://projecteuler.net/problem=255
! DESCRIPTION
! -----------
-! We define the rounded-square-root of a positive integer n as the square root
-! of n rounded to the nearest integer.
+! We define the rounded-square-root of a positive integer n as
+! the square root of n rounded to the nearest integer.
-! The following procedure (essentially Heron's method adapted to integer
-! arithmetic) finds the rounded-square-root of n:
+! The following procedure (essentially Heron's method adapted to
+! integer arithmetic) finds the rounded-square-root of n:
! Let d be the number of digits of the number n.
! If d is odd, set x_(0) = 2×10^((d-1)⁄2).
! until x_(k+1) = x_(k).
-! As an example, let us find the rounded-square-root of n = 4321.
-! n has 4 digits, so x_(0) = 7×10^((4-2)⁄2) = 70.
+! As an example, let us find the rounded-square-root of n =
+! 4321. n has 4 digits, so x_(0) = 7×10^((4-2)⁄2) = 70.
! [ see URL for figure ]
! Since x_(2) = x_(1), we stop here.
-! So, after just two iterations, we have found that the rounded-square-root of
-! 4321 is 66 (the actual square root is 65.7343137…).
+! So, after just two iterations, we have found that the
+! rounded-square-root of 4321 is 66 (the actual square root is
+! 65.7343137…).
-! The number of iterations required when using this method is surprisingly low.
-! For example, we can find the rounded-square-root of a 5-digit integer
-! (10,000 ≤ n ≤ 99,999) with an average of 3.2102888889 iterations (the average
-! value was rounded to 10 decimal places).
+! The number of iterations required when using this method is
+! surprisingly low. For example, we can find the
+! rounded-square-root of a 5-digit integer (10,000 ≤ n ≤ 99,999)
+! with an average of 3.2102888889 iterations (the average value
+! was rounded to 10 decimal places).
-! Using the procedure described above, what is the average number of iterations
-! required to find the rounded-square-root of a 14-digit number
-! (10^(13) ≤ n < 10^(14))? Give your answer rounded to 10 decimal places.
+! Using the procedure described above, what is the average
+! number of iterations required to find the rounded-square-root
+! of a 14-digit number (10^(13) ≤ n < 10^(14))? Give your answer
+! rounded to 10 decimal places.
-! Note: The symbols ⌊x⌋ and ⌈x⌉ represent the floor function and ceiling
-! function respectively.
+! Note: The symbols ⌊x⌋ and ⌈x⌉ represent the floor function and
+! ceiling function respectively.
! SOLUTION
! --------
sequences sets ;
IN: project-euler.265
-! https://projecteuler.net/index.php?section=problems&id=265
+! https://projecteuler.net/problem=265
-! 2^(N) binary digits can be placed in a circle so that all the N-digit
-! clockwise subsequences are distinct.
+! 2^(N) binary digits can be placed in a circle so that all the
+! N-digit clockwise subsequences are distinct.
-! For N=3, two such circular arrangements are possible, ignoring rotations.
+! For N=3, two such circular arrangements are possible, ignoring
+! rotations.
-! For the first arrangement, the 3-digit subsequences, in clockwise order, are:
-! 000, 001, 010, 101, 011, 111, 110 and 100.
+! For the first arrangement, the 3-digit subsequences, in
+! clockwise order, are: 000, 001, 010, 101, 011, 111, 110 and
+! 100.
-! Each circular arrangement can be encoded as a number by concatenating
-! the binary digits starting with the subsequence of all zeros as the most
-! significant bits and proceeding clockwise. The two arrangements for N=3 are
-! thus represented as 23 and 29:
+! Each circular arrangement can be encoded as a number by
+! concatenating the binary digits starting with the subsequence
+! of all zeros as the most significant bits and proceeding
+! clockwise. The two arrangements for N=3 are thus represented
+! as 23 and 29:
! 00010111 _(2) = 23
! 00011101 _(2) = 29
-! Calling S(N) the sum of the unique numeric representations, we can see that S(3) = 23 + 29 = 52.
+! Calling S(N) the sum of the unique numeric representations, we
+! can see that S(3) = 23 + 29 = 52.
! Find S(5).
! Copyright (c) 2023 Cecilia Knaebchen.
! See https://factorcode.org/license.txt for BSD license.
-USING: combinators kernel locals math math.functions project-euler.common ;
+USING: combinators kernel locals math math.functions
+project-euler.common ;
IN: project-euler.463
-! https://projecteuler.net/index.php?section=problems&id=463
+! https://projecteuler.net/problem=463
! DESCRIPTION
! -----------
-! The function f is defined for all positive integers as follows:
+! The function f is defined for all positive integers as
+! follows:
! f(1) = 1
! f(3) = 3
! --------
! Recursion for S(n):
-! S(n) = S([n/2]) + 2S([(n+1)/2]) + 3S([(n-1)/2]) - 2S([(n+1)/4]) - 4S([(n-1)/4]) - 2S([(n-3)/4]) - 1
+! S(n) = S([n/2]) + 2S([(n+1)/2]) + 3S([(n-1)/2]) -
+! 2S([(n+1)/4]) - 4S([(n-1)/4]) - 2S([(n-3)/4]) - 1
MEMO:: S ( n -- Sn )
n {
project-euler.common ;
IN: project-euler.508
-! https://projecteuler.net/index.php?section=problems&id=508
+! https://projecteuler.net/problem=508
! DESCRIPTION
! -----------
-! Consider the Gaussian integer i-1. A base i-1 representation of a Gaussian integer a+bi is a finite sequence of digits
+! Consider the Gaussian integer i-1. A base i-1 representation
+! of a Gaussian integer a+bi is a finite sequence of digits
! d(n-1) d(n-2) ... d(1) d(0) such that:
! a+bi = d(n-1) (i-1)^(n-1) + ... + d(1) (i-1) + d(0)
! Each d(k) is in {0,1}
-! There are no leading zeros, i.e. d(n-1) != 0, unless a+bi is itself 0
+! There are no leading zeros, i.e. d(n-1) != 0, unless a+bi is
+! itself 0.
! Here are base i-1 representations of a few Gaussian integers:
! 11+24i -> 111010110001101
! -5+ 0i -> 11001101
! 0+ 0i -> 0
-! Remarkably, every Gaussian integer has a unique base i-1 representation!
+! Remarkably, every Gaussian integer has a unique base i-1
+! representation!
-! Define f(a+bi) as the number of 1s in the unique base i-1 representation of a+bi.
-! For example, f(11+24i) = 9 and f(24-11i) = 7.
+! Define f(a+bi) as the number of 1s in the unique base i-1
+! representation of a+bi. For example, f(11+24i) = 9 and
+! f(24-11i) = 7.
-! Define B(L) as the sum of f(a+bi) for all integers a, b such that |a| <= L and |b| <= L.
-! For example, B(500) = 10,795,060.
+! Define B(L) as the sum of f(a+bi) for all integers a, b such
+! that |a| <= L and |b| <= L. For example, B(500) = 10,795,060.
! Find B(10^15) mod 1,000,000,007.
a b [ zero? ] both? [ 0 ] [ a b + 2 rem dup a - dup [ b + 2 / ] [ b - 2 / ] bi* fab + ] if ;
! B(P,Q,R,S) := Sum(a=P..Q, b=R..S, f(a+bi))
-! Recursion for B(P,Q,R,S) exists, basically four slightly different versions of B(-S/2,-R/2,P/2,Q/2)
-! If summation is over fewer than 5000 terms, we just calculate values of f
+! Recursion for B(P,Q,R,S) exists, basically four slightly
+! different versions of B(-S/2,-R/2,P/2,Q/2). If summation is
+! over fewer than 5000 terms, we just calculate values of f.
MEMO:: B ( P Q R S -- n )
Q P - S R - * 5000 <
projects / factor.git / commitdiff