Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
Code Golf

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

Required fields*

Find a function with cycles of every length

A function is said to have a cycle of length n if there exists an x in its domain such that fn(x) = x and fm(x) ≠ x for 0 < m < n, where the superscript n denotes n-fold application of f. Note that a cycle of length 1 is a fixed point f(x) = x.

Your task is to implement a bijective function from the integers to themselves, which has exactly one cycle of every positive length n. A bijective function is a one-to-one correspondence, i.e. every integer mapped to exactly once. Having exactly one cycle of length n means that there are exactly n distinct numbers x for which fn(x) = x and fm(x) ≠ x for 0 < m < n.

Here is an example of what such a function might look like around x = 0:

x ... -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 ...
f(x) ... 2 4 6 -3 -1 1 -4 0 -2 5 7 -7 -6 3 -5 ...

This excerpt contains cycles of length 1 to 5:

n cycle
1 0
2 -2 1
3 -4 -3 -1
4 -5 6 3 7
5 -7 2 5 -6 4
...

Note that above I'm using "function" only in the mathematical sense. You may write either a function or a full program in your language of choice, as long as it takes a single (signed) integer as input and returns a single (signed) integer. As usual you may take input via STDIN, command-line argument, function argument etc. and output via STDOUT, function return value or function (out) argument etc.

Of course, many languages don't (easily) support arbitrary-precision integers. It's fine if your implementation only works on the range of your language's native integer type, as long as that covers at least the range [-127, 127] and that it would work for arbitrary integers if the language's integer type was replaced with arbitrary-precision integers.

Standard rules apply.

Answer*

Draft saved
Draft discarded
Cancel
5
  • 1
    \$\begingroup\$ I think you can remove an whitespace before the if statement at the first line. And mi could be changed to something smaller, such as b. \$\endgroup\$ Commented May 25, 2016 at 3:56
  • \$\begingroup\$ Here is the same program golfed down: f=lambda x:1+2*int(abs(x)**0.5)if x<1 else 2*int(x**0.5+0.5) x=int(input()) n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n) \$\endgroup\$ Commented May 25, 2016 at 4:00
  • 1
    \$\begingroup\$ Thanks, @TuukkaX . I forgot about the 2 character variable 'mi'. \$\endgroup\$ Commented May 25, 2016 at 5:23
  • 1
    \$\begingroup\$ I also changed input('') to input(). The quotes are useless since we don't have to print anything to the console when we want to just get the input. \$\endgroup\$ Commented May 25, 2016 at 8:37
  • 1
    \$\begingroup\$ Even shorter. Removed the zeroes before the dots. f=lambda x:1+2*int(abs(x)**.5)if x<1 else 2*int(x**.5+.5) x=int(input());n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n) \$\endgroup\$ Commented May 25, 2016 at 8:41

AltStyle によって変換されたページ (->オリジナル) /