Номера ружья

45

Эти номера Ружья представляют собой последовательность с довольно простым определением , но некоторые интересными структурами. Начните с натуральных чисел:

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

Теперь возьмите все числа с индексами, кратными 2 , сгруппируйте их в пары и поменяйте местами числа в каждой паре:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
   ^     ^     ^     ^      ^       ^       ^  
    <--->       <--->        <----->         <----
1, 4, 3, 2, 5, 8, 7, 6, 9, 12, 11, 10, 13, 16, ...

Теперь сделайте то же самое с индексами, кратными 3 :

1, 4, 3, 2, 5, 8, 7, 6, 9, 12, 11, 10, 13, 16, ...
      ^        ^        ^           ^          
       <------>          <--------->           
1, 4, 8, 2, 5, 3, 7, 6, 10, 12, 11, 9, 13, 16, ...

А потом для 4 , 5 , 6 и так далее:

1, 4, 8, 2, 5, 3, 7, 6, 10, 12, 11, 9, 13, 16, ...
1, 4, 8, 6, 5, 3, 7, 2, 10, 12, 11, 14, 13, 16, ...
1, 4, 8, 6, 12, 3, 7, 2, 10, 5, 11, 14, 13, 16, ...
1, 4, 8, 6, 12, 14, 7, 2, 10, 5, 11, 3, 13, 16, ...
...

После k таких шагов первые k + 1 числа будут зафиксированы. Таким образом, мы можем определить бесконечную последовательность чисел дробовика как предел, позволяющий k перейти в бесконечность. Первые 66 номеров:

1, 4, 8, 6, 12, 14, 16, 9, 18, 20, 24, 26, 28, 22, 39, 15, 36, 35, 40, 38, 57, 34, 48, 49, 51, 44,
46, 33, 60, 77, 64, 32, 75, 56, 81, 68, 76, 58, 100, 55, 84, 111, 88, 62, 125, 70, 96, 91, 98, 95,
134, 72, 108, 82, 141, 80, 140, 92, 120, 156, 124, 94, 121, 52, 152, 145, ...

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

Соревнование

По заданному целому числу n > 0найти nномер дробовика. Вы можете написать программу или функцию, получая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и возвращать вывод или выводить его в STDOUT (или ближайшую альтернативу).

Это код гольф, поэтому выигрывает самое короткое представление (в байтах).

Leaderboards

Это дает больше ответов, чем я думал, а также несколько человек соревнуются на одном языке. Итак, вот фрагмент стека для генерации как регулярной таблицы лидеров, так и обзора победителей по языкам.

Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:

# Language Name, N bytes

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

# Ruby, <s>104</s> <s>101</s> 96 bytes

Мартин Эндер
источник
1
Этот забавный факт сумасшедший, этот алгоритм тасует все простые числа до конца? Или есть другие натуральные числа, которые также не будут встречаться?
Девон Парсонс
1
@DevonParsons Да, это перемешивает все простые числа "до конца". Но я думаю, что пропали и другие цифры. Похоже 10, 21, 25и 30не появляются либо, например.
Мартин Эндер
3
Это звучит как вопрос проекта Эйлера. Я не думаю, что это ... но, возможно, так и должно быть.
Кори Огберн
9
В общем, на kй-й итерации, kй-й элемент в массиве перемещается в т- 2kю позицию и больше не будет касаться до 2kитераций, когда он будет транспонирован в т- 4kю позицию до бесконечности. Простое число не транспонируется до тех пор, пока не наступит его очередь, так что все простые числа перемещаются вперед. Но мы можем легко составить список невинных жертв, просто распечатав первый элемент для транспонирования на итерации 2 и каждой нечетной итерации. Список идет: 2, 3, 5, 7, 10, 11, 13, 21, 17, 19, 30, 23, 27, 25, 29, 31, 45, 42, 37, 54, 41, 43, 65, ...
Теофиль
3
@ Шерлок9 Готово! В случае одобрения это будет https://oeis.org/A266679 . С Новым Годом!
Теофил

Ответы:

5

Пиф, 19 22

u-G*H^_!%GH/GHrhQ2Q

Довольно наивная реализация ответа @ PeterTaylor's golfscript .

