Impatient divisibility test

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
14
down vote

favorite
2












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



code-golf number decision-problem number-theory division




share|improve this question






















  • I think we should assume that one digit will be given every time our solution asks for input, right? And, it should be a full program, since this is the objective way to ensure that input is given digit by digit, no? (The challenge says "program or function", hmm...)
    – Erik the Outgolfer
    Sep 1 at 21:47







  • 1




    @EriktheOutgolfer The input format is explained in detail in the bulleted list in the question.
    – Doorknob♦
    Sep 1 at 21:50






  • 1




    I was just thinking about how objective can those formats be...I guess I'll just quit nitpicking and start actually solving this. :-)
    – Erik the Outgolfer
    Sep 1 at 21:52






  • 1




    Is anything wrong with just taking a list as the digits input with a special value for EOF?
    – Jonathan Allan
    Sep 2 at 9:48







  • 1




    @EriktheOutgolfer not if there is an EOF value, unless I've misunderstood something. For example let's say the whole value is 132 and the potential divisor is 4 then and [2] return anything other than false or true (including the function itself etc...) while [2,3], [2,3,1], and [2,3,1,EOF] return true. It strikes me as close to the global state option.
    – Jonathan Allan
    Sep 2 at 11:44















up vote
14
down vote

favorite
2












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



code-golf number decision-problem number-theory division




share|improve this question






















  • I think we should assume that one digit will be given every time our solution asks for input, right? And, it should be a full program, since this is the objective way to ensure that input is given digit by digit, no? (The challenge says "program or function", hmm...)
    – Erik the Outgolfer
    Sep 1 at 21:47







  • 1




    @EriktheOutgolfer The input format is explained in detail in the bulleted list in the question.
    – Doorknob♦
    Sep 1 at 21:50






  • 1




    I was just thinking about how objective can those formats be...I guess I'll just quit nitpicking and start actually solving this. :-)
    – Erik the Outgolfer
    Sep 1 at 21:52






  • 1




    Is anything wrong with just taking a list as the digits input with a special value for EOF?
    – Jonathan Allan
    Sep 2 at 9:48







  • 1




    @EriktheOutgolfer not if there is an EOF value, unless I've misunderstood something. For example let's say the whole value is 132 and the potential divisor is 4 then and [2] return anything other than false or true (including the function itself etc...) while [2,3], [2,3,1], and [2,3,1,EOF] return true. It strikes me as close to the global state option.
    – Jonathan Allan
    Sep 2 at 11:44













up vote
14
down vote

favorite
2









up vote
14
down vote

favorite
2






2





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



code-golf number decision-problem number-theory division




share|improve this 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




code-golf number decision-problem number-theory division





share|improve this question













share|improve this question




share|improve this question








edited Sep 4 at 12:28

























asked Sep 1 at 21:17









Doorknob♦

53.4k16111339




53.4k16111339











  • I think we should assume that one digit will be given every time our solution asks for input, right? And, it should be a full program, since this is the objective way to ensure that input is given digit by digit, no? (The challenge says "program or function", hmm...)
    – Erik the Outgolfer
    Sep 1 at 21:47







  • 1




    @EriktheOutgolfer The input format is explained in detail in the bulleted list in the question.
    – Doorknob♦
    Sep 1 at 21:50






  • 1




    I was just thinking about how objective can those formats be...I guess I'll just quit nitpicking and start actually solving this. :-)
    – Erik the Outgolfer
    Sep 1 at 21:52






  • 1




    Is anything wrong with just taking a list as the digits input with a special value for EOF?
    – Jonathan Allan
    Sep 2 at 9:48







  • 1




    @EriktheOutgolfer not if there is an EOF value, unless I've misunderstood something. For example let's say the whole value is 132 and the potential divisor is 4 then and [2] return anything other than false or true (including the function itself etc...) while [2,3], [2,3,1], and [2,3,1,EOF] return true. It strikes me as close to the global state option.
    – Jonathan Allan
    Sep 2 at 11:44

















  • I think we should assume that one digit will be given every time our solution asks for input, right? And, it should be a full program, since this is the objective way to ensure that input is given digit by digit, no? (The challenge says "program or function", hmm...)
    – Erik the Outgolfer
    Sep 1 at 21:47







  • 1




    @EriktheOutgolfer The input format is explained in detail in the bulleted list in the question.
    – Doorknob♦
    Sep 1 at 21:50






  • 1




    I was just thinking about how objective can those formats be...I guess I'll just quit nitpicking and start actually solving this. :-)
    – Erik the Outgolfer
    Sep 1 at 21:52






  • 1




    Is anything wrong with just taking a list as the digits input with a special value for EOF?
    – Jonathan Allan
    Sep 2 at 9:48







  • 1




    @EriktheOutgolfer not if there is an EOF value, unless I've misunderstood something. For example let's say the whole value is 132 and the potential divisor is 4 then and [2] return anything other than false or true (including the function itself etc...) while [2,3], [2,3,1], and [2,3,1,EOF] return true. It strikes me as close to the global state option.
    – Jonathan Allan
    Sep 2 at 11:44
















