Modulus Problem

Mar 2012
566
29
Choose three integer numbers x, y, and z = c, respectively, where x>=1, y>=1, and z >=1 to get (a, b) pairs. The condition is (1<=a<=x, 1<=b<=y) where [ (a + b) % c = 0 ] , a and b are integer numbers.

Note: % is modulus

For example: x = 10, y = 5, z = 2
answer = 25 pairs

I will show a few pairs, (1,1), (1,3), (5,1), (7,3)…..etc

I got the answer using two loops in java programming language. This way is not effective when you use large numbers. It takes a lot of time to get the answer. Therefore, I tried to create a formula.

I discovered that when I do this xy / z, I get an approximate answer for large numbers while most of the time I get same answer for small numbers.

For example: x = 70001, y = 6022, z = 316
xy / z = (70001)(6022)/(316) = 1334006 but the correct answer = 1333997 exact pairs


Is there another formula that gives me exact pairs?
 
Last edited:
Jun 2013
1,127
601
Lebanon
Try this. I don't know if this formula can be simplified or whether this is an efficient way of solving the problem

\(\displaystyle \sum _{a=1}^x \left(\left\lfloor \frac{a+y}{z}\right\rfloor -\left\lceil \frac{a+1}{z}\right\rceil +1\right)\)
 
  • Like
Reactions: joshuaa
Mar 2012
566
29
for x = 10, y = 5, and z = 2, the formula give 30, but the answer is 25
 
Mar 2012
566
29
wOW man. your formula is working perfectly so far, even for large numbers. Its speed is also fabulous. How did you attack the problem to create that magic formula?

at first I have not noticed the floor and the ceiling, but later wOW MAGIC!
 
Mar 2012
566
29
I am sorry to tell you this, I want to implement this function for very large numbers up to 10^18, so it will take some time to get the summation. Do you think that there is a way to solve this formula to get rid of the summation (sigma) part?

I need something similar to this: the summation of n = n(n+1)/2

By, the way, what you have done to create this formula is very smart!
 
Jun 2013
1,127
601
Lebanon
Another approach.
Consider the following union of intersections of intervals

\(\displaystyle S=\underset{k=1}{\overset{m}{\cup }}([1,x]\cap [k z-y,k z-1])\)

where

\(\displaystyle m= \left\lfloor \frac{x+y}{z}\right\rfloor \)

Each element $a\in S$ will produce a solution in the form $(a,k z-a)$
therefore the number of solutions equals card $S$

If $m$ is not too big this might actually work
 
  • Like
Reactions: joshuaa
Mar 2012
566
29
How can I apply this for x = 5, y = 10, z = 8? the answer is should be 5 pairs

let me try

m = 1
S = [1,5] intersecton [-2, 7]

then what?
 
Jun 2013
1,127
601
Lebanon
How can I apply this for x = 5, y = 10, z = 8? the answer is should be 5 pairs

let me try

m = 1
S = [1,5] intersecton [-2, 7]

then what?
that gives $S=[1,5]= \{1,2,3,4,5\}$ . An interval here is just a set of natural numbers

so we have $k=1$ and $a=1,2,3,4,5$

since $z=8$ we get $b = z - a = 7,6,5,4,3$

5 pairs: $(1,7),(2,6),(3,5),(4,4),(5,3)$
 
  • Like
Reactions: topsquark
Mar 2012
566
29
wOW. that’s beautiful! is k always = 1? What about y = 10, we did not use it!!