Попробуйте онлайн здесь

При этом используются те же приемы для преобразования цикла while в сгиб, что и в другой программе Pyth, представленной ниже.


u+G**H!%GHty%/GH2rhQ2Q

Наивная копия алгоритма @ Sp3000, переведенная на Pyth.

Вы можете попробовать это онлайн здесь

Использует уменьшение (имя Python для свертывания) для эмуляции цикла while. Он перечисляет, над range(input, 2)чем работает Pyth range(2, input)[::-1]. Другой Pyth связанных гольф предполагают использование notвместо <2и используя y«ы режим удвоения значения числовых аргументов скрыты.

оборота FryAmTheEggman
источник
21

> <>, 52 45 байт

Страница Esolangs для> <>

i:&&:&1-?vn;
2*1-*+20.>:&:&%1(&:&*{:}&:1-&,2%

Благодаря нескольким модулям и необходимым умножениям происходит много копирования и перемещения элементов. Логика точно такая же, как и у моего решения на Python .

Принимает ввод через кодовую точку из STDIN, например "!" = 33 -> 75.

Sp3000
источник
10
И вы получили награду за самый неудобный формат ввода: P
Caridorc
+1 в любом случае, не волнуйтесь :)
Caridorc
@ Sp3000 IMO должно считаться только одним
SuperJedi224
@ SuperJedi224 На самом деле, согласно этому мета посту, по- видимому, -vсчитается три: /
Sp3000
17

Python 2, 58 байт

i=n=input()
while~-i:n+=(n%i<1)*i*(n/i%2*2-1);i-=1
print n

Как и большинство других ответов, идея состоит в том, чтобы работать задом наперед.


Давайте назовем шаг k+1step i, так что на шаге iвсе кратные iпоменялись местами. Нам нужно два простых наблюдения:

  • Позиция nв массиве местами только на этапе , iесли nделится на i,
  • Чтобы узнать, меньше ли у вас число или больше в свопе, посмотрите n/i mod 2. Если это 1, то у вас меньшее число (и оно будет меняться), в противном случае вы будете иметь более высокое число (и оно будет меняться).

Это дает нам алгоритм для работы в обратном направлении. Давайте попробуем это с 6, начиная с последнего шага (шага i = 6):

Step 6: Position 6 swaps with position 12 (6 is divisible by 6, 6/6 = 1 == 1 mod 2)

Итак, теперь мы знаем, что число пришло с позиции 12. Тогда:

Step 5: No swap (12 not divisible by 5)
Step 4: Position 12 swaps with position 16 (12 is divisible by 4, 12/4 = 3 == 1 mod 2)

Итак, теперь мы знаем, что это произошло с 16 до этого. В заключение:

Step 3: No swap (16 not divisible by 3)
Step 2: Position 16 swaps with position 14 (16 divisible by 2, 16/2 = 8 == 0 mod 2)

Так как это первый шаг (помните k+1), мы закончили, и число, которое заканчивается в позиции 6, первоначально пришло из позиции 14, то есть номер 6-го ружья равен 14.

Итак, теперь для объяснения Python:

i=n=input()             Read input, and store into i (step) and n (position)
while~-i:               while i-1 != 0:, or since we're descending with i this is just while i>1:
  n+=                   Add to the current position...
    (n%i<1)*            1* whatever's next if n is divisible by i, otherwise 0* (i.e. nothing)
    i*                  How many positions n might go up/down
    (n/i%2*2-1)         n/i%2 tell us higher/lower, *2-1 maps 0 or 1 to -1 (down) or +1 (up)
  i-=1                  Decrement the step number
print n                 Output
Sp3000
источник
Интересный способ написать i-1как~-i
mbomb007
6
@ mbomb007: Согласен. Умный, хотя, поскольку он имеет то же значение, но устраняет необходимость в пробеле после while. Хорошая работа, Sp3000.
Алекс А.
Самое короткое, что я мог получить в pyth, это использовать u+G**H!%GHty%/GH2rhQ2Q
Reduce
1
@FryAmTheEggman, Sp3000, никто из вас не собирается это публиковать?
Мартин Эндер
@ MartinBüttner Первоначально я не публиковал его, так как чувствовал, что это слишком большая копия. Я отправлю это как ответ CW пока.
FryAmTheEggman
6

