### March 3, 2020

Many of the tasks I publish on this blog come from beginning-programmer forums. Here is a task taken from some sort of entrance examination:

Jason rings every multiple of 13 less than 500. He then crosses every multiple of 17 less than 500. How many numbers get both ringed and crossed?

The test is a multiple-choice examination with possible selections 10, 0, 1 and 4. The solution sheet shows the correct answer is 4. The questioner who posted this question was asking how to calculate the answer given on the solution sheet.

And here is another simple task:

Given positive integer n < 1018, find the sum of the integers from 1 to n, mod 109 + 7. Assume you are using a language that provides 64-bit arithmetic, so no intermediate results can be larger than 264.

Your task is to write a program to solve these two tasks. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 8 Responses to “Two Easy Tasks”

1. Zack said

Yet another reason why multiple choice problems don’t make sense in a programming setting! Anyway, I got 2 or 3 too, depending on what the starting point is: 0, 221, and 442. Not sure what the creator of the problem was smoking, in order to come up with 4 as the correct answer, but I’m pretty certain it wasn’t over-the-counter stuff.
Cheers

2. Salvatore said

yeah i think like zack his wrong. 13 and 17 are prime… so their first common multipler is 221… and the 2nd 442. it’s impossible have 4 as result. cya.

3. Pascal Bourguignon said
```;; Jason rings every multiple of 13 less than 500. He then crosses every
;; multiple of 17 less than 500. How many numbers get both ringed and
;; crossed?
;;
;; The test is a multiple-choice examination with possible selections 10,
;; 0, 1 and 4. The solution sheet shows the correct answer is 4. The
;; questioner who posted this question was asking how to calculate the
;; answer given on the solution sheet.

;; So, basic fizz-buzz ;-)

;; But the QCM is wrong.  There is 2 or 3 solutions, depending on whether you count 0 or not.

(loop
for n below 500
when (and (zerop (mod n 13))
(zerop (mod n 17)))
sum 1)
;; --> 3

(intersection (remove-if (lambda (x) (>= x 500)) (mapcar (lambda (x) (* x 13)) (iota 500)))
(remove-if (lambda (x) (>= x 500)) (mapcar (lambda (x) (* x 17)) (iota 500))))
;; --> (442 221 0)

(loop for n below 500
for p = (factorize n)
when (and (find 13 (rest p) :key (lambda (factor)
(if (integerp factor)
factor
(second factor))))
(find 17 (rest p) :key (lambda (factor)
(if (integerp factor)
factor
(second factor)))))
collect p)
;; --> ((* 17 13) (* 17 13 2))

;; (This uses the library functions:
;;       com.informatimago.common-lisp.cesarum.list:iota
;;       com.informatimago.common-lisp.arithmetic.primes:factorize
;; )
;;
;; Probably the QCM answer was computed using permutations of 13 and 17
;; but not of the other factors! (* 13 17) (* 17 13) (* 13 17 2) (* 17 13 2)

;; And here is another simple task:
;;
;; Given positive integer n < 1e18, find the sum of the integers from 1
;; to n, mod 1e9 + 7. Assume you are using a language that provides
;; 64-bit arithmetic, so no intermediate results can be larger than 2^64.
;;
;; finished, you are welcome to read or run a suggested solution, or to
;; post your own solution or discuss the exercise in the comments below.

;;
;; The formula to compute the sum of integers between 1 and n is:
;;
;; Σ(i,1,n) = (/ (* n (+ n 1)) 2)
;;
(defun sum (n) (/ (* n (+ n 1)) 2))

(expt 2 64)
;; --> 18446744073709551616
(sum 1000000007001)
;; --> 500000007001500024510501
(mod (sum 1000000007001) 1000000007)
;; --> 1
(sum 999999999999999999)
;; --> 499999999999999999500000000000000000
(mod (sum 999999999999999999) 1000000007)
;; --> 1176
(sum 100000000000000000)
;; --> 5000000000000000050000000000000000
(mod (sum 100000000000000000) 1000000007)
;; --> 935000021

;; (log (expt 2 64) 10) -> 19.26592
;; therefore any 0<=n<1e18 can be represented on 64 bits.
;;
;; 1e18<(1e9+7)²<1e19
;; therefore (1e9+7)² can also be represented on 64 bits.
;;
;; Therefore a representant of n[1e9+7] * (n+1)[1e9+7] can be computed
;; using the integer multiplication, on 64 bits, and its modulo can be
;; computed on this intermediate result.
;;
;; n (n+1)
;; -------  [1e9+7]
;;    2
;;
;;   n[1e9+7] * (n+1)[1e9+7]
;; = ----------------------- [1e9+7]
;;             2

(defun msum (n modulus)
(mod (/ (* (mod n modulus) (mod (1+ n) modulus)) 2)
modulus))

(msum 1000000007001 1000000007)
;; --> 1

(msum 999999999999999999 1000000007)
;; --> 1176

(msum 100000000000000000 1000000007)
;; --> 935000021
```
4. Pascal Bourguignon said

