## Two Easy Tasks

### 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< 10^{18}, find the sum of the integers from 1 ton, mod 10^{9}+ 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.

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

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.

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.

Here are two Python solutions to the first problem.

Output:

Here’s a C solution to the second problem.

Example:

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

Klong version