Study Guide: Project Euler

Solutions

#1

Various solutions, all running in under one second:

RPL+

0 =sum

1 999 FOR i

i 3 mod 0 ==

i 5 mod 0 ==

or

IF THEN i =+sum END

NEXT

sum

or (RPL+ alt)

1000 3 5 → n a b ≪

--n

a b lcm =c

n n a mod - =na

n n b mod - =nb

n n c mod - =nc

'(na*((na/a)+1) + nb*((nb/b)+1) - nc*((nc/c)+1) )/2' EVAL

≫≫

or (closed-form, classic RPL)

1000 → n '((n-1)*(((n-1)/3)+1)+(n-5)*(((n-5)/5)+1)-(n-10)*(((n-10)/15)+1))/2' ≫

or (classic RPL)

0. 1. 999.

FOR I

IF I 3. MOD 0. ==

THEN I +

ELSE

IF I 5. MOD 0. ==

THEN I +

END

END

NEXT

or (JavaScript; fastest)

function () { /*as is*/

var sum = 0;

for (var i = 0; i<1000; i++)

if (i%3 === 0 || i%5 === 0)

sum += i;

return sum;

}

#2

0 =sum

1 1

DO

DUP ROT + =:val

IF val isEven THEN val =+sum END

UNTIL

val>4e6

END

DROP DROP

sum

#3

or (GolfScript/MorphEngine)

#4

-1 =r @ palindrome result

999 11 / floor 11 * =i

WHILE

i 100 >

i 999 * r > @ potential for bigger r?

and

REPEAT

100 999 FOR j

i j * →STR =s

1 =a s size =b

DO s[a] s[b] ++a --b

UNTIL ≠ =:cmp a b ≥ OR

END

IF cmp NOT THEN r i j * max =r END

NEXT

i 11 - =i

END

r

#5

1..20 vlcm ≫

or (using range)

1 20 range vlcm ≫

or (using fold operator)

1 20 range [lcm] fold ≫

or (using classic RPL commands)

1 20 range ≪ LCM ≫ STREAM ≫

or (GolfScript/MorphEngine)

21,tail{lcm}*

#6

1..100 =v

v total squared

v squared total

-

or (using classic RPL commands)

1 100 range =v

v ≪ + ≫ STREAM SQ

v SQ ≪ + ≫ STREAM

-

or (GolfScript/MorphEngine)

101,tail.{+}*SQSQ{+}*-

#7

1.1e5 primes 10001 at ≫

or (a bit slower)

2 1 10000 START NEXTPRIME NEXT≫

or (GolfScript/MorphEngine)

2{NEXTPRIME}10000*

#8

#8_data fromString split

5 ≪ * * * * ≫ DOSUBS

vmax

or (GolfScript/MorphEngine)

→{2{max}DOSUBS+}1-*

#8_data

"7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

#9

function () { /*as is*/

for (var a=1;a<500;a++)

for (var b=1;b<500;b++)

if (a*a+b*b == (1000-a-b)*(1000-a-b))

return a*b*(1000-a-b);

}

#10

2e6 primes total ≫

or

2e6 primes { + } STREAM ≫

or (JavaScript)

function () {

var sum = 0, p = primes(2e6);

for (var i=p.length-1; i>=0; i--)

sum += p[i];

return sum;

}

or (GolfScript/MorphEngine)

2000000primes{+}*

#11

#11_data =m

0 @ max product kept on stack

m

m transpose concat

m diagonals concat

m flip diagonals concat

1

≪ 4 [ * * * MAX ] DOSUBS ≫

DOSUBS

#11_data

[[8,2,22,97,38,15,0,40,0,75,4,5,7,78,52,12,50,77,91,8],[49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,0],[81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65],[52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,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,3,45,2,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,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21],[24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],[21,36,23,9,75,0,76,44,20,45,35,14,0,61,33,97,34,31,33,95],[78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92],[16,39,5,42,96,35,31,47,55,58,88,24,0,17,54,24,36,29,85,57],[86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58],[19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40],[4,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66],[88,36,68,87,57,62,20,72,3,46,33,67,46,55,12,32,63,93,53,69],[4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36],[20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36,16],[20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54],[1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48]]

#12

1 =counter

0 =num

DO

counter =+num

++counter

UNTIL

