20
\$\begingroup\$

Let \$Z\$ be either the integers, the positive integers, or the non-zero integers; pick whatever's convenient. Give two functions \$f\$ and \$g\$, each \$Z \to Z\$, such that:

  • \$f(g(a)) = g(f(a))\$, for infinitely many integers \$a\$, and
  • \$f(g(b)) \ne g(f(b))\$, for infinitely many integers \$b\$.

Rules

Many of the rules from f(g(x)) decreases while g(f(x)) increases are stolen here:

  • Please provide an argument for why your functions fulfill the requirements.
  • Interpret "function" in the mathematical sense. That is, they must be total (defined over all of \$Z\$) and pure (given the same input, it must produce the same output).
  • You may submit the functions as a single program or two separate ones.
    • A single program must either have two named functions \$f\$ and \$g\$, or, when run, have output that can be interpreted as a pair of two functions \$f\$ and \$g\$.
    • Two separate programs must have one give \$f\$, and the other give \$g\$. The two programs may not refer to each other. In this case, functions may be unnamed.
  • Standard submission rules and input/output methods apply, but we require that \$f\$ and \$g\$ must have identical input and output representations; that is, they can be directly composed without manually converting in between. Conceptually, they must be functions over integers, so you can't cheat by using two different string representations of the same number or anything like that.
  • The usual integer overflow rules apply: your solution must be able to work for arbitrarily large integers in a hypothetical (or perhaps real) version of your language in which all integers are unbounded by default, but if your program fails in practice due to the implementation not supporting integers that large, that doesn't invalidate the solution.
  • This is . If you submit a single program, your score is the number of bytes of that program. If you submit two programs, your score is the sum of the number of bytes of both programs.
Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ Sandbox. \$\endgroup\$
    – cjquines
    Jun 13, 2022 at 4:39
  • \$\begingroup\$ Can we return 1.0? \$\endgroup\$
    – Number Basher
    Jun 13, 2022 at 4:56
  • \$\begingroup\$ What counts as a function? Does 1+1 count as a function that returns 2? What about in brainf*ck? \$\endgroup\$
    – Number Basher
    Jun 13, 2022 at 5:03
  • 2
    \$\begingroup\$ @NobodyNeedsNames We have a standard rule for that. In typical languages like Python, 1+1 is a snippet and not a function. \$\endgroup\$
    – Anders Kaseorg
    Jun 13, 2022 at 5:21
  • \$\begingroup\$ @NobodyNeedsNames Even if 1+1 were considered a function, if f is a constant function, then so are fg and gf, so it's impossible to satisfy the challenge condition. \$\endgroup\$
    – Nitrodon
    Jun 14, 2022 at 17:55

25 Answers 25

Reset to default
13
\$\begingroup\$

Retina, 0 + 1 = 1 byte

Try it online!

This is a Count stage that matches an empty string at the start, between every two consecutive digits, and at the end. This produces the number of digits plus 1.

.

Try it online!

This is a Count stage that matches every digit, producing the number of digits.

Applying these in the two possible orders gives \$\mathrm{ndigits}(\mathrm{ndigits}(n))+1\$ and \$\mathrm{ndigits}(\mathrm{ndigits}(n)+1)\$, which are equal if and only if \$\mathrm{ndigits}(n)\$ is 1 less than a power of 10.

Improve this answer
\$\endgroup\$
13
\$\begingroup\$

Python, 3+4 = 7 bytes

abs

hash

These two builtins commute for most integers.

But not all:

The following depends on an implementation detail of CPython; I didn't find an official spec, below I give my best guess:

hash maps integers onto themselves modulo 2**61-1 (which appears to be the 9th Mersenne prime; also, this may depend on the bitness (32/64 etc.) of the C long of the platform) while keeping the sign (so -4 does not map to 2**61-5 but to -4). Therefore hash(-n)==-hash(n) for all integers except those which equal +/-1 modulo 2**61-1 because in the underlying C implementation -1 is used as an error indicator. So, whenever the hash would be -1, -2 is returned instead.

Minimal demo at TIO

Improve this answer
\$\endgroup\$
1
9
\$\begingroup\$

Jelly, 1 + 1 = 2 bytes

Ḃ

\$f(x) = x \bmod 2\$ (Try it online!).

Ḥ

\$g(x) = 2x\$ (Try it online!). These functions commute only for even input.

Improve this answer
\$\endgroup\$
0
9
\$\begingroup\$

