21
\$\begingroup\$

Let's define a sequence of positive integers. We will define the sequence on even numbers to be double the previous term. The odd indices of the sequence will be smallest positive integer not yet appearing in the sequence.

Here are the first couple terms.

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

You can also think of this as the list of concatenated pairs (n,2n) where n is the least unused positive integer so far.

Task

Given a number n as input calculate the nth term in this sequence.

This is so you should aim to minimize the size of your source code as measured in bytes.

OEIS A036552

\$\endgroup\$
  • \$\begingroup\$ The fact that The odd indices of the sequence will be smallest positive integer not yet appearing in the sequence. is irrelevant, right? \$\endgroup\$ – Adám Jul 12 '17 at 14:53
  • 1
    \$\begingroup\$ Also, what pairs? \$\endgroup\$ – Adám Jul 12 '17 at 14:53
  • \$\begingroup\$ @Adám No this is not the case. I'm not sure what gives you that impression perhaps I have worded this poorly. \$\endgroup\$ – Wheat Wizard Jul 12 '17 at 14:54
  • 1
    \$\begingroup\$ @Adám another way to think of the sequence is that it consists of concatenated pairs (n,2n) and each number appears only once. Each pair is chosen to be the smallest possible while adhering to the latter constraint. \$\endgroup\$ – Martin Ender Jul 12 '17 at 14:56
  • 3
    \$\begingroup\$ The 2-adic valuation of odd elements of the series is always even. Might be useful to someone. \$\endgroup\$ – CalculatorFeline Jul 12 '17 at 15:57

20 Answers 20

11
\$\begingroup\$

Haskell, 40 bytes

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

Zero-based. l incrementally builds the sequence from a lazy list of remaining integers.

\$\endgroup\$
7
\$\begingroup\$

JavaScript (ES6), 92 82 69 67 65 bytes

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

How?

We keep track of:

  • The last inserted value b.
  • All previously encountered values in the lookup table a.

Internally, we're using a 0-based index i. Odd and even behaviors are therefore inverted:

  • At odd positions, the next value is simply 2 * b.

  • At even positions, we use the recursive function g() and the lookup table a to identify the smallest matching value:

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

To save a few bytes, i is initialized to {} rather than 0. This compels us to use:

  • i^n to compare i with n because ({}) ^ n === n whereas ({}) - n evaluates to NaN.
  • -~i to increment i, because ({}) + 1 would generate a string.

Demo

let f =

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

for(n = 1; n <= 20; n++) {
  console.log('a[' + n + '] = ' + f(n));
}

\$\endgroup\$
5
\$\begingroup\$

Python 3, 80 72 69 bytes

