Project Euler #5

Community Support
1

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+til10;i:10;while[anyimodf;i+:1]; i2520

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

q)(anymod[;1+til10]@) (1+)/102520

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)(anymod[;1+til10]@) (P+)/P:prd23572520q)\ts:100(anymod[;1+til10]@) (1+)/102392064q)\ts:100(anymod[;1+til10]@) (P+)/P:prd235712848

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

q)\ts:100(anymod[;1+til20]@) (P+)/P:prd23571113171933168

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<>tiln:1+i:y?1b)}. / sieve next primees:raze@[;1;1+where@] {{x>lastfirsty}[floorsqrtx]snp/kcx}@ / Eratosthenes' sieve




q){(anymod[;1+tilx]@) (P+)/P:prdesx}102520
2

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