Une fonction est dite avoir un cycle de longueur n s'il existe un x dans son domaine tel que f ⁿ (x) = x et f ^m (x) ≠ x pour 0 <m <n , où l'exposant n désigne n - plier l'application de f . Notez qu'un cycle de longueur 1 est un point fixe f (x) = x .

Votre tâche consiste à implémenter une fonction bijective des entiers à eux-mêmes, qui a exactement un cycle de chaque longueur positive n . Une fonction bijective est une correspondance biunivoque, c'est-à-dire que chaque entier est mappé exactement une fois. Avoir exactement un cycle de longueur n signifie qu'il existe exactement n nombres distincts x pour lesquels f ⁿ (x) = x et f ^m (x) ≠ x pour 0 <m <n .

Voici un exemple de ce à quoi pourrait ressembler une telle fonction autour 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 ...

Cet extrait contient des cycles de longueur 1 à 5 :

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

Notez que ci-dessus, j'utilise "fonction" uniquement dans le sens mathématique. Vous pouvez écrire une fonction ou un programme complet dans la langue de votre choix, tant qu'il prend un seul entier (signé) en entrée et renvoie un seul entier (signé). Comme d'habitude, vous pouvez prendre une entrée via STDIN, un argument de ligne de commande, un argument de fonction, etc. et une sortie via STDOUT, une valeur de retour de fonction ou un argument de fonction (out), etc.

Bien sûr, de nombreux langages ne prennent pas (facilement) en charge les entiers de précision arbitraire. C'est bien si votre implémentation ne fonctionne que sur la plage du type d'entier natif de votre langue, tant que cela couvre au moins la plage [-127, 127] et qu'elle fonctionnerait pour des entiers arbitraires si le type d'entier du langage était remplacé par arbitraire- entiers de précision.

Les règles de code-golf standard s'appliquent.

Pyth, 27 18 octets

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

Explication (Pyth initialise Qà l'entier d'entrée):

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

Cela a des 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, 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)
⋮

Le cycle de longueur n est donné par

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

Chaque entier k ≥ -1 apparaît comme le premier élément du cycle ( k + 2). Pour chaque entier k <−1, nous pouvons écrire de façon unique 1 - k = 2 ^ i ⋅ (2⋅ j + 1) pour certains i , j ≥ 0; alors k apparaît comme le ( j + 2) ème élément du cycle ( i + j + 2).

MATL , 47 octets

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

Essayez-le en ligne!

Explication générale

La fonction 2 ci-dessous est la même que celle utilisée dans la réponse de @ Sp3000 au défi associé. Merci à @ Agawa001 de l'avoir remarqué.

La fonction est la composition de trois:

1. Bijection de Z (les entiers) à N (les naturels).
2. Bijection de N à N avec la caractéristique souhaitée (un cycle de chaque longueur).
3. Inverse de la fonction 1.

Fonctions 1 et 3 sont utilisés car il est plus facile (je crois) pour obtenir le comportement souhaité en N qu'en Z .

La fonction 2 est la suivante: la ligne supérieure est le domaine, la ligne inférieure est le domaine codé. Les virgules sont utilisées pour plus de clarté:

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

Le premier bloc (de haut 1en bas 1) est un cycle de longueur 1. Le second (de 2 3à 3 2) est un cycle de longueur 2, etc. Dans chaque bloc, la partie inférieure (image de la fonction) est la partie supérieure décalée circulairement un pas à droite.

La fonction 1 est la suivante:

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

La fonction 3 est la même que 1 avec les deux lignes inversées.

Exemples

