Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Visit Stack Exchange
Stack Internal
Knowledge at work
Bring the best of human thought and AI automation together at your work.
Explore Stack Internal The second line will be evaluated for every (k, n), with 0 < k <≤ n. F > > M calls M, discards the first two elements, then extracts the first remaining one. As we've seen before, M returns 1(k, ?, 1, ...) if k is a divisor of n, 0(k, ?, 0, ...) otherwise, so the final vector returned by D(n, n) is (0, n, 1 | n, 2 | n, ..., kn | n).
Since f(f(n)) = f(0, n) = (n, n), D will return (0, n, 1 | n, 2 | n, ..., kn | n).
The second line will be evaluated for every (k, n), with 0 < k < n. F > > M calls M, discards the first two elements, then extracts the first remaining one. As we've seen before, M returns 1 if k is a divisor of n, 0 otherwise, so the final vector returned by D(n, n) is (0, n, 1 | n, 2 | n, ..., k | n).
Since f(f(n)) = f(0, n) = (n, n), D will return (0, n, 1 | n, 2 | n, ..., k | n).
The second line will be evaluated for every (k, n), with 0 < k ≤ n. F > > M calls M, discards the first two elements, then extracts the first remaining one. As we've seen before, M returns (k, ?, 1, ...) if k is a divisor of n, (k, ?, 0, ...) otherwise, so the final vector returned by D(n, n) is (0, n, 1 | n, 2 | n, ..., n | n).
Since f(f(n)) = f(0, n) = (n, n), D will return (0, n, 1 | n, 2 | n, ..., n | n).
DD D , N F > > M D expects (n, n) as its initial argument.
The first line will recursively call D on the result of ,, so we'll call D(n, n) → D(n - 1, n) → ... → D(1, n) → D(0, n) → D(1, n), surrendering and returning (0, n).
The second line will be evaluated for every (k, n), with 0 < k < n. F > > M calls M, discards the first two elements, then extracts the first remaining one. As we've seen before, M returns 1 if k is a divisor of n, 0 otherwise, so the final vector returned by D(n, n) is (0, n, 1 | n, 2 | n, ..., k | n).
main N , , + > > D f f Our entry point expects a singleton (n), with n > 0.
Since f(f(n)) = f(0, n) = (n, n), D will return (0, n, 1 | n, 2 | n, ..., k | n).
After discarding (0, n) with > >, a call to + takes the sum of the Booleans, counting the number of divisors of n.
, , dips the divisor count twice, resulting in a 0 only for zero or two divisors. Since n > 0, there is at least one divisor, so the result is 0 if and only if n has exactly two divisors.
Finally, N takes the logical NOT, returning 1 for primes and 0 for non-primes.
DD D , N F > > M D expects (n, n) as its initial argument.
The first line will recursively call D on the result of ,, so we'll call D(n, n) → D(n - 1, n) → ... → D(1, n) → D(0, n) → D(1, n), surrendering and returning (0, n).
The second line will be evaluated for every (k, n), with 0 < k < n. F > > M calls M, discards the first two elements, then extracts the first remaining one. As we've seen before, M returns 1 if k is a divisor of n, 0 otherwise, so the final vector returned by D(n, n) is (0, n, 1 | n, 2 | n, ..., k | n).
main N , , + > > D f f Our entry point expects a singleton (n), with n > 0.
Since f(f(n)) = f(0, n) = (n, n), D will return (0, n, 1 | n, 2 | n, ..., k | n).
After discarding (0, n) with > >, a call to + takes the sum of the Booleans, counting the number of divisors of n.
, , dips the divisor count twice, resulting in a 0 only for zero or two divisors. Since n > 0, there is at least one divisor, so the result is 0 if and only if n has exactly two divisors.
Finally, N takes the logical NOT, returning 1 for primes and 0 for non-primes.
N , , + > > D f f D D , N F > > > M M M m B + B m f m F > + B , dip F > F + B f f + > + B N N B dip + dot > dab On occasions, we'll call f outside of F. Notably, f(x) = (0, x), f(0, x) = (x, x), and
f(x, y) = (y, x + y)
, dip F > yet to comedip F dips the first coordinate of the argument vector, while > returns the remaining coordinates. Thus, , maps (v1, ..., vn) to (|v1 - 1|, ..., vn).
In particular, , maps (x) to (|x - 1|), so we can use it instead of dip for singleton vectors.
M and mM M m + B m f m F + B m is always meant to be called on a pair. It simply combines a few functions we've seen before. Recall that B behaves differently if x ≤ y and if not.
We have m(x, y) = (x, y - x) if x ≤ y but m(x, y) = (x, (x - y) % 2) otherwise.
M is always meant to be called on a pair, whose first coordinate will be non-zero. M attempts to recursively call itself on the result of m. Since m doesn't change the first coordinate of its argument, we only need to examine the second one.
On the second line, B(m(f(x, y))) = B(m(y, x + y)) = B(y, x). After + takes the sum, we get x - y if x ≥ y, but (y - x) % 2 otherwise.
If y = qx, M(x, y) = M(x, qx) will successively call M(x, (q - 1)x), M(x, (q - 2)x), ..., M(x, x), M(x, 0). At the end, M(x, 0) attempts to recursively call itself, which surrenders. The return value is (x, 0), concatenated with all singletons returned by the second line. Since the second line maps (x, x) to 0, the result of M(x, y) will match the pattern (x, 0, 0, ...).
If y = qx + r, with 0 < r < x, we'll proceed in similar fashion, eventually reaching M(x, x + r), then M(x, r).
If r = 1 and x is even, m(x, r) = (x, (x - r) % 2) = (x, 1), and the recursive call to M surrenders. In the previous call, the second line mapped (x, x + r) to (x + r - x) % 2 = 1, so the result of M(x, y) will match the pattern (x, 1, 1, ...).
If r = 1 and x is odd, m(x, r) = (x, (x - r) % 2) = (x, 0), and the recursive call to M succeeds.
Likewise, if r > 1, then m(x, r) = (x, (x - r) % 2) ≤ (x, 1) < (x, r), and the recursive call to M succeeds.
In both cases, the second line will be evaluated for the last time with argument (x, t). Since we have t < r < x, the outcome is the non-zero vector (x - t), so the result of M(x, y) will match the pattern (x, ?, x - t, ...).
Thus, the third element of the vector returned by M(x, y) will be 0 if and only if x is a divisor of y.
[TIO-jf0gja4y]: https://tio.run/##HYyxCgMxDENn6yu0J0sPumYIIVvuH@4IgQ4hhfb/XaUIhGw9u6@@Pu52MkqBSSocHCiwwgg19b9NbGiwxgnLnCIUKiwxQ1h/vbknyAKz6rFDkiHrC859JgpB8PpCTb9udz@ejx8https://tio.run/##JYy9CoQwEITrnaeYPjYn2KYIwS6@gxICFiGCvv/enMfAMj8fW0cdt7ttnKTAKGU2NmRY5gQt69sWFFhhhwUmdhGy65sgrJ4XlSL@leb2M1EHSV@wwRJFIQgeD7TU/XD3efl8AQ "Dodos – Try It Online" "Dodos – Try It Online" [DOS]: https://github.com/DennisMitchell/dodos#divide-or-surrender "DennisMitchell/dodos: Dodos Only Divide Or Surrender"
N , , + > > D f f D D , N F > > > M M M m B m f m F > B , dip F > F + B f f + > + B N N B dip + dot > dab On occasions, we'll call f outside of F. Notably, f(x) = (0, x), f(0, x) = (x, x), and f(x, y) = (y, x + y)
yet to come
[TIO-jf0gja4y]: https://tio.run/##HYyxCgMxDENn6yu0J0sPumYIIVvuH@4IgQ4hhfb/XaUIhGw9u6@@Pu52MkqBSSocHCiwwgg19b9NbGiwxgnLnCIUKiwxQ1h/vbknyAKz6rFDkiHrC859JgpB8PpCTb9udz@ejx8 "Dodos – Try It Online" "Dodos – Try It Online" [DOS]: https://github.com/DennisMitchell/dodos#divide-or-surrender "DennisMitchell/dodos: Dodos Only Divide Or Surrender"
N , , + > > D f f D D , N F > > M M M m + B m f m F + B , dip F > F + B f f + > + B N N B dip + dot > dab On occasions, we'll call f outside of F. Notably, f(x) = (0, x), f(0, x) = (x, x), and
f(x, y) = (y, x + y)
, dip F > dip F dips the first coordinate of the argument vector, while > returns the remaining coordinates. Thus, , maps (v1, ..., vn) to (|v1 - 1|, ..., vn).
In particular, , maps (x) to (|x - 1|), so we can use it instead of dip for singleton vectors.
M and mM M m + B m f m F + B m is always meant to be called on a pair. It simply combines a few functions we've seen before. Recall that B behaves differently if x ≤ y and if not.
We have m(x, y) = (x, y - x) if x ≤ y but m(x, y) = (x, (x - y) % 2) otherwise.
M is always meant to be called on a pair, whose first coordinate will be non-zero. M attempts to recursively call itself on the result of m. Since m doesn't change the first coordinate of its argument, we only need to examine the second one.
On the second line, B(m(f(x, y))) = B(m(y, x + y)) = B(y, x). After + takes the sum, we get x - y if x ≥ y, but (y - x) % 2 otherwise.
If y = qx, M(x, y) = M(x, qx) will successively call M(x, (q - 1)x), M(x, (q - 2)x), ..., M(x, x), M(x, 0). At the end, M(x, 0) attempts to recursively call itself, which surrenders. The return value is (x, 0), concatenated with all singletons returned by the second line. Since the second line maps (x, x) to 0, the result of M(x, y) will match the pattern (x, 0, 0, ...).
If y = qx + r, with 0 < r < x, we'll proceed in similar fashion, eventually reaching M(x, x + r), then M(x, r).
If r = 1 and x is even, m(x, r) = (x, (x - r) % 2) = (x, 1), and the recursive call to M surrenders. In the previous call, the second line mapped (x, x + r) to (x + r - x) % 2 = 1, so the result of M(x, y) will match the pattern (x, 1, 1, ...).
If r = 1 and x is odd, m(x, r) = (x, (x - r) % 2) = (x, 0), and the recursive call to M succeeds.
Likewise, if r > 1, then m(x, r) = (x, (x - r) % 2) ≤ (x, 1) < (x, r), and the recursive call to M succeeds.
In both cases, the second line will be evaluated for the last time with argument (x, t). Since we have t < r < x, the outcome is the non-zero vector (x - t), so the result of M(x, y) will match the pattern (x, ?, x - t, ...).
Thus, the third element of the vector returned by M(x, y) will be 0 if and only if x is a divisor of y.
[TIO-jf0gja4y]: https://tio.run/##JYy9CoQwEITrnaeYPjYn2KYIwS6@gxICFiGCvv/enMfAMj8fW0cdt7ttnKTAKGU2NmRY5gQt69sWFFhhhwUmdhGy65sgrJ4XlSL@leb2M1EHSV@wwRJFIQgeD7TU/XD3efl8AQ "Dodos – Try It Online" "Dodos – Try It Online" [DOS]: https://github.com/DennisMitchell/dodos#divide-or-surrender "DennisMitchell/dodos: Dodos Only Divide Or Surrender"