Programming Praxis

8 Responses to “Two Easy Tasks”

1. Zack said

   March 3, 2020 at 1:08 PM

   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

   March 3, 2020 at 4:20 PM

   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

   March 3, 2020 at 8:31 PM

   ;; 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.
   ;; 
   ;; 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.
   
   
   
   ;;
   ;; 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

   March 3, 2020 at 8:34 PM

   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

   March 7, 2020 at 9:26 PM

   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

   March 7, 2020 at 9:27 PM

   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[1], NULL, 10);
     printf("%ld\n", task2(n));
     return EXIT_SUCCESS;
   }
   

   Example:

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

   March 8, 2020 at 3:52 AM

   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

   March 24, 2020 at 6:23 PM

   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
   
   

Leave a Reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out /  Change )

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

Notify me of new comments via email.

Notify me of new posts via email.

Δ