Define a function f such that f(f(n)) = -n for all non-zero integers n

Question

This challenge was inspired by a programming blog I frequent. Please see the original post here: A Programming Puzzle

---

Challenge

Define a function \$f:\mathbb{Q}\to\mathbb{Q}\$ such that \$f(f(n)) = -n\$ for all non-zero integers \$n\$, and where \$\mathbb{Q}\$ is the set of rational numbers.

Details

In whatever language you prefer, please define one function or program \$f\$ that accepts as parameter one number \$n\$ and returns or outputs one number \$f(n)\$.

Input may be provided through whichever mechanism is most natural for your language: function argument, read from STDIN, command-line argument, stack position, voice input, gang signs, etc.

Output should be a return value from a function/program or printed to STDOUT.

I would like to restrict answers to functions that do not take advantage of program state or global memory/data that is visible from outside of the function \$f\$. For example, keeping a counter outside of \$f\$ that counts how many times \$f\$ was called and just doing a negation based on this count isn't very challenging or interesting for anyone. The decisions \$f\$ makes should rely only on data within \$f\$'s lexical scope.

However, this restriction is probably inappropriate for some stack-oriented languages or other types of languages that do not distinguish these types of data or scopes. Please use your best judgement to keep with the spirit of this challenge.

---

Scoring

Standard code golf rules apply - your score is the number of bytes in your source code.

The minimal answer requires the domain and codomain of \$f\$ to be a subset of the rationals \$\mathbb{Q}\$. If you restrict your domain and codomain of \$f\$ to the integers \$\mathbb{Z}\$, then your score is the ceiling of 90% of the number of bytes in your source code.

Tiebreak

In the event of a tie, the following will be used in order:

1. Fewest number of printable non-whitespace symbols in your source code
2. Earliest date and time of answer submission

---

You are not required to support arbitrarily sized numbers. Please interpret the sets \$\mathbb{Z}\$ and \$\mathbb{Q}\$ as datatypes in your chosen language (typically integer and floating point, respectively).

If your solution relies entirely on the underlying structure or bit pattern of a data type, please describe its limitations and how it is being used.

Answer 1

Python: 61 34 30 29 27 points

f: Q -> Q

in math:

       | 0.5-x   if x is in Q \ Z
f(x) = |
       | x+0.5   if x is in Z

in Python:

f=lambda x:.5+[x,-x][x%1>0]

tested with

filter(lambda n: n[0] != -n[1], map(lambda n:(n,f(f(n))),range(0,50)))

logic behind this:

When you take an integer n and put it into f you will get x+0.5. This is not an integer any more, so the next application will be 0.5-(x+0.5) which is -x.

Credits

Thanks to

• Bakuriu for striping it down from 61 characters to 34 characters.
• Volatility for further reducing code size to 30 characters.
• copy for reducing code size to 29 characters (and fixing a potential floating point problem).
• aditsu for mentioning an inconsistency that came with the changes above.

Notes

First I thought this would be ok

f = lambda n: 1j*n

but its f:N->C and that is not allowed :-/

Answer 2

J, 9 points (10 chars)