ndivs(num)>500

END

num

#13

#13_data

total →STR 1 10 SUB STR→

#13_data

function () {

var data = requestURL("http://naivedesign.com/redist/PE_13_data.txt").split("");

return data.map(function(x){return BigNum.fromString(x);});

}

#14

function () { /*as is*/

var longest = 0, index = 0;

var cache = []; cache[1] = 0;

for (var i=2; i<1e6; i++) {

var cur = i, steps = 0;

while (cur != 1 && cur >= i) {

cur = (cur % 2 ? (3*cur+1) : (cur/2));

++steps;

}

if (cur < i)

steps += cache[cur];

cache[i] = steps;

if (steps > longest) {

longest = steps;

index = i;

}

}

return index;

}

or (in RPL+)

0 =longest

[] =cache @ length of chain at num

0 =cache[1] @ length for num 1

2 1e6 1 - FOR i

i

0 =steps

DO

IF DUP isEven

THEN 2 / ELSE 3 * ++ END

++steps

UNTIL

DUP =:cur i <

END

DROP

cache[cur] =+steps

steps =cache[i]

IF steps longest >

THEN steps =longest i =index END

NEXT

index

#15

20 → x 'round((x*2)!/(x!^2), 0)' ≫

or

20 → x ≪ x 2 * ! x ! 2 ^ / 0 RND ≫≫

#16

2 1000 →big ^ split total ≫

#18

#18_data OBJ→

2 SWAP START

2 ≪ MAX ≫ DOSUBS

+

NEXT

or (GolfScript/MorphEngine)

→{2{max}DOSUBS+}1-*

#18_data

