Impatient divisibility test

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


digits

[2]

false

true

[2,3]

[2,3,1]

[2,3,1,EOF]

true

2 Answers
2

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!

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

$$ktimes 10^n+q pmod ptag1$$

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

$$xtimes 10^n+q pmod p=\
(mp+k)times 10^n+q pmod p=\
(mptimes 10^n pmod p)+ (ktimes 10^n+q pmod p)pmod p=\
0+(ktimes 10^n+q pmod p)pmod p=\
ktimes 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.

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
) //


@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:

d

n

-

1

0

@set n=


Initialise n to the empty string.

n

@set g=1


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

g

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.

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.

g

len(n)

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.

r

d

n

g

d

r

d

n

g

d

:g


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

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


Calculate and implicitly output the result.

If this is an answer to a challenge…

…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.

…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one.
Explanations of your answer make it more interesting to read and are very much encouraged.

…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.

More generally…

…Please make sure to answer the question and provide sufficient detail.

…Avoid asking for help, clarification or responding to other answers (use comments instead).

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.