Еще неиспользованные пары

21

Давайте определим последовательность натуральных чисел. Мы определим последовательность на четных числах, чтобы она была вдвое больше предыдущего. Нечетные индексы последовательности будут наименьшим положительным целым числом, еще не появившимся в последовательности.

Вот первая пара терминов.

1,2,3,6,4,8,5,10,7,14,9,18,11,22,12,24,13,26,15,30

Вы также можете думать об этом как о списке сцепленных пар (n, 2n), где n является наименее неиспользованным положительным целым числом.

задача

Учитывая число n в качестве входных данных, рассчитайте n- й член в этой последовательности.

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

OEIS A036552

code-golf sequence Мастер пшеницы
источник
Тот факт, что нечетные индексы последовательности будут наименьшим положительным целым числом, еще не появившимся в последовательности. не имеет значения, верно?
Адам
1
Кроме того, какие пары ?
Адам
@ Adám Нет, это не тот случай. Я не уверен, что создает у вас такое впечатление, возможно, я плохо сформулировал это.
Пшеничный волшебник
1
@ Adám Другой способ думать о последовательности состоит в том, что она состоит из сцепленных пар, (n,2n)и каждое число появляется только один раз. Каждая пара выбирается наименьшей из возможных, соблюдая при этом последнее ограничение.
Мартин Эндер
3
2-адическая оценка нечетных элементов ряда всегда четна. Может быть полезным для кого-то.
CalculatorFeline

Ответы:

11

Haskell, 40 байт

l(a:r)=a:2*a:l[x|x<-r,x/=2*a]
(l[1..]!!)

Нулевой основе. lпостепенно строит последовательность из ленивого списка оставшихся целых чисел.

Кристиан Сиверс
источник
7

JavaScript (ES6), 92 82 69 67 65 байт

n=>(F=i=>i^n?F(a[b=i&1?2*b:(g=k=>a[k]?g(k+1):k)(1)]=-~i):b)(a={})

Как?

Мы отслеживаем:

  • Последнее введенное значение b .
  • Все ранее встречающиеся значения в справочной таблице a .

Внутренне мы используем 0 на основе индекса I . Поэтому нечетное и четное поведение инвертируется:

  • В нечетных позициях следующее значение просто 2 * b.

  • В четных позициях мы используем рекурсивную функцию g () и таблицу поиска a, чтобы определить наименьшее значение соответствия:

    (g = k => a[k] ? g(k + 1) : k)(1)

Чтобы сохранить несколько байтов, я инициализируется {}вместо 0. Это заставляет нас использовать:

  • i^nдля сравнения I с п потому , что в ({}) ^ n === nто время как ({}) - nпринимает значение NaN.
  • -~iувеличить I , потому что ({}) + 1будет генерировать строку.

демонстрация

Показать фрагмент кода

Arnauld
источник
60 байтов
лохматый
5

Python 3 , 80 72 69 байт

-7 байт благодаря мистеру Xcoder !

f=lambda n:n and[f(n-1)*2,min({*range(n+1)}-{*map(f,range(n))})][n%2]

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

