2022.10.27 06:38 AM - edited 2022.10.27 06:39 AM
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?
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
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
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
2022.10.27 10:12 PM - edited 2022.10.27 10:17 PM
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
EMEA
Tel: +44 (0)28 3025 2242
AMERICAS
Tel: +1 (212) 447 6700
APAC
Tel: +61 (0)2 9236 5700
KX. All Rights Reserved.
KX and kdb+ are registered trademarks of KX Systems, Inc., a subsidiary of FD Technologies plc.