Haskell, 68 байт

n#k|mod k(2*n)<1=k-n|mod k n<1=k+n|k>0=k
s n=foldr((.).(#))id[2..n]n

Вероятно, дальше гольф, особенно в первом ряду. Это определяет функцию, sкоторая принимает nи возвращает nномер дробовика.

map s [1..66]
[1,4,8,6,12,14,16,9,18,20,24,26,28,22,39,15,36,35,40,38,57,34,48,49,51,44,46,33,60,77,64,32,75,56,81,68,76,58,100,55,84,111,88,62,125,70,96,91,98,95,134,72,108,82,141,80,140,92,120,156,124,94,121,52,152,145]

объяснение

Вспомогательная функция #принимает два числа nи kи возвращает kth-е число в списке, определенном путем применения операции парного обмена к каждому nth-му числу. Например, применяя его к первым 20 числам, n = 4получим следующее:

map (4#) [1..20]
[1,2,3,8,5,6,7,4,9,10,11,16,13,14,15,12,17,18,19,24]

Результат s nполучается путем сокращения («сворачивания») списка с [2..n]помощью функции второго порядка (.).(#), которая принимает число mи функцию f(первоначально тождественную функцию id) и возвращает функцию, которая принимает kи возвращает f (m # k). Например, в случае, n = 4если список [2,3,4]сводится к функции, которая принимает kи возвращает id (4 # (3 # (2 # k))). Требуется idтолько для базового случая n = 1, когда список пуст. Наконец, мы даем этой функции вход k = n, получая nномер дробовика.

Zgarb
источник
6

CJam, 32 байта

Просто следуя спецификации к сути. Выполнение инструкций на большем наборе, чтобы не влиять на n- е число.

ri:N)2#,:)N{))/2/{:)~\@}%:+}/N(=

Попробуйте онлайн здесь

оптимизатор
источник
5

Рубин, 92 байта

def s(d,n)
d==1?n:s(d-1,n%d==0?n+(n%(d*2)==0?-d :d):n)
end
n=ARGV[0].to_i
print s(n,n).to_s

Мой первый опыт игры в гольф. Не основано ни на каком другом ответе.


Теперь, когда я посмотрел на некоторые другие, я заметил, что большинство просто определяют функцию, а не полную программу, которая принимает ввод и производит вывод. ОП попросил полную программу с вводом и выводом. Принято ли игнорировать такие требования?


84 байта

n=ARGV[0].to_i
d=n
while d>1
n+=(n%d==0?(n%(d*2)==0?-d :d):0)
d-=1
end
print n.to_s

Посмотрев на другие ответы и поняв, что итеративное решение возможно.

Соломон Медленный
источник
2
Несколько улучшений для вашего 84-байтового решения: 1. Перейдите ARGVв $*магический глобальный. 2. Это to_sненужно. 3. Вместо того, dчтобы назначать nна отдельной строке, просто сделайте, d=n=...чтобы сбрить символ. Хорошая работа для вашего первого гольфа! :)
Дверная ручка
1
Где я прошу полную программу? «Вы можете написать программу или функцию ...»;) (Это также значение по умолчанию для задач по коду-гольфу , но я обычно включаю их для полноты.)
Мартин Эндер
Чтобы добавить к предложениям @ Doorknob, два набора скобок в n+=строке не нужны, и оба случая ==0можно смело изменить на <1.
Питер Тейлор
5

Python 2, 97 79 символов

g=lambda n,k:n>1and g(n-1,k-(k%n<1)*n*(-1)**(k/n%2))or k
n=input()
print g(n,n)

Для каждого индекса он определяет правильное значение, рекурсивно преследуя число в обратном направлении. Алгоритм был обнаружен независимо.

редактировать: теперь он печатает только nномер вместо первых nчисел. Конечно, итеративный подход будет короче, но я не хочу копировать код Sp3000.

Jakube
источник
Да, я думаю, что все сойдутся в этом. Я нашел эту g(i,i)часть особенно раздражающей, хотя ...
Sp3000
2
Язык должен быть помечен как Python 2, из-за printутверждения.
mbomb007
@ mbomb007 Исправил это.
Якуб
4

Haskell, 79 байтов

1#i=i
s#i|i`mod`(2*s)==0=(s-1)#(i-s)|i`mod`s==0=(s-1)#(i+s)|1<2=(s-1)#i
p n=n#n

Использование: p 66какие выводы145

Объяснять особо нечего: функция #рекурсивно вычисляет номер ружья в положении iшага s. p nвозвращает число в позиции nшага n.

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

к, 41 байт

{{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]}

 / apply to an int
 {{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]} 42
111
 / apply to 1 through 66
 {{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]}'1+!66
1 4 8 6 12 14 16 9 18 20 24 26 28 22 39 15 36 35 40 38 57 34 48 49 51 44 46 33 60 77 64 32 75 56 81 68 76 58 100 55 84 111 88 62 125 70 96 91 98 95 134 72 108 82 141 80 140 92 120 156 124 94 121 52 152 145
  • {...} лямбда, х и у неявный 1-й и 2-й аргумент
  • $[b;t;f] троичный оператор, оценивает b с последующим t / f соответственно
  • b!a по модулю б
  • _ этаж, приводит результат деления к int
  • % деление
  • {...}/[x;y] простое число {...} с x и применение к списку y, эквивалентно f [f [.. f [f [x; y0]; y1]; .. yn-1]; yn]
  • | обратный
  • ! Функция йота, генерировать список от 0 до n-1
mollmerx
источник
4

Common Lisp, 113 91

(повторяется: 91)

(defun s(n)(do((r n(1- r)))((= r 1)n)(if(= 0(mod n r))(incf n(* r(if(oddp(/ n r))1 -1))))))

(оригинал, рекурсив: 113)

(defun s(n &optional(r n))(cond((= r 1)n)((= 0(mod n r))(s(+ n(* r(if(oddp(/ n r))1 -1)))(1- r)))(t(s n(1- r)))))

пример

С рекурсивной версией:

(trace s)
(s 10)

  0: (S 10)
    1: (S 20 9)
      2: (S 20 8)
        3: (S 20 7)
          4: (S 20 6)
            5: (S 20 5)
              6: (S 15 4)
                7: (S 15 3)
                  8: (S 18 2)
                    9: (S 20 1)
                    9: S returned 20
         ...
    1: S returned 20
  0: S returned 20

тесты

Проверки и меры для итерационной версии:

(let ((list '(1 4 8 6 12 14 16 9 18 20 24 26 28 22 39 15 36 35 40 38 57 34 48 49 51 44
              46 33 60 77 64 32 75 56 81 68 76 58 100 55 84 111 88 62 125 70 96 91 98 95
              134 72 108 82 141 80 140 92 120 156 124 94 121 52 152 145)))
  (time
   (loop for r in list
         for n from 1
         always (= r (s n)))))

 => T

Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  807,160 processor cycles
  32,768 bytes consed
