Введение (может быть проигнорировано)

Поместить все натуральные числа в их регулярном порядке (1, 2, 3, ...) немного скучно, не правда ли? Итак, вот серия проблем, связанных с перестановками (перестановками) всех натуральных чисел. Это шестая задача в этой серии (ссылки на первую , вторую , третью , четвертую и пятую задачи).

Эта задача имеет мягкую пасхальную тему (потому что это Пасха). Я черпал свое вдохновение из этого высоко украшенного (и, по моему личному мнению, довольно некрасивого) гусиного яйца.

Это напомнило мне спираль Улама , где все натуральные числа помещены в спираль против часовой стрелки. Эта спираль имеет некоторые интересные особенности, связанные с простыми числами, но это не относится к этой задаче.

Мы переходим к перестановке в этом задании положительных целых чисел, если мы возьмем числа в спирали Улама и проследим все целые числа по спирали с поворотом по часовой стрелке , начиная с 1. Таким образом, мы получим

1, 6, 5, 4, 3, 2, 9, 8, 7, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 25, 24, 23, etc.

Если бы вы нарисовали обе спирали, вы бы получили какую-то бесконечную сетку из (яичной скорлупы) спиралей ( обратите внимание на ссылку « Новый порядок» ).

Эта последовательность присутствует в OEIS под номером A090861 . Так как это «чистая последовательность» вызов, задача состоит в том, чтобы выходной $a(n)$ для заданного$n$ качестве входных данных, где$a(n)$ равноA090861.

задача

Учитывая целочисленный ввод $n$ , вывод$a(n)$ в целочисленном формате, где$a(n)$ равноA090861.

Примечание: здесь предполагается индексирование на основе 1; Вы можете использовать индексирование на основе 0, поэтому $a(0) = 1; a(1) = 6$ и т. д. Пожалуйста, укажите это в своем ответе, если вы решите использовать это.

Контрольные примеры

Input | Output
---------------
1     |  1
5     |  3
20    |  10
50    |  72
78    |  76
123   |  155
1234  |  1324
3000  |  2996
9999  |  9903
29890 |  29796

правила

• Вход и выход являются целыми числами.
• Ваша программа должна как минимум поддерживать ввод в диапазоне от 1 до 32767).
• Неверный ввод (0, значения с плавающей запятой, строки, отрицательные значения и т. Д.) Может привести к непредсказуемому выводу, ошибкам или (не) определенному поведению.
• Применяются правила ввода / вывода по умолчанию .
• Лазейки по умолчанию запрещены.
• Это код-гольф , поэтому самые короткие ответы в байтах выигрывают

Желе ,  16 14 11 10 9  8 байт

-1 благодаря Линн (мод-2; логическое НЕ; добавить к себе: Ḃ¬+ -> побитовое ИЛИ с 1: |1)

|1×r)ẎQi

Монадическая ссылка, принимающая целое число, n , которое дает целое число a(n).

Попробуйте онлайн! (очень неэффективно, так как выходит на слой$\lceil\frac n2\rceil$

½‘|1×rƲ€ẎQi$\lceil\frac{\lfloor\sqrt n\rfloor+1}2\rceil$

Как?

Перестановка состоит в том, чтобы взять натуральные числа в перевернутых кусках длины [1,5,3,11,5,17,7,23,9,29,11,35,13,...] - нечетные натуральных числа вперемешку с конгруэнтным натуральными числами до пяти по модулю шесть, то есть [1, 2*3-1, 3, 4*3-1, 5, 6*3-1, 7, 8*3-1, 9, ...].

Это то же самое, что конкатенация, а затем дедупликация обратных диапазонов, [1..x]гдеx это совокупные суммы этих длин срезов (т.е. максимума каждого среза) - [1,6,9,20,25,42,49,72,81,110,121,156,169,...], что нечетные целые числа в квадрате перемежаются с четными номерами , умноженных на самом увеличиваются, то есть [1*1, 2*3, 3*3, 4*5, 5*5, 6*7, 7*7,...].

Поскольку все различия больше 1, мы можем сохранить байт (обращение) путем [x..k]непосредственного построения диапазонов , где kесть индекс с индексом 1 среза.

$P(n) = v \iff P(v) = n$n|1×r)ẎQị@n|1×r)ẎQi

|1×r)ẎQi - Link: integer, n       e.g. 10
    )    - for each k in [1..n]:  vs = [ 1, 2, 3, 4, 5, 6, 7, 8, 9,10]
