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.

• 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. – Martin Ender May 24 '16 at 17:47
• "has exactly one cycle of every length", "has many cycles of evry length": is this the only difference which distingishes thid from other ? – Abr001am May 24 '16 at 18:14
• @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. – Martin Ender May 24 '16 at 18:15
• 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. – xnor May 24 '16 at 19:33
• @xnor Whoops, good point. – Martin Ender May 24 '16 at 21:28

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.

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).

• I don't know whether it helps, but another way of calculating k seems to be Math.floor(Math.sqrt(n))*2+1. – Neil May 24 '16 at 21:36
• @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. – xnor May 24 '16 at 21:37

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

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

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.

• You could change 0.5 to .5 and input('') to input(). – Yytsi May 25 '16 at 8:42

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.

• 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 May 25 '16 at 3:56
• 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) – Yytsi May 25 '16 at 4:00
• Thanks, @TuukkaX . I forgot about the 2 character variable 'mi'. – Magenta May 25 '16 at 5:23
• 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 May 25 '16 at 8:37
• 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) – Yytsi May 25 '16 at 8:41

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.

• I used this technique awhile ago to define hash functions in an old C program of mine, it works neat ! – Abr001am May 24 '16 at 23:42

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.