I think we should assume that one digit will be given every time our solution asks for input, right? And, it should be a full program, since this is the objective way to ensure that input is given digit by digit, no? (The challenge says "program or function", hmm...)
– Erik the Outgolfer
Sep 1 at 21:47





I think we should assume that one digit will be given every time our solution asks for input, right? And, it should be a full program, since this is the objective way to ensure that input is given digit by digit, no? (The challenge says "program or function", hmm...)
– Erik the Outgolfer
Sep 1 at 21:47





1




1




@EriktheOutgolfer The input format is explained in detail in the bulleted list in the question.
– Doorknob♦
Sep 1 at 21:50




@EriktheOutgolfer The input format is explained in detail in the bulleted list in the question.
– Doorknob♦
Sep 1 at 21:50




1




1




I was just thinking about how objective can those formats be...I guess I'll just quit nitpicking and start actually solving this. :-)
– Erik the Outgolfer
Sep 1 at 21:52




I was just thinking about how objective can those formats be...I guess I'll just quit nitpicking and start actually solving this. :-)
– Erik the Outgolfer
Sep 1 at 21:52




1




1




Is anything wrong with just taking a list as the digits input with a special value for EOF?
– Jonathan Allan
Sep 2 at 9:48





Is anything wrong with just taking a list as the digits input with a special value for EOF?
– Jonathan Allan
Sep 2 at 9:48





1




1




@EriktheOutgolfer not if there is an EOF value, unless I've misunderstood something. For example let's say the whole value is 132 and the potential divisor is 4 then and [2] return anything other than false or true (including the function itself etc...) while [2,3], [2,3,1], and [2,3,1,EOF] return true. It strikes me as close to the global state option.
– Jonathan Allan
Sep 2 at 11:44





@EriktheOutgolfer not if there is an EOF value, unless I've misunderstood something. For example let's say the whole value is 132 and the potential divisor is 4 then and [2] return anything other than false or true (including the function itself etc...) while [2,3], [2,3,1], and [2,3,1,EOF] return true. It strikes me as close to the global state option.
– Jonathan Allan
Sep 2 at 11:44











2 Answers
2






active

oldest

votes

















up vote
8
down vote













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



$$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.



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