Pascal (FPC), 7 bytes

succ

odd

Try it online!

succ acted as \$x \rightarrow x+1\$; while odd acted as \$x \rightarrow x \bmod 2\$. So succ(odd(x)) = odd(succ(x)) iff x is even.

Improve this answer
\$\endgroup\$
7
\$\begingroup\$

Brachylog, 1 byte (or 2 bytes if including call modifier)

b

Try it online!

I don’t know exactly if that’s bending the rules or not, let me know.

In this single program, f(x) is b - behead, with a given input and an unknown output, and g(x) is also b - behead, but with a given output and an unknown input.

You can run f(g(x) with ↰₁~↰₁ in the header, and g(f(x)) with ~↰₁↰₁. This is why I’m ok with this being scored as 2 bytes, as you need to use ~ to "reverse" the program’s calling order.

Explanation

b asserts that its output is the input without the first element.

  • For all positive integers that begin with a leading 1 (except 1 itself), f(g(x)) will remove this leading 1, and then add an unknown leading digit back. Since 0 cannot be a leading digit, this leading digit will unify with 1 as the next possibility, and so f(g(x)) = x. Similarily, g(f(x)) will append an unknown leading digit first, and then remove it, so once again g(f(x)) = x = f(g(x)).

  • For all positive integers that don’t begin with a leading 1 (and 1), f(g(x)) will remove the leading digit, and then append an unknown leading digit, which will unify with 1 as it is the first possibility. Since the initial leading digit wasn’t 1, we have f(g(x)) ≠ x. On the other hand, g(f(x)) will append an unknown leading digit, and then remove it, leaving x unchanged. So we have g(f(x)) = x ≠ f(g(x)).

Obviously, there are infinitely many positive integers that start with a leading 1, and infinitely many positive integers that don’t.

Improve this answer
\$\endgroup\$
2
  • 5
    \$\begingroup\$ My personal feeling is that a program that needs to be called in two different ways (using two different calling setups) is really two programs, so scoring 2 bytes here. But it's pretty cool anyway. \$\endgroup\$
    – Dominic van Essen
    Jun 13, 2022 at 9:45
  • 2
    \$\begingroup\$ @DominicvanEssen I mostly agree with this, although technically you don’t have to use ~ to call this program in the opposite way; you could just give a fixed output and a variable input. It’s just needed when I run both f and g in the same TryItOnline example. I’ve edited my answer anyway. \$\endgroup\$
    – Fatalize
    Jun 13, 2022 at 10:56
6
\$\begingroup\$

Wolfram Language (Mathematica), 7 bytes

Abs

#+1&

Try it online!

\$(f\circ g)(x)=|x+1|\$, the distance of \$x\$ from \$-1\$. \$(g\circ f)(x)=|x|+1\$, one more than the distance of \$x\$ from \$0\$. These are equal when \$x\ge0\$, and unequal when \$x<0\$.

Plot of abs(x) vs x+1

I suspect this is minimal. Trig functions such as Sin unfortunately are not \$\mathbb Z\to\mathbb Z\$.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ It seems that the shortest built-in-only results are {Abs | GCD | LCM, Hash | Ramp}. \$\endgroup\$
    – alephalpha
    Jun 14, 2022 at 2:54
6
\$\begingroup\$

Zsh, 6 + 6 = 12 bytes

tr 1 2

Attempt This Online!

tr 2 3

Attempt This Online!

The first program replaces 1s with 2s; the second replaces 2s with 3s. These commute only for numbers not containing the digit 1.

Old answer:

Zsh, 10 + 10 = 20 bytes

\$ f(x) = \lfloor \frac x 2 \rfloor \$

<<<$[$1/2]

Attempt This Online!

\$ g(x) = 2x \$

<<<$[$1*2]

Attempt This Online!

For even \$ x \$, \$ f(x) = \frac x 2 \$, so \$ g(f(x)) = x \$.

But for odd \$ x \$, /2 rounds downwards, so \$ f(x) = f(x-1) \$, so \$ g(f(x)) = x - 1 \ne x \$

\$ g(x) \$ is always even, so for all \$ x \$, \$ f(g(x)) = x \$.

Therefore, \$ f(g(x)) = g(f(x)) \$ if and only if \$ x \$ is even.

Improve this answer
\$\endgroup\$
0
6
\$\begingroup\$

Python, 9 + 3 = 12 bytes

\$ f(x) = \operatorname{bitwise\_or}(x, 1) = \begin{cases} x & x \text{ is odd} \\ x + 1 & x \text{ is even} \end{cases} \$

1 .__or__

Attempt This Online!

\$ g(x) = \lvert x \rvert = \begin{cases} x & x \ge 0 \\ -x & x \le 0 \end{cases} \$

abs

Attempt This Online!

Commutes for all \$ x \$ except negative even numbers.

If \$ x \$ is positive or odd, then at least one of \$ f \$ and \$ g \$ will act as the identity function \$ \operatorname{id} \$ and return \$ x \$ unchanged. In that case, clearly, they commute:

$$ h(\operatorname{id}(x)) = h(x) = \operatorname{id}(h(x)) $$

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Why wouldn't 1.__or__ work? \$\endgroup\$
    – Number Basher
    Jun 13, 2022 at 7:23
  • 4
    \$\begingroup\$ @NobodyNeedsNames Python parses that as 1. (a float), and the identifier __or__, which gives a syntax error, rather than 1, ., __or__ \$\endgroup\$
    – pxeger
    Jun 13, 2022 at 7:23
  • \$\begingroup\$ OH OK.............................................................. \$\endgroup\$
    – Number Basher
    Jun 13, 2022 at 7:24
5
\$\begingroup\$

R, 5 + 3 = 8 bytes

nchar

abs

Attempt This Online!

Commutative for positive values & zero, non-commutative for negative values (since the minus sign is counted as a character by nchar).

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ nchar has 5, not 4, or am I missing something here? \$\endgroup\$
    – loopy walt
    Jun 15, 2022 at 8:07
  • 2
    \$\begingroup\$ @loopywalt - Doh! Obviously my counting skills deteriorate once I need to use my thumb as well as fingers... \$\endgroup\$
    – Dominic van Essen
    Jun 15, 2022 at 8:27
4
\$\begingroup\$

Julia, 17

f(n)=n%2;g(n)=n%3

consider the numbers of form 6k and 6k+3.

ATO

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ two programs that return anonymous functions is shorter (n->n%2 and n->n%3) \$\endgroup\$
    – MarcMush
    Jun 13, 2022 at 21:33
4
\$\begingroup\$

K (ngn/k), 2 + 2 = 4 bytes

0=
1>

Try it online!

  • f: 0=, returns 1 if the input is 0, 0 otherwise.
  • g: 1>, returns 1 if the input is 0 or negative, 0 otherwise.

g is boolean negation when the domain is limited to booleans (0 and 1). f(x) and g(x) are the same for x>=0 and different otherwise, and the same can be said for g(f(x)) (negation of f(x)) and f(g(x)) (negation of g(x)).

4 bytes is optimal in ngn/k since any monadic function is at least two bytes long.

Czylabson Asa's mod-2 and mod-3 are also the same length in K: 2! and 3!.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

J, 3 bytes

|  absolute value

>: increment

Try it online!

See att's answer for explanation.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Octave, 14 bytes

I haven't seen anyone use this one yet, it might work better in another language. (And it is definitely possible to do better in Octave!)

@(x)x<0
@(x)x>0

The key here is that true == 1 and false == 0. Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 6 + 5 = 11 bytes

These functions commute for odd negative values and for even non-negative values. They do not commute for the other cases.

f=
x=>x%2 // 6 bytes
g=
x=>~x  // 5 bytes

Try it online!

Explanation

The sign of the modulo in JS is the sign of the numerator. So the functions are more formally defined as:

$$\begin{align}&f(x)=\cases{0&if $x$ is even\\-1&if $x<0$ and $x$ is odd\\1&if $x>0$ and $x$ is odd}\\ &g(x)=-x-1\end{align}$$

For odd negative values, we have: \$\cases{g(f(x))=g(-1)=0\\f(g(x))=f(-x-1)=0}\$

For even negative values, we have: \$\cases{g(f(x))=g(0)=-1\\f(g(x))=f(-x-1)=1}\$

For odd non-negative values, we have: \$\cases{g(f(x))=g(1)=-2\\f(g(x))=f(-x-1)=0}\$

For even non-negative values, we have: \$\cases{g(f(x))=g(0)=-1\\f(g(x))=f(-x-1)=-1}\$

Generalization

We can actually use any modulo \$m>1\$ for \$f\$, making the non-commutative cases more and more sparse as \$m\$ increases (but obviously, we'd still get infinitely many of them).

Try it online! (example with \$m=5\$)

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 4 bytes

| absolute value

1∘+ increment (lit. 1 curried to plus)

Try it online!

See att's answer for explanation.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Retina, 8 + 4 = 12 bytes

V`[1-9]+

Try it online! Link includes test cases. Explanation: Reverses all runs of non-zero digits.

L`.$

Try it online! Link includes test cases. Explanation: Outputs the last digit, without a sign.

The functions commute in a lot of cases such as the trivial ones of the input being a multiple of 10 or a repdigit.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

BQN, 3 bytes (SBCS)

|¬
|

Try it online!

abs(1-x) and abs(x) respectively. f(g(x)) = abs(1-abs(x)) and g(f(x)) = abs(abs(1-x)) = abs(1-x). The results differ if and only if x is negative.

   F←|¬
   G←|
   x←¯10+↕20
   (F G x)≍(G F x)
┌─                                           
╵  9  8 7 6 5 4 3 2 1 0 1 0 1 2 3 4 5 6 7 8  
  11 10 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8  
                                            ┘
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

x86 32-bit machine code, 2 + 2 = 4 bytes

40 C3
98 C3

Try it online!

Uses the regparm(1) calling convention – argument in EAX, result in EAX.

In assembly:

inc eax; ret – \$f\$ simply adds 1 to a number.

cwde; ret – \$g\$ sign-extends the low 16 bits of EAX, duplicating bit 15 into all the higher bits.

If the low 15 bits are not all 1, these two functions do not interact, thus they commute.

If the low 16 bits are 1111 1111 1111 1111, either order of functions results in 0.

If the low 16 bits are 0111 1111 1111 1111, applying \$f\$ then \$g\$ results in -32768, while applying \$g\$ then \$f\$ results in 32768.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

22 bytes total

R, 15 bytes

\(x)round(x,-2)

Attempt This Online!

R, 7 bytes

\(x)x^2

Attempt This Online!

Commutes for x 0 mod 100, doesn't for x 0 mod 10 but not 0 mod 100.

Improve this answer
\$\endgroup\$
1
2
\$\begingroup\$

Husk, 1+1 = 2 bytes

ṗ
¬

Try it online!

There are several 1+1 bytes pairs that work in Husk (including a port of the absolute-value/offset approach [a/→] that separates a/b by positive/negative values, and some other interesting approaches).

But I like this one best: ṗ and ¬ are commutative only for prime numbers, and non-commutative for all positive non-prime integers.

ṗ    # index of x in the infinite list of primes, or zero if non-prime
D    # logical NOT

So:

ṗ¬   # outputs zero for all nonzero inputs
¬ṗ   # outputs 1 for non-primes, zero for prime numbers
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 1 + 1 = 2 bytes

f(x) = ‹ and g(x) = ȧ.

ȧ is absolute value and ‹ is decrement, so \$f(g(x))\$ = \$\left|x-1\right|\$ and \$g(f(x))\$ = \$ \left|x\right| - 1\$, which are the same only on positive integers.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 3 + 3 = 6 bytes

Ｉ↔Ｎ

Try it online! Link is to verbose version of code.

Ｉ⊕Ｎ

Try it online! Link is to verbose version of code.

Another port of @att's Mathematica answer.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 3 + 4 bytes

abs
(+1)

If x is non-negative the functions commute, otherwise they do not.

Haskell, 4 + 8 bytes

(*2)
(`div`2)

If x is even, the functions commute. If x is odd, (``div`` 2) $ (*2) x is equl to x, while (*2) $ (``div`` 2) x is equal to x-1.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Not an improvement but (+1) can alternatively be written as succ. \$\endgroup\$
    – flawr
    Jun 13, 2022 at 9:53
0
\$\begingroup\$

Factor, 3 + 3 = 6 bytes

abs

?1+

Try it online!

Absolute value and increment. (?1+ is a single word/function that always increments integers by one or changes f [Factor's canonical false value] to 0.) Factor does not come with a 'normal' increment word, such as 1+ in Forth.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

sh + coreutils, 16 + 7 bytes

(cat;echo +1)|bc
tr -d -

The first function adds one to the number given in input; the second function calculates the absolute value. The composition here is intended as piping the output of one into the other, that is:

echo -n "-12" | (cat;echo +1)|bc | tr -d -
echo -n "-12" | tr -d - | (cat;echo +1)|bc
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.