関数型で Project Euler を解く
#001: こてしらべ
1000 未満の 3 もしくは 5 の倍数の合計。R.range で1..1000の配列を作って、filter して sum:
const app = R.pipe(
R.range,
R.filter(x => x % 3 === 0 || x % 5 === 0),
R.sum,
);
app(1, 1000); // -> 233168
#002: ジェネレータ + takeWhile
400万以下で偶数のフィボナッチ数の総和。フィボナッチ数はジェネレータで生成。R.takeWhile をつかって打ち切る:
function* fib() {
yield 1;
yield 1;
for (let [a, b] = [1, 1]; ; [a, b] = [b, a + b]) yield a + b;
}
const xForm = R.compose(
R.takeWhile(x => x < 4e6),
R.filter(x => x % 2 === 0),
);
const app = R.transduce(xForm, R.add, 0);
app(fib()); // -> 4613732
#003: 再帰
N = 600851475143 の最大素因数。これを app(N) とおこう。1..√N までに N を割り切る数が存在しなければ、N は素数なので app(N) = N 。もし存在する場合、それを x とおくと（注:この手順だとx は素数） app(N) = max(x, app(N/x)) と、再帰に帰着。なお、1..√N は配列だと少し大きいので、ジェネレータ rangeG で持つことにした:
function* rangeG(start, end, step = 1) {
for (let i = start; i < end; i += step) yield i;
}
const app = (n) => {
const reducer = (_, x) => (n % x === 0 ? R.reduced(R.max(x, app(n / x))) : null);
const reduced = R.reduce(reducer, null, rangeG(2, Math.ceil(Math.sqrt(n) + 1)));
return reduced || n;
};
app(600851475143); // -> 6857
#004: ジェネレータ + take
3桁×3桁で作られる最大の回文数 (注: 回文数とは前から読んでも後ろから読んでも同じ数字を表す数)。999 * 999 から 1 ずつ小さくしていった数字のうち、回文数条件を満たし、かつ 100...999 で割り切れてその商も 100..999 になるという条件で filter して、 take(1) する:
function* gen() {
for (let i = 999 * 999; i > 100 * 100; i -= 1) yield i;
}
const isPalindromic = n => n === R.pipe(R.toString, R.reverse, parseInt)(n);
const isComposedBy3digits = n => R.range(100, 1000)
.some(x => n % x === 0 && n / x > 99 && n / x < 1000);
const app = R.into('', R.compose(
R.filter(isPalindromic),
R.filter(isComposedBy3digits),
R.take(1),
));
app(gen()); // -> 906609
#005: 再帰
1..20の各数で割り切れる最小の数。これは最小公倍数を求めるという算数の問題で、プログラム上の工夫はあんまりない。ユークリッドの互除法という最大公約数を求めるアルゴリズムは再帰構造をとる、くらいか:
const gcd = (a, b) => {
if (a < b) return gcd(b, a);
if (a % b === 0) return b;
return gcd(b, a % b);
};
const gcm = (a, b) => a * b / gcd(a, b);
const app = R.pipe(
R.range,
R.reduce(gcm, 1),
);
app(1, 21); // -> 232792560
#006: こてしらべ
1..100の和の二乗と、二乗の和の差。特にいうことはないね:
const app = R.pipe(
R.range,
arr => R.sum(arr) ** 2 - R.sum(arr.map(x => x ** 2)),
);
app(1, 101); // -> 25164150
#007: ジェネレータ + drop
10001番目の素数。素数を出力するジェネレータに、先頭から 10000 個をdrop して take(1) する:
const isPrime = n => R.range(2, Math.ceil(Math.sqrt(n)) + 1).every(x => n % x !== 0);
function* primes() {
yield 2;
for (let i = 3; ; i += 2) {
if (isPrime(i)) yield i;
}
}
const app = R.into('', R.compose(R.drop(10000), R.take(1)));
app(primes()); // -> 104743
#008: aperture
連続する13数値の積の最大値。この操作は aperture と呼ばれ、R.aperture が使える:
const DATA = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450';
const app = R.pipe(
R.aperture,
R.map(R.product),
R.reduce(R.max, 0),
);
app(13, DATA); // -> 23514624000
#009: 組み合わせ
足して1000となるピタゴラス数。1..1000 の数を二つ選んで直角三角形ができるかを判定する。一般性を失わずに a <= b とできるので、組み合わせ総数は 1000 * 1000 よりも少し小さくできる:
const isSquare = n => n === Math.floor(Math.sqrt(n)) ** 2;
const app = R.pipe(
() => R.range(1, 1000),
R.map(a => R.range(a, 1000).map(b => [a, b])),
R.unnest, // -> [[a, b]]
R.find(([a, b]) => {
const c2 = a ** 2 + b ** 2;
return isSquare(c2) && a + b + Math.sqrt(c2) === 1000;
}),
([a, b]) => a * b * Math.sqrt(a ** 2 + b ** 2),
);
app(); // -> 31875000
#010: やや複雑なジェネレータ
200万以下の素数の総和。#007 の方法で基本いけるが、わずかに改良して 数秒で終わるようにする。改良点は以下
- ジェネレータ内で評価する素数候補を 1, 5 mod 6 の整数に限定
- それ以外の数値は2 または 3 で割り切れるので候補たりえない
const isPrime = n => R.range(3, Math.ceil(Math.sqrt(n)) + 1, 2).every(x => n % x !== 0);
function* primes() {
yield 2;
yield 3;
yield 5;
for (let base = 6; ; base += 6) {
if (isPrime(base + 1)) yield base + 1;
if (isPrime(base + 5)) yield base + 5;
}
}
app = R.reduceWhile((acc, x) => x < 2e6, R.add, 0);
app(primes()); // -> 142913828922
このサイズになるとエラトステネスのふるいが正着だろうが、まあよい。
#011: 二次元 aperture
盤面20x20で縦横ナナメの連続4整数の積で最大のもの。各座標において、その点を起点とした縦横ナナメを計算し、局所的な最大値を求める。そののちに、全座標での最大値を求める:
// convert coordinate to 0..399, -1 for invalid corrdinate
const idxOf = (row, col) => {
if (row > -1 && row < 20 && col > -1 && col < 20) return 20 * row + col;
return -1;
};
const localMax = data => ([row, col]) => {
const table = data.split(' ').map(R.unary(parseInt));
const yoko = R.range(0, 4).map(n => idxOf(row + n, col));
const tate = R.range(0, 4).map(n => idxOf(row, col + n));
const dia1 = R.range(0, 4).map(n => idxOf(row + n, col + n));
const dia2 = R.range(0, 4).map(n => idxOf(row + n, col - n));
return [yoko, tate, dia1, dia2]
.filter(R.all(y => y !== -1))
.map(arr => arr.map(idx => table[idx]))
.map(R.product)
.reduce(R.max, 0);
};
const app = data => R.pipe(
() => R.xprod(R.range(0, 20), R.range(0, 20)),
R.map(localMax(data)),
R.reduce(R.max, 0),
);
const DATA = '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 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48';
app(DATA)(); // -> 70600674
#012: ジェネレータ
約数の数量が500を超える三角数。三角数ジェネレータから逐次三角数を取り出し、素因数分解して(factor)、その結果をもとに、約数カウント関数(yakuNum)で条件を最初に満たした三角数を出力する:
function* trigen() {
for (let n = 1; ; n += 1) yield n * (n + 1) / 2;
}
const factor = (n) => {
if (n === 1) return [];
const reducer = (_, x) => (n % x === 0 ? R.reduced([x, ...factor(n / x)]) : null);
const reduced = R.reduce(reducer, null, R.range(2, Math.ceil(Math.sqrt(n) + 1)));
return reduced || [n];
};
const yakuNum = R.pipe(
R.countBy(R.identity),
obj => Object.values(obj).map(R.inc).reduce(R.multiply, 1),
);
const app = R.into('', R.compose(
R.map(factor),
R.filter(x => yakuNum(x) > 500),
R.take(1),
R.map(R.product),
));
app(trigen()); // -> 76576500
#013: compose
50桁の整数を100個足した総和の上位10桁を求める。JavaScript は大きい数字を扱えないので、1の位から順に足し算をして、繰り上げを次の位の足し算に利用する(adderの実装を見よ)。プログラム全体は、データを加工し続けるので、R.pipe, R.compose でまとめるのが functional:
const adder = (arr, acc) => { // NOTE: its for reduceRight. check signature.
const val = acc.kuri + R.sum(arr);
return { kuri: Math.floor(val / 10), buf: [val % 10, ...acc.buf] };
};
const app = R.pipe(
R.split(' '), // -> [string]
R.transpose,
R.reduceRight(adder, { kuri: 0, buf: [] }), // 1桁ずつ計算
obj => `${obj.kuri}${obj.buf.join('')}`, // 結果の構築
R.slice(0, 10),
);
const DATA = '37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 23067588207539346171171980310421047513778063246676 89261670696623633820136378418383684178734361726757 28112879812849979408065481931592621691275889832738 44274228917432520321923589422876796487670272189318 47451445736001306439091167216856844588711603153276 70386486105843025439939619828917593665686757934951 62176457141856560629502157223196586755079324193331 64906352462741904929101432445813822663347944758178 92575867718337217661963751590579239728245598838407 58203565325359399008402633568948830189458628227828 80181199384826282014278194139940567587151170094390 35398664372827112653829987240784473053190104293586 86515506006295864861532075273371959191420517255829 71693888707715466499115593487603532921714970056938 54370070576826684624621495650076471787294438377604 53282654108756828443191190634694037855217779295145 36123272525000296071075082563815656710885258350721 45876576172410976447339110607218265236877223636045 17423706905851860660448207621209813287860733969412 81142660418086830619328460811191061556940512689692 51934325451728388641918047049293215058642563049483 62467221648435076201727918039944693004732956340691 15732444386908125794514089057706229429197107928209 55037687525678773091862540744969844508330393682126 18336384825330154686196124348767681297534375946515 80386287592878490201521685554828717201219257766954 78182833757993103614740356856449095527097864797581 16726320100436897842553539920931837441497806860984 48403098129077791799088218795327364475675590848030 87086987551392711854517078544161852424320693150332 59959406895756536782107074926966537676326235447210 69793950679652694742597709739166693763042633987085 41052684708299085211399427365734116182760315001271 65378607361501080857009149939512557028198746004375 35829035317434717326932123578154982629742552737307 94953759765105305946966067683156574377167401875275 88902802571733229619176668713819931811048770190271 25267680276078003013678680992525463401061632866526 36270218540497705585629946580636237993140746255962 24074486908231174977792365466257246923322810917141 91430288197103288597806669760892938638285025333403 34413065578016127815921815005561868836468420090470 23053081172816430487623791969842487255036638784583 11487696932154902810424020138335124462181441773470 63783299490636259666498587618221225225512486764533 67720186971698544312419572409913959008952310058822 95548255300263520781532296796249481641953868218774 76085327132285723110424803456124867697064507995236 37774242535411291684276865538926205024910326572967 23701913275725675285653248258265463092207058596522 29798860272258331913126375147341994889534765745501 18495701454879288984856827726077713721403798879715 38298203783031473527721580348144513491373226651381 34829543829199918180278916522431027392251122869539 40957953066405232632538044100059654939159879593635 29746152185502371307642255121183693803580388584903 41698116222072977186158236678424689157993532961922 62467957194401269043877107275048102390895523597457 23189706772547915061505504953922979530901129967519 86188088225875314529584099251203829009407770775672 11306739708304724483816533873502340845647058077308 82959174767140363198008187129011875491310547126581 97623331044818386269515456334926366572897563400500 42846280183517070527831839425882145521227251250327 55121603546981200581762165212827652751691296897789 32238195734329339946437501907836945765883352399886 75506164965184775180738168837861091527357929701337 62177842752192623401942399639168044983993173312731 32924185707147349566916674687634660915035914677504 99518671430235219628894890102423325116913619626622 73267460800591547471830798392868535206946944540724 76841822524674417161514036427982273348055556214818 97142617910342598647204516893989422179826088076852 87783646182799346313767754307809363333018982642090 10848802521674670883215120185883543223812876952786 71329612474782464538636993009049310363619763878039 62184073572399794223406235393808339651327408011116 66627891981488087797941876876144230030984490851411 60661826293682836764744779239180335110989069790714 85786944089552990653640447425576083659976645795096 66024396409905389607120198219976047599490197230297 64913982680032973156037120041377903785566085089252 16730939319872750275468906903707539413042652315011 94809377245048795150954100921645863754710598436791 78639167021187492431995700641917969777599028300699 15368713711936614952811305876380278410754449733078 40789923115535562561142322423255033685442488917353 44889911501440648020369068063960672322193204149535 41503128880339536053299340368006977710650566631954 81234880673210146739058568557934581403627822703280 82616570773948327592232845941706525094512325230608 22918802058777319719839450180888072429661980811197 77158542502016545090413245809786882778948721859617 72107838435069186155435662884062257473692284509516 20849603980134001723930671666823555245252804609722 53503534226472524250874054075591789781264330331690';
app(DATA) // -> 5537376230
#014: メモ化
コラッツ列が最長となる100万以下の初期値。R.memoizeでメモ化して高速化を狙う:
const collazLen = R.memoizeWith(R.identity, (n) => {
if (n === 1) return 1;
return (n % 2 === 0) ? 1 + collazLen(n / 2) : 1 + collazLen(3 * n + 1);
});
const app = R.pipe(
R.range(1),
R.sortBy(collazLen),
R.last,
);
app(1e6) // -> 837799
#015: メモ化
20x20の格子の対角線を最短で抜ける道順の数。これは有名な問題で 40C20なのだが、漸化式でまともにやると、#014 同様メモ化が有効な再帰構造になる:
const app = R.memoizeWith((x, y) => `${x},${y}`, (x, y) => {
if (x === 0 || y === 0) return 1;
return app(x - 1, y) + app(x, y - 1);
});
app(20, 20); // -> 137846528820
#016: compose
2^100の各桁の総和。#013 と同じ:
const doubleRed = (x, acc) => { // NOTE: its for reduceRight. check signature.
const val = acc.kuri + x * 2;
return { kuri: Math.floor(val / 10), buf: [val % 10, ...acc.buf] };
};
const myDouble = R.pipe(
R.reduceRight(doubleRed, { kuri: 0, buf: [] }),
obj => (obj.kuri ? [...obj.kuri.toString(), ...obj.buf] : obj.buf),
);
const app = R.pipe(
() => R.range(1, 1001),
R.reduce(myDouble, [1]),
R.sum,
);
app(); // -> 1366
#017: 英語の勉強
1000以下のすべての自然数の英語表記の文字数の総計。数字を入力に英語表記を返す関数をつくるだけ:
const translate = (n) => {
const A = [null, 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine'];
const B = ['ten', 'eleven', 'twelve', 'thirteen', 'fourteen', 'fifteen', 'sixteen', 'seventeen', 'eighteen', 'nineteen']
const C = [null, null, 'twenty', 'thirty', 'forty', 'fifty', 'sixty', 'seventy', 'eighty', 'ninety']
if (n < 10) return A[n];
if (n > 9 && n < 20) return B[n - 10];
if (n > 19 && n < 100) {
if (n % 10 === 0) return C[n / 10];
return `${C[Math.floor(n / 10)]} ${translate(n % 10)}`;
}
if (n > 99 && n < 1000) {
if (n % 100 === 0) return `${A[n / 100]} hundred`
return `${A[Math.floor(n / 100)]} hundred and ${translate(n % 100)}`;
}
if (n === 1000) return 'one thousand';
};
const app = R.pipe(
() => R.range(1, 1001),
R.map(translate),
R.map(R.replace(/ /g, '')),
R.map(R.length),
R.sum,
);
app(); // -> 21124
#018: compose
三角山の降下時の最大スコア。発想は #015 に似ている。点P を通過する際の累計スコアの最大値 f(P) が計算できる。つまり、ある点に到達するためには、一つ上流の 2 点 P1, P2 のいずれかを必ず通らなければいけないので、 f(P) = max(f(P1), f(P2)) + Pのスコア と計算ができる。最終段の最大値をとれば解になる:
const update = (last, now) => now.map((val, idx) => {
if (idx === 0) return val + last[0];
if (idx === now.length - 1) return val + last[last.length - 1];
return val + R.max(last[idx - 1], last[idx]);
});
const updateTriangle = arrs => arrs.reduce(
(acc, arr, idx) => {
if (idx === 0) return acc;
acc.result[idx] = update(acc.result[idx - 1], arr);
return acc;
},
{ result: R.clone(arrs) },
);
const app = R.pipe(
R.split('\n'),
R.map(R.split(' ')),
R.map(R.map(parseInt)), // parsed.
updateTriangle,
R.prop('result'),
R.last,
R.reduce(R.max, 0),
);
const DATA = `75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23`;
app(DATA); // -> 1074
#019: compose
20世紀中、月初が日曜日だった月の数。1200 回ある月初を 1900-01-01 を エポック(0) とする日付で表すことを目標にする。そのために、各年の各月の日数を取得する関数 days およびその結果をもとに月初のエポックを生成する reduce 処理を頑張って作る(toEpoch リデューサー)
const days = (year) => {
const base = [31, null, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
base[1] = (year % 100 === 0 || year % 4 !== 0) ? 28 : 29;
return base;
};
const app = R.pipe(
() => R.range(1901, 2001),
R.map(days),
R.flatten,
R.scan(R.add, R.sum(days(1900))), // -> [first day of month in epoch]
R.dropLast(1), // last element falls at 2001-01-01
R.filter(n => n % 7 === 6), // -> check if it is sundays
R.length,
);
app(); // -> 171
#020: カリー化
100!の各桁の総和。#013, #016 と同じ発想。 n を掛ける関数を作るための関数 myMultiply はカリー化で実現。
const mulRed = n => (x, acc) => { // NOTE: its for reduceRight. check signature.
const val = acc.kuri + x * n;
return { kuri: Math.floor(val / 10), buf: [val % 10, ...acc.buf] };
};
const myMultiply = n => R.pipe(
R.reduceRight(mulRed(n), { kuri: 0, buf: [] }),
obj => (obj.kuri ? [...obj.kuri.toString(), ...obj.buf] : obj.buf),
);
const app = R.pipe(
() => R.range(1, 101),
R.reduce((acc, x) => myMultiply(x)(acc), [1]),
R.sum,
);
app(); // -> 648
#021: xprod
10000以下の友愛数の総和。素因数分解して(factor)から、約数を作る操作(divisors)は、直積なので R.xprod が利用できる:
const factor = (n) => {
if (n < 2) return [];
if (n % 2 === 0) return [2, ...factor(n / 2)];
const reduced = R.reduce(
(_, x) => (n % x === 0 ? R.reduced([x, ...factor(n / x)]) : null),
null,
R.range(3, Math.ceil(Math.sqrt(n)) + 1),
);
return reduced || [n];
};
const divisors = (n) => {
const factored = factor(n);
const grouped = Object.entries(R.countBy(R.identity, factored));
return grouped.reduce(
(acc, x) => R.xprod(acc, R.range(0, x[1] + 1).map(a => x[0] ** a))
.map(tup => tup.reduce(R.multiply)),
[1],
);
};
const isAmicable = R.memoizeWith(R.identity, (n) => {
const summed = divisors(n).filter(x => x !== n).reduce(R.add, 0);
if (summed === n) return false;
return n === divisors(summed).filter(x => x !== summed).reduce(R.add, 0);
});
const app = R.pipe(
() => R.range(2, 10000),
R.filter(isAmicable),
R.sum,
);
app(); // -> 31626
#022: ソート
名前一覧からスコアの総計を求めよ（注: スコア計算の詳細は略）。ソートをどうするのか？というのが意図なのだろうけど、R.sort を使うので簡単:
const fs = require('fs');
const scoreOf = (name, position) => {
const base = 'A'.charCodeAt(0);
const nameScore = [...name].reduce((acc, c) => acc + c.charCodeAt(0) - base + 1, 0);
return nameScore * position;
};
const app = R.pipe(
() => '[' + fs.readFileSync('./names.txt', 'utf8') + ']',
JSON.parse,
R.sortBy(R.identity), // sort
names => names.map((name, i) => scoreOf(name, i + 1)),
R.reduce(R.add, 0),
);
app() // -> 871198282
#023: Set
二つのabundant数で表せれない28123以下の自然数の総和。abundantの判定関数は、#021 の友愛数判定関数とほぼ同一。まずは、1..28123 abundant数を列挙する(ABUNDANTS)。このうち二つを選んで足し上げて、28123 を超えないものを列挙する(APLUSA)。足した結果は同一のものが山ほどできるので Set の利用を考えないととても時間がかかってしまう。
const factor = (n) => {
if (n < 2) return [];
if (n % 2 === 0) return [2, ...factor(n / 2)];
const reduced = R.reduce(
(_, x) => (n % x === 0 ? R.reduced([x, ...factor(n / x)]) : null),
null,
R.range(3, Math.ceil(Math.sqrt(n)) + 1),
);
return reduced || [n];
};
const divisors = (n) => {
const factored = factor(n);
const grouped = Object.entries(R.countBy(R.identity, factored))
return grouped.reduce(
(acc, x) => R.xprod(acc, R.range(0, x[1] + 1).map(a => x[0] ** a))
.map(tup => tup.reduce(R.multiply)),
[1],
);
};
const isAbundant = n => n < divisors(n).filter(x => x !== n).reduce(R.add, 0);
// main
const LIMIT = 28123;
const ABUNDANTS = R.range(1, LIMIT).filter(isAbundant);
const APLUSA = ABUNDANTS.reduce( // [a + b] with a <= b and a + b < LIMIT
(acc, a) => {
if (a > LIMIT / 2) return acc;
ABUNDANTS.forEach(b => (a <= b && a + b < LIMIT && acc.add(a + b)));
return acc;
},
new Set(),
);
const app = R.pipe(
R.difference(R.range(1, LIMIT)),
R.sum,
);
app([...APLUSA]); // -> 4179871
#024: 順列
0..9を1文字ずつ使った10文字を辞書順に並べた100万番目の文字。大学受験でよく出るやつ。1E6 - 1 = 2 * 9! + 6 * 8! + ... + 1 * 1! というように分解できれば、10文字のうち、(0から数えて)2番目に小さいものを選んで、次にのこり9文字のうち6番目に小さいものを選んで、という形で答えの 2783915460 が得られる。というわけで、まず 1! から 9! まで作って配列に入れ、前述のように 100万 -1 を分解して(reduceRight), 分解結果を使って文字をピックアップしていく(pick):
const pick = (idxs, target) => {
if (idxs.length === 1) return idxs[0] === 0 ? target : R.reverse(target);
return [target[idxs[0]], ...pick(R.remove(0, 1, idxs), R.remove(idxs[0], 1, target))];
};
const app = R.pipe(
() => R.range(1, 10).map(n => R.range(1, n + 1).reduce(R.multiply, 1)), // ->[factorials]
R.reduceRight(
(f, acc) => {
acc.buf.push(Math.floor(acc.rest / f));
acc.rest %= f;
return acc;
},
{ buf: [], rest: 1e6 - 1 }, // 1million-th has a index of 1e6 - 1.
),
R.prop('buf'),
idxs => pick(idxs, [...'0123456789']),
R.join(''),
);
app() // -> 2783915460
#025: ジェネレータ
はじめて1000桁を超えるフィボナッチ数は何番目か？。#002 で作ったフィボナッチ数ジェネレータを #013 でやったように桁あふれ対応をさせればよい:
function* bigFib() {
yield { idx: 1, val: [1] };
yield { idx: 2, val: [1] };
for (let idx = 3, [a, b] = [[1], [1]]; ; idx += 1) {
const added = myAdd(a, b);
yield { idx, val: added };
[a, b] = [b, added];
}
}
const adder = (acc, arr) => {
const val = acc.kuri + arr.reduce(R.add);
return { kuri: Math.floor(val / 10), buf: [val % 10, ...acc.buf] };
};
const myAdd = (arr1, arr2) => {
// arrange them to be a same length
const len = R.max(arr1.length, arr2.length);
const a = [...Array(len - arr1.length).fill(0), ...arr1];
const b = [...Array(len - arr2.length).fill(0), ...arr2];
// calculate
const obj = R.zip(a, b).reduceRight(adder, { kuri: 0, buf: [] });
if (obj.kuri === 0) return obj.buf;
if (obj.kuri === 1) return [1, ...obj.buf];
throw new Error('cannnot reach here');
};
const app = R.into('', R.compose(
R.dropWhile(bignum => bignum.val.length < 1000),
R.take(1),
R.map(R.prop('idx')),
));
app(bigFib()) // -> 4782
#026: reduce の打ち切り
1/n (n=1...1000)の循環小数部の長さが一番長い n。循環しているかどうかは、筆算の途中で同じ余りが出てきた場合にわかる。なのであまりを覚えておき(acc.mod)、次の桁の筆算をする際に、この余りは以前に出てきたか？をチェックすればよい。プログラム的には、実際の小数部(acc.digits)は不要なのが興味深い（とはいえ、検算のためにコードは残してある）。
const toDigit = n => R.reduce(
(acc) => { // grow digits until same amari occurs
const nextDigit = Math.floor(acc.val / n);
const nextVal = (acc.val % n) * 10;
const nextAcc = ({
...acc,
digits: [...acc.digits, nextDigit],
mod: [...acc.mod, nextVal],
val: nextVal,
});
if (nextAcc.val === 0) return R.reduced(nextAcc); // divisable!
if (acc.mod.includes(nextVal)) return R.reduced(nextAcc); // recuurence
return nextAcc;
},
{ number: n, digits: [], mod: [10], val: 10 },
R.range(1, n + 1),
);
const app = R.pipe(
() => R.range(2, 1001),
R.map(toDigit),
R.map(({ number, mod }) => {
if (R.last(mod) === 0) return { number, len: 1 }; // divisible
return { number, len: mod.length - mod.indexOf(R.last(mod)) - 1 };
}),
R.sortBy(R.prop('len')),
R.reverse,
R.take(1),
R.map(R.prop('number')),
);
app() // -> [ 983 ]
#027: 関数ジェネレータ, メモ化
多項式 n^2+an+b が n=0,1,...で連続した素数を生むような(a, b)の組み合わせで最長の素数をうむもの。(|a|<1000, |b|<1000)。n = 0 で素数なので b は1000以下の素数であることがわかり、範囲を縮めることができる。あとは、(a, b) の組み合わせを、「n = 1が素数である」、「n = 2が素数である」、・・・というフィルターで残り 1 になるまで絞り込む。つまり、フィルター関数のジェネレータが必要。一連の操作で、「n が素数か」という操作が頻出するので、これをメモ化して高速化することも必要。
function* probablePrimes(end) { // -> 2, 3, 5, 7, 11, 13, 17, ...
yield 2;
yield 3;
yield 5;
for (let i = 1; ; i += 1) {
if (i * 6 + 1 >= end) break;
yield i * 6 + 1;
if (i * 6 + 5 >= end) break;
yield i * 6 + 5;
}
}
const isPrime = R.memoizeWith(R.identity, (n) => {
if (n < 0 || n === 1 || n === 4) return false;
if (n === 2 || n === 3 || n === 5) return true;
return R.reduce(
(_, x) => (n % x === 0 ? R.reduced(false) : true),
true,
probablePrimes(Math.ceil(Math.sqrt(n)) + 1),
);
});
const CANDICATES = R.xprod(R.range(-1000, 1001), R.range(1, 1001).filter(isPrime));
const FILTERS = (function* () {
for (let n = 1; ; n += 1) {
yield (a, b) => isPrime(n ** 2 + a * n + b);
}
}());
const app = R.pipe(
R.reduce((acc, fil) => {
const nextAcc = acc.filter(([a, b]) => fil(a, b));
return (nextAcc.length === 1) ? R.reduced(nextAcc) : nextAcc;
}),
R.head,
R.product,
);
app(CANDICATES, FILTERS) // -> -59231
#028: こてしらべ
1001x1001サイズのうずまき魔法陣の対角和。内側から n 番目の正方形の四隅の和は、一番大きい隅が (2n-1)**2 なので 4 * (2 * n - 1) ** 2 - 12 * n + 12 となる。あとは、n = 2...(1001-1)/2 でのその和を計算する:
const N = (1001 - 1) / 2 + 1; // num of squares
const app = R.pipe(
() => R.range(2, N + 1), // first square (which is just a point) is exception
R.map(n => 4 * (2 * n - 1) ** 2 - 12 * n + 12),
R.sum,
R.inc, // add value for n = 1
);
app() // -> 669171001
#029: xprod
a,bが1..100まで変化する際にpow(a,b)は何種類あるか。組み合わせは100×100なのでたいした量ではないが、桁溢れするので別の方法が望まれる。さて、a,b が所与の場合、a を素因数分解すれば、pow(a,b)の素因数分解は簡単に計算できる。そして素因数分解は一意なので、pow(a,b)の素因数分解結果をハッシュ化して重複を取り除けば良さそうだ、となる:
const factor = (n) => {
if (n < 2) return [];
if (n % 2 === 0) return [2, ...factor(n / 2)];
const reduced = R.reduce(
(_, x) => (n % x === 0 ? R.reduced([x, ...factor(n / x)]) : null),
null,
R.range(3, Math.ceil(Math.sqrt(n)) + 1),
);
return reduced || [n];
};
const hash = ([a, b]) => R.pipe(
() => factor(a),
primes => Object.entries(R.countBy(R.identity, primes)),
R.map(([pr, num]) => [pr, num * b].join(',')),
R.join(','),
);
const app = R.pipe(
() => R.xprod(R.range(2, 101), R.range(2, 101)),
R.map(x => hash(x)()),
R.uniq,
R.length,
);
app() // -> 9183
#030: ジェネレータ
各桁の5乗の和が自分自身に一致する2以上の整数の和。条件を関数に落とし込むのは簡単(isWanted)。むしろ問題は、いつまで走査すればよいのかを決めることだ。n桁の整数 N を考えよう。すると、N はざっくり 10^n のオーダーなのに対して、各桁の5乗の和はざっくり、n のオーダーになる。なので、N がある程度大きくなると、各桁の5乗和をしても N に追いつけなくなるので、確かに走査の上限がある。具体的には、 10^(n-1) > n * 9^5 が成立する n を求めて（n = 7）、n-1桁 以下を走査すればよいことになる。
function* rangeG(start, end, step = 1) {
for (let i = start; i < end; i += step) yield i;
}
const isWanted = n => n === [...n.toString()].reduce((acc, x) => acc + x ** 5, 0);
const app = R.transduce(R.filter(isWanted), R.add, 0);
const LIMIT = R.head(R.range(1, 10).filter(n => 10 ** (n - 1) > n * (9 ** 5))) - 1;
app(rangeG(2, 10 ** LIMIT - 1)); // -> 443839
#031: 再帰
8種類のコインで2ポンドを支払う方法の数。有名な問題で再帰で解ける。下から数えて k種類のコインで nペニーを支払う方法の数を app(k, n) とおくと、app(8, 200) = app(7, 0) + app(7, 200) というように再帰に帰着。つまり、最大額のコインの使用枚数で場合分けして、それぞれの方法の数を足し上げる。という方向性
const app = (kinds, amount) => {
if (kinds.length === 1) return 1;
return R.range(0, Math.floor(amount / R.last(kinds)) + 1)
.map(n => app(R.init(kinds), amount - n * R.last(kinds)))
.reduce(R.add, 0);
};
const KINDS = [1, 2, 5, 10, 20, 50, 100, 200];
app(KINDS, 200); // -> 73682
#032: xprod
数A, Bおよびその積 Cの各桁を合わせると1...9がちょうど 1回ずつでるようなA,Bの積 Cの総和。A,B,Cの桁数をa,b,c とおこう。a + b + c = 9 とならなければならないが、c はその構成方法より、 a + b - 1 <= c <= a + b という制約がある。a <= b であるとして一般性を失わないので、とりうる組み合わせは、(a, b, c) = (1, 4, 4), (2, 3, 4) の二つしかない:
const isPandigital = ([a, b]) => {
const str = [...a.toString(), ...b.toString(), ...(a * b).toString()];
if (str.length !== 9) return false;
if (R.sortBy(R.identity, str).join('') === '123456789') return true;
return false;
};
const app = R.pipe(
() => R.concat(
R.xprod(R.range(1, 10), R.range(1000, 9999)),
R.xprod(R.range(10, 100), R.range(100, 999)),
),
R.filter(isPandigital),
R.map(R.product),
R.uniq, // hint says it may be duplicate
R.sum,
);
app(); // -> 45228
#033: グルーピング
変な分数が4つある。それらの積を約分した分母を求めよ（注:変な分数のルールは省略）。どちらかというと約分の方がややこしい気がする。
const isWanted = ([a, b]) => {
const [astr, bstr] = [[...a.toString()], [...b.toString()]];
if (astr.includes('0') || bstr.includes('0')) return false;
const common = R.intersection(astr, bstr);
if (common.length !== 1) return false;
const acmpl = parseInt(R.difference(astr, common).join(''));
const bcmpl = parseInt(R.difference(bstr, common).join(''));
return (a / b === acmpl / bcmpl);
};
const factor = (n) => {
if (n === 1) return [];
const reducer = (_, x) => (n % x === 0 ? R.reduced([x, ...factor(n / x)]) : null);
const reduced = R.reduce(reducer, null, R.range(2, Math.ceil(Math.sqrt(n) + 1)));
return reduced || [n];
};
const bunbo = (vals) => {
const [a, b] = vals.map(factor).map(R.countBy(R.identity));
let ret = 1;
Object.entries(b).forEach(([pr, numB]) => {
const numA = a[pr] || 0;
ret *= pr ** ((numA >= numB) ? 0 : numB - numA);
});
return ret;
};
const app = R.pipe(
() => R.range(11, 100),
R.map(a => R.range(a, 100).map(b => [a, b])),
R.unnest, // -> [a, b] for a / b
R.filter(isWanted),
R.transpose,
R.map(R.product), // -> [分子の積, 分母の積]
bunbo,
);
app(); // -> 100
#034: ジェネレータ
各桁の階乗を足すと自分自身になる整数の総和。これは完全に #030 と同じ問題。思考プロセスも完全に同一。
function* rangeG(start, end, step = 1) {
for (let i = start; i < end; i += step) yield i;
}
const fact = R.memoizeWith(R.identity, n => R.product(R.range(1, n + 1)));
const isWanted = n => n === [...n.toString()].reduce((acc, x) => acc + fact(parseInt(x)), 0);
const app = R.transduce(R.filter(isWanted), R.add, 0);
const LIMIT = R.head(R.range(1, 15).filter(n => 10 ** (n - 1) > n * fact(9))) - 1;
app(rangeG(10, LIMIT * fact(9) - 1)); // -> 40730
#035: 循環
各桁を循環させた数値もすべてが素数である100万以下の素数の総和。いわれたとおりに書き下すだけ。
function* probablePrimes(end) { // -> 2, 3, 5, 7, 11, 13, 17, ...
yield 2;
yield 3;
yield 5;
for (let i = 1; ; i += 1) {
if (i * 6 + 1 >= end) break;
yield i * 6 + 1;
if (i * 6 + 5 >= end) break;
yield i * 6 + 5;
}
}
const isPrime = R.memoizeWith(R.identity, (n) => {
if (n < 0 || n === 1 || n === 4) return false;
if (n === 2 || n === 3 || n === 5) return true;
return R.reduce(
(_, x) => (n % x === 0 ? R.reduced(false) : true),
true,
probablePrimes(Math.ceil(Math.sqrt(n)) + 1),
);
});
const isWanted = (n) => {
const arr = [...n.toString()];
return R.range(0, arr.length)
.map(i => [...arr.slice(i, arr.length), ...arr.slice(0, i)].join(''))
.map(R.unary(parseInt))
.every(isPrime);
};
const app = R.pipe(
() => probablePrimes(1e6),
R.into([], R.filter(isWanted)),
R.length,
);
app(); // -> 55
#036: こてだめし
2進、10進表現の両方で回文数になる100万以下の数の総和。#002 でやったのを2進表現にするだけ:
const isPalindromic10 = n => n === R.pipe(R.toString, R.reverse, parseInt)(n);
const isPalindromic2 = n => n === R.pipe(
n => n.toString(2), R.reverse, str => parseInt(str, 2))(n);
const app = R.pipe(
() => R.range(0, 1e6 / 2).map(R.multiply(2)).map(R.inc), // -> [1, 3, 5...
R.filter(isPalindromic2),
R.filter(isPalindromic10),
R.sum,
);
app(); // -> 872187
#037: メモ化
右から1文字ずつ切り詰めていっても左から切り詰めていっても素数であり続ける素数11個の総計。いわれたとおりに判定関数を書くのは難しくない(isWanted)。これまでの素数判定の効率化(メモ化・候補の制限）をするとともに、最初の桁が2, 3, 5, 7のどれかでないといけなかったり、最後の桁が 3, 5, 7のどれかでないといけないなど、計算量を削減するための工夫をすれば1秒で終わる。
function* probablePrimes(end) { // -> 2, 3, 5, 7, 11, 13, 17, ...
yield 2;
yield 3;
yield 5;
for (let i = 1; ; i += 1) {
if (i * 6 + 1 >= end) break;
yield i * 6 + 1;
if (i * 6 + 5 >= end) break;
yield i * 6 + 5;
}
}
const isPrime = R.memoizeWith(R.identity, (n) => {
if (n < 0 || n === 1 || n === 4) return false;
if (n === 2 || n === 3 || n === 5) return true;
return R.reduce(
(_, x) => (n % x === 0 ? R.reduced(false) : true),
true,
probablePrimes(Math.ceil(Math.sqrt(n)) + 1),
);
});
const isWanted = (n) => {
if (n < 10) return false;
const digits = [...n.toString()].map(R.unary(parseInt));
// shortcuts
if ([1, 4, 6, 8, 9].includes(R.head(digits))) return false;
if ([1, 2, 4, 6, 8, 9].includes(R.last(digits))) return false;
// do check
const nDigit = n.toString().length;
const check1 = R.reduce(
(_, i) => (isPrime(parseInt(digits.slice(0, i + 1).join(''))) ? true : R.reduced(false)),
true,
R.range(0, nDigit),
);
if (check1 === false) return false;
const check2 = R.reduce(
(_, i) => (isPrime(parseInt(digits.slice(i).join(''))) ? true : R.reduced(false)),
true,
R.range(0, nDigit),
);
if (!check2) return false;
return true;
};
const app = R.pipe(
R.into([], R.compose(R.filter(isWanted), R.take(11))),
R.sum,
);
app(probablePrimes(Infinity)) // -> 748317
#038: reduceの打ち切り
ある数N に 1,2,...を掛けた数を用意し、それを最初から2以上の任意の個数つなげて、ちょうど1..9を一度ずつ使うように構成できたとする。その9桁の数を（色々なNで試して）最大化せよ。このように問題を言い換えると、素直に実装すればよくなる。2 以上の個数をつなげるので、最大で N は4桁なので 10000までを走査対象にすれば十分:
const gen = n => (function* () {
for (let i = 1; ; i += 1) yield n * i;
}());
const pandRed = (acc, val) => {
const newAcc = [...acc, ...val.toString()];
if (newAcc.length > 9) return R.reduced(false);
if (newAcc.length < 9) return newAcc;
if (R.sortBy(R.identity, newAcc).join('') === '123456789') {
return R.reduced(parseInt(newAcc.join(''), 10));
}
return R.reduced(false);
};
const app = R.pipe(
() => R.range(1, 10000),
R.map(gen), // create generator for each number
R.map(R.reduce(pandRed, [])), // do calculate
R.filter(R.identity), // filter out false element
R.reduce(R.max, 0),
);
app() // -> 932718654
#039: 組み合わせ
1000以下のどの自然数を三辺の和に指定すれば、それを満たす（三辺が自然数の）直角三角形の数を最大化できるか？。見た目ほど難しくはない。まず、[1, 4, 9, ..., 1e6] という二乗の数値一覧を用意しよう。斜辺でない二辺の候補 (a, b) をこの一覧から選ぶ。その和 a + b が、このテーブルに乗っていれば晴れて(a,b,a+b)という直角三角形は存在できるということがわかる。この組み合わせに対してさらに、三辺の和を計算し 1000 以下になるものだけを抽出する。三辺の和でグルーピングし、そのカウント数が一番大きなものを選べば答え。
const N = 1000;
const TABLE = R.range(1, N).map(x => x ** 2);
const app = R.pipe(
() => R.range(1, N).map(x => R.range(x, N).map(y => [x, y])),
R.unnest,
R.map(([x, y]) => [TABLE[x], TABLE[y]]),
R.filter(([x, y]) => TABLE.includes(x + y)),
R.map(([x, y]) => R.sum([x, y, x + y].map(w => Math.sqrt(w)))),
R.filter(len => len <= 1000),
R.countBy(R.identity),
R.toPairs,
R.sortBy(R.nth(1)),
R.last,
R.nth(0),
);
app(); // -> 840
#040: ジェネレータ
自然数を1から順にくっつけていった文字列1234...91011...における 1,10,100,..1e6桁目の数字をかけ合わせた数。ジェネレータの基本操作:
function* champer() {
let count = 0;
for (let i = 1; ; i += 1) {
for (const ch of [...i.toString()]) {
count += 1;
if ([1, 10, 100, 1e3, 1e4, 1e5, 1e6].includes(count)) yield parseInt(ch);
if (count === 1e6) return;
}
}
}
const app = () => R.product([...champer()]);
app() // -> 210
#041: 順列
1..k (k = 1,2....9)をちょうど1回ずつ使った最大の素数。1..9を一回ずつ使った素数は、1...9 の順列を考えて、素数条件を満たすものを探せばよい。順列は、再帰を使ってすっきり実装。ただ、1...9では見つからなかったので、 8桁、7桁とどんどん減らしていく必要がある
function* probablePrimes(end) { // -> 2, 3, 5, 7, 11, 13, 17, ...
yield 2;
yield 3;
yield 5;
for (let i = 1; ; i += 1) {
if (i * 6 + 1 >= end) break;
yield i * 6 + 1;
if (i * 6 + 5 >= end) break;
yield i * 6 + 5;
}
}
const isPrime = R.memoizeWith(R.identity, (n) => {
if (n < 0 || n === 1 || n === 4) return false;
if (n === 2 || n === 3 || n === 5) return true;
return R.reduce(
(_, x) => (n % x === 0 ? R.reduced(false) : true),
true,
probablePrimes(Math.ceil(Math.sqrt(n)) + 1),
);
});
const permute = (arr, prefix = []) => {
if (arr.length === 1) return [[...prefix, ...arr]];
return R.unnest(R.range(0, arr.length)
.map(i => permute(R.remove(i, 1, arr), [...prefix, arr[i]])))
};
const app = R.pipe(
() => R.range(1, 10),
R.map(i => R.reverse(R.range(1, i + 1).join(''))), // [1, 21, 321, ....]
R.reverse,
R.map(num => permute([...num])), // [[arr]]
R.unnest,
R.map(arr => parseInt(arr.join(''))), // [num]
R.filter(isPrime),
R.head,
);
app(); // -> 7652413
#042: 逆関数
単語のスコアが三角数になるものの個数。スコア計算の方法は略。ある数が三角数であるかの判定は、逆関数が整数になるか？で判定:
const fs = require('fs');
const score = ch => ch.codePointAt(0) - 'A'.codePointAt(0) + 1;
const scoreOf = word => R.sum([...word].map(score));
const isTriangle = n => (-1 + Math.sqrt(1 + 8 * n)) % 2 === 0;
const app = R.pipe(
() => '[' + fs.readFileSync('./words.txt') + ']',
JSON.parse,
R.map(scoreOf),
R.filter(isTriangle),
R.length,
);
app(); // -> 162
#043: zipWith
0...9までの数字を1度ずつ使った10桁の数で、上から2桁目からaperture(3)して生成される7つの3桁の整数がそれぞれ2, 3, 5, 7, 11, 13, 17で割り切れるものの総和。条件を満たす関数 isWanted 実装する際に、3桁の整数の配列と、割る数字の配列を突き合わせながら条件を満たすかを確認する。これは zipWithで実現できる。また、候補となる数字は 10! をメモリに持つのは難しいので、順列生成関数 permuteX の中で適宜刈り取りをしている。ジェネレータ + transduce という方向性の方がきれいだが、それは宿題。
const permuteX = (arr, prefix = []) => {
if (prefix.length === 1 && prefix[0] === 0) { // d0 must be nonzero
return [];
}
if (prefix.length === 4 && prefix[3] % 2 !== 0) {
return [];
}
if (prefix.length === 6 && prefix[5] % 5 !== 0) {
return [];
}
if (arr.length === 1) { // d10 must be odd.
return (arr[0] % 2 === 0) ? []: [[...prefix, ...arr]];
}
return R.unnest(R.range(0, arr.length)
.map(i => permuteX(R.remove(i, 1, arr), [...prefix, arr[i]])))
};
const isWanted = R.pipe(
R.tail, // ignore d0
R.aperture(3),
R.map(arr => parseInt(arr.join(''))), // -> ex. [406, 63, ....]
R.zipWith(R.flip(R.modulo), [2, 3, 5, 7, 11, 13, 17]),
R.all(R.equals(0)),
);
const app = R.pipe(
() => [...'0123456789'].map(R.unary(parseInt)),
permuteX,
R.filter(isWanted),
R.map(arr => parseInt(arr.join(''))),
R.sum,
);
app() // -> 16695334890
#044: 逆関数
和も差も五角数となる五角数のペアを考える。一番小さい差は。走査の上限を考える。何らかの方法で一つのペアが見つけて、その差を SUP としよう。この差よりも小さい差であるペアを探せばよいのだが、五角数同士の間隔は n が大きくなるとどんどん大きくなるので、ある n を超えると、隣接する五角数の間隔が SUP を超える。 この n を LIMIT と呼ぶと、これ以上大きい n に対しては走査する必要がない。これで走査上限が判明した。あとは、何とかして一つのペアを見つければよいのだが、これは、「自分より小さい五角数をペア候補にして検索する」、という操作を、五角数を少しずつ大きくしていけばよい。
function* pentagonals(end = Infinity) {
for (let i = 1; ; i += 1) {
const nextVal = i * (3 * i - 1) / 2;
if (nextVal >= end) return;
yield nextVal;
}
}
const isPentagonal = R.memoizeWith(R.identity,
n => (Math.sqrt(24 * n + 1) + 1) % 6 === 0);
const findPairs = pen1 => [...pentagonals(pen1)]
.map(pen2 => [pen1, pen2])
.filter(([p1, p2]) => isPentagonal(p1 + p2) && isPentagonal(p1 - p2));
const findFirstPairXform = R.compose(
R.map(findPairs),
R.dropWhile(R.isEmpty),
R.take(1),
);
const app = () => {
const SUP = (R.pipe(
() => R.into([], findFirstPairXform, pentagonals()), // [[pair]]
R.unnest, // [pair]
R.head,
([a, b]) => a - b,
)());
const LIMIT = Math.ceil((SUP - 1) / 3) + 1;
return (R.pipe(
() => R.into([], findFirstPairXform, pentagonals(LIMIT * (3 * LIMIT - 1) / 2)),
R.unnest, // -> [pair]
R.map(([a, b]) => a - b),
R.sortBy(R.identity),
R.head,
)());
};
app() // -> 5482660
#045: ジェネレータ
三角数かつ五角数かつ六角数で40755の次。六角数は必ず三角数なので、六角数ジェネレータから得た各数が五角数であるかをチェックすればよい
function* hexagonals(end = Infinity) {
for (let i = 1; ; i += 1) {
const nextVal = i * (2 * i - 1);
if (nextVal >= end) return;
yield nextVal;
}
}
const isPentagonal = R.memoizeWith(R.identity,
n => (Math.sqrt(24 * n + 1) + 1) % 6 === 0);
const app = R.into('', R.compose(
R.filter(isPentagonal),
R.dropWhile(x => x !== 40755),
R.take(2),
R.drop(1),
));
app(hexagonals()); // -> 1533776805
#046: ジェネレータ
奇数の合成数のうち、1素数と1平方数の2倍で表せれない最小の数。これまで作ってきた関数を使えば難しいものはない。
function* probablePrimes(end) { // -> 2, 3, 5, 7, 11, 13, 17, ...
yield 2;
yield 3;
yield 5;
for (let i = 1; ; i += 1) {
if (i * 6 + 1 >= end) break;
yield i * 6 + 1;
if (i * 6 + 5 >= end) break;
yield i * 6 + 5;
}
}
const isPrime = R.memoizeWith(R.identity, (n) => {
if (n < 0 || n === 1 || n === 4) return false;
if (n === 2 || n === 3 || n === 5) return true;
return R.reduce(
(_, x) => (n % x === 0 ? R.reduced(false) : true),
true,
probablePrimes(Math.ceil(Math.sqrt(n)) + 1),
);
});
function* primes(end = Infinity) {
for (let i = 2; i <= end; i += 1) {
if (isPrime(i)) yield i;
}
}
const isSquare = n => Math.sqrt(n) % 1 === 0;
const isDecomposable = pr => [...primes(pr)].some(pr2 => isSquare((pr - pr2) / 2));
function* input() {
for (let i = 3; ; i += 2) {
if (!isPrime(i)) yield i;
}
}
const app = R.into('', R.compose(
R.dropWhile(isDecomposable),
R.take(1),
));
app(input()); // -> 5777
#047: ジェネレータ
素因数が4つである連続した最小の4整数の最初の項。これまでの関数を使えば楽勝。入力は4つ組を返すジェネレータで実装し、条件を満たした段階で打ち切る。
const factorOf = R.memoizeWith(R.identity, (n) => {
if (n < 2) return [];
if (n % 2 === 0) return [2, ...factorOf(n / 2)];
const reduced = R.reduce(
(_, x) => (n % x === 0 ? R.reduced([x, ...factorOf(n / x)]) : null),
null,
R.range(3, Math.ceil(Math.sqrt(n)) + 1),
);
return reduced || [n];
});
const isWanted = n => R.all(R.pipe(factorOf, R.uniq, R.length, R.equals(n)));
const app = R.pipe(
R.into([], R.compose(R.filter(isWanted(4)), R.take(1))),
R.head, // first tuple
R.head, // first element of first tuple
);
function* input() {
for (let i = 0; ; i += 1) {
yield [i, i + 1, i + 2, i + 3];
}
}
app(input()); // -> 134043
#048: reduceRight
n^n (n=1,2,...1000)の総和の下10桁。桁あふれを考慮した掛け算および足し算を使う。
const mulRedL10 = n => (acc, digit) => {
const val = acc.kuri + digit * n;
const buf = [val % 10, ...acc.buf].slice(-10);
const result = { buf, kuri: Math.floor(val / 10) };
return (buf.length === 10) ? R.reduced(result) : result;
};
const mulL10 = (n, target) => {
const reduced = R.reduce(
mulRedL10(n),
{ kuri: 0, buf: [] },
R.reverse(target), // calc from last digit
);
if (reduced.kuri === 0) {
return reduced.buf.slice(-10);
}
const karr = [...reduced.kuri.toString()].map(R.unary(parseInt));
return [...karr, ...reduced.buf].slice(-10);
};
// Pow(n, n) [int] of size 10.
const calcL10 = (n) => {
const reduced = R.range(1, n + 1).reduce(acc => mulL10(n, acc), [1]);
return [...R.repeat(0, 10 - reduced.length), ...reduced];
};
const finalize = (digitSum, acc) => { // NOTE: check signature.
const val = acc.kuri + digitSum;
const buf = [val % 10, ...acc.buf].slice(-10);
return { buf, kuri: Math.floor(val / 10) };
};
const app = R.pipe(
() => R.range(1, 1001),
R.map(calcL10),
R.transpose,
R.map(R.sum),
R.reduceRight(finalize, { kuri: 0, buf: [] }),
obj => parseInt(obj.buf.slice(-10).join('')),
);
app(); // -> 9110846700
#049: groupBy
4桁の素数の三つ組みのうち、それぞれが等間隔に位置するとともに、互いに各桁の順序変更で重なり合うもののうち、1487を含まないものを小さい順に並べてつくる12桁の数。1000以上10000以下の素数を列挙して、各素数をそれらを構成する数字で groupBy して、いくつかのグループに分解する。これによりグループ内の素数は全て順序変更でかなさるようになる。グループの要素数が3以上の各グループにおいて、任意の二つを取り出し、そこから計算される等間隔の点に、自グループの数字があればそれが答えになる。
function* probablePrimes(end) { // -> 2, 3, 5, 7, 11, 13, 17, ...
yield 2;
yield 3;
yield 5;
for (let i = 1; ; i += 1) {
if (i * 6 + 1 >= end) break;
yield i * 6 + 1;
if (i * 6 + 5 >= end) break;
yield i * 6 + 5;
}
}
const isPrime = R.memoizeWith(R.identity, (n) => {
if (n < 0 || n === 1 || n === 4) return false;
if (n === 2 || n === 3 || n === 5) return true;
return R.reduce(
(_, x) => (n % x === 0 ? R.reduced(false) : true),
true,
probablePrimes(Math.ceil(Math.sqrt(n)) + 1),
);
});
function* primes(end = Infinity) {
for (let i = 2; i <= end; i += 1) {
if (isPrime(i)) yield i;
}
}
const findWanted = arr => (R.pipe(
() => R.range(0, arr.length - 1).map(i => R.range(i + 1, arr.length).map(j => [arr[i], arr[j]])),
R.unnest, // -> [[a, b]]
R.filter(([a, b]) => arr.includes(b + (b - a))),
)());
const groups = R.pipe(
() => [...primes(10000)].filter(x => x > 1000),
R.groupBy(n => R.uniq([...n.toString()].sort()).join('')),
R.toPairs(),
R.map(R.last),
R.filter(vals => vals.length > 2),
);
const app = R.pipe(
() => groups(),
R.map(findWanted),
R.unnest,
R.filter(pair => !pair.includes(1487)),
R.map(([a, b]) => [...a.toString(), ...b.toString(), ...(2 * b - a).toString()].join('')),
R.head,
);
app(); // -> 296962999629
#050: stateful transducer
連続する素数の和で表される 1e6 未満の素数のうち、その連続する素数列長が一番長いもの。まず走査範囲を求めよう。2,3, ... と素数を足していって初めて累計が 1e6 を超える際に足した素数列長 SUP を求める。求める素数の列長は絶対にこの数を超えない。また、ヒントにあるように最低でも 列長は21 あるので、求める素数の素数列の先頭は 1e6 / 21 を超えない。そこで、この数字より大きい素数から数えて 21番目の素数が、解の素数列末尾の上限 LIMIT となる。以上により、素数列構築のために走査する素数一覧と、上限となる列長がわかった。そこで、上限となる列長から徐々に減らしていくという考え方で解に至る。
function* probablePrimes(end) { // -> 2, 3, 5, 7, 11, 13, 17, ...
yield 2;
yield 3;
yield 5;
for (let i = 1; ; i += 1) {
if (i * 6 + 1 >= end) break;
yield i * 6 + 1;
if (i * 6 + 5 >= end) break;
yield i * 6 + 5;
}
}
const isPrime = R.memoizeWith(R.identity, (n) => {
if (n < 0 || n === 1 || n === 4) return false;
if (n === 2 || n === 3 || n === 5) return true;
return R.reduce(
(_, x) => (n % x === 0 ? R.reduced(false) : true),
true,
probablePrimes(Math.ceil(Math.sqrt(n)) + 1),
);
});
function* primes(end = Infinity) {
for (let i = 2; i <= end; i += 1) {
if (isPrime(i)) yield i;
}
}
const supFinder = num => (xf) => {
let count = 0;
let summed = 0;
return {
'@@transducer/step': (acc, x) => {
count += 1;
summed += x;
return summed > num ? R.reduced(true) : acc;
},
'@@transducer/result': () => count,
};
};
const isWanted = prs => isPrime(R.sum(prs)) && R.sum(prs) < 1e6;
const app = () => {
const SUP = R.into([], supFinder(1e6), primes());
const SUPPRIME = R.last(R.into(
[],
R.compose(R.dropWhile(x => x < Math.floor(1e6 / 21)), R.take(21)),
primes(),
));
const PRIMES = [...primes(SUPPRIME + 1)];
return R.head(R.into(
[],
R.compose(
R.map(n => R.aperture(n, PRIMES).filter(isWanted)),
R.filter(x => x.length !== 0),
R.take(1),
R.map(R.map(R.sum)), // convert to primes
R.map(R.head),
),
R.range(21, SUP).reverse(),
));
};
app(); // -> 997651
#051: Prime digit replacements
任意の複数の桁を同じ数字n (n=0,1,2...9)で置き換えてできる10の数のうち8が素数となるもので、最小の素数はなにか。置き換える場所の数は3の倍数である。もっというと、解が100万未満(7桁未満)であると仮定するならば置き換える箇所は3か所であると決まる（解が100万以下でなかったらその時考えるが、見つかったのでよしとする）。これはなぜかというと、置き換え部分の桁の和を N、それ以外の桁の和を M とおくと、置換箇所が3の倍数でない限り、10種類の置換で、 N は mod 3 で 0, 1, 2 をそれぞれ最低でも 3 回あたり、それにともない、 M + N mod 3 も 0, 1, 2 をそれぞれ最低でも 3 回あたるが、これは、少なくとも 3つが 3の倍数であることになり、題意に反するから。
上限と、置換箇所の個数が決まったのであとは素直に実装すればよい。
- 素数を小さい順に巡り
- 同じ数字が3回出てくる素数でなければスキップし、
- 同じ数字が 0, 1, 2 でなければスキップし、
- 同じ数字の箇所のうち3か所を選んで 0...9 で置換して題意を満たすかを確認して
- OKならそれが解
上記の手順で説明が必要なのは、 0, 1, 2 の時のみしかチェックしないというところだろう。置換により8の素数が生まれるので、少なくとも置換する数字には 0, 1, 2 が含まれるし、3, ...9 の場合は、上記の手順で巡る場合検討済みだから。
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/051.js
#052: Permuted multiples
1,2,3,4,5,6倍した数が全て同じ数字で構成されている数。5倍するので、元の数は必ず0もしくは5を持っていなければいけない、なので少し効率的に検索できる。それ以外のアルゴリズムに特記事項はない。
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/052.js
#053: Combinatoric selections
nCr (n=1,2,...100) が100万を超える項の数（重複は考慮しない)。真面目に計算すると桁あふれするので、計算上の工夫が必要。nを固定した際に r を増やしていき、初めて100万を超えたら、左右対称なので100万未満の項の数が同数あることになるので、100万以上の項の数もおのずと決まる。次の r の二項係数は漸化式 nCr+1 = nCr * n-r/r+1 を使って出せばよい。
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/053.js
#054: Poker hands
Player1が勝つ回数。ポーカーの手札を、以下の三つの情報でエンコードする
- 役 (例: フルハウス)
- 役の中での強さ (例: スリーカード部:3 ＋ペア部: 7
- 役以外の部分(キッカー) （例: フルハウスの場合存在しない)
今回は上記3つを文字列にエンコードした。文字列比較なので、A, T, J, Q, K をそれぞれ Z, V, W, X, Y に置換した。これにより、カードの強さが文字の強さになる。（文字では弱い順に23456789VWXYZ。
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/054.js
#055: Lychrel numbers
1万以下のLychrel numbersの数。考え方は簡単だけれども、なんども操作するうちに、数が桁あふれするので、それを考慮する必要がある
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/055.js
#056: Powerful digit sum
Pow(a, b) a,b <= 100 の各桁の和の最大数。これも桁あふれを考慮して計算するだけ
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/056.js
#057: Square root convergents
√2の連分数展開の際の最初の10000項のうち、分子の桁数が分母の桁すうを超えるものの数。これも桁あふれをするのでそれを考慮する必要がある。連分数展開の次の項は、漸化式を使うことで得られる
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/057.js
#058: Spiral primes
渦巻魔法陣の対角線上の素数分布が10%を下回る際の魔法陣の辺の長さ。解説不要
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/058.js
#059: XOR decryption
XORで暗号化された文字列を解読し、各文字のコード値の総和。パスワードが小文字3文字というヒントがあるので総当たりで行けばよい。解読成功条件は、 a, the を含む（注：両端にはスペースあり）としたところ、一意に決まった。
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/059.js
#060: Prime pair sets
5つ組のうち、任意の二つを選択してくっつけた数字が素数となるようなもので、組の数の総和が一番小さくなるもの。総当たりでやるしかない。とりあえず5つ組の素数全てが10000未満であると仮定しよう（みつからなかったら後で考える）。一つ目の素数 a を適当に選び、二つ目の素数 b を a < b の中で、くっつけて素数かを判定OK（以降判定と略）だったものを選び、三つ目の素数を b < c の中で、a, b 双方に対して判定OKのものを選び、、、、（以下略）。
5重ループになるので少しでも計算量を減らす必要がある。素数のうち、mod 3 が 1のグループと、2のグループに分けると、必ず、5つ組は同じグループ に存在することがわかる。もし違うグループだったらくっつけたら各桁の和が 0 mod 3 になり、3の倍数になってしまうので。
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/060.js
#061: Cyclical figurate numbers
4桁の整数の6つ組であり、その要素が、3,4,5,6,7,8角数からひとつづつ選んだものであり、かつ下二桁と上二桁がしりとりのようにつながり、かつ最後の下二桁が最初の上二桁とつながるようなものが一つある。その要素の総和。
4桁なので組み合わせはそれほど大きくない。まずは、3,4,5,6,7,8角数の4桁の一覧（ただし3桁目は0でない）を作る。一番要素数が少ない8角数から始めて、しりとりをする要領でつなげていき、最後に循環するかのチェックをすればよい。再帰構造となる。
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/061.js
#062: Cubic permutations
各桁を順列させて生成される整数の集合が（自身を含んで）ちょうど5個三乗数を含むような三乗数のうち最小のもの。
以下のような手順で簡単に求まる。ただし桁あふれするのでその対応をする。
- 1から順に以下を実施
- 三乗数を計算する
- 生成した三乗数の各桁をソートした文字列/数値 をキーとするハッシュに突っ込む
- そのキーのハッシュ長が5なら、そのハッシュの先頭が解になる
- ハッシュ長が5じゃないなら、ループの先頭に戻る
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/062.js
#063: Powerful digit counts
自身の桁数 nに対し、ある整数a が存在し、a ** n が自身に一致するという性質をもつ自然数はいくつあるか。
少し考えるとこのような数は非常に限られる。まず n の候補を考えよう。N 桁の任意の数 x に対して、x = a ** N なるa が存在するとすると、 10 ** (N-1) <= a ** N < 10 **N なる不等式が成立するが、これは、 (N - 1) / log(N) <= a < N/log(N) と同値変形できる。N <＝ 10 だとこのような a は存在する可能性はあるが、 n > 10 においては、この区間が1より小さくなってしまうので a は存在しえない。よって、 n = 1, 2, .... 10 を考えれば十分。
解の候補を探そう。イテレート数 a を1から順に大きくしていく。 a, a ** 2, a ** 3 ...a ** 10 の中で、題意を満たすものを列挙すれば解となる。イテレートをやめるのは、いつだろうか？これも分かり切った話で、 a < 10 である。なぜなら、 a > 10なる a に対して、 a は2桁以上だし、 a ** 2 は4桁以上であり、。。。。となるので題意を満たしようがないから。したがって、 a も 1..9 までで探せば十分。
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/063.js
#064: Odd period square roots
√N (N = 1, 2, ....10000)を連分数分解した際に、循環の長さが奇数である者の数。連分数の作成手順は、[0, 1) の数値 (B√N + C)/D から、[0, 1) の数値 (B'√N + C')/D' を作るゲームだと思えばよい。その際に項 A が出てくる。このように考えたときに数列 A, B, C, D の漸化式はちょっとした計算で出せる。ジェネレータで次々と (A, B, C, D) の四つ組を生み出していくのだが、以前と同じ四つ組が出てきたら、循環したと判断できるので、循環長がわかる。あとはコードに落とし込むだけ。途中で約分の作業が必要となるので、最小公約数の公式（ユークリッドの互除法）が必要になる。
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/064.js
#065: Convergents of e
eを連分数分解し、100桁で打ち切った時、近似値の分母の各桁を足した数。右端（というか連分数の末端）から順々にreduce していくだけなので簡単。 桁あふれがあるので注意。
コードは https://github.com/41semicolon/projectEulerRamda/blob/master/src/065.js