Note: since the modulus is odd, we must divide by 2 before taking the final modulo, because even[odd] can give odd. But n[odd]*(n+1)[odd] will be even.

5. Daniel said

Here are two Python solutions to the first problem.

```from itertools import count, takewhile

def multiples_13_17_v1(n=500):
return [x for x in range(n) if x % 13 == 0 and x % 17 == 0]

def multiples_13_17_v2(n=500):
multiples_17 = takewhile(lambda x: x < n, (17 * x for x in count()))
return [x for x in multiples_17 if x % 13 == 0]

print(multiples_13_17_v1())
print(multiples_13_17_v2())
```

Output:

```[0, 221, 442]
[0, 221, 442]
```
6. Daniel said

Here’s a C solution to the second problem.

```#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

long task2(unsigned long long n) {
static unsigned long long m = 1000000007;
n %= m;
n *= n + 1;
n /= 2;
n %= m;
return (long)n;
}

int main(int argc, char* argv[]) {
assert(argc == 2);
unsigned long long n = strtoull(argv, NULL, 10);
return EXIT_SUCCESS;
}
```

Example:

```\$ ./a.out 1234567
78450694
```
7. Globules said

Here’s a Haskell version. Instead of relying upon 64-bit numbers I use typesafe modular numbers from the arithmoi library.

```{-# LANGUAGE DataKinds #-}

import Data.Maybe (fromJust)
import Math.NumberTheory.Moduli.Class
import Numeric.Natural

-- The size of the set of numbers in [1..n] that are divisible by both x and y.
easy1 :: Natural -> Natural -> Natural -> Natural
easy1 x y n = n `div` lcm x y

type M = Mod 1000000007

-- The sum of (1 + 2 + ... + n) mod 10^9+7.  Our use of invertMod depends on 2
-- and M being coprime.
easy2 :: M -> M
easy2 n = (n * (n + 1)) * fromJust (invertMod 2)

main :: IO ()
main = do
print \$ easy1 13 17 500
print \$ easy2 1000000007001
print \$ easy2 999999999999999999
print \$ easy2 100000000000000000
```
```\$ ./two_easy
2
(1 `modulo` 1000000007)
(1176 `modulo` 1000000007)
(935000021 `modulo` 1000000007)
```
8. Steve said

Klong version

```
:" Test each multiple of 17 to see if it's even divisible by 13"
l::[];{x<500}{[n];l:::[(_n)=n::x%13;l,x;l];x+17}:~0;l
[0 221 442]

:"Or grab them all and then isolate the ones that are divisible"
l::[];{x<500}{[n];l::l,(_n)=n::x%13;x+17}:~0;17*&l
[0 221 442]

{(_(x*(x+1)%2))!1000000000+7}@1234567
78450694

```