Говорят, что функция имеет цикл длины n, если в ее области существует x, такой что f ⁿ (x) = x и f ^m (x) ≠ x при 0 <m <n , где верхний индекс n обозначает n - сложите приложение f . Обратите внимание, что цикл длины 1 является фиксированной точкой f (x) = x .

Ваша задача - реализовать биективную функцию от целых чисел до самих себя, которая имеет ровно один цикл каждой положительной длины n . Биективная функция - это взаимно-однозначное соответствие, т. Е. Каждое целое число сопоставляется ровно один раз. Наличие ровно одного цикла длины n означает, что существует ровно n различных чисел x, для которых f ⁿ (x) = x и f ^m (x) ≠ x при 0 <m <n .

Вот пример того, как такая функция может выглядеть вокруг 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 ...

Этот отрывок содержит циклы длиной от 1 до 5 :

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

Обратите внимание, что выше я использую «функцию» только в математическом смысле. Вы можете написать либо функцию, либо полную программу на выбранном вами языке, если она принимает одно (подписанное) целое число в качестве входных данных и возвращает одно (подписанное) целое число. Как обычно, вы можете принимать ввод через STDIN, аргумент командной строки, аргумент функции и т. Д. И выводить через STDOUT, возвращаемое значение функции или аргумент функции (out) и т. Д.

Конечно, многие языки (легко) не поддерживают целые числа произвольной точности. Хорошо, если ваша реализация работает только с диапазоном целочисленного типа вашего языка, если он охватывает хотя бы диапазон [-127, 127], и что она будет работать для произвольных целых чисел, если целочисленный тип языка был заменен на произвольный точные целые числа.

Применяются стандартные правила игры в гольф .

Pyth, 27 18 байт

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

Пояснение (Pyth инициализируется Qво входное целое число):

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

Это имеет циклы

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

Цикл длины n определяется как

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

Каждое целое число k ≥ −1 появляется как первый элемент цикла ( k + 2). Для каждого целого числа k <−1 мы можем однозначно записать 1 - k = 2 ^ i ⋅ (2⋅ j + 1) для некоторого i , j ≥ 0; тогда k появляется как ( j + 2) -й элемент цикла ( i + j + 2).

MATL , 47 байт

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

Попробуйте онлайн!

Общее объяснение

Функция 2 ниже такая же, как и в ответе @ Sp3000 на соответствующий вызов. Спасибо @ Agawa001 за то, что заметили.

Функция состоит из трех:

1. Биекция от Z (целые числа) до N ( натуральные числа ).
2. Биекция от N до N с желаемой характеристикой (один цикл каждой длины).
3. Обратная функция 1.

Функции 1 и 3 используются , потому что это проще (я думаю) , чтобы достичь желаемого поведения в N , чем в Z .

Функция 2 выглядит следующим образом: верхняя строка - домен, нижняя строка - кодомен. Запятые используются для ясности:

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

Первый блок (от верхнего 1к нижнему 1) представляет собой цикл длины 1. Второй (от 2 3до 3 2) - цикл длины 2 и т. Д. В каждом блоке нижняя часть (изображение функции) - это верхняя часть, смещенная по кругу. один шаг вправо.

Функция 1 выглядит следующим образом:

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

Функция 3 такая же, как 1 с двумя линиями поменялись местами.

Примеры

