The modulus validation

Question

Given a list of math expressions that all hold true and consist of modulo remainder calculations with two numbers and a result, your task is to yield the first n numbers that hold true for all the statements in the list.

For example:

[m % 3 = 0, m % 4 = 1, m % 5 = 3], where % is the modulo operator.

For n = 3, the first 3 numbers (counting from 0) that fit the sequence are 33, 93, 153, thus your result would be that (format up to you).

Rules / IO

1. You take a positive number n and a list of truths. Of course, the things you need take are only the RHS of the modulo operation and the result.
2. n and the numbers in the list of truths will always be in the range 1 -> 2^31-1, and so are the results.
3. You take input in any convenient form and output in any convenient form. For example, input: 3 [3 0, 4 1, 5 3] and output: 33 93 153.
4. It's guaranteed that the solution is mathematically possible.
5. The source of input can be from a file, function parameters, stdin, etc... Same goes for the output.
6. No loopholes.
7. This is code-golf, so the lowest byte count wins.

Testcases

# Input in the form <n>, <(d r), (d2 r2), ...>
# where <d> = RHS of the modulo expression and <r> the result of the expression. Output in the next line.

5, (3 2), (4 1), (5 3)
53 113 173 233 293

3, (8, 0), (13, 3), (14, 8)
120 848 1576

Reference implementation in pseudo-code

n = (an integer from stdin)
truths = (value pairs from stdin)
counter = 0

while n != 0 {
    if matches_criterias(counter, truths) {
        print counter
        n -= 1
    }

    counter += 1
}

Answer 1

Jelly, 7 bytes

%⁼⁴
0ç#

This is a full program. Arguments are divisors, target moduli, and number of solutions, in that order.

Try it online!

How it works

0ç#  Main link.
     Left argument: D (array of divisors)
     Right argument: M (array of target moduli)
     Third argument: n (number of solutions)

0ç#  Execute the helper link with k = 0, 1, 2, ... as left argument and D as the
     right one until n of them return 1. Yield the array of matches.


%⁼⁴  Helper link. Left argument: k. Right argument: D

%    Compute k % d for each d in D.
 ⁼⁴  Compare the result with M.

Answer 2

Perl 6, 33 bytes

{grep((*X%@^b)eqv@^c,0..*)[^$^a]}

Try it

The input is ( number-of-values, list-of-divisors, list-of-remainders )

Expanded:

{   # bare block lambda with placeholder parameters ｢$a｣ ｢@b｣ ｢@c｣

  grep(

    # WhateverCode lambda:
    (

      *        # the value being tested

      X%       # cross modulus

      @^b      # with the divisors ( second parameter )

    )

    eqv        # is that list equivalent with

    @^c        # the expected remainders ( third parameter )

    # end of WhateverCode lambda

    ,

    0 .. *     # Range of all Integers starting with 0

  )[ ^$^a ]    # grab up-to ｢$a｣ values ( first parameter )
               # ( ｢^$a｣ is the same as ｢0 ..^ $a｣ )
}

Answer 3

JavaScript (ES6), 71 68 bytes

a=>f=(n,m=0)=>n?a.some(x=>m%x[0]-x[1],++m)?f(n,m):[m,...f(n-1,m)]:[]

A simple recursive function. Use by currying in the array first and n second, like so:

g=a=>f=(n,m=0)=>n?a.some(x=>m%x[0]-x[1],++m)?f(n,m):[m,...f(n-1,m)]:[]
g([[3, 2], [4, 1], [5, 3]])(5)

Answer 4

JavaScript (ES6), 74 70 69 bytes

Takes input as an integer n and an array a of [modulo, remainder] arrays with currying syntax (n)(a).

n=>a=>eval('for(i=r=[];a.some(([b,c])=>i%b-c)||--n*r.push(i);i++);r')

Test cases

let f =

n=>a=>eval('for(i=r=[];a.some(([b,c])=>i%b-c)||--n*r.push(i);i++);r')

console.log(f(5)([[3, 2], [4, 1], [5, 3]]))
console.log(f(3)([[8, 0], [13, 3], [14, 8]]))

