Find a function with cycles of every length

Question

A function is said to have a cycle of length n if there exists an x in its domain such that fⁿ(x) = x and f^m(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 fⁿ(x) = x and f^m(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 code-golf rules apply.

• Martin Ender: Closely related. While the differences seem minor, they imply that none of the old approaches work without significant modification, and in particular I don't think the winning approach from that challenge can be adapted at all.
• Abr001am: "has exactly one cycle of every length", "has many cycles of evry length": is this the only difference which distingishes thid from other ?
• Martin Ender: @Agawa001 That's one difference, the other is that the other challenge is about functions on the positive integers, whereas this challenge asks for a function on all integers.
• xnor: I think your definition of cycle needs to include that n is minimal. Otherwise, your cycle of length 2 also counts as your cycle of length 4 and 6 and so on.
• Martin Ender: @xnor Whoops, good point.

Answer 1

Python 2, 55 bytes

g=lambda n,k=1:n/k and~g(~n+k*(n>0),k+1)+k*(n>0)or-~n%k

---

59 bytes:

g=lambda n,k=1:n<0and~g(~n,2)or n/k and k+g(n-k,k+2)or-~n%k

Creates the cycles

[0]
[-1, -2]
[1, 2, 3]
[-3, -4, -5, -6]
[4, 5, 6, 7, 8]
...

Modified from my solution on the earlier challenge, which is modified from Sp3000's construction.

The function

g=lambda n,k=1:n/k and k+g(n-k,k+2)or-~n%k

makes odd-size cycles of non-negative numbers

[0]
[1, 2, 3]
[4, 5, 6, 7, 8]
...

To find the correct cycle size k, shift the input n down by k=1,3,5,7,... until the result is in the interval [0,k). Cycle this interval with the operation n->(n+1)%k, then undo all the subtractions done on the input. This is implemented recursively by k+g(n-k,k+2).

Now, we need the negative to make the even cycles. Note that if we modify g to start with k=2 in g, we'd get even-size cycles

[0, 1]
[2, 3, 4, 5]
[6, 7, 8, 9, 10, 11]
...

These biject to negatives via bit-complement ~. So, when n is negative, we simply evaluate g(n) as ~g(~n,2).

• Neil: I don't know whether it helps, but another way of calculating k seems to be Math.floor(Math.sqrt(n))*2+1.
• xnor: @Neil I looked into determining the boundaries and cycle sizes arithmetically and even doing the whole computation that way, but these expressions are lengthy in Python and I found recursion to be shorter.

Answer 2

MATL, 47 bytes

E|G0<-QXJ:tQ*2/0hStJ<f0))Q2MQ)&:J6M-)2/ttk>Eq*k

Try it online!

General explanation

Function 2 below is the same as used in @Sp3000's answer to the related challenge. Thanks to @Agawa001 for noticing.

The function is the composition of three:

1. Bijection from Z (the integers) to N (the naturals).
2. Bijection from N to N with the desired characteristic (one cycle of each length).
3. Inverse of function 1.

Functions 1 and 3 are used because it's easier (I think) to achieve the desired behaviour in N than in Z.

Function 2 is as follows: upper line is domain, lower line is codomain. Commas are used for clarity:

1, 2 3, 4 5 6, 7 8 9 10 ...
1, 3 2, 6 4 5, 10 7 8 9 ...

The first block (from upper 1 to lower 1) is a cycle of length 1. The second (from 2 3 to 3 2) is a cycle of length 2, etc. In each block, the lower part (image of the function) is the upper part circularly shifted one step to the right.

Function 1 is as follows:

 -5 -4 -3 -2 -1 0 +1 +2 +3 +4 ...
+10 +8 +6 +4 +2 +1 +3 +5 +7 +9 ...

Function 3 is the same as 1 with the two lines swapped.

Examples

