# Divmod continuously until the remainder is 1 or 0, then get the remainder

The task is simple, divide, get the quotient and the remainder, and if the remainder isn't 1 or 0, do the same thing (quotient divmod remainder) until the remainder is 1 or 0, then get the remainder. If the last input number is 1 or 0, output it.

If the inputs are 15 and 4, then the result would be 0:

• 15 ÷ 4 = 3 remainder 3. Since 3 isn't 0 or 1, we continue. Now 3 ÷ 3 = 1 remainder 0, so just return the remainder, 0.

Another example would be 102 and 7:

• 102 ÷ 7 = 14 remainder 4; 14 ÷ 4 = 3 remainder 2; 3 ÷ 2 = 1 remainder 1, the result is 1.

Both input numbers are assumed to be non-negative integers less than 1000.

This is , so the shortest program/function in bytes wins.

## Testcases:

[15, 4] => 0
[102, 7] => 1
[20, 2] => 0
[10, 0] => 0
[11, 1] => 1
[99, 7] => 1
[45, 45] => 0
[31, 30] => 1
[999, 7] => 0
[999, 6] => 1
[88, 7] => 0
[1, 999] => 1
[98, 7] => 0
[999, 998] => 1

• Is it permissible to output two unique outputs for 1 and 0 other than 1 and 0? Commented Jan 14 at 8:35
• It would also be worth clarifying the spec. As currently written, I would say that [10, 0] is an invalid input because the spec suggests there is always at least one divmod. You’ve also not specified that the input have to be integers or non-negative, but the examples would suggest that is the case. Commented Jan 14 at 11:17
• "and if the remainder is 1 or 0, do the same thing" - is that supposed to say "if the remainder isn't 1 or 0"? Commented Jan 14 at 12:51
• @user2357112 Fixed Commented Jan 14 at 12:54
• So this is the gcd algorithm, but implemented by a student who sucks at arithmetic!
– Stef
Commented Jan 14 at 13:17

# Nekomata, 4 bytes

