Uma função é dito que tem um ciclo de comprimento n se existe um x no seu domínio de tal modo que f ⁿ (x) = x e f ^m (x) ≠ x para 0 <m <n , onde o expoente n denota n - dobre a aplicação de f . Observe que um ciclo de comprimento 1 é um ponto fixo f (x) = x .

Sua tarefa é implementar uma função bijetiva dos números inteiros para si mesmos, que possui exatamente um ciclo de cada comprimento positivo n . Uma função bijetiva é uma correspondência individual, ou seja, todo número inteiro mapeado para exatamente uma vez. Tendo exactamente um ciclo de comprimento n significa que não são exactamente n números distintos x para o qual f ⁿ (x) = x e f ^m (x) x ≠ para 0 <m <n .

Aqui está um exemplo de como essa função pode parecer em torno de 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 ...

Este trecho contém ciclos de 1 a 5 :

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

Observe que, acima, estou usando "função" apenas no sentido matemático. Você pode escrever uma função ou um programa completo no idioma de sua escolha, desde que use um único número inteiro (assinado) como entrada e retorne um único número inteiro (assinado). Como de costume, você pode receber entradas via STDIN, argumento de linha de comando, argumento de função etc. e saída via STDOUT, valor de retorno da função ou argumento da função (saída) etc.

Obviamente, muitos idiomas não suportam (facilmente) números inteiros de precisão arbitrária. Tudo bem se a sua implementação funcionar apenas no intervalo do tipo inteiro nativo do seu idioma, desde que abranja pelo menos o intervalo [-127, 127] e funcione para números inteiros arbitrários se o tipo inteiro do idioma for substituído por arbitrário- números inteiros de precisão.

Aplicam-se as regras de código-golfe padrão .

Pitão, 27 18 bytes

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

Explicação (Pyth inicializa Qno número inteiro de entrada):

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

Isso tem ciclos

(−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)
⋮

O ciclo de comprimento n é dado por

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

Cada número inteiro k ≥ −1 aparece como o primeiro elemento do ciclo ( k + 2). Para cada número inteiro k <−1, podemos escrever exclusivamente 1 - k = 2 ^ i ⋅ (2⋅ j + 1) para alguns i , j ≥ 0; então k aparece como o ( j + 2) º elemento do ( i + j + 2) -Ciclo.

MATL , 47 bytes

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

Experimente online!

Explicação geral

A função 2 abaixo é a mesma usada na resposta do @ Sp3000 para o desafio relacionado. Obrigado a Agawa001 por perceber.

A função é a composição de três:

1. Bijeção de Z (números inteiros) a N (os naturais).
2. Bijeção de N a N com a característica desejada (um ciclo de cada comprimento).
3. Inverso da função 1.

As funções 1 e 3 são usadas porque é mais fácil (penso) para obter o comportamento desejado em N do que em Z .

A função 2 é a seguinte: linha superior é domínio, linha inferior é codomain. Vírgulas são usadas para maior clareza:

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

O primeiro bloco (de cima 1para baixo 1) é um ciclo de comprimento 1. O segundo (de 2 3para 3 2) é um ciclo de comprimento 2, etc. Em cada bloco, a parte inferior (imagem da função) é a parte superior deslocada circularmente um passo para a direita.

A função 1 é a seguinte:

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

A função 3 é igual a 1 com as duas linhas trocadas.

Exemplos