The image of 3 is -5. First 3 is mapped to 7 by function 1; then 7 is mapped to 10 by function 2; then 10 is mapped to -5` by function 3.

The length-1 cycle is 0. The length-2 cycle is -1 1. The length-3 cycle is -3 2 -2, etc.

Code explained

Functions 1 and 3 are straightforward.

Function 2 works by finding the lower endpoint of the corresponding input block. For example, if the input to this function is 9 it finds 7 (see blocks above). It then picks the upper endpoint, which is 10 in the example. The circular shift of the block is achieved thanks to MATL's 1-based, modular indexing.

 % FUNCTION 1
 % Implicit input
E| % Multiply by two. Absolute value
G0< % 1 if input is negative, 0 otherwise
- % Subtract
Q % Add 1
XJ % Copy to clipboard J. Used as input to the next function
 % FUNCTION 2
: % Range [1 2 ... J], where J denotes the input to this function
tQ* % Duplicate, increment by 1, multiply
2/ % Divide by 2
0hS % Prepend a 0. This is needed in case J is 0
tJ<f % Duplicate. Find indices that are less than the input J
0) % Pick the last index.
) % Apply as index to obtain input value that ends previous block
Q % Add 1: start of current block
2M % Push the two arguments to second-to-last function call
Q) % Add 1 and use as index: end of current block
&: % Inclusive binary range: generate input block 
J % Push J (input to function 2)
6M- % Subtract start of block
) % Apply as index (1-based, modular). This realizes the shifting
 % FUNCTION 3
2/ % Divide by 2
ttk> % Duplicate. 1 if decimal part is not 0; 0 otherwise
Eq % Multiply by 2, add 1
* % Multiply
k % Round down
 % Implicit display

• Abr001am: this is a twist of sp3000 s function right ?
• Luis Mendo: @Agawa001 Oh is it? I didn't see the other challenge. I'll take a look
• Luis Mendo: Oh. It definitely is. At least that clarifies that my reasoning, if not original, was correct :-)
• Abr001am: it is surprising how more than one mind are closely framed to exude close ideas.

Answer 3

Pyth, (削除) 27 (削除ここまで) 18 bytes

_h?gQ0^2Q*.5@,Q-xh

Explanation (Pyth initializes Q to the input integer):

_ negative of (
 (
 ?gQ0 if Q >= 0:
 ^2Q 2**Q
 else:
 *.5 half of
 @ Q element Q (modulo list length) in
 , the two element list [
 Q Q,
 hQ ((Q plus 1)
 x Q XOR Q)
 - Q minus Q
 ]
 h ) plus 1
 )

This has cycles

(−1)
(0, −2)
(1, −3, −4)
(2, −5, −7, −6)
(3, −9, −13, −11, −8)
(4, −17, −25, −21, −15, −10)
(5, −33, −49, −41, −29, −19, −12)
(6, −65, −97, −81, −57, −37, −23, −14)
(7, −129, −193, −161, −113, −73, −45, −27, −16)
(8, −257, −385, −321, −225, −145, −89, −53, −31, −18)
(9, −513, −769, −641, −449, −289, −177, −105, −61, −35, −20)
⋮

The cycle of length n is given by

(n − 2,
−2^(n − 2)⋅1 − 1,
−2^(n − 3)⋅3 − 1,
−2^(n − 4)⋅5 − 1,
...,
−2^2⋅(2·n − 7) − 1,
−2^1⋅(2·n − 5) − 1,
−2^0⋅(2·n − 3) − 1).

Each integer k ≥ −1 appears as the first element of the (k + 2)-cycle. For each integer k < −1, we can uniquely write 1 − k = 2^i ⋅ (2⋅j + 1) for some i, j ≥ 0; then k appears as the (j + 2)th element of the (i + j + 2)−cycle.

Answer 4

Python 3, 110 bytes

I still have not figured out how to get a lambda in there

if n is a triangle number [1,3,6,10,15,21,28,etc...] then f(n) is the order in the list multiplied by negative one. if the number is negative, give it 1+the next smallest triangle number. else, increment.

Example: 5 is not a triangle number, so add 1.

Next iteration, we have 6. 6 is a triangle number, and it is the 3rd in the list, so out comes -3.

The program gives these lists

length 1:[0]

length 2:[1,-1]

length 3:[2,3,-2]

length 4:[4,5,6,-3]

length 5:[7,8,9,10,-4]

x=int(input())
if x<0:print((x**2+x)/2+1)
else:
 a=((8*x+1)**.5-1)/2
 if a%1:print(x+1)
 else:print(-a)

Edit: Thanks again to @TuukkaX for removing excess charcters.

• Yytsi: You could change 0.5 to .5 and input('') to input().

Answer 5

Python 3, 146 bytes

For every number greater than 0, there are even loops (len 2,4,6,8...), and less than 0, odd loops (1,3,5,7). 0 maps to 0.

(-3,-2,-1),(0),(1,2),(3,4,5,6)

maps to

(-2,-1,-3),(0),(2,1),(6,3,4,5)

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)

Edit: @TuukkaX took off 8 bytes from the previous solution. And another 3.

• Yytsi: 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.
• Yytsi: 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)
• Magenta: Thanks, @TuukkaX . I forgot about the 2 character variable 'mi'.
• Yytsi: 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.
• Yytsi: 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)

Answer 6

Matlab(423)

function u=f(n),if(~n)u=n;else,x=abs(n);y=factor(x);for o=1:nnz(y),e=prod(nchoosek(y,o)',1);a=log(x)./log(e);b=find(a-fix(a)<exp(-9),1);if ~isempty(b),k=e(b);l=fix(a(b));break;end;end,if(abs(n)==1)k=2;l=0;end,if(k==2)l=l+1;x=x*2;end,e=dec2base(l,k)-48;o=xor(e,circshift(e,[0 1]));g=~o(end);if(~o|nnz(o==1)~=numel(e)-g),u=n*k;else,if((-1)^g==sign(n)),u=sign(n)*k^(base2dec([e(2:end-1) 1]+48,k)-(k==2));else,u=n*k;end,end,end

• Non-competing because it breaks a good record of being condidate for the last ranking, whilst I am struggling to shorten it as possible as i can.

• Some nonesensical bugs concerning accuracy in matlab that I couldnt find any way out except making my code sarcatistically big, in other hand the mapping I opt for was in terms of prime facors and n-ary logarithm.

Execution

 f(2)
 1
 f(1)
 2
 f(-2)
 -4
 f(-4)
 -8
 f(-8)
 -1
 f(0)
 0
 ----------------------------

Explanation

• Knonwing, first off, that any number can be written as product of exponents of primes N=e1^x1*e2^x2... from this base i chose to map images of cycles C which are extracted from the biggest exponent of the smallest factor (not necessarily prime) that N is a perfect power of.

• in simpler words, let N=P^x where P is the smallest perfect root, x denotes precisely two essential terms for the cycle : x=Ʃ(r*P^i), a term P is the base of cycle as well a perfect root for the main number N, and k is the degree of the cycle C=p^k, where i varies between 1 and k, the coeffecient r is incremented by 1 and bounded by P-1 for any following pre-image until all coeffecients are set to r=1, so we move to the start of that cycle.

• To avoid collisions between cycles the choice of exponentiation of primes rather than their products is accurate, because as an example of two cycles of bases 3 and 2 a meetpoint between them can be 3*2, so this is avoided since a cycle is defined by its degree more than its base , and for the meetpoint there is another cycle of base 6 and degree 1.

• Negative numbers place an exception, as for it, i reserved odd degrees for negative numbers, and even degrees for the rest. How so ?

  for any number N embedded within a cycle P^k, is written as P^(a0*P^i0+a1*P^i1+...), the amount (a0*P^i0+a1*P^i1+...) is transalted in P-ary base as a0,a1,.... , to clarify this point if (p=2) the sequence must be in binary base. As is known prealably without setting the condition of positive/negative degrees and the (+/-1) exception, a number N is on the edges of a cycle of degree k if and only if the sequence A is written as 1111..{k+1}..10 or 111..{k}..1 for all bases, otherwise no rotation is needed, thus assigning negative/positive condition for a respective odd/even degrees k/k' for both makes an odd sequence written in the form 101..{k}..100, an even sequence is written in the form 101..{k'}..10 for a beginning edge of a respectively negative/positive number-cycle.

  Example:

  Taking a number N=2^10, x=10=2^1+2^3 , the sequence A is written A=1010, this type of sequence symptomizes a finite edge of positive number-cycle, which is C=2^3, so the next image is that of beginning edge A=011 which is 8, But, by standarizing this result to (+/-)1 exception 2^10/2 maps to 8/2 and the previous image mustnt be rotated.

  Taking a number N=-3^9, x=9=3^2 , the sequence A is written A=100, this type of sequence symptomizes a finite edge of negative number-cycle, which is C=3^1, so the next image is that of beginning edge A=01 which is 3, But, by adapting this result to negative/positive condition -3^9 maps to -3 .

• for the couple (-/+)1, i envisaged to intrude it within numbers of cycle-bases 2, in a guise that an ordinary sequence of cyclic groups {2,4}{8,16,32,64}.. are made up in another form {1,2}{4,8,16,32}.., this prevents any loss of previous elements, and the opeation done is just shifting with popping a new element in.

---

Results:

running this little code-sheet to verify the first reasonable ranges of cyclic numbers:

for (i=1:6) 
index=1;if(max(factor(i))>=5) index=0;end
for ind=0:index
j=f(((-1)^ind)*i); while(((-1)^ind)*i~=j)fprintf('%d ',j);j=f(j);end,fprintf('%d \n',(-1)^ind*i),pause,end,
end

This leads to this results

 2 1 
 -2 -4 -8 -1 
 1 2 
 -4 -8 -1 -2 
 9 27 3 
 -9 -27 -81 -243 -729 -2187 -6561 -19683 -3 
 8 16 32 64 128 256 512 4 
 -8 -1 -2 -4 
 25 125 625 3125 5 
 36 216 1296 7776 46656 6 
 -36 -216 -1296 -7776 -46656 -279936 -1679616 -10077696 -60466176 -362797056 -2.176782e+009 -1.306069e+010 ??? Error using ==> factor at 27

The last one is segmentation-error but it fits the [-127,127] standard signed-integer range.

• Abr001am: I used this technique awhile ago to define hash functions in an old C program of mine, it works neat !

Answer 7

JavaScript (ES6), 73 bytes

f=(n,i=0,j=0,k=0,l=1,m=i<0?-i:~i)=>n-i?f(n,m,k++?j:i,k%=l,l+!k):++k-l?m:j

Works by enumerating the sequence (0, -1, 1, -2, 2, -3, 3, ...) until it finds n, counting cycles as it goes. i contains the current entry; j contains the start of the current cycle, k the index within the cycle, l the length of the current cycle and m the next entry in the sequence. Once we find n we then take j if we're at the end of a cycle or m if not.