|1       -   bitwise-OR (k) with 1     [ 1, 3, 3, 5, 5, 7, 7, 9, 9,11]
  ×      -   multiply (by k)           [ 1, 6, 9,20,25,42,49,72,81,110]
   r     -   inclusive range (to k)    [[1],[6..2],[9..3],[20..4],...,[110..10]]
     Ẏ   - tighten                     [1,6,5,4,3,2,9,8,7,6,5,4,3,20,...,4,......,110,...,10]
      Q  - de-duplicate                [1,6,5,4,3,2,9,8,7,20,...,10,......,110,...82]
       i - first index with value (n)  20

JavaScript (ES7),  46 45  41 байт

0 индексированные.

n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

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

Как?

Это основано на формуле с 1 индексом, используемой в примерах программ A090861 .

$x_n$$0$

$$x_n=\left\lfloor\frac{\sqrt{n-1}+1}{2}\right\rfloor$$

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

$k_n$$6$$-2$

$$k_n=\begin{cases} -2&\text{if }n\le 4{x_n}^2+2x_n\\ 6&\text{otherwise} \end{cases}$$

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

$a_n$

$$a_n=8{x_n}^2+k_nx_n+2-n$$

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

Который может быть переведен на:

n=>8*(x=(n-1)**.5+1>>1)*x+(n<=4*x*x+2*x?-2:6)*x+2-n

Делая это с 0 индексами экономит 5 байтов сразу:

n=>8*(x=n**.5+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n

Формула может быть дополнительно упрощена с помощью:

$${x'}_n=2\times\left\lfloor\frac{\sqrt{n}+1}{2}\right\rfloor$$

который может быть выражен как:

x=n**.5+1&~1

ведущий к:

n=>2*(x=n**.5+1&~1)*x+(n<x*x+x?-1:3)*x+1-n

и наконец:

n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

Wolfram Language (Mathematica) , 60 байт

8(s=⌊(⌊Sqrt[#-1]⌋+1)/2⌋)^2-#+2+If[#<=4s^2+2s,-2,6]s&

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

MATL , 12 11 байт

Eq1YL!tPG=)

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

Очень мало памяти. Предоплата X^kделает его более эффективным .

C # (интерактивный компилятор Visual C #) , 67 байт

n=>8*(x=(int)Math.Sqrt(--n)+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n;int x;

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

Python 3.8, 104 74 65 60 57 байт

lambda n:(-2,6)[n>4*(x:=(n**.5+1)//2)*x+2*x]*x+2+~n+8*x*x

Редактировать: Спасибо Джонатану Аллану за получение от 74 до 57 байтов!

В этом решении используется индексация на основе 0.

Python 3.8 (предварительная версия) , 53 байта

Прямой порт ответа JavaScript Арнаулда, upvote, и / или ответ Mathematica J42161217 , и / или ответ Python Капоши :)

lambda n:((x:=int(n**.5+1)&-2)*2-(n<x*x+x)*4+3)*x+1-n

0 индексированные.

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

Befunge, 67 57 байт

Это решение предполагает индексирование на основе 0 для входных значений.

p&v-*8p00:+1g00:<
0:<@.-\+1*g00+*<|`
0g6*\`!8*2+00g4^>$:0

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

объяснение

Начнем с вычисления "радиуса", при котором вход n найден с помощью цикла:

radius = 0
while n > 0
  radius += 1
  n -= radius*8

В конце цикла предыдущее значение n - это смещение по спирали на этом радиусе:

offset = n + radius*8

Затем мы можем определить, находимся ли мы в верхней или нижней части спирали, следующим образом:

bottom = offset >= radius*6

И как только мы получим все эти детали, спиральное значение рассчитывается по формуле:

value = ((bottom?10:2) + 4*radius)*radius + 1 - offset

Радиус - это единственное значение, которое нам нужно сохранить как «переменную», ограничивая его максимальным значением 127 в Befunge-93, поэтому этот алгоритм может обрабатывать входы до 65024.

Japt , 15 байт

Порт Джонатана в желе раствор. 1-индексироваться.

gUòȲ+X*v)õÃcÔâ

Попытайся

gUòȲ+X*v)õÃcÔâ     :Implicit input of integer U
g                   :Index into
 Uò                 :  Range [0,U]
   È                :  Map each X
    ²               :    Square X
     +X*            :    Add X multiplied by
        v           :    1 if X is divisible by 2, 0 otherwise
         )          :    Group result
          õ         :    Range [1,result]
           Ã        :  End map
            c       :  Flatten
             Ô      :    After reversing each
              â     :  Deduplicate

C ++ (gcc) , 88 байт

#import<cmath>
int a(int n){int x=(sqrt(n-1)+1)/2;return x*(8*(x+(n>4*x*x+2*x))-2)+2-n;}

1-индексированных; использует формулу на странице OEIS, но манипулирует, чтобы сохранить несколько байтов.

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