Project Euler

Table of Contents

Mostly in pursuit of practice in and the shilling of J. Also probably a place to notate useful idioms that pop up.

Friend Key: 1192827_7FygK15NhrFABu30oD3SXl346yWNtTU6

Problem 659

Define \(P(k)\) to be the largest prime such that \(p | n^2 + k^2\) and \(p | (n+1)^2 + k^2\).

Subtracting gives that \(p | 2\cdot n+1\). So, \(n \equiv \frac{p-1}{2}\). Substituting gives that \[ 0 \equiv \Big (\frac{p-1}{2}\Big)^2 + k^2 \equiv 1 + 4\cdot k^2 \] So, the solution is a matter of finding the largest divisor of \(1 +4\cdot k^2\) for the interrogated \(k\). 

M | +/ (M=.10^18) | ({:@q:) (1+4**:) 1+i.100

Problem 202

Equilateral billiards, description to come. 

W =: (3|-) + (*&3) @: i. @: <. @: (%&6)
E =: 2 * +/ @: (1 = (+. W)) @: ([: <. 0.5 * 3&+)
E 1000001

Problem 153

OK. So, key observation, I think, is the following. Let \(a+bi\in \mathbb{Z}[i]\) with \(a\perp b\) and let \(n\) have \(a+bi\) as a factor. Then \[\frac{n}{a+bi}=\frac{n\cdot (a-bi)}{a^2+b^2}\implies a^2+b^2 \mid n.\]

Numbers \(k \cdot (a+bi)\cdot (a-bi)\) for \(1\le k\le \frac{N}{a^2+b^2}\) bring us all contributions from this base pair. Which add \(2\cdot a\cdot \sigma_1(k)\), where \(\sigma_1\) is divisor sum function, to the overall calculation. 

dsum=: +/@:((]*[:<.%)(>:@i.)) M.

e153=: 3 : 0
A=. (dsum y) + +: dsum <.y%2 [ a=. 1
while. a <: <.%:-:y do. hi=. <.%:y-*:a [ b=. a+1
  while. b <: hi do.
    if. 1=a+.b do. A=. A + +: (a+b) * dsum <. y % a +&*: b
    end. b =. >: b
  end. a =. >: a
end. A
)

e153 100000

Problem 97

Large non-mersenne prime. Mersenne primes have form \(M_p = 2^p - 1\) for prime \(p\). Find the last 10 digits of \(28433×2^{7830457}+1\). 

M | 1 + 28433 * 2 (M=. 10x^10)&|@^ 7830457

Problem 95

Amicable chains are sequences whose divisor sums repeat. This finds them by indexing repeatedly into an array of divisor sums. 

DS =: (*//.~ (* %&<: ]) ~.)&.q:
I =: 1 : '[: /:~ [: ~. u {~ (#~ <:&(#u))'
C =: 1 : 0
n =. 1 [ c =. y{u
while. y ~: c do. n =. >: n [ c =. c{u end. n
)

({~ (i. >./) @: (G C"0)) G I^:_ i. # G=. 0,(-~DS) >: i. 1000000

Problem 72

Like Problem 71, but asks for how reduced fractions there are with denominator \(\le 10^6\) It's tempting to enumerate farey sequences, but this can also just be boiled down to \(\Phi(n)\). 

+/ 5 p: 2+i.1e6-1

Problem 71

In set of reduced fractions with denominator \(d\le 10^6\), what's the fraction to the left of \(\frac{3}{7}\)? To get terms in Farey sequence, we just take fractions \((\frac{a}{b},\frac{c}{d}) \mapsto \frac{a+b}{c+d}\). From the input we see that \(\frac{2}{5}\) is a neighbor of \(\frac{3}{7}\) and we keep iterating until this process would exceed the limit. 

{. (+/@:(,:&3 7)) ^: ((1e6-7) > {:) ^: _ (2 5)

Problem 67

>./ (+ 2 >. /\ ],0:)/ ".;._2 ] 1!:1 < 'p067_triangle.txt'

Problem 54

Rank 5-card poker hands. The trick is to give an ordering to the types of hands that matches how J sorts arrays, while keeping enough information to break ties on equal type hands. Verb K classifies various pair types of hands based on the result of key /.. Straights and flushes are similarly classified, with two bits to determine if a hand is a stright flush or a high card or if we have pairs to pass to K. 

rank=: _2&(34 b.)
suit=: 3&(17 b.)
K =: ((5#1);(2,3#1);(1,~2#2);(3,2#1);'S';'F';3 2;4 1;'SF') i. [: < #/.~

ORD =: \: ((,.~ [: +/"1 (=/~)) @: rank)
OST =: ]`(}.,13-~{.)@.(12 3-:2&{.)

S =: ((4={.-{:)+.(12 3-:2&{.))*.([:-.[:=/2&{.)
F =: 1=#@(#/.~suit)
SF =: S@] + [: +: F@[
H =: ((,~K)@]`(4,OST@])`(5,])`(8,OST@])@.SF rank)@:ORD
WIN =: (([: <: [: +: [: (-: /:~) ;)`0:@.-:)&H

in =. 1!:1 < 'p054_poker.txt'
hands=: ([: (('CDHS'i.{:) + 4*'23456789TJQKA'i.{.) ;._2 ' ',~]) ;. _2 in
]e54=: +/ (_1 = 5&{. WIN 5&}.)"1 hands

Problem 49

Find sequence of 4 primes whose digits are permutations of each other and are in arithmetic sequence together. 

combo=: 4 : 0
z=. (d$<(0,y)$0),<,:y#0[k=. <"1 (-i.1+d=.y-x)|."0 1 y{.1
for. i.x do. z=. k (+."1)&.> ,&.>/\. (_1&|."1)&.> z end. ; z
)
ps =: 1000 + I. 1 p: 1000 + i. 9000
good =: (#~ (=/ @ (2 -/\ ]))"1) @ ({~ [: I. 3 combo #)
; ":"0 {: ; good &.> (#~ 2<# &>) (</.~ /:~ @ (10 10 10 10&#:)"0) ps

Problem 48

Last 10 digits of \(\sum i^i\) for \(1\le i\le 1000\) 

M | +/ (M&|@^~) 1 + i. 1000 [ M=: 10^10x

Problem 46

Find the smallest odd composite which is the sum of a prime with twice a square (Goldbach's other conjecture). 

ps =: 1 p: i. 10000
qs =: ((= <. &. %:)@-:) i. 10000
{.(#~1&<*.2&|)I.1-ps +. 10000 {. ps +.//. @ (*./) qs

Problem 35

Circular primes are primes where all digit rotations are also prime. How many below 1,000,000? 

primes=: i. &. (p: ^: _1)
rots=: ($ ]\ <:@+:@$ $ ]) &. (10&#.^:_1)
+/ ([: *./ [: ; 1 p: rots)"0 primes 1000000

Problem 31

coins=: 1 2 5 10 20 50 100 200
count=: 4 : 0
A =. 1,y$0 
for_c. x do. for_j. i.&.(-&c) 1+y do. A=. A j}~ +/ A{~j,j-c end. end.
)

{: coins count 200

Problem 30

<: +/ I. (= +/"1 @ (^&5) @ (10 10 10 10 10 10&#:)) i. 10^6

Problem 29

#~.,^/~ 2x+i.99

Problem 26

Period \(l\) of expansion of \(\frac{1}{r}\) will divide \(l\mid \phi(r)\). It will exactly equal it when 10 is a primitive root in \(\mathbb{Z}^\times_{r}\). Best candidates are primes, so the task boils down to finding the largest prime \(< 1000\) such that 10 is a primitive root. 

prim=: (% 3&p:) @ (5&p:)
cycl=: 3 : '1 < <./ 10 (y&|@^) prim y'
{: (#~ cycl"0) i. &. (p:^:_1) 1000

Problem 25

lim=. >. (-:>:%:5) ^. (10x^1000)
1000 I.~ (#@":)"0 {:"1 (1 1,:1 0)&(+/ . *)^:(i.lim) 1 0x

Problem 24

999999 A. '0123456789'

Problem 23

DS =: (*//.~ (* %&<: ]) ~.)&.q:
+/ I. 28124 {. 1 - * (+//. @(*/))~ 0,(< (-~ DS)) 1+i.28123

Problem 21

I think I have slightly improved on a way to list all divisors of a number from my previous tries. The idea is to list all prime factors 3&p:, group them together /., append 1, and scan multiply */\. For example if \(8 \mid n\) then there will be a box <1 2 4 8. Next step is taking a cartesian product { of all these factors to get all combinations \(\prod_i p_i^{k_i}\) where \(k_i \le \alpha_i\) for \(n = \prod_i p_i^{\alpha_i}\).

Amicable numbers are found by comparing results from two applications of divisor sum divs ^: 1 2 to the input and seeing if there's exactly 1 match (if y = divs y then it must be that y = divs^:2 y as well). 

grpp=: ([:<[:*/\ 1,])/.~
divs=: (-~ [: +/ */&> @: , @: { @: grpp @: (3&p:))
amic=: (1 = +/) @: (= divs ^: 1 2)"0
+/ 2 + I. amic 2+i.9999

Problem 20

+/ 10#.^:_1 ! 100x

Problem 18

Through a reduction /, collapse the right row by taking maxes >. of consecutive numbers 2>./\]. pad that with 0 to keep sizes matching and add to left row. answer will be at head {. 

tri=: ".;._2 ] 0 : 0
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
)
{. (+ 2 >./\ ],0:)/ tri

Problem 16

Sum the digits of \(2^{1000}\) 

+/ 10#.^:_1 (2^1000x)

Problem 15

Number of paths from corner to corner in a 20x20 grid (only going up/right) 

20 ! 40

Problem 14

Should come up with a nicer solution… 

mem=:0,1,999998 $_1
collatz=:(-:`([: >: 3&*))@.(2&|)
chain=: 3 : 0
if. 1000000<:y do. 1 + chain collatz y
elseif. 0 <: y{mem do. y{mem
else. l [ mem=:l(y})mem [ l=.1+chain collatz y
end.
)
mem i. >./ chain"0 i. 1000000

Problem 13

Would be included but these horrible inputs are cramping J's style. Pretend the 50 digit number is an array of 100 50 digits numbers parsed in the same way as problems 8 or 11. The program wouldn't change. Find first 10 digits of sum of numbers is the task 

;(":"0) 10{. 10#.^:_1 +/ 91942213363574161572522430563301811072406154908250x

Problem 12

Find the first triangular number with 500 divisors 

divs=: [:*/1+[:1&{2&p: [ tri=:(*>:)%2:
x: tri (>:^:(500&>@divs@tri)^:_) 1

For me p: is one of those verbs that's hard to remember what all the options do. By options I mean how \(x\) in dyadic usage modifies the behavior. 

2 p: 140

So, 2&p: lists prime factors in first row with multiplicities in second. We can count divisors by adding 1 to multiplicities then taking the product. The control flow uses one of J's looping idioms to apply function increment >: if there aren't enough divisors of the \(y^\text{th}\) triangular number. This reaches a fixpoint when the function doesn't get applied via ^:_, so it is a kind of while-do analogue.

Problem 11

Find the largest product of 4 numbers up down left right or diagonal 

G=: }. ([: , [: ". ;._1 ' ',]) ;. _2 LF , 0 : 0
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
)
>./ (,4*/\G),(,4*/\|:G),(,(4*/\])/.G),(,(4*/\])/.|.G)

Problem 10

Sum up the primes \(\le 2000000\) 

bonsai '+/ i.&.(p:^:_1) 2000000'

Problem 9

find \(a\cdot b\cdot c\) for the only pythagorean triple such that \(a+b+c=1000\) 

e9=: 3 : 0
y_3=.<.y%3 [ y_2=.>.y%2
for_c. y_3+i.y_2-y_3 do. c_2=. <.c%%:2
  for_a. 1+i.c_2 do. b=. %: (c (- & *:) a)
    if. (b-:<.b) *. (y-:a+b+c) do. y=. a*b*c return. y end.
  end.
end.
)

x: e9 1000

Problem 8

Find the largest possible product of 13 consecutive digits of the following 1000 digit number 

>./ 13 */\ , "."0 ;. _1 LF,0 : 0
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
)

Problem 7

10001th prime (10000 below because of 0 indexing) 

p: 10000

Problem 6

For \(1, \dots, 100\) find the difference between the square of the sum and the sum of the squares? 

(*:@:(+/) - +/@:*:) 1+i.100

Problem 5

Find the smallest number evenly divisible by \(1, \dots, 20\) 

*./ 1+i.20

Problem 4

>./ps{~I. ((-:|.)@:(10&#.^:_1))"0 ps=.~.,*/~(100+i.900)

Problem 3

Find the largest prime factor of \(600851475143\) 

>./ 3 p: 600851475143

Problem 2

Sum the even fibonacci numbers under \(4000000\) 

+/ (#~ 0=2&|) }:{:"1 (4000000<.(1 1,:1 0)&(+/ . *))^:a: 1 0

Problem 1

Sum the numbers that are multiples of 3 or 5 below 1000 

+/ I. +./ 0 = 3 5 |/ i. 1000

Created: 2021-01-15 Fri 13:45

Validate