-7 bytes thanks to Mr. Xcoder!

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can repace set(...) with `{*...} for 78 bytes \$\endgroup\$ – Mr. Xcoder Jul 12 '17 at 15:10
  • \$\begingroup\$ @Zacharý Were you reffering to my comment? If so, a set in Python 3 can be {*...} instead of set(...). \$\endgroup\$ – Mr. Xcoder Jul 12 '17 at 15:12
  • \$\begingroup\$ I was commenting without thinking, I realized a few moments later that {...for...in...} woould be more byes. \$\endgroup\$ – Zacharý Jul 12 '17 at 15:13
  • \$\begingroup\$ Actually, it would save 4 bytes, because you use it twice \$\endgroup\$ – Mr. Xcoder Jul 12 '17 at 15:13
  • \$\begingroup\$ 69 bytes. (and it doesn't use True for 1) \$\endgroup\$ – Wheat Wizard Jul 12 '17 at 15:20
3
\$\begingroup\$

Jelly, 15 bytes

Jḟ⁸ḢðḤṭṭ
0Ç¡Ḋị@

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Mathics, 56 53 bytes

-3 bytes thanks JungHwan Min!

(w={};Do[w~FreeQ~k&&(w=w~Join~{k,2k}),{k,#}];w[[#]])&

Try it online!

Based on the Mathematica expression given in the OEIS link.

\$\endgroup\$
  • 1
    \$\begingroup\$ Also 53 bytes: Nest[k=0;If[#~FreeQ~++k,#~Join~{k,2k},#]&,{},#][[#]]& \$\endgroup\$ – JungHwan Min Jul 12 '17 at 16:32
3
\$\begingroup\$

PHP, 64 bytes

for(;$argn-$i++;)if($i&$$e=1)for(;${$e=++$n};);else$e*=2;echo$e;

Try it online!

PHP, 77 bytes

for(;$argn-$i++;$r[]=$e)if($i&1)for(;in_array($e=++$n,$r););else$e*=2;echo$e;

Try it online!

PHP, 78 bytes

for(;$argn-$i++;)$e=$r[]=$i&1?end(array_diff(range($i,1),$r?:[])):2*$e;echo$e;

Try it online!

\$\endgroup\$
3
\$\begingroup\$

PHP, 56 bytes

while($$n=$i++<$argn)for($n*=2;$i&$$k&&$n=++$k;);echo$n;

PHP, 75 72 bytes

for($a=range(1,$argn);$i++<$argn;)$a[~-$n=$i&1?min($a):2*$n]=INF;echo$n;

Try it online

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 16 15 14 bytes

1-indexed.
Uses the fact that the binary representation of elements at odd indices in the sequence ends in an even number of zeroes: A003159.

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

Try it online!

Explanation

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)
\$\endgroup\$
3
\$\begingroup\$

Python 2, 59 51 49 bytes

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

Try it online!

Background

Every positive n integer can be expressed uniquely as n = 2o(n)c(n), where c(n) is odd.

Let ⟨ann>0 be the sequence from the challenge spec.

We claim that, for all positive integers n, o(a2n-1) is even. Since o(a2n) = o(2a2n-1) = o(a2n-1) + 1, this is equivalent to claiming that o(a2n) is always odd.

Assume the claim is false and let 2m-1 be the first odd index of the sequence such that o(a2m-1) is odd. Note that this makes 2m be the first even index of the sequence such that o(a2m-1) is even.

o(a2m-1) is odd and 0 is even, so a2m-1 is divisible by 2. By definition, a2m-1 is the smallest positive integer not yet appearing in the sequence, meaning that a2m-1/2 must have appeared before. Let k be the (first) index of a2m-1/2 in a.

Since o(ak) = o(a2m-1/2) = o(a2m-1) - 1 is even, the minimality of n implies that k is odd. In turn, this means that ak+1 = 2ak = a2m-1, contradicting the definition of a2m-1.

How it works

yet to come

\$\endgroup\$
3
\$\begingroup\$

R, 70 69 65 bytes

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

Try it online!

An anonymous function that takes one argument. F defaults to FALSE or 0 so that the algorithm correctly assesses that no positive integers are in the sequence yet.

The algorithm generates the pairs in a for loop in the following manner (where i goes from 2 to 2n by 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
\$\endgroup\$
2
\$\begingroup\$

Haskell, 63 bytes

g x=[2*g(x-1),[a|a<-[1..],a`notElem`map g[1..x-1]]!!0]!!mod x 2

Try it online!

This one abuses Haskell's lazy evaluation to the fullest extent.

\$\endgroup\$
2
\$\begingroup\$

Perl 6, 50 bytes

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

Try it online!

  • 1, { ... } ... * is a lazily-generated infinite sequence where each term after the first is provided by the brace-delimited code block. Since the block references the @_ array, it receives the entire current sequence in that array.
  • If the current number of elements is odd (@_ % 2), we're generating an even-indexed element, so the next element is double the last element we have so far: 2 * @_[*-1].
  • Otherwise, we get the first positive integer that does not yet appear in the sequence: first * ∉ @_, 1..*.
  • $_ is the argument to the outer function. It indexes into the infinite sequence, giving the function's return value.
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 82 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 58 bytes in Mathematica (although I should probably just post a separate answer since the idea is pretty different). \$\endgroup\$ – notjagan Jul 12 '17 at 15:26
  • \$\begingroup\$ Did you copy that from OEIS link? \$\endgroup\$ – J42161217 Jul 12 '17 at 15:48
  • \$\begingroup\$ I modified it to fit the task and to be golfed more, but it more or less is the same as the OEIS link. \$\endgroup\$ – notjagan Jul 12 '17 at 15:50
  • 1
    \$\begingroup\$ @not post a new answer if you want and credit the author \$\endgroup\$ – J42161217 Jul 12 '17 at 15:55
1
\$\begingroup\$

k, 27 bytes

*|{x,*(&^x?!y;|2*x)2!y}/!2+

1-indexed. Try it online!

Using (!y)^x instead of &^x?!y works too.

\$\endgroup\$
1
\$\begingroup\$

C# (Visual C# Interactive Compiler), 82 bytes

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

Try it online!

-6 bytes thanks to @ASCIIOnly!

\$\endgroup\$
  • \$\begingroup\$ C#8 may be too new to be common on online interpreters for now, added to the fact that csi is a Mono thing so you'd have to wait for Mono to implement it and add it to a stable build (if it hasn't already) \$\endgroup\$ – ASCII-only Jan 6 at 7:33
  • \$\begingroup\$ sadly it isn't easy to check for this in C# \$\endgroup\$ – ASCII-only Jan 6 at 8:12
  • \$\begingroup\$ Use this to start? But yeah, doesn't seem like a straightforward thing. docs.microsoft.com/en-us/dotnet/api/… \$\endgroup\$ – dana Jan 6 at 8:16
  • 1
    \$\begingroup\$ 86? - don't think the :s are needed since it will be the largest number in the list \$\endgroup\$ – ASCII-only Jan 6 at 8:22
  • \$\begingroup\$ Also 2.0 => 2f \$\endgroup\$ – dana Jan 6 at 8:23
0
\$\begingroup\$

Clojure, 102 bytes

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

Iterates n times to build up the sequence and returns the nth item, 1-indexed.

\$\endgroup\$
0
\$\begingroup\$

Ruby, 60 bytes

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

0-indexed. We loop n/2+1 times, generating two values each time and storing them by populating an array at their indices. v+v*n%2 gives the output, either v or v*2 depending on the parity of n.

\$\endgroup\$
0
\$\begingroup\$

Ruby, 49 bytes

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

Start with [0], add pairs to the array until we have at least n+1 elements, then take the n+1th (1-based)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 60 65 bytes

An iterative solution.

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

Less golfed

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;  
}

Test

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

\$\endgroup\$
0
\$\begingroup\$

Jelly, 13 12 10 bytes

ḤRọ2ḂĠZFị@

This uses the observation from my Python answer.

Try it online!

How it works

Ḥ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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.