Based on stackoverflow answer:

   (*-[*_1&^)

First idea (13 chars):

   ((-*)-2&|*+:)

   ((-*)-2&|*+:) _10 _9 _8 _7 _6 _5 _4 _3 _2 _1 0 1 2 3 4 5 6 7 8 9 10
_9 10 _7 8 _5 6 _3 4 _1 2 0 _2 1 _4 3 _6 5 _8 7 _10 9

   ((-*)-2&|*+:) _9 10 _7 8 _5 6 _3 4 _1 2 0 _2 1 _4 3 _6 5 _8 7 _10 9
10 9 8 7 6 5 4 3 2 1 0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _10

Answer 3

C, 41 points (41 or 45 chars)

Works using both 32- and 64-bit.

f : Z -> Z (except INT_MAX):

f(n){return (abs(n)%2*2-1)*n+n?(-n<n)*2-1:0;}

---

If we don't have to include 0 we can shave off some chars (41 chars):

f : Z -> Z (except 0 & INT_MAX):

f(n){return (abs(n)%2*2-1)*n+(-n<n)*2-1;}

---

This function works by dividing all integers into 4 groups based on their sign and parity.

So we have the 4 different combinations:

+ even, + odd, - even, - odd

As we need to switch the sign of the number, but not the parity after two passes, we get two different possible sequences:

  + even -> - odd -> - even -> + odd -\
^-------------------------------------/

  + even -> + odd -> - even -> - odd -\
^-------------------------------------/

In this example I have chosen the first one.

First we need to map all even positive integers to odd negative integers. We do this by changing the sign and incrementing the number (you could also choose to decrement the number instead):

f1(n) = -n + 1

We then need to map all odd negative integers to even negative integers. We need to make sure that f2(f1(n)) = -n:

f2(f1(n)) = -n
f2(-n + 1) = -n
f2(-n) = -n - 1
f2(n) = n - 1

Using the same methods we find f3 and f4:

f3(n) = -n - 1
f4(n) =  n + 1

To combine these functions into one single function, we observe that every time n is even we switch the sign of n and every time n is positive we increment by one and otherwise we decrement by one:

f1(n) = -n + 1 (+ even)
f2(n) =  n - 1 (- odd)
f2(n) = -n - 1 (- even)
f4(n) =  n + 1 (+ odd)

This can thus be rewritten as:

f(n) = odd(n) * n + sign(n)

where odd(n) returns 1 for odd numbers and -1 for even numbers.

There are 4 solutions total:

f(n) = odd(n) * n + sign(n)  (edge cases: f(f(0))  -> -2, f(f(INT_MAX))   -> -8)
f(n) = even(n) * n - sign(n) (edge cases: f(f(0))  -> -2, f(f(INT_MIN+1)) -> -6)
f(n) = odd(n) * n - sign(n)  (edge cases: f(f(1))  -> -3, f(f(INT_MIN))   -> -5)
f(n) = even(n) * n + sign(n) (edge cases: f(f(-1)) -> -1, f(f(INT_MIN))   -> -5)

INT_MIN might always be considered an edge case in all 4 functions as -INT_MIN == INT_MIN => f(f(INT_MIN)) = INT_MIN.

Answer 4

Here's my go at it.

long f(int i){return i;}
int f(long i){return -i;}

Live example:

int main()
{
  for(int i=-10; i<10; i=i+3)
    std::cout << f(f(i)) << "\n";
}

The input types cn be arbitrarily tailored to suit your needs. This version works for integer literals that are smaller in magnitude than 2^32-1.

Answer 5

JavaScript, 18

f=n=>n%1?.5-n:n+.5

Using the new fat arrow notation (Firefox 22).

Other version (18):

f=n=>n%1?-.5/n:.5/n

Previous version (20):

f=n=>n-~~n?.5-n:n+.5

Example:

> [-3,-2,-1,1,2,3].map(f).map(f)
[3, 2, 1, -1, -2, -3]

Answer 6

Mathematica 18

f=#+1/2-4#(#-⌊#⌋)&

Here ⌊...⌋ is the floor function. It uses only rational numbers (not lists, complex numbers, etc)

f[10]
f[f[10]]

21/2

-10

f[-5]
f[f[-5]]

-9/2

5

Answer 7

x86 assembly language (FASM). The argument and the result are in eax register.

It works properly for -2^30 < N < +2^30-1

16 bytes executable code.

        use32

f_n:
        lea     edx, [2*eax]
        xor     edx, eax
        btc     eax, 30
        shl     edx, 1
        jnc     .end
        neg     eax
.end:
        retn

Answer 8

Common Lisp: 35 bytes

(defun f(x)(/(if(> 1 x)-1/2 1/2)x))

Scheme (and Racket): 36 bytes

(define(f x)(/(if(> 1 x)-1/2 1/2)x))

Ungolfed with comments and explanation:

(define (f x)
  (/             ;; divide
     (if (> 1 x) ;; if x is below 1 
         -1/2    ;; then -1/2 (the fraction)
         1/2)    ;; else 1/2 (the fraction)
      x))        ;; gets divided with x

For any number x in [1,->] the if will turn into the fraction 1/2 which is a real exact number in both languages.

The divide part will then become (/ 1/2 x) so the fraction will become 1/(x*2) which always is below 1. For 1 it will be 1/2, for 2 it's 1/4, etc.

For any number below 1 the if will turn in to the fraction -1/2, which makes the function do (/ -1/2 x) which is -1/(2*x) but since we can expect the value to be result of the previous run we can substitute x for 1/(x*2) making a double application -1/((1/(x*2))*2) = -x

E.g. since 1 turns into 1/2 the second application is (/ -1/2 1/2) ==> -1

Answer 9

C, 60 (⌈66 * .9⌉)

int f(int x){if(!x&1||!~x)return ~x;if(x<0)return x-1;return x+1;}

Here is an uncondensed version:

int f(int x){
    if(!x&1 || !~x) return ~x;
    if(x<0) return x-1;
    return x+1;
}

This method works using only integers, so it gets the 90% score bonus. I was originally writing it in java, but realized that this program in particular could benefit from C-style logical operators.

As there is no integer corresponding to -INT_MIN, f(f(INT_MIN)) returns INT_MIN instead.

The underlying mapping is algebraically rather simple. Executing the statement x=f(x) replaces x with:

• x+1, if x is positive and odd
• -x+1, if x is positive and even
• x-1, if x is negative and odd
• -x-1, if x is negative and even

The result of each case will fall under the next case the next time the function is applied to x.

As you can see, composing a case with the case following it yields -x.

The code is a result of some clever simplification of the function to take advantage of the bit structure of two's compliment integers.

Answer 10

><>, 21 + 3 = 24 bytes, 22 points

:0)$:0($:1$2%2*-*+-n;

Use the official Python interpreter, and use the -v command line option to enter input, at a cost of 3 bytes.

I have a feeling that this could be better--I'll keep looking at it and try to golf it down.

Given input n, the program outputs

(n>0) - ((n<0) + n * (1 - 2*(n%2)))

where (n>0) and (n<0) are booleans. This is equivalent to Gelatin's Python answer

(n>0) - (n<0) - n * (-1)**n

but ><> doesn't have a built-in exponentiation operator so we use (1 - 2*(n%2)) in place of (-1)**n.

What follows is mathematical theory -- read if (and only if) you are interested:

Given any function f: Z -> Z such that f(f(n)) = -n for all n in Z, we see immediately that f(f(f(f(n)))) = n, or in other words, f^4 is the identity function. In particular, f is invertible, and its inverse function is f^3. Thus f is a permutation of Z, and since f^4 = Id, it follows that every orbit (or cycle) of f has size either 1, 2, or 4.

Next, we see that f(0) = 0. Proof: f(0) = f(-0) = f(f(f(0))) = -f(0), so f(0) = 0, as desired. Conversely, suppose x is in a cycle of length 1 or 2, so f(f(x)) = x. Then -x = x so x = 0.

Thus f is made up entirely of 4-cycles, except for the fixed point (1-cycle) at 0.

Further, every 4-cycle must have the form (x, y, -x, -y), and by rotating the cycle around we may assume that x and y are both positive. Conversely, every such product of 4-cycles partitioning the nonzero integers determines a choice of f.

Thus each choice of f corresponds uniquely to a directed graph whose vertices are the positive integers, such that every vertex is incident to exactly one arrow, either entering or exiting. More precisely, in the underlying undirected graph, every vertex has degree exactly 1. (Each 4-cycle (x y -x -y) with x and y positive corresponds to the arrow x --> y.)

The function in this answer (and several other answers here) corresponds to the graph where 1 --> 2, 3 --> 4, and in general 2k-1 --> 2k.

Such graphs are in bijection with infinite sequences of ordered pairs (a_n, p_n), where each a_n is a positive integer and each p_n is either 0 or 1: given a sequence (a_1, p_1), (a_2, p_2), (a_3, p_3), ..., we first pair 1 with 1 + a_1, and then we form either the arrow 1 --> 1 + a_1 or the arrow 1 + a_1 --> 1 depending on whether p_1 is 0 or 1. Essentially, the arrow is either a < sign or a > sign, depending on the parity of p_1.

Next, take the smallest unpaired positive integer k, and count up from k, exactly a_2 steps, SKIPPING any number that is already paired with something. Pair k with the result, and set the direction of the arrow depending on p_2 as above. Then repeat with (a_3, p_3), etc.

Each arrow will eventually be determined this way, so the process is well defined. The function in this answer corresponds to the sequence (1,0), (1,0), (1,0), ..., since at step n the smallest unpaired integer is 2n-1 and no integers larger than 2n-1 have been paired with anything, so we get 2n-1 --> 2n for each n (arrows are oriented this way because each p_n equals 0).

The cardinality of this set is (N*2)^N = N^N, which by the last paragraph of this answer equals 2^N, the cardinality of the real numbers.

Answer 11

To fix the earlier J answer (I don't have enough reputation to comment on the original):

(*+[*1-~2*2|])

It just replaces the _1&^ with 1-~2*2|], which gives the opposite sign. So I changed the - to a + (which only matters on input of 1 and _1).

Here are the tests:

   (*+[*1-~2*2|])6 3 _9 _8 1r2 _4.6 0 1 _1
7 _2 8 _9 1 7.28 0 2 _2
   (*+[*1-~2*2|])7 _2 8 _9 1 7.28 0 2 _2
_6 _3 9 8 0 _10.3568 0 _1 1

   NB. f^:2 = f@:f
   (*+[*1-~2*2|])^:(2)6 3 _9 _8 1r2 _4.6 0 1 _1
_6 _3 9 8 2 _5.0832 0 _1 1

As you can see, the domain and range are of all real numbers, but it only works for integers (including 0).

Explanation:

(   *     + [ *  1-~    2*     2|]    )
 signum n + n * pred (twice (n mod 2))

Answer 12

GolfScript ceiling(26*.9)=24

Golfscript only handles integers, so apply the Z bonus for a total of 24 points:

.{..0>2*(\)2%!2*(@*+}{ }if

The special case of 0 accounts for 8 characters. Ignoring 0, we can have a 17 point answer:

..0>2*(\)2%!2*(@*+

This code does the following to an integer x on top of the stack:

• If x is 0, leave 0 on the stack and apply no more rules.
• If x is even, negate x.
• If x is positive, add 1.
• If x is negative, subtract 1.

This logically connects sets of 4 numbers in a cycle, where f traverses elements of the cycle, and opposite corners of the cycle are negatives of each other. Every integer is part of exactly 1 such cycle, except 0 which is special cased. For example, for {-8, -7, 7, 8}:

• 7 f -> 8
• 8 f -> -7
• -7 f -> -8
• -8 f -> 7

The only relevant test cases I could think of were a negative odd, negative even, positive odd, positive even, 0, and then I threw in -1 and 1 since their proximity to 0 may have caused problems:

[-10 -5 -1 0 1 5 10]
{.{..0>2*(\)2%!2*(@*+}{ }if}:f;
{f f}%
-> [10,5,1,0,-1,-5,-10]

I'm sure the actual GolfScript can be improved somewhat. It doesn't feel like it should take up 26 characters! Would love to hear some suggestions.

Answer 13

Java, just for fun

Here's an implementation that does an actual bijection between ℤ and ℤ², which is an odd function at the same time (g(-x) == -g(x)). It treats the corresponding ℤ² element as a complex number and multiplies it by "i", then converts back to ℤ.

f(x)=g⁻¹(ig(x))
f(f(x))=g⁻¹(-g(x))=-x

The function runs in O(1).

public class Ffn {
    public static int f(int n) {
        if (n == 0) {
            return 0;
        }
        // adjust sign
        int s = n > 0 ? 1 : -1;
        int m = n * s;
        // calculate square "radius"
        int r = (int) (Math.sqrt(2 * m - 1) + 1) / 2;
        int q = r * 2;
        // starting point
        int x = r, y = r;
        int k = q * (r - 1) + 1;

        if (m - k < q) {
            // go left
            x -= m - k;
        }
        else {
            // go left
            x -= q;
            // go down
            y -= m - k - q;
        }

        // multiply by i
        int x2 = -y * s, y2 = x * s;
        // adjust sign
        s = y2 < x2 || y2 == x2 && x2 < 0 ? -1 : 1;
        x2 *= s;
        y2 *= s;

        if (y2 == r) {
            // go left
            k += r - x2;
        }
        else {
            // go left and down
            k += q + r - y2;
        }
        return k * s;
    }

    public static void main(final String... args) {
        for (int i = 0; i < 1000000; ++i) {
            if (f(f(i)) != -i || f(f(-i)) != i) {
                System.out.println(i);
            }
        }
    }
}

P.S. Happy New Year!

Answer 14

Python 3 - 38

Similar to @moose's answer, but, f(n) == n. Works for all integer values.

f=lambda x:x*(isinstance(x,int)*2.0-1)

Answer 15

Perl, 33 (non-whitespace)

sub f{($=)=@_;$=-$_[0]?-$=:"$=.1"}

Edit:

• $=.".1" shortened to "$=.1" (thanks ardnew).

Math:

Ungolfed:

# script.pl
sub f {
  ($=) = @_;   # short for $= = int($_[0]); 
               # "int" is implicit in assignments to $=;
               # ($=) can be prepended by "local" to get
               # the function free of side effects.

  $= - $_[0] ? # short for $= != $_[0], check if input is integer
    -$=        # input is not an integer  
  : $= . ".1"  # input is integer
}  

# Testing
chomp;
$_ = sprintf "f(f($_)) = f(%s) = %s\n", f($_), f(f($_));

Examples:

perl -p script.pl
7
f(f(7)) = f(7.1) = -7
2
f(f(2)) = f(2.1) = -2
0
f(f(0)) = f(0.1) = 0
-1
f(f(-1)) = f(-1.1) = 1
-10
f(f(-10)) = f(-10.1) = 10
-1.23
f(f(-1.23)) = f(1) = 1.1
3.4
f(f(3.4)) = f(-3) = -3.1
1.0
f(f(1.0)) = f(1.1) = -1

Answer 16

Julia, 26

julia> f(n::Int)=n//1
f (generic function with 1 method)
julia> f(n)=int(-n)
f (generic function with 2 methods)
julia> f(f(4))
-4

Not super competitive, but very Julian since it relies on multiple dispatch. It just makes n a Rational if its an Int, or an int with a minus sign if it is anything else. One might object that this is 2 functions, but Julia considers this to be one function with two methods, and it is equivalent to defining one function with an if statment on the type of n.

Answer 17

Candy, 20 18 bytes

Uses the 3 -> 4 -> -3 -> -4 -> 3 trick.

~A2%{|m}1A0>{+|-}.

To invoke it use the -i switch on the interpreter

Example of double-invokation:

$ candy -i 7 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> 8
$ candy -i 8 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> -7
$ candy -i -7 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> -8
$ candy -i -8 -e '~A2%{|m}1A0>{+|-}.'
program length: 18
>>> 7

Long form:

peekA
pushA
digit2
mod          # even/odd
if
else
  negate     # negate even numbers
endif
digit1
pushA
digit0
greater      # positive/negative
if
  add        # add two numbers from stack (original stack value, and delta)
else
  sub        # diff two numbers from stack (original stack value, and delta)
endif
retSub

Answer 18

Dyalog APL, 9 points

×-⍨⊢ׯ1*⊢

The source is 9 bytes long and qualifies for the bonus (which doesn't help at all). It also uses the formula from the top SO answer.

Answer 19

Python: 32 bytes (29 points)

f: Z -> Z

f=lambda n:(n>0)-(n<0)-n*(-1)**n

Using Ben Reich's method.

Answer 20

GTB, 22

@S;N,"--$x?N)→N~N#~-N&

Answer 21

Java, 113 bytes

The approach is pretty simple. It ended up more bytes than I anticipated, but can perhaps be golfed down a bit.

public class F{public static int f(int x){if(x<0)x+=-2147483647-++x;x+=1073741824;return x<0?-2147483647-++x:x;}

It basically creates 4 different "areas" of x, utilizing the fact that Java happily lets variables wrap around. I had to do some tricky conversion for negative numbers which is the main reason this ended up bigger than anticipated.

Works for all x besides -2147483648.

Answer 22

Same sequence of numbers (3, 4, -3, -4, 3 ...) as the golfscript answer, but implemented in perl (42 chars after whitespace is stripped)

sub f{($_[0]%2?1:-1)*$_[0]+($_[0]<0?-1:1)}

More legibly:

sub f { ($_[0] % 2 ? $_[0] : -$_[0] ) + ( $_[0] < 0 ? -1 : 1 ) }

Or even more legibly:

sub f {
  my $n = shift;
  my $sign = $n >= 0 ? 1 : -1;
  # note that in perl $n % 2 is the same as int($n) % 2
  if( $n % 2 ) {
    # odd: add one to magnitude
    return $n + $sign
  } else {
    # even: subtract one from magnitude then invert
    return -($n - $sign)
  }
}

Output:

ski@anito:~/mysrc/.../acme$ echo 3 | perl -e 'sub f{($_[0]%2?1:-1)*$_[0] + ($_[0]<0?-1:1)}; my $x = <>; for(0..10) { print "$_: $x\n"; $x = f($x); }'
0: 3
1: 4
2: -3
3: -4
4: 3
5: 4
6: -3
7: -4
8: 3
9: 4
10: -3

Answer 23

Sed, 25 bytes.

|sed s/0+/0-/|sed s/^/0+/

Usage:

$ echo 1.23 |sed s/0+/0-/|sed s/^/0+/
0+1.23
$ echo 0+1.23 |sed s/0+/0-/|sed s/^/0+/
0+0-1.23

Answer 24

Matlab, 26 characters

f=@(n) (n<0)-(n<0)-n*(-1)^n

Answer 25

C++ - 63 55.8

This is how the code looks:

int f(int n){return (n&45056?n^45056:n|45056)*(n&45056?-1:1);}

It doesn't work on integers whose fourth byte is equal to 0xB as it uses that value to keep track of passes. Otherwise works on any member of Z, including zero.

Answer 26

Updated with function supplied by Synthetica (obviously the one who should get credit for this now)

Language: Python

Number of characters: 41 including whitespace

f=lambda x:-float(x) if str(x)==x else`x`

Answer 27

Prolog, 36 bytes

Code:

X*Y:-X//1=:=X,Y is 0.5+X;Y is 0.5-X.

Explained:

Dyadic predicate which converts integers to floats and floats back to negated integers.

Example:

10*X.
X = 10.5

10*Y,Y*X.
X = -10,
Y = 10.5

Answer 28

Javascript ES6, 27 26 bytes

a=>a%1?-Math.floor(a):a+.2

Answer 29

Mouse-2002, 21 19 12 bytes

$A1%[1%_|1%]

Defines a function A; call it like #A,#A,?;; (which will wait for the user to enter any number). Alternatively, call it like #A,#A,n;; where n is any number.

Answer 30

Julia, 21

f(x)=(1-2(1>x>-1))/2x

Then

julia> f(f(12//1))
-12//1

p//q is julia's literal notation of rational numbers.