notjagan
источник
1
Вы можете восстановить set(...)с помощью {{* ...} на 78 байт
Mr. Xcoder
@ Zacharý Вы ссылались на мой комментарий? Если это так, набор в Python 3 может быть {*...}вместо set(...).
г-н Xcoder
Я комментировал без раздумий, через несколько мгновений я понял, что {...for...in...}должно быть больше прощаний.
Захарий
На самом деле, это сэкономит 4 байта, потому что вы используете его дважды
Mr. Xcoder
69 байтов. (и он не используется Trueдля 1)
Мастер пшеницы
3

05AB1E , 16 15 14 байтов

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

Lʒb1¡`gÈ}€x¹<è

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

объяснение

L                 # range [1 ... input]
 ʒ      }         # filter, keep only elements whose
  b               # ... binary representation
   1¡             # ... split at 1's
     `gÈ          # ... ends in an even length run
         €x       # push a doubled copy of each element in place
           ¹<è    # get the element at index (input-1)
Emigna
источник
3

Python 2 , 59 51 49 байтов

f=lambda n,k=2:2/n%-3*(1-k)or f(n+~(k&-k)%-3,k+1)

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

Задний план

Каждое положительное целое число n может быть однозначно выражено как n = 2 o (n) c (n) , где c (n) нечетно.

Пусть ⟨A п ⟩ п> 0 будет последовательность из провокационной спецификации.

Мы утверждаем, что для всех натуральных чисел n , o (a 2n-1 ) четно. Поскольку o (a 2n ) = o (2a 2n-1 ) = o (a 2n-1 ) + 1 , это эквивалентно утверждению, что o (a 2n ) всегда нечетно.

Предположим, утверждение является ложным, и пусть 2m-1 будет первым нечетным индексом последовательности, так что o (a 2m-1 ) будет нечетным. Обратите внимание, что это делает 2m первым четным индексом последовательности, так что o (a 2m-1 ) является четным.

о (а 2m-1 ) нечетно и 0 четно, так 2m-1 делится на 2 . По определению, 2m-1 представляет собой наименьшее целое положительное число пока не появляется в последовательности , а это означает , что 2m-1 /2 , должно быть , появились раньше. Пусть K быть (первый) индекс в 2m-1 /2 в .

Так как o (a k ) = o (a 2m-1 /2) = o (a 2m-1 ) - 1 является четным, из минимальности n следует, что k нечетно. В свою очередь, это означает , что к + 1 = 2а к = а 2m-1 , что противоречит определению в 2m-1 .

Как это устроено

еще впереди

Деннис
источник
3

р , 70 69 65 байт

function(n){for(i in 2*1:n)F[i-1:0]=which(!1:n%in%F)[1]*1:2
F[n]}

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

Анонимная функция, которая принимает один аргумент. Fпо умолчанию FALSEили 0так, что алгоритм правильно оценивает, что в последовательности еще нет положительных чисел.

Алгоритм генерирует пары в forцикле следующим образом (где iидет от 2к 2nдо 2):

           which(!1:n%in%l)[1]     # the missing value
                              *1:2 # keep one copy the same and double the next
l[i-1:0]=                         # store into l at the indices i-1 and i
Giuseppe
источник
2

Perl 6 , 50 байт

{(1,{@_%2??2*@_[*-1]!!first *∉@_,1..*}...*)[$_]}

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

  • 1, { ... } ... *является лениво сгенерированной бесконечной последовательностью, где каждый член после первого предоставляется блоком кода с разделителями-скобками. Поскольку блок ссылается на@_ массив, он получает всю текущую последовательность в этом массиве.
  • Если текущее количество элементов нечетное (@_ % 2 ), мы генерируя даже индексированный элемент, так что следующий элемент является двойным последним элементом мы имеем до сих пор: 2 * @_[*-1].
  • В противном случае мы получаем первое положительное целое число, которое еще не появляется в последовательности: first * ∉ @_, 1..* .
  • $_является аргументом для внешней функции. Он индексируется в бесконечной последовательности, давая возвращаемое значение функции.
Шон
источник
1

Mathematica, 82 байта

(s={};a=1;f=#;While[f>0,If[s~FreeQ~a,s~AppendTo~{a,2a}];a++;f--];Flatten[s][[#]])&

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

J42161217
источник
58 байтов в Mathematica (хотя я, вероятно, должен просто опубликовать отдельный ответ, так как идея довольно разная).
notjagan
Вы скопировали это из ссылки OEIS?
J42161217
Я изменил его, чтобы соответствовать задаче и больше играть в гольф, но это более или менее то же самое, что и ссылка OEIS.
notjagan
1
@ не публикуйте новый ответ, если хотите, и
указывайте
1

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

x=>{int y=1;for(var s="";x>2;x-=2)for(s+=2*y+":";s.Contains(++y+""););return x*y;}

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

-6 байт благодаря @ASCIIOnly!

Dana
источник
C # 8 может быть слишком новым, чтобы быть распространенным в онлайн-переводчиках, добавлено к тому факту, что csi - это вещь Mono, поэтому вам придется подождать, пока Mono ее реализует, и добавить ее в стабильную сборку (если она не t уже)
ASCII-только
к сожалению , это не так просто , чтобы проверить это в C #
ASCII-только
Используйте это, чтобы начать? Но да, это не кажется простой вещью. docs.microsoft.com/en-us/dotnet/api/…
дана
1
86? - не думайте, что :нужны s, так как это будет самое большое число в списке
только ASCII
Также 2.0=>2f
Дана
0

Clojure, 102 байта

#(nth(loop[l[0 1 2 3]i %](if(= i 0)l(recur(conj l(*(last l)2)(nth(remove(set l)(range))0))(dec i))))%)

Итерирует nвремя для построения последовательности и возвращает n1-й элемент, проиндексированный 1.

NikoNyrh
источник
0

Рубин, 60 байт

->n,*a{eval"v+=1while a[v];a[v]=a[2*v]=v+v*n%=2;"*(n/2+v=1)}

0 индексированные. Мы зацикливаем n/2+1время, генерируя два значения каждый раз и сохраняя их, заполняя массив по их индексам. v+v*n%2дает выход, либо vили в v*2зависимости от четности n.

histocrat
источник
0

Рубин , 49 байтов

->n{*s=t=0;s|[t+=1]==s||s<<t<<t*2until s[n];s[n]}

Начните с [0], добавляйте пары в массив, пока у нас не будет хотя бы n + 1 элементов, затем возьмите n + 1-й (основанный на 1)

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

гигабайт
источник
0

JavaScript (ES6), 60 65 байт

Итеративное решение.

n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

Меньше гольфа

n=>{
  s = {}; //hashtable for used values
  for(i=0; n; )
  {
    if ( ! s[++i] )
    {
      s[i*2] = 1; // remember i*2 is already used
      if (--n)
        if (--n)
          0;
        else
          result = i*2;
      else
        result = i;
    }
  }
  return result;  
}

Тестовое задание

F=
n=>eval("for(s={},i=0;n;)s[++i]?0:(s[i+i]=--n)?--n?0:i+i:i")

for (a=1; a < 50; a++)
  console.log(a,F(a))
Развернуть фрагмент

edc65
источник
0

Желе , 13 12 10 байт

ḤRọ2ḂĠZFị@

Это использует наблюдение из моего ответа Python .

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

Как это устроено

ḤRọ2ḂĠZFị@  Main link. Argument: n

Ḥ           Unhalve; yield 2n.
 R          Range; yield [1, ... , 2n].
  ọ2        Compute the order of 2 in the factorization of each k in [1, ..., 2n].
    Ḃ       Bit; compute the parity of each order.
     G      Group the indices [1, ..., 2n] by the corresponding values.
      Z     Zip/transpose the resulting 2D array, interleaving the indices of 0
            with the indices of 1, as a list of pairs.
       F    Flatten. This yields a prefix of the sequence.
        ị@  Take the item at index n.
Деннис
источник