CoreDump
источник
4

Mathematica, 53 49 байтов

(For[i=n=#,n>1,--n,If[n∣i,i+=Mod[i,2n]2-n]];i)&

Я решил сыграть в свою референсную игру Символ Unicode для «делит» и имеет значение 3 байта. В противном случае используется тот же алгоритм, что и у всех остальных.

Он определяет безымянную функцию, которая принимает nв качестве единственного параметра и возвращает nномер дробовика.

Мартин Эндер
источник
4

GolfScript, 27 символов

~.,(~%{):i\.@%!~)1$i/?i*-}/

объяснение

Если f(i, n)это значение в позиции nпосле i-1преобразований, мы имеем

f(1, n) = n
f(i, n) = f(i - 1, n % i == 0 ? (((n / i - 1) ^ 1) + 1) * i : n)  for i > 1

где ^обозначает побитовый xor; учитывая ввод n, мы хотим вычислить f(n, n).

Преобразование из рекурсивной функции в цикл неинтересно; Что интересно, так это способ, которым

n % i == 0 ? (((n / i - 1) ^ 1) + 1) * i : n

можно переписать Более очевидный подход состоит в том, чтобы сказать, что это должно быть

n + (n % i == 0 ? i : 0) * g(n / i)

для некоторых g. Очевидно, gчередуется между 1и -1, так как позиции меняются поочередно вверх и вниз; так как g(1) = 1(потому что 1поменяется 2) мы имеем

n + (n % i == 0 ? i : 0) * -1**(1 + n / i)

где **обозначает возведение в степень. Окончательные сбережения прибывают из переписывания этого как

n - i * (n % i == 0 ? -1 : 0)**(n / i)

рассечение

~             # Evaluate input to get n
.,(~%{        # For n-1 downto 1...
  ):i         #   Let i be that value + 1, so for i = n downto 2...
  \.@%!       #   Find n % i == 0 ? 1 : 0
  ~)          #   Negate
  1$i/?       #   Raise to the power of n/i
  i*-         #   Multiply by i and subtract
}/
Питер Тейлор
источник
Если у вас есть самые короткие ответы GS и CJam, почему бы не получить самый короткий ответ Pyth? u-G*H^_!%GH/GHrhQ2QЕсли вы не хотите публиковать это сами, скажите мне / добавьте это в ответ CW.
FryAmTheEggman
@FryAmTheEggman, я не очень опытен в CJam, но я могу, по крайней мере, более или менее прочитать его. Я не имею понятия, что говорит Пит в вашем комментарии, хотя из контекста я предполагаю, что это порт этого ответа. Поэтому лучше, если вы разместите это, потому что вы можете ответить на вопросы об этом.
Питер Тейлор
4