L'image de l' 3est -5. Le premier 3est mappé 7par la fonction 1; 7est ensuite mappé 10par la fonction 2; 10est ensuite mappé à -5` par la fonction 3.

Le cycle de longueur 1 est 0. Le cycle de longueur 2 est -1 1. Le cycle de longueur 3 est -3 2 -2, etc.

Explication du code

Les fonctions 1 et 3 sont simples.

La fonction 2 fonctionne en trouvant le point final inférieur du bloc d'entrée correspondant. Par exemple, si l'entrée de cette fonction est 9trouvée 7(voir les blocs ci-dessus). Il sélectionne ensuite le point de terminaison supérieur, qui est 10dans l'exemple. Le déplacement circulaire du bloc est obtenu grâce à l'indexation modulaire basée sur 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 octets

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

59 octets:

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

Crée les cycles

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

Modifié à partir de ma solution sur le défi précédent , qui est modifié à partir de la construction du Sp3000 .

La fonction

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

crée des cycles de taille impaire de nombres non négatifs

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

Pour trouver la taille de cycle correcte k, décaler l'entrée vers le nbas k=1,3,5,7,...jusqu'à ce que le résultat soit dans l'intervalle [0,k). Faites défiler cet intervalle avec l'opération n->(n+1)%k, puis annulez toutes les soustractions effectuées sur l'entrée. Ceci est implémenté récursivement par k+g(n-k,k+2).

Maintenant, nous avons besoin du négatif pour faire les cycles pairs. Notez que si nous modifions gpour commencer k=2dans g, nous aurions des cycles de taille égale

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

Ces bijects aux négatifs via bit-complément ~. Donc, quand nest négatif, nous évaluons simplementg(n) comme ~g(~n,2).

Python 3, 110 octets

Je n'ai toujours pas compris comment obtenir un lambda

si n est un nombre triangulaire [1,3,6,10,15,21,28, etc ...] alors f (n) est l'ordre dans la liste multiplié par un négatif. si le nombre est négatif, donnez-lui 1 + le plus petit nombre de triangle suivant. sinon, incrémenter.

Exemple: 5 n'est pas un nombre triangulaire, alors ajoutez 1.

La prochaine itération, nous avons 6. 6 est un nombre triangulaire, et c'est le 3ème de la liste, donc vient -3.

Le programme donne ces listes

longueur 1: [0]

longueur 2: [1, -1]

longueur 3: [2,3, -2]

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

longueur 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: Merci encore à @TuukkaX pour avoir supprimé les caractères en excès.

Python 3, 146 octets

Pour chaque nombre supérieur à 0, il existe des boucles paires (len 2,4,6,8 ...), et inférieures à 0, des boucles impaires (1,3,5,7). 0 correspond à 0.

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

correspond à

(-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 a enlevé 8 octets de la solution précédente. Et encore 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

• Non compétitif car il bat un bon record de condidate pour le dernier classement, alors que j'ai du mal à le raccourcir le plus possible.

• Quelques bugs non sensés concernant la précision dans matlab que je ne pouvais pas trouver d'autre que de rendre mon code sarcastique, en revanche le mappage que j'opte était en termes de facteurs principaux et de logarithme n-aire.

Exécution

 f(2)

 1

 f(1)

 2

 f(-2)

 -4

 f(-4)

 -8

 f(-8)

 -1

 f(0)

 0



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

Explication

• Sachant, tout d'abord, qu'un nombre quelconque peut être écrit comme le produit d'exposants de nombres premiers N=e1^x1*e2^x2...de cette base, j'ai choisi de cartographier des images de cycles Cqui sont extraites du plus grand exposant du plus petit facteur (pas nécessairement premier) que N est une puissance parfaite de .

• en termes plus simples, soit N=P^xoù P est la plus petite racine parfaite, xdésigne précisément deux termes essentiels pour le cycle:, x=Ʃ(r*P^i)un terme Pest la base du cycle ainsi qu'une racine parfaite pour le nombre principal N, et kest le degré du cycle C=p^k, où ivarie entre 1 et k, le coefficient rest incrémenté de 1 et limité par P-1 pour toute pré-image suivante jusqu'à ce que tous les coefficients soient définis sur r = 1, nous passons donc au début de ce cycle.

• Pour éviter les collisions entre les cycles, le choix de l'exponentiation des nombres premiers plutôt que de leurs produits est précis, car comme un exemple de deux cycles de bases 3et d' 2un point de rencontre entre eux, cela peut être 3*2évité car un cycle est défini par son degré plus que son base, et pour le point de rencontre, il y a un autre cycle de base 6et de degré 1.

• Les nombres négatifs placent une exception, quant à lui, j'ai réservé des degrés impairs pour les nombres négatifs, et même des degrés pour le reste. Comment ?

  pour tout nombre N intégré dans un cycle P^k, est écrit comme P^(a0*P^i0+a1*P^i1+...), la quantité (a0*P^i0+a1*P^i1+...)est transaltée en base P-aire comme a0,a1,...., pour clarifier ce point si (p = 2) la séquence doit être en base binaire. Comme on le sait de façon réaliste sans définir la condition des degrés positifs / négatifs et l'exception (+/- 1), un nombre N est sur les bords d'un cycle de degré ksi et seulement si la séquence Aest écrite comme 1111..{k+1}..10ou 111..{k}..1pour toutes les bases, sinon aucune rotation n'est nécessaire, affectant ainsi une condition négative / positive pour un degré impair / pair respectif k/k'pour les deux crée une séquence impaire écrite sous la forme 101..{k}..100, une séquence paire est écrite sous la forme 101..{k'}..10pour un bord de début d'un cycle numérique négatif / positif respectivement .

  Exemple:

  En prenant un nombre N=2^10, x=10=2^1+2^3la séquence A est écrite A=1010, ce type de séquence symptomatique d'un bord fini de cycle numérique positif, qui est C=2^3, donc l'image suivante est celle du bord de départ A=011qui est 8, mais , en standardisant ce résultat à (+ / -) 1 exception 2^10/2mappe 8/2et l'image précédente ne doit pas être tournée.

  En prenant un nombre N=-3^9, x=9=3^2la séquence A est écrite A=100, ce type de séquence symptomatique d'un bord fini de cycle numérique négatif, qui est C=3^1, donc l'image suivante est celle du bord de départ A=01qui est 3, Mais, en adaptant ce résultat à négatif / positif condition -3^9correspond à -3.

• pour le couple (-/+)1, j'ai envisagé de l' introduire dans un certain nombre de bases cycliques 2, sous prétexte qu'une séquence ordinaire de groupes cycliques {2,4}{8,16,32,64}..est constituée sous une autre forme {1,2}{4,8,16,32}.., cela évite toute perte d'éléments précédents, et l'opération effectuée ne fait que changer avec l'éclatement un nouvel élément.

Résultats:

exécuter cette petite feuille de code pour vérifier les premières plages raisonnables de nombres cycliques:

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

Cela conduit à ces résultats

 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

Le dernier est une erreur de segmentation mais il correspond à la plage d'entiers signés standard [-127,127].

JavaScript (ES6), 73 octets

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

Fonctionne en énumérant la séquence (0, -1, 1, -2, 2, -3, 3, ...) jusqu'à ce qu'elle trouve n, en comptant les cycles au fur et à mesure. icontient l'entrée actuelle; jcontient le début du cycle en cours, kl'index dans le cycle, lla durée du cycle en cours et ml'entrée suivante dans la séquence. Une fois que nous trouvons, nnous prenons alors jsi nous sommes à la fin d'un cycle ou mnon.