ʷ{Ƶþ

ʷ{Ƶþ
ʷ{      While; run the following code until it fails
Ƶ       Check if the absolute value of the top of the stack is greater than 1
þ      Divmod


Both Ƶ and þ are new built-ins in Nekomata 0.5.1, which is not yet on ATO.

# JavaScript (ES6), 27 bytes

f=(p,q)=>q>1?f(p/q|0,p%q):q


Try it online!

Or 25 bytes with BigInts.

# Python 2, 35 bytes

f=lambda a,b:f(a/b,a%b)if b>1else b


Try it online!

• -1: f=lambda a,b:1-(b>1>f(a/b,a%b))**b Commented Jan 14 at 5:54
• @Albert.Lang Uh. I learned something today.
– Stef
Commented Jan 14 at 12:50

# R, 33 bytes

f=\(x,y)if(y>1,f(x%/%y,x%%y),y)


Attempt This Online!

A recursive function taking two arguments and returning 1 or 0.

# C (gcc), 27 bytes

f(a,b){a=b>1?f(a/b,a%b):b;}


Try it online!

# 05AB1E, 6 bytes

[D!#‰


Explanation:

[       # Start an infinite loop:
#  Pop and push both values in the pair separately to the stack
#  (which will use the implicit input-pair in the first iteration)
D     #  Duplicate the top value (the remainder)
!    #  Take its factorial (0 becomes 1; 1 remains 1; ≥2 becomes larger)
#   #  If it's truthy (==1), stop the infinite loop
#  (after which the duplicated remainder is output implicitly as result)
‰  #  (else) Divmod the two values


# x86-32 machine code, 9 bytes

## x86-64 machine code, 10 bytes, same asm source

Args in EAX (dividend), ECX (divisor), return value in ECX (0 or 1 final remainder).

To call from C, gcc -mregparm=3 will put args in EAX, EDX, ECX in that order (so a dummy second arg works), but won't look for retval in ECX. Returning in EAX costs 1 extra byte for xchg eax,ecx at the end.

Args must be signed non-negative. (At least the dividend must be; the divisor can be full-range 32-bit unsigned. And the first remainder must also be non-negative). Divisor must be non-zero or the first iteration will fault.

               divmod_repeat:
.loop:
99               cdq        ; zero-extend (for numbers that fit as non-negative integers)
F7F1             div ecx        ; EAX = EDX:EAX/ecx unsigned; EDX = remainder

89D1             mov ecx, edx
4A               dec edx        ; 1 byte instruction in 32-bit mode
7FF8             jg .loop       ; }while(remainder-- > 1);   or  }while(--rem > 0)
C3               ret

;   cmp ecx, 2     ; simple but less golfed version
;   jae .loop      ; }while(new_divisor >= 2);


This shows a hexdump of the 32-bit machine code on the left, from a NASM listing. The x86-64 version (still using 32-bit operand-size) uses FFCA dec edx.

Not much scope for golfing, other than choosing a good calling convention. div only works with EDX:EAX / src, producing its outputs in EDX (remainder) and EAX (quotient). We don't want to touch quotient, so all the special-case accumulator short-form encodings of instructions like xchg eax, reg and cmp al, imm8.

But we can destroy the old copy of the remainder in EDX after copying it to ECX as the new divisor (or return value). So we can use 1-byte (in 32-bit mode) dec reg to set FLAGS instead of cmp. The next iteration's cdq will overwrite EDX anyway, and we need cdq anyway.

We can only use signed conditions with dec because it leaves CF unmodified, but is otherwise like sub or cmp ecx, 1.

# Retina 0.8.2, 35 bytes

.+
$* +(..+)¶(\1)*(.*)$3¶$#2$*
^.


Try it online! Takes the integers in reverse order on separate lines but link is to test suite that takes input in the format given in the question. Explanation:

.+
$*  Convert to unary. (..+)¶(\1)*(.*)$3¶$#2$*


If the denominator is at least 2, divmod the numerator by the denominator, replacing the denominator by the remainder and the numerator by the quotient.

+


Repeat until the denominator is reduced to less than 2.

^.


Convert the denominator to 0 or 1.

# UiuaSBCS, 13 bytes

⊙◌⍢(:⌊⊃÷◿|>1)


Try it!

⊙◌⍢(:⌊⊃÷◿|>1)
⍢(     |  )  # while
>1   # top of stack is greater than one
⊃÷◿      # quotient and remainder
⌊         # take the floor of the quotient
:          # swap so remainder is on top
⊙◌             # drop the quotient from the stack

• That version of the SBCS does not have the ◌ glyph added today. Here's my updated version: tinyurl.com/Uiua-SBCS-Jan-14
– Tbw
Commented Jan 14 at 12:25
• @Tbw Thanks, updated. Commented Jan 14 at 12:49

# Funge-98, 51 bytes

v   >.@   @.<
>    "HTRF"4 (&& v
\/RRw11:%OOw11:<


Try it online!

• Welcome to Code Golf, nice first answer! Commented Jan 17 at 2:58

# Perl 5-Minteger -ap, 37 bytes

@F=("@F"/$_,"@F"%$_)while($_=$F[1])>1


Try it online!

# Scratch, 77 70 bytes

Ports @enzo's answer. Run without screen refresh.

define(x)(y
if<(y)>(1)>then
([floor v]of((x)/(y)))((x)mod(y
else
say(y


• set[i v]to(y => say(y, with "run without screen refresh" checked on Commented Jan 17 at 3:00

# Go, 47 bytes

func(a,b int)int{for b>1{a,b=a/b,a%b}
return b}


Attempt This Online!

=LET(F,LAMBDA(F,d,m,LET(x,MOD(d,m),IF(x<2,x,F(F,INT(d/m),x)))),F(F,A1,A2))


Simple recursive function that stops the execution when the remainder is 0 or 1.

# Pyth, 10 bytes

eu?>eG1.DF


Attempt This Online!

# Charcoal, 23 bytes

ＮθＮηＷ∧⊖ηη«≔﹪θιη≔÷θιθ»Ｉη


Try it online! Link is to verbose version of code. Explanation: Lack of divmod and recursion makes this annoyingly long.

ＮθＮη


Input the two values.

Ｗ∧⊖ηη«


Compare the second value against both 1 and 0, but in such a way that if it is neither than the implicit loop variable has the same value.

≔﹪θιη≔÷θιθ


Modulo and divide the first value by the copy of the second, thus allowing the second and first values to be safely overwritten.

»Ｉη


Output the final value.

# Jelly, 8 bytes

d/ỊṪ¬Ɗ¿Ṫ


Try it online!

A monadic link taking a pair of non-negative integers and returning 1 or 0.

## Explanation

     Ɗ¿  | While the following is true:
Ị      | - <= 1
Ṫ     | - Tail (i.e. second list member)
¬    | - Not
d/       | … Reduce using divmod
Ṫ | Tail



If we were allowed to guarantee the second input were non-zero, this is shorter:

# Jelly, 7 bytes

d/%/¿ṪỊ


Try it online!

• Can you please explain it? I like this language. Commented Jan 15 at 16:40
• @Fmbalbuena thanks, hope that makes sense! Commented Jan 16 at 23:33

# TI-BASIC, 37 bytes

While 1<Ans(2
Ans→L
Ans(1)/Ans(2
int({Ans,ʟL(2)fPart(Ans
End
Ans(2


Takes input in Ans. Replace the second to fourth lines with int({Ans(1)/Ans(2),remainder(Ans(1),Ans(2 for -2 bytes if remainder( is supported.

# APL(Dyalog Unicode), 18 bytes SBCS

{1<⍵:(⌊⍺÷⍵)∇⍵|⍺⋄⍵}


Try it on APLgolf!

A dfn that takes the first number as the left argument and the second number as the right argument.

# TypeScript's type system, 97 bytes

//@ts-ignore
type M<A,B,T=[]>=A extends[...B,...infer I]?M<I,B,[...T,1]>:A extends[1]|[]?A:M<T,A>


Try it at the TypeScript playground!

I/O is unary numbers / tuples of 1s.

Modified from my solution to Division and remainder.

T-SQL 77 bytes

declare @x int = 88, @y int = 7, @z int

while @y > 1 BEGIN
select @z = @x/@y, @y = @x-(@z*@y)
set @x = @z
end
select @y


Try it!