Impatient divisibility test

Question

Your task is to write a program or function that determines whether a number is divisible by another. The catch is that it should give an answer as soon as possible, even if not all digits of the number have been given.

Your program should take an integer D ≥ 2 and then a series of digits as input. These represent the digits of another integer N ≥ 1, starting at the least significant digit. At the first point that N either must or must not be divisble by D, your program should output the appropriate answer and exit. If the end of the input is reached, it should output whether the full N is divisible by D.

Here is a list of acceptable input formats for N (leave a comment if you think something that isn't included should be allowed):

• Standard input: digits are given on separate lines; end of input is EOF or a special value; exit means that the function returns or the program exits.

• Analog input: through e.g. keystrokes or ten buttons representing each digit; end of input is a special value; exit means that the function returns or the program exits.

• Function with global state: called repeatedly with successive digits; end of input is a special value; exit means that the function returns a non-null value. Note that if you use global state, it must be cleared after a value is returned or otherwise reset such that the function works multiple times.

• Curried function: returns either another function to be called with the next digit or a value; end of input is a special value or calling the function with no argument; exit means that the function returns an answer rather than another function.

• GUI prompt or similar: displayed repeatedly; end of input is "cancel" or equivalent, or a special value; exit means that prompts stop appearing.

• Iterator function: input is a stateful object or function that returns the next digit when called, end of input is an exception or special value; exit means that the iterator stops being called.

Input for D and the output can be through any acceptable standard method.

Test cases:

2;   6               => true
5;   6               => false
20;  0 3             => false
20;  0 4             => true
100; 1               => false
100; 0 0             => true
100; 0 2             => false
4;   2 4             => false
4;   2 5             => true
4;   2 [eof]         => false
4;   4 [eof]         => true
625; 5 5             => false
625; 5 7 2           => false
625; 5 7 3 6         => false
625; 5 7 3 4         => true
7;   9 3 4 [eof]     => false
7;   9 3 4 5 [eof]   => true
140; 0 3             => false
140; 0 4 5 [eof]     => false
140; 0 4 5 1 [eof]   => true
14;  4 5 1 4 [eof]   => false
14;  4 5 1 4 1 [eof] => true

Answer 1

JavaScript (ES6), 70 bytes

Input format: Curried function

A function that takes the divisor and returns a function that takes each digit or \$-1\$ for EOF. The second function returns either \$0\$ (false), \$1\$ (true) or itself (no answer).

p=>(q='',g=(d,t=k=z=!~d||(q=d+q,p))=>k--?g(d,t-=(k+q)%p<1):t?t-z&&g:1)

Try it online!

How?

Given a divisor \$p\$ and a dividend \$q\$ consisting of \$n\$ decimal digits, we compute the following expression for all \$0 \le k < p\$:

$$k\times 10^n+q \pmod p\tag{1}$$

For any \$x\ge p\$ there exists \$m\ge 1\$ and \$0 \le k < p\$ such that \$x=mp+k\$, leading to:

$$x\times 10^n+q \pmod p=\\ (mp+k)\times 10^n+q \pmod p=\\ (mp\times 10^n \pmod p)+ (k\times 10^n+q \pmod p)\pmod p=\\ 0+(k\times 10^n+q \pmod p)\pmod p=\\ k\times 10^n+q \pmod p$$

Therefore, if \$(1)\$ is equal to \$0\$ for all \$0 \le k < p\$, it will also be equal to \$0\$ for any \$k \ge p\$ and the answer is true.

For the same reason, if \$(1)\$ is greater than \$0\$ for all \$0 \le k < p\$, the answer is false.

If the results of \$(1)\$ are mixed, we can't decide yet and need either more digits of \$q\$ or the EOF notification.

Commented

p => (                       // p = divisor
  q = '',                    // q = dividend stored as a string, initially empty
  g = (                      // g() = curried function taking:
    d,                       //   d = next digit
    t =                      //   t = number of iterations yielding a non-zero value
    k =                      //   k = total number of iterations to process
    z =                      //   z = copy of k
      !~d ||                 //   if d == -1 (meaning EOF), use only 1 iteration
                             //   so that we simply test the current value of q
      (q = d + q, p)         //   otherwise, prepend d to q and use p iterations
  ) =>                       //
    k-- ?                    //   decrement k; if it was not equal to zero:
      g(                     //     do a recursive call to g():
        d,                   //       pass the current value of d (will be ignored anyway)
        t -= (k + q) % p < 1 //       test (k + q) % p and update t accordingly
      )                      //     end of recursive call
    :                        //   else:
      t ?                    //     if t is greater than 0:
        t - z && g           //       return 0 if t == z, or g otherwise
      :                      //     else:
        1                    //       return 1
)                            //

Answer 2

Batch, 177 169 bytes

@set n=
@set g=1
:l
@set/ps=
@if %s%==- goto g
@set n=%s%%n%
@set/ae=%1/g,g*=2-e%%2,g*=1+4*!(e%%5),r=n%%g
@if %g% neq %1 if %r%==0 goto l
:g
@cmd/cset/a!(n%%%1)

Takes d as a command-line parameter and reads digits of n on separate lines with - as the EOF marker. Outputs 1 for divisible, 0 if not. Explanation:

@set n=

Initialise n to the empty string.

@set g=1

g is gcd(d, 10**len(n))

:l

Begin a loop reading digits.

@set/ps=

Read the next digit.

@if %s%==- goto g

Stop processing at EOF.

@set n=%s%%n%

Prepend the next digit to n.

@set/ae=%1/g,g*=2-e%%2,g*=1+4*!(e%%5),r=n%%g

Update g now that len(n) has increased and calculate n%g.

@if %g% neq %1 if %r%==0 goto l

If r is non-zero then the d definitely does not divide n, because g, a factor of d, does not. If r is zero then we only know whether d divides n if g equals d, so if it isn't, continue the loop.

:g

Break out of the digit-reading loop here on EOF.

@cmd/cset/a!(n%%%1)

Calculate and implicitly output the result.