share|improve this answer





























    up vote
    2
    down vote













    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.






    share|improve this answer






















      Your Answer




      StackExchange.ifUsing("editor", function ()
      return StackExchange.using("mathjaxEditing", function ()
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
      );
      );
      , "mathjax-editing");

      StackExchange.ifUsing("editor", function ()
      StackExchange.using("externalEditor", function ()
      StackExchange.using("snippets", function ()
      StackExchange.snippets.init();
      );
      );
      , "code-snippets");

      StackExchange.ready(function()
      var channelOptions =
      tags: "".split(" "),
      id: "200"
      ;
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function()
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled)
      StackExchange.using("snippets", function()
      createEditor();
      );

      else
      createEditor();

      );

      function createEditor()
      StackExchange.prepareEditor(
      heartbeatType: 'answer',
      convertImagesToLinks: false,
      noModals: false,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: null,
      bindNavPrevention: true,
      postfix: "",
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      );



      );













       

      draft saved


      draft discarded


















      StackExchange.ready(
      function ()
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f171568%2fimpatient-divisibility-test%23new-answer', 'question_page');

      );

      Post as a guest

















      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      8
      down vote













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



      $$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.



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





      share|improve this answer


























        up vote
        8
        down vote













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



        $$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.



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





        share|improve this answer
























          up vote
          8
          down vote










          up vote
          8
          down vote









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



          $$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.



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





          share|improve this answer














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



          $$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.



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






          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Sep 2 at 16:34

























          answered Sep 1 at 22:16









          Arnauld

          63.6k580268




          63.6k580268




















              up vote
              2
              down vote













              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.






              share|improve this answer


























                up vote
                2
                down vote













                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.






                share|improve this answer
























                  up vote
                  2
                  down vote










                  up vote
                  2
                  down vote









                  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.






                  share|improve this answer














                  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.







                  share|improve this answer














                  share|improve this answer



                  share|improve this answer








                  edited Sep 2 at 10:13

























                  answered Sep 2 at 10:06









                  Neil

                  75.1k744170




                  75.1k744170



























                       

                      draft saved


                      draft discarded















































                       


                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f171568%2fimpatient-divisibility-test%23new-answer', 'question_page');

                      );

                      Post as a guest
































































                      Comments

                      Post a Comment

                      Popular posts from this blog

                      What does second last employer means? [closed]

                      Image
                      Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote -3 down vote favorite Say, for example I have worked in the following companies, Company A => 2010 - 2011 Company B => 2011 - 2012 Company C => 2012 - Till Date Company D => Have offer Now assume Company D is asking to submit documents from my second last employer. So from the list of companies given, which company would be qualified as second last employer? software-industry employer share | improve this question asked Aug 10 '14 at 5:16 Rajaprabhu Aravindasamy 559 1 6 13 closed as off-topic by Jim G., jmort253 ♦ Aug 11 '14 at 1:58 This question appears to be off-topic. The users who voted to close gave this specific reason: "Questions seeking advice on company-specific regulations, agreements, or policies should be directed to your manager or HR department. Questions that address...
                      Read more

                      List of Gilmore Girls characters

                      Image
                      The season three cast—(Back row): Lane, Michel, Paris, Emily, Richard, Sookie, Miss Patty, Kirk; Front row: Jess, Luke, Lorelai, Rory, Dean This is a list of characters for the comedy-drama television series Gilmore Girls . Contents 1 Main characters 1.1 Lorelai Gilmore 1.2 Rory Gilmore 1.3 Sookie St. James 1.4 Lane Kim 1.5 Michel Gerard 1.6 Luke Danes 1.7 Emily Gilmore 1.8 Richard Gilmore 1.9 Paris Geller 1.10 Dean Forester 1.11 Jess Mariano 1.12 Kirk Gleason 1.13 Jason Stiles 1.14 Logan Huntzberger 2 Major recurring characters 2.1 Christopher Hayden 2.2 Jackson Belleville 2.3 Mrs. Kim 2.4 Tristin DuGray 2.5 Max Medina 2.6 Taylor Doose 2.7 Dave Rygalski 2.8 Marty 3 Recurring characters 3.1 Stars Hollow 3.2 Chilton 3.3 Yale 3.4 Other 4 Notable guest stars 5 Unseen characters 6 Notes 7 References Main characters Actor Character Appearances Season 1 Season 2 Season 3 Season 4 Season 5 Season 6 Season 7 A Year in the Life Lauren Graham Lorelai Gilmore...
                      Read more

                      Confectionery

                      Image
                      Prepared foods made with a lot of sugar or other cabohydrates "Sweetmeat" redirects here. For the racehorse, see Sweetmeat (horse). Not to be confused with Sweetbread. This Kransekake is a traditional Scandinavian baker's confection. Confectionery is the art of making confections , which are food items that are rich in sugar and carbohydrates. Exact definitions are difficult. [1] In general, though, confectionery is divided into two broad and somewhat overlapping categories, bakers' confections and sugar confections. [2] Bakers' confectionery, also called flour confections , includes principally sweet pastries, cakes, and similar baked goods. Sugar confectionery includes candies ( sweets in British English), candied nuts, chocolates, chewing gum, bubble gum, pastillage, and other confections that are made primarily of sugar. In some cases, chocolate confections (confections made of chocolate) are treated as a separate category, as are sugar-free versions of ...
                      Read more