Project Euler #5

[SJT]

5. Smallest multiple

https://projecteuler.net/problem=5

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

Solve

Start by reproducing the example. 10 is the smallest candidate. Start with 10 and keep incrementing; as long as any mod 1+til 10

A while-loop will do the job.

q)f:1+til 10; i:10; while[any i mod f; i+:1]; i
2520

We can write the same in functional form using the While form of the Over iterator, with a composition as the truth function.

q)(any mod[;1+til 10]@) (1+)/10
2520

Improve

But we don’t need to test every number. A number evenly divisible by 1+til 10 must be evenly divisible by each of the primes in that list, i.e. 2 3 5 7, and must therefore be divisible by their product P. We can start with P, and test multiples of it.

q)(any mod[;1+til 10]@) (P+)/P:prd 2 3 5 7
2520

q)\ts:100 (any mod[;1+til 10]@) (1+)/10
239 2064
q)\ts:100 (any mod[;1+til 10]@) (P+)/P:prd 2 3 5 7
1 2848

With the numbers from 1 to 20, P becomes 9699690, and the search takes very little longer.

q)\ts:100 (any mod[;1+til 20]@) (P+)/P:prd 2 3 5 7 11 13 17 19
3 3168

Generalise

For a number N we need the primes below it. Enter Eratosthenes’ Sieve.

kc:{(1#2;0b,1_x#10b)}                                             / (known primes; flag candidates)
snp:{(x,n;y&count[y]#i<>til n:1+i:y?1b)}.                         / sieve next prime
es:raze@[;1;1+where@] {{x>last first y}[floor sqrt x] snp/kc x}@  / Eratosthenes' sieve

q){(any mod[;1+til x]@) (P+)/P:prd es x}10
2520

[cillianreilly]

Another method for this problem. We can construct the smallest multiple by iterating through a list of numbers up to the target. At each step, we multiply by the next number and divide out the greatest common divisor.  The Euclidean algorithm is an efficient method of finding the gcd.

q)gcd:{first last({y,x mod y}.)/(x;y)}
q)f:{{7h$(x*y)%gcd[x;y]}/[reverse 1+til x]}
q)f each 10 20
2520 232792560

 This method is comparable in speed for 10 and 20, but is an improvement for larger inputs.

q)f1:{(any mod[;1+til x]@) (P+)/P:prd es x}
q)\ts:100 f 10
4 848
q)\ts:100 f1 10
3 960
q)\ts:100 f 20
8 976
q)\ts:100 f1 20
9 1472
q)\ts:100 f 30
12 976
q)\ts:100 f1 30
110 1472
q)\ts:100 f 42
22 1232
q)\ts:100 f1 42
218 2496