Образ 3есть -5. Первый 3сопоставлен 7с функцией 1; затем 7сопоставляется 10функцией 2; затем 10отображается на -5` функцией 3.

Длина цикла равна 1 0. Длина цикла - 2 -1 1. Длина цикла 3 -3 2 -2и т. Д.

Код объяснил

Функции 1 и 3 просты.

Функция 2 работает путем нахождения нижней конечной точки соответствующего входного блока. Например, если вход для этой функции - 9это находка 7(см. Блоки выше). Затем он выбирает верхнюю конечную точку, которая есть 10в примере. Круговое смещение блока достигается благодаря модульной индексации MATL на основе 1.

         % 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 байт

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

59 байтов:

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

Создает циклы

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

Модифицировано из моего решения на более ранней проблеме , которая модифицирована от конструкции Sp3000 .

Функция

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

делает нечетные циклы неотрицательных чисел

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

Чтобы найти правильный размер цикла k, сдвигайте вход nвниз, k=1,3,5,7,...пока результат не окажется в интервале [0,k). Цикл этого интервала с операцией n->(n+1)%k, а затем отменить все вычитания, сделанные на входе. Это реализовано рекурсивно k+g(n-k,k+2).

Теперь нам нужен негатив, чтобы сделать четные циклы. Обратите внимание, что если мы изменим, gчтобы начать с k=2in g, мы получим циклы четного размера

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

Они связывают с негативами через битовое дополнение ~. Итак, когда nотрицательно, мы просто оцениваем g(n)как ~g(~n,2).

Python 3, 110 байт

Я до сих пор не понял, как получить там лямбду

если n - это номер треугольника [1,3,6,10,15,21,28 и т. д.], то f (n) - это порядок в списке, умноженный на отрицательный. если число отрицательное, присвойте ему 1 + следующий наименьший номер треугольника. иначе, приращение.

Пример: 5 не является числом треугольника, поэтому добавьте 1.

Следующая итерация, у нас есть 6. 6 - это номер треугольника, и это третье место в списке, так что получается -3.

Программа выдает эти списки

длина 1: [0]

длина 2: [1, -1]

длина 3: [2,3, -2]

длина 4: [4,5,6, -3]

длина 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)

Изменить: Еще раз спасибо @TuukkaX за удаление лишних символов.

Python 3, 146 байт

Для каждого числа больше 0 существуют четные петли (len 2,4,6,8 ...), и меньше 0 - нечетные петли (1,3,5,7). 0 сопоставляется с 0.

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

карты для

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

Изменить: @TuukkaX удалил 8 байтов из предыдущего решения. И еще 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

• Неконкурентоспособен, потому что он побивает хороший рекорд того, чтобы быть близким к последнему рейтингу, в то время как я изо всех сил стараюсь сократить его, насколько это возможно.

• Некоторые бессмысленные ошибки, касающиеся точности в matlab, которые я не смог найти, кроме как сделать мой код саркастически большим, с другой стороны, я выбрал отображение с точки зрения простых множителей и n-арного логарифма.

выполнение

 f(2)

 1

 f(1)

 2

 f(-2)

 -4

 f(-4)

 -8

 f(-8)

 -1

 f(0)

 0



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

объяснение

• Прежде всего, зная, что любое число может быть записано как произведение показателей простых чисел N=e1^x1*e2^x2...из этой базы, я выбрал для отображения изображений циклов, Cкоторые извлекаются из наибольшего показателя наименьшего фактора (не обязательно простого), что N является совершенной степенью ,

• Проще говоря, пусть, N=P^xгде P - наименьший совершенный корень, xобозначает ровно два существенных члена цикла: x=Ʃ(r*P^i)термин P- это основание цикла, а также совершенный корень для основного числа N и kстепень цикла C=p^k, где iизменяется между 1 и k, коэффициент rувеличивается на 1 и ограничивается P-1 для любого последующего предварительного изображения, пока все коэффициенты не будут установлены в r = 1, поэтому мы переходим к началу этого цикла.

• Чтобы избежать столкновений между циклами, выбор степени возведения в степень простых чисел, а не их произведений, является точным, поскольку в качестве примера можно привести два цикла оснований 3и 2точку встречи между ними 3*2, поэтому этого избегают, поскольку цикл определяется его степенью больше, чем его база, а для точки встречи есть еще один цикл базы 6и степени 1.

• Отрицательные числа ставят исключение, поскольку для него я зарезервировал нечетные градусы для отрицательных чисел и четные градусы для остальных. Как же так ?

  для любого числа N, встроенного в цикл P^k, записывается как P^(a0*P^i0+a1*P^i1+...), сумма (a0*P^i0+a1*P^i1+...)переводится в P-арную базу как a0,a1,...., чтобы прояснить этот момент, если (p = 2) последовательность должна быть в двоичной базе. Как известно предварительно без установки условия положительных / отрицательных степеней и исключения (+/- 1), число N находится на краях цикла степени kтогда и только тогда, когда последовательность Aзаписана как 1111..{k+1}..10или 111..{k}..1для всех оснований, в противном случае вращение не требуется, таким образом, при назначении отрицательного / положительного условия для соответствующих нечетных / четных степеней k/k'для обоих получается нечетная последовательность, записанная в форме 101..{k}..100, четная последовательность записывается в форме 101..{k'}..10для начального края соответственно отрицательного / положительного числового цикла ,

  Пример:

  Взяв число N=2^10, x=10=2^1+2^3записывается последовательность A A=1010, этот тип последовательности символизирует конечное ребро положительного числового цикла, то есть C=2^3следующее изображение - это изображение начального ребра, A=011которое 8, но , стандартизируя этот результат с (+ / -) 1 исключение 2^10/2сопоставляется 8/2и предыдущее изображение не должно вращаться.

  Взяв число N=-3^9, x=9=3^2записывается последовательность A A=100, этот тип последовательности символизирует конечное ребро отрицательного числового цикла, то есть C=3^1следующее изображение - это изображение начального ребра, A=01которое 3, но, адаптируя этот результат к отрицательному / положительному -3^9карты условий для -3.

• для пары (-/+)1я планировал внедрить его в число оснований цикла 2, при условии, что обычная последовательность циклических групп {2,4}{8,16,32,64}..составлена ​​в другой форме {1,2}{4,8,16,32}.., это предотвращает любую потерю предыдущих элементов, а выполненная операция просто перемещается с появлением новый элемент в.

Полученные результаты:

запустим этот маленький кодовый лист для проверки первых разумных диапазонов циклических чисел:

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

Это приводит к этим результатам

 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

Последний - ошибка сегментации, но он соответствует стандартному целочисленному диапазону со знаком [-127,127].

JavaScript (ES6), 73 байта

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

Работает, перечисляя последовательность (0, -1, 1, -2, 2, -3, 3, ...) до тех пор, пока она не найдет n, считая циклы по ходу. iсодержит текущую запись; jсодержит начало текущего цикла, kиндекс в цикле, lдлину текущего цикла и mследующую запись в последовательности. Как только мы находим, nмы берем, jесли мы находимся в конце цикла или mнет.