Answer 5

Haskell, 47 bytes

n#l=take n[i|i<-[0..],all(\(d,r)->mod i d==r)l]

Usage example: 3 # [(8,0),(13,3),(14,8)] -> [120,848,1576].

Answer 6

Python, 67 bytes

lambda n,r:[k for k in range(2**32)if all(k%d==m for d,m in r)][:n]

Answer 7

JavaScript (ES6), 72 70 bytes

a=>g=(n,i,r=[],m=a.some(e=>i%e[0]^e[1]))=>n?g(n-!m,-~i,m?r:[...r,i]):r

Curried over the conditions array first and number of results second. Edit: Saved 2 bytes by not handling the zero case.

Answer 8

Mathematica, 42 bytes

#2~ChineseRemainder~#+Range[0,#3-1]LCM@@#&

Unnamed function, returning a list of positive integers, and taking three inputs: the list of moduli, the list of remainders, and the number n of integers to return. For example, the second test case is invoked by

#2~ChineseRemainder~#+Range[0,#3-1]LCM@@#&[{8,13,14},{0,3,8},3]

and returns {120, 848, 1576}.

The builtin #2~ChineseRemainder~# gives the smallest nonnegative solution; to get all the desired solutions, we add this number to Range[0,#3-1]LCM@@#, which is the first n nonnegative multiples of the least common multiple of all the moduli.

Mathematica doesn't have lazily-evaluated infinite lists as far as I know, so this implementation was shorter than anything I found that tested nonnegative integers one by one—even with the length of the function name ChineseRemainder, and even though a test like Mod[k,{8,13,14}]=={0,3,8} works perfectly well.

Answer 9

PHP, 97 bytes

longest answer so far. But I´m glad I could get it below 100.

for($a=$argv;++$k;)for($i=$v=2;$m=$a[$i++];$v>$argc/2&&$a[1]-->0?print$k._:0)$v+=$k%$m==$a[$i++];

takes input from separate command line arguments,
prints matches separated and trailed by underscores.
Loop never breaks; barely suitable for online testers.

Run like php -r 'code' <n> <modulo1> <result1> <modulo2> <result2> ....

breakdown

for($a=$argv;++$k;)         // loop $k up from 1
    for($i=$v=2;                // $i = argument index, $v=2+ number of satisfied equations
        $m=$a[$i++];            // loop through modulo/result pairs
        $v>$argc/2                  // 2. if $v>argument-count/2
        &&$a[1]-->0                 // and match count not exhausted
            ?print$k._                  // print match
            :0                          // else do nothing
        )
            $v+=$k%$m==$a[$i++];    // 1. if $k%modulo==result, increment $v

notes

$argc==count($argv). For three pairs there are 8 arguments: the filename $argv[0], n=$argv[1] and the modulo/result pairs above that. $v=2 incremented 3 times gives 5>$argc/2.

Add one byte for a clean exit: Replace &&$a[1]-->0?print$k._ with ?$a[1]--?print$k._:die.

Answer 10

Pyth - 14 13 bytes

.f!fneT%ZhTQE

Try it online here.

Answer 11

SmileBASIC, 102 bytes

DEF V N,M
FOR K=1TO N@L
T=T+1F=0FOR J=1TO LEN(M)F=F||T MOD M[J-1]-M[J]J=J+1NEXT
ON!F GOTO @L?T
NEXT
END

This is the first time I've ever used ON in SB. The reason I used it here instead of IF F GOTO@L was so I could put ?T after it on the same line, saving 1 byte.

Answer 12

Python, 59 bytes

lambda n,m:[i for i in range(2**31)if all(map(eval,m))][:n]

m is a list of expressions in string form like ["i % 4 == 1", ...]

Try it online (with a shorter range, so it will actually finish)

Answer 13

PHP, 91 Bytes

Take the list as associative array

<?for($t=1;$r<$_GET[1];$i+=$t=!$t?:print+$i._.!++$r)foreach($_GET[0]as$k=>$v)$t*=$i%$k==$v;

Try it online!