[75,[95,64],[17,47,82],[18,35,87,10],[20,4,82,47,65],[19,1,23,75,3,34],[88,2,77,73,7,63,67],[99,65,4,28,6,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,4,68,89,53,67,30,73,16,69,87,40,31],[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]

#19

floor(12*100/7) ≫

#20

100 ! split total ≫

or (ignorant of split and total, using a loop)

100 ! →STR =s

0 =sum

1 s SIZE FOR i

s[i] STR→ =+sum

NEXT

sum

or (using list processing)

100 ! →STR

split

{ STR→ }  MAP

{ + } STREAM

#21

function () {

function isAmicable(a) {

function d(n) {

var divs = calculator.functions.divs(n);

divs.pop();

return calculator.functions.vector.total(divs);

}

var b = d(a);

return (b != a && d(b) == a);

}

var sum = 0;

for (var i=2; i<10000; i++)

if (isAmicable(i))

sum += i;

return sum;

}

#22

#22_data { →STR } MAP

SORT

split

1 { NSUB SWAP

1 { NUM 64 - } DOSUBS

total *

} DOSUBS

total

#22_data

function () {

var data = requestURL("http://projecteuler.net/project/names.txt");

return eval("(" + "[" + data + "]" + ")");

}

#23

function () { /*as is*/

var F = calculator.functions;

var abundants = [];

for (var i=1; i<28123; i++)

if (F.vector.total(F.divs(i)) > i*2)

abundants.push(i);

var count = abundants.length;

var arr = [];

for (var i=0; i<count; i++)

for (var j=0; j<=i; j++)

arr[abundants[i]+abundants[j]] = true;

var sum = 0;

for (var i=0; i<28123+1000; i++)

if (!arr[i]) sum += i;

return sum;

}

#24

"2" "013456789" permutate 1e6-9!*2 at + fromString ≫

#25

Closed-form solution

ceil((1000-1+log(√5))/log((1+√5)/2)) ≫

or (using evaluation of traditional algebraic expression; note; spaces allowed in expression)

'ceil((1000-1+log(√5)) / log((1+√5)/2))' EVAL≫

or (brute-force; very slow)

1 =count

0 1 →big

DO

DUP ROT +

++count

UNTIL

DUP →STR size 1000 >=

END

DROP DROP

count

#28

1001 → n '(4*n^3+3*n^2+8*n-9)/6'≫

#29

2 100 FOR a

2 100 FOR b

a b ^

NEXT

NEXT

99 99 * fromElements

removeDuplicates

size

#30

0 =sum

10 200000 FOR i

i split DUP SQ SQ * total

IF i == THEN i =+sum END

NEXT

sum

#33

function () {

var r = new Fraction(1);

for (var i=12; i<=99; i++) {

var n = split(i);

for (var j=i+1; j<=99; j++) {

var d = split(j);

if (n[1]==d[0] && i/j == n[0]/d[1])

r=r.multiply(new Fraction(i,j));

}

}

return r;

}

or (in RPL+)

whole =r

12 99 FOR i

i split =n

i 1 + 99 FOR j

j split =d

IF n[2] d[1] == THEN

IF i j / n[1] d[2] / == THEN

i j →fract =*r

END

END

NEXT

NEXT

r

#34

0 =sum

10 50000 FOR i

i split ! total

IF i == THEN i =+sum END

NEXT

sum

#40

function () { /*as is*/

var s = "", p = 1;

for (var i=1; s.length<1e6; i++)

s += i;

for (var i=0; i<7; i++)

p *= s[Math.pow(10, i)-1];

return p;

}

#41

123456 permutate rsort =p

1 p size FOR i

p[i] 7000000 + =:x isPrime IFTB

NEXT

x

#42

#42_data { →STR } MAP

split

1 {

{ NUM 64 - } MAP

total

8 * incr √ decr 2 / @ inv triangle

fract not { true } IFT

} DOSUBS

size

#42_data

function () {

var data = requestURL("http://projecteuler.net/project/words.txt");

return eval("(" + "[" + data + "]" + ")");

}

#47

1 =c false =foundIt

DO

c factors size

IF 8 == THEN c 1 + factors size

IF 8 == THEN c 2 + factors size

IF 8 == THEN c 3 + factors size

IF 8 == THEN true =foundIt END

END END END

++c

UNTIL foundIt

END

c decr

#48

Classic RPL

1e10 R→I MODSTO

0

1 1000 FOR i

i R→I DUP POWMOD +

NEXT

1e10 R→I MOD

#53

0 =count

23 100 FOR n

3 n 3 - FOR r

n r COMB

IF 1e6 > THEN ++count END

NEXT

NEXT

count

#56

0 =m

80 100 FOR a

80 100 FOR b

a b toBigNum ^ split total

m max =m

NEXT

NEXT

m

#57

0 =count

big0 =p0

big1 =p1

1 1000 START

big2 p1 * p0 + =:p @ Pell number

p1 + =:n @ numerator

IF size p size > THEN ++count END

p1 =p0

p =p1

NEXT

count

or (in JavaScript; note: same speed)

function () {

var sum = 0;

var p0 = big0, p1 = big1;

for (var i=0; i<1000; i++) {

var p = BigNum["+"](BigNum["*"](big2, p1), p0); // Pell number

var n = BigNum["+"](p, p1); // numerator

if (String(n).length > String(p).length)

++sum;

p0 = p1; p1 = p;

}

return sum;

}

#63

0 =sum

1 9 FOR i

'floor(1/(1-log(i)))' EVAL =+sum

NEXT

sum

#64

2..10000

[toSqrtCF period isEven not] map

total

#67

#67_data OBJ→

2 SWAP START

2 ≪ MAX ≫ DOSUBS

NEXT

V→

#67_data

function () {

var data = requestURL("http://projecteuler.net/project/triangle.txt").split("");

data.pop(); // remove empty row

return data.map(function(x){return x.split(" ").map(function(x){return +x;});});

}

#69

function () {  /*as is*/

var M = 1000001;

function phi(x) {

if(x <= 1) return 1;

var f = fact[x];

if(f == 1) return x-1;

var p = 1, fp = 1;

while((x /= f) % f == 0) { p++; fp *= f; }

return phi(x)*(f-1)*fp;

}

var fact = [];

for(var i=0; i<M; i++) fact[i]=1;

for(var i=2; i<M; i++)

if(fact[i]==1)

for(var k=i+i; k<M; k+=i) if(fact[k]==1) fact[k]=i;

var mn, mx = 0;

for(var n=2; n<M; n++) {

var val = n/phi(n);

if (val > mx) { mx = val; mn = n; }

}

return mn;

}

#71

1e6 → n 'int((n-5)/7)*3+2' ≫

#72

function () {  /*as is*/

var M = 1000001;

function phi(x) {

if(x <= 1) return 1;

var f = fact[x];

if(f == 1) return x-1;

var p = 1, fp = 1;

while((x /= f) % f == 0) { p++; fp *= f; }

return phi(x)*(f-1)*fp;

}

var fact = [];

for(var i=0; i<M; i++) fact[i]=1;

for(var i=2; i<M; i++)

if(fact[i]==1)

for(var k=i+i; k<M; k+=i) if(fact[k]==1) fact[k]=i;

var s = 0;

for(var i=2; i<M; i++) s += phi(i);

return s;

}

or (in RPL+)

2..1e6 phi total ≫

#76

(Requires the Number Theory shared folder, which defines “p”, a function to compute the number of partitions of an integer)

100 NT.p 1 - ≫

or (using immediate algebraic expression syntax)

NT.p(100)-1 ≫

#77

function () {

function part(a, b) {

if (a == 0)

return 1;

else if (a < 0 || b == 0)

return 0;

else return (part(a, b-1) +

part(a-ps[b], b));

}

var ps = primes(5000);

ps.unshift(0);

var i=1;

while (part(++i, ps.length-1) <= 5000)

;

return i;

}

#80

1..100 squareFree

99 setBigFPrecision toBigF √ split

[total] MAP

total

or (not using array processing, but a regular loop)

99 setBigFPrecision

0 =sum

1 100 FOR i

IF i √ fract THEN

i toBigF √

split total =+sum

END

NEXT

sum

or (using ContinuedFraction)

99 setBigFPrecision

0 =sum

1 100 FOR i

IF i √ fract THEN

i toSqrtCF @ convert to CF

toNumber @ get decimals

split @ into array of digits

total =+sum

END

NEXT

sum

#87

50e6 √ primes =p

p SQ =p2

p2 p * 75 resize =p3

p2 SQ 25 resize =p4

p2 p3 [+] combine [ 50e6 <= ] filter

removeDuplicates =p23

p23 p4 [+] combine [ 50e6 <= ] filter

removeDuplicates

size

#97

2 7830457 1e10 modpow 28433 * 1 + 1e10 mod ≫

#100

1 =:x =y

WHILE y<1e12

REPEAT

x =xx

3*x+2*y-2 =x

4*xx+3*y-3 =y

END

x

#102

#102_data

≪ V→ →V2 =a →V2 =b →V2 =c

a b cross last sign =s

b c cross last sign s ==

c a cross last sign s == and ≫ MAP

total

#102_data

function () {

var data = requestURL("http://projecteuler.net/project/triangles.txt").split("\r\n");

data.pop(); // remove empty row

return data.map(function(x){return x.split(",").map(function(x){return +x;});}

);

}

#119

[]

2 =a DO

2 10 FOR b

a b ^ =:val

split total a == { val + } IFT

NEXT

++a

UNTIL DUP SIZE 31 ==

END

sort

30 GET

#120

0 =sum

3 1000 FOR a

a DUP isEven { 2 - } { 1 - } IFTE

a * =+sum

NEXT

sum

or

0 =sum

3 1000 FOR a

a^2-(2-mod(a,2))*a =+sum

NEXT

sum

#123

300e3 primes DUP ≪ =p

2*N*p>1e10

≫ 7038 =offset find pos ++

#124

1..100000 DUP

2 [ @tag ] DOLIST

sort

10000 at tag

#131

1e6 =top

0 =sum

1 top FOR n

3*n*n+3*n+1 =:n top >= IFTB

n isPrime =+sum

NEXT

sum

#188

8 =nDigits

1777 toBig =base

1855 =expo

10 toBig nDigits pow =m

base

1 expo-1 START

base @swap m modpow

NEXT

Overview

This guide presents a number of solutions to Project Euler problems, in three languages supported by ND1 and upcoming MorphEngine calcs: RPL+, JavaScript, GolfScript/MorphEngine.

Most solutions have been developed in RPL+. This guide is recommended if you want to pick up the language.

For several problems, solutions in more than one language, or taking different approaches, are shown. Run-times are reported for each, so you can see how they compare speed-wise. Note that a variety of styles are explored in these solutions. Many more variations are possible. (RPL+ can look like RPN or algebraic notation, for example.)

Run-times for CalcPad/Mac, an upcoming product that will allow WiFi folder sharing with ND1, are also included. This is to give you an idea of how MorphEngine performs on a desktop system.