Юлия, 61 57 байт

n->(i=n;while~-i!=0 n+=(n%i<1)*i*(n÷i%2*2-1);i-=1;end;n)

Это создает безымянную функцию, которая принимает один аргумент nи возвращает nномер дробовика. Чтобы назвать его, дайте ему имя, например f=n->(...).

Примеры:

julia> for i = 1:10 println(f(i)) end
1
4
8
6
12
14
16
9
18
20

В настоящее время это основано на удивительном Python-ответе @ Sp3000 . Я скоро вернусь к этому, потому что в Джулии должен быть более короткий способ сделать это, чем то, что я сделал здесь. Любой вклад приветствуется, как всегда.

Алекс А.
источник
3

CJam, 28 27 байт

Так что это немного смущает ... перед тем как опубликовать это, я сам попробовал сыграть в гольф и получил 30 байтов в CJam. Ни один из существующих ответов еще не победил. Тем временем мне также удалось сбрить еще три байта. В комментарии есть более короткое решение Pyth, но в ответ не было добавлено ничего более короткого, так что вот оно. Может быть, это вдохновляет людей APL / J попытаться немного усерднее (или кто-то действительно публикует решение Pyth), прежде чем я приму свой ответ. ;)

l~__(,f-{_I_+%_+I-_zI=*+}fI

Проверьте это здесь.

объяснение

l~                          "Read input N and eval.";
  __(,                      "Duplicate twice, create range [0 1 2 ... N-2].";
      f-                    "Subtract each from N, giving [N N-1 N-2 ... 2].";
        {               }fI "For each element, storing the element in I.";
         _I_+%_+I-          "Compute 2(N % 2I)-I - the shuffling offset";
                  _zI=      "Check that this offset is ±I.";
                      *+    "Multiply the offset by this boolean and update to N.";
Мартин Эндер
источник
3

J, 34 32 байта

   (]+[*(1-~2*2|%~)*0=|)/@(_1}2+i.)

   ((]+[*(1-~2*2|%~)*0=|)/@(_1}2+i.)) every 1+i.20  NB. running with inputs 1..20
1 4 8 6 12 14 16 9 18 20 24 26 28 22 39 15 36 35 40 38

Попробую немного поиграть в гольф и добавить некоторые объяснения позже.

Попробуйте это онлайн здесь.

randomra
источник
1

Рубин, 57 47 байт

По сути, это решение Python для Sp3000предложением xnor ) переведено на Ruby. Я мог бы, вероятно, сыграть в гольф в нескольких местах.

->n{n.downto(2).map{|i|n+=i*(n/i%2-~-n/i%2)};n}
Sherlock9
источник