11
\$\begingroup\$

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.

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

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.

\$\endgroup\$
5
\$\begingroup\$

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

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

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ You could change 0.5 to .5 and input('') to input(). \$\endgroup\$ – Yytsi May 25 '16 at 8:42
2
\$\begingroup\$

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.

\$\endgroup\$
  • 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\$ – Yytsi May 25 '16 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\$ – Yytsi May 25 '16 at 4:00
  • 1
    \$\begingroup\$ Thanks, @TuukkaX . I forgot about the 2 character variable 'mi'. \$\endgroup\$ – Magenta May 25 '16 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\$ – Yytsi May 25 '16 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\$ – Yytsi May 25 '16 at 8:41
2
\$\begingroup\$

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.

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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