A imagem de 3é -5. Primeiro 3é mapeado para 7pela função 1; então 7é mapeado para 10pela função 2; então 10é mapeado para -5` pela função 3.

O ciclo comprimento-1 é 0. O ciclo comprimento-2 é -1 1. O ciclo comprimento-3 é -3 2 -2etc.

Código explicado

As funções 1 e 3 são simples.

A função 2 funciona encontrando o ponto final inferior do bloco de entrada correspondente. Por exemplo, se a entrada para esta função for 9encontrada 7(consulte os blocos acima). Ele escolhe o ponto final superior, que está 10no exemplo. O deslocamento circular do bloco é alcançado graças à indexação modular baseada em 1 do MATL.

         % 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

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

Cria os ciclos

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

Modificado da minha solução no desafio anterior , modificado da construção do Sp3000 .

A função

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

faz ciclos de tamanho ímpar de números não negativos

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

Para encontrar o tamanho correto do ciclo k, nreduza a entrada k=1,3,5,7,...até que o resultado esteja no intervalo [0,k). Cicle esse intervalo com a operação n->(n+1)%ke desfaça todas as subtrações feitas na entrada. Isso é implementado recursivamente por k+g(n-k,k+2).

Agora, precisamos do negativo para fazer os ciclos pares. Nota que, se modificar gpara começar k=2em g, teríamos ciclos mesmo tamanho

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

Estes biject para negativos via bit-complemento ~. Então, quando né negativo, simplesmente avaliamos g(n)como ~g(~n,2).

Python 3, 110 bytes

Eu ainda não descobri como conseguir um lambda lá

se n for um número de triângulo [1,3,6,10,15,21,28, etc ...], então f (n) é a ordem na lista multiplicada pela negativa. se o número for negativo, dê 1 + o próximo número menor do triângulo. caso contrário, incremente.

Exemplo: 5 não é um número triângulo, então adicione 1.

Na próxima iteração, temos 6. 6 é um número de triângulo e é o terceiro da lista; daí sai -3.

O programa fornece essas listas

comprimento 1: [0]

comprimento 2: [1, -1]

comprimento 3: [2,3, -2]

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

comprimento 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: Obrigado novamente a @TuukkaX por remover o excesso de caracteres.

Python 3, 146 bytes

Para cada número maior que 0, existem loops pares (len 2,4,6,8 ...) e menos de 0, loops ímpares (1,3,5,7). 0 mapeia para 0.

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

mapeia para

(-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 retirou 8 bytes da solução anterior. E outro 3.

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

• Não-concorrente porque quebra um bom recorde de liderança no último ranking, enquanto estou lutando para reduzi-lo o máximo possível.

• Alguns erros absurdos relativos à precisão no matlab que eu não conseguia encontrar outra saída a não ser tornar meu código sarcatisticamente grande, por outro lado, o mapeamento que escolhi foi em termos de principais fatores e logaritmo n-ário.

Execução

 f(2)

 1

 f(1)

 2

 f(-2)

 -4

 f(-4)

 -8

 f(-8)

 -1

 f(0)

 0



 ----------------------------

Explicação

• Sabendo, em primeiro lugar, que qualquer número pode ser escrito como produto de expoentes de números primos a N=e1^x1*e2^x2...partir dessa base, escolhi mapear imagens de ciclos Cextraídos do maior expoente do menor fator (não necessariamente o número primo) de que N é uma potência perfeita de .

• em palavras mais simples, N=P^xonde P é a menor raiz perfeita, xdenota precisamente dois termos essenciais para o ciclo:, x=Ʃ(r*P^i)um termo Pé a base do ciclo e também uma raiz perfeita para o número principal N e ké o grau do ciclo C=p^k, em que ivaria entre 1 e k, o coeficiente ré incrementado em 1 e delimitado por P-1 para qualquer pré-imagem a seguir, até que todos os coeficientes sejam configurados para r = 1, então passamos para o início desse ciclo.

• Para evitar colisões entre ciclos, a escolha da exponenciação dos números primos, em vez de seus produtos, é precisa, porque como um exemplo de dois ciclos de bases 3e 2um ponto de encontro entre eles, pode ser 3*2evitado, pois um ciclo é definido por seu grau mais do que o seu base e para o ponto de encontro há outro ciclo de base 6e grau 1.

• Os números negativos colocam uma exceção; por isso, reservei graus ímpares para números negativos e graus pares para o resto. Como assim ?

  para qualquer número N incorporado dentro de um ciclo P^k, é escrito como P^(a0*P^i0+a1*P^i1+...), a quantidade (a0*P^i0+a1*P^i1+...)é transaltada na base P-ária como a0,a1,...., para esclarecer esse ponto se (p = 2) a sequência deve estar na base binária. Como é sabido de forma inquestionável, sem definir a condição de graus positivos / negativos e a exceção (+/- 1), um número N está nas bordas de um ciclo de grau kse, e somente se, a seqüência Afor escrita como 1111..{k+1}..10ou 111..{k}..1para todas as bases, caso contrário nenhuma rotação é necessária, assim, atribuir uma condição negativa / positiva para os respectivos graus pares / ímpares k/k'para ambos cria uma sequência ímpar escrita no formulário 101..{k}..100, uma sequência par é escrita no formulário 101..{k'}..10para uma aresta inicial de um ciclo numérico respectivamente negativo / positivo .

  Exemplo:

  Tomando um número N=2^10, x=10=2^1+2^3a sequência A é escrita A=1010, esse tipo de sequência sintetiza uma aresta finita do ciclo numérico positivo, ou seja C=2^3, a próxima imagem é a aresta inicial A=011que é 8, Mas , ao padronizar esse resultado para (+ / -) 1 exceção é 2^10/2mapeada 8/2e a imagem anterior não deve ser girada.

  Tomando um número N=-3^9, x=9=3^2a sequência A é escrita A=100, esse tipo de sequência sintetiza uma aresta finita do ciclo numérico negativo, ou seja C=3^1, a próxima imagem é a aresta inicial A=01que é 3, mas, adaptando esse resultado a negativo / positivo a condição -3^9mapeia para -3.

• para o casal (-/+)1, pretendia intrometê-lo em um número de bases de ciclo 2, sob o pretexto de que uma sequência comum de grupos cíclicos {2,4}{8,16,32,64}..é composta de outra forma {1,2}{4,8,16,32}.., isso evita a perda de elementos anteriores, e a opação feita está apenas mudando com estalos um novo elemento no.

Resultados:

executando esta pequena planilha de códigos para verificar os primeiros intervalos razoáveis ​​de números cíclicos:

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

Isso leva a esses resultados

 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

O último é o erro de segmentação, mas se encaixa no intervalo de número inteiro assinado padrão [-127.127].

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

Funciona enumerando a sequência (0, -1, 1, -2, 2, -3, 3, ...) até encontrar n, contando os ciclos à medida que avança. icontém a entrada atual; jcontém o início do ciclo atual, ko índice dentro do ciclo, la duração do ciclo atual e ma próxima entrada na sequência. Assim que descobrimos n, tomamos jse estamos no final de um ciclo ou mse não.