Calculate A190810

Question

Your task is pretty simple, calculate the n-th element of A190810.

Elements of A190810 are calculated according to these rules:

1. The first element is 1
2. The sequence is increasing
3. If x occurs in the sequence, then 2x+1 and 3x-1 also do

You can use 1-based or 0-based indexing, but if you use 0-based indexing, please say it in the answer.

Test cases

a(1) = 1
a(2) = 2
a(3) = 3
a(4) = 5
a(5) = 7
a(10) = 17
a(20) = 50
a(30) = 95
a(55) = 255

Since this is code-golf, the shortest answer in bytes wins!

Answer 1

Jelly, 16 bytes

×3’;Ḥ‘$;
1Ç¡ṢQ³ị

Very inefficient. Try it online!

How it works

1Ç¡ṢQ³ị   Main link. Argument: n (integer)

1         Set the return value to 1.
 Ç¡       Execute the helper link n times.
   Ṣ      Sort the resulting array.
    Q     Unique; deduplicate the sorted array.
     ³ị   Retrieve its n-th element.


×3’;Ḥ‘$;  Helper link. Argument: A (array)

×3        Multiply all elements of A by 3.
  ’       Decrement the resulting products.
      $   Combine the two links to the left into a monadic chain.
    Ḥ     Unhalve; multiply all elements of A by 2.
     ‘    Increment the resulting products.
   ;      Concatenate 3A-1 and 2A+1.
       ;  Concatenate the result with A.

Answer 2

Python 2, 88 83 72 bytes

You may want to read the programs in this answer in reverse order...

Slower and shorter still, thanks to Dennis:

L=1,;exec'L+=2*L[0]+1,3*L[0]-1;L=sorted(set(L))[1:];'*input()
print L[0]

Try it online

---

This doesn't run as fast, but is shorter (83 bytes.) By sorting and removing duplicates each iteration, as well as removing the first element, I remove the need for an index into the list. The result is simply the first element after n iterations.

I may have out-golfed Dennis. :D

L=[1]
n=input()
while n:L+=[2*L[0]+1,3*L[0]-1];n-=1;L=sorted(set(L))[1:]
print L[0]

Try it online

---

This version below (88 bytes) runs really fast, finding the 500000th element in about two seconds.

It's pretty simple. Compute elements of the list until there are three times more elements than n, since every element added may add at most 2 more unique elements. Then remove duplicates, sort, and print the nth element (zero-indexed.)

L=[1]
i=0
n=input()
while len(L)<3*n:L+=[2*L[i]+1,3*L[i]-1];i+=1
print sorted(set(L))[n]

Try it online

Answer 3

Python 2, 59 bytes

t={1}
exec'm=min(t);t=t-{m}|{2*m+1,3*m-1};'*input()
print m

Based on @mbomb007's Python answer. Test it on Ideone.

Answer 4

Haskell, 76 73 69 bytes

a#b=mod a b<1&&t(div a b)
t x=x<2||(x-1)#2||(x+1)#3
(filter t[1..]!!)

Uses a 0-based index. Usage example: (filter t[1..]!!) 54 -> 255.

Instead of building the list by repeatedly inserting 2x+1 and 3x-1 as seen in most other answers, I go through all integers and check if they can reduced to 1 by repeatedly applying (x-1) / 2 or (x+1) / 3 if divisible.

Answer 5

Haskell, 77 74 bytes

import Data.List
i=insert
f(x:y)=x:f(i(2*x+1)$i(3*x-1)y)
a=(!!)(nub$f[1])

This provides a function a for the n-th entry. It's zero indexed. Alternatively, a=nub$f[1] will create the whole list (lazily).

It's a list-variant of Reinhard Zumkeller's Set code.

Answer 6

Pyth, 20 19 bytes

hutS{+G,hyhGt*3hGQ0

Try it online. Test suite.

Uses zero-based indexing.

Answer 7

Python 2, 88 84 bytes

g=lambda k:g(k%2*k/2)|g(k%3/2*-~k/3)if k>1else k
f=lambda n,k=1:n and-~f(n-g(k),k+1)

Test it on Ideone.

Answer 8

Brachylog, 45 bytes

:1-I,?:?*:1ydo:Im.
1.|:1-:1&I(:3*:1-.;I*:1+.)

Computes N = 1000 in about 6 seconds on my machine.

This is 1-indexed, e.g.

run_from_file('code.brachylog',1000,Z).
Z = 13961 .

Explanation

• Main predicate:

  :1-I,               I = Input - 1
       ?:?*           Square the Input
           :1y        Find the first Input*Input valid outputs of predicate 1
              do      Remove duplicates and order
                :Im.  Output is the Ith element
  

• Predicate 1:

  1.                  Input = Output = 1
  |                   Or
  :1-:1&I             I is the output of predicate 1 called with Input - 1 as input
         (            
           :3*:1-.      Output is 3*I-1
         ;            Or
           I*:1+.       Output is 2*I+1
         )
  

You may note that we don't pass any input to predicate 1 when we call y - Yield. Because of constraint propagation, it will find the right input once reaching the 1. clause which will propagate the correct input values.

Answer 9

MATL, 19, 18 17 bytes

1w:"tEQy3*qvSu]G)

This is an extremely inefficient algorithm. The online interpreter runs out of memory for inputs greater than 13.

One byte saved, thanks to Luis Mendo!

Try it online!

This version is longer, but more efficient (21 bytes)

1`tEQy3*qvSutnG3*<]G)

Try it online

Explanation:

The logical way to do it, is to add elements to the array until it is long enough to grab the i'th element. That's how the efficient one works. The golfy (and inefficient) way to do it, is to just increase the array size i times.

So first, we define the start array: 1. Then we swap the top two elements, so that input is on top. w. Now, we loop through the input with :". So i times:

t             %Duplicate our starting (or current) array.
 EQ           %Double it and increment
   y          %Push our starting array again
    3*q       %Multiply by 3 and decrement
       v      %Concatenate these two arrays and the starting array
        Su    %Sort them and remove all duplicate elements.

Now, we have a gigantic array of the sequence. (Way more than is needed to calculate) So we stop looping, ], and grab the i'th number from this array with G) (1-indexed)

Answer 10

05AB1E, 18 17 bytes

Uses CP-1252 encoding.

$Fз>s3*<)˜Ù}ï{¹è

Explanation

$                  # initialize with 1
 F          }      # input number of times do
  Ð                # triplicate current list/number
   ·>              # double one copy and add 1
     s3*<          # multiply one copy by 3 and subtract 1
         )˜Ù       # combine the 3 lists to 1 list and remove duplicates
             ï{    # convert list to int and sort
               ¹è  # take the element from the list at index input

Try it online for small numbers

Very slow.
Uses 0-based indexing.

Answer 11

JavaScript (ES6), 63 bytes

 f=(n,a=[1],i=0)=>a[i++]?--n?f(n,a,a[i*2]=a[i*3-2]=1):i:f(n,a,i)

Probably gives up quickly due to the recursion.

Answer 12

Clojure, 114 108 bytes

#(loop[a(sorted-set 1)n 1](let[x(first a)](if(= n %)x(recur(conj(disj a x)(+(* 2 x)1)(-(* 3 x)1))(inc n)))))

I wouldn't be surprised if this could be golfed/reduced by a significant amount but set's not supporting nth really hurt my train of thought.

Try the online

Version with spaces:

#(loop [a (sorted-set 1)
        n 1]
  (let [x (first a)]
    (if (= n %)
      x
      (recur (conj (disj a x) (+ (* 2 x) 1) (- (* 3 x) 1)) (inc n))
      )))

Answer 13

Retina, 57

^.+
$*¶¶1
¶¶(1(1*))
¶1$1$1¶$2$1$1
O`
}`(¶1+)\1\b
$1
G2`
1

Try it online!

0-indexed. Follows the frequently used algorithm: remove the minimum value from the current set, call it x, and add 2x+1 and 3x-1 to the set a number of times equal to the input, then the leading number is the result. The "set" in Retina is just a list that is repeatedly sorted and made to contain only unique elements. There are some sneaky bits added to the algorithm for golf, which I will explain once I've had some more time.

Big thanks to Martin for golfing off around 20 bytes!

Answer 14

C++, 102 bytes

[](int i){int t;map<int,int>k;for(k[1];i--;k.erase(t))t=k.begin()->first,k[t*2+1],k[t*3-1];return t;};

This lambda function requires #include <map> and using std::map.

The map here is just a collection of keys; their values are ignored. I use map in order to benefit from the terse code for insertion:

k[1]; // inserts the key 1 into the map

Thanks to the sorted order of map, the smallest element is extracted by k.begin()->first.

Answer 15

Actually, 27 bytes

╗1#╜`;;2*1+)3*1@-#++╔S`n╜@E

Try it online!

This program uses 0-based indexing. The approach is very brute-force, so don't expect it to work in the online interpreter for larger inputs.

Explanation:

╗1#╜`;;2*1+)3*1@-#++╔S`n╜@E
╗                            save input (n) in register 0
 1#                          push [1]
   ╜                         push n
    `;;2*1+)3*1@-#++╔S`n     do the following n times:
     ;;                        make two copies of the list
       2*1+                    apply 2x+1 to each element in one copy
           )3*1@-              and 3x-1 to each element in the other copy
                 #             workaround for a weird list bug
                  ++           append those two lists to the original list
                    ╔S         uniquify and sort
                        ╜@E  get the nth element (0-indexed)

Answer 16

CJam (25 bytes)

ri1a1${{_2*)1$3*(}%_&}*$=

Online demo. Note that this uses zero-based indexing.

This uses a similar approach to most: apply the transforms n times and then sort and extract the nth item. As a nod to efficiency the deduplication is applied inside the loop and the sorting is applied outside the loop.

Answer 17

Retina, 48 bytes

.+
$*
+1`^(((!*)!(!|\3)(?=\3!1))*!)1|\b
!$1
-2`.

Try it online!

Inspired by nimi's answer I thought I'd try a different approach for Retina, making use of the regex engine's backtracking to figure out if any given (unary) number is in the sequence or not. It turns out this can be determined with a 27 byte regex, but making use of it costs a few more, but it still ends up shorter than the generative approach.

Here's an alternative 48-byte solution:

.+
$*
{`1\b
1!
}T`1``1((!*)!(!|\2)(?=!\2$))*!$
!

And using unary I/O we can do 42 bytes, but I'm trying to avoid that and the other Retina answer uses decimal as well:

1\b
1!
}T`1``1((!*)!(!|\2)(?=!\2$))*!$
!
1

Answer 18

Ruby, 70 bytes

->n{a=*1
n.times{a<<a.map{|i|([2*i+1,3*i-1]-a).min||1.0/0}.min}
a[-2]}

Explanation

->n{
    # Magical, golfy way of initializing an array. Equivalent to a = [1].
    a=*1
    n.times{
        # Generate the next element in the sequence, by...
        a<<
            # ... finding the minimal term that will appear at some point.
            a.map{|i|
                ([2*i+1,3*i-1]-a).min||1.0/0
            }.min
    }
    # We generated n+1 elements, so we'll take the *second* to last one.
    a[-2]
}

Answer 19

J, 31 bytes

{1(]]/:~@~.@,3&*,&:<:2*>:)^:[~]

Uses zero-based indexing. Very memory-inefficient.

Explanation

{1(]]/:~@~.@,3&*,&:<:2*>:)^:[~]  Input: n
                              ]  Identity function, gets n
 1                               The constant 1
  (                      )^:[~   Repeat n times with an initial array a = [1]
                       >:          Increment each in a
                     2*            Multiply by 2 to get 2a+2
             3&*                   Multiply each in a by 3 to get 3a
                 &:<:              Decrement both x and y to get 2a+1 and 3a-1
                ,                  Join them
    ]                              Identity function, gets a
            ,                      Join a with 2a+1 and 3a-1
         ~.@                       Take the distinct values
     /:~@                          Sort up
   ]                               Return the sorted list
{                                Select the value from the list at index n and return it

Answer 20

Octave, 68 bytes

function r=a(n)s=1;for(i=1:n)r=s(i);s=union(s,[r*2+1 r*3-1]);end;end

Answer 21

Perl, 173 132 bytes +1 for -n = 133

sub c{my$a=pop;return($a==1||($a%2&&c(($a-1)/2))?1:$a%3!=2?0:$a%3==2?c(($a+1)/3):1)}while($#b<$_){$i++;@b=(@b,$i)if c$i}say$b[$_-1];

Ungolfed:

my @array = ();
my $n = <>;
sub chk {
    my $a = shift;
    return 1 if ($a == 1);
    if ($a % 2 == 0) {
        if ($a % 3 != 2) {
            return 0;
        } else {
            return chk(($a + 1) / 3);
        }
    } else {
        if (chk(($a - 1) / 2) == 0) {
            if ($a % 3 != 2) {
                return 0;
            } else {
                return chk(($a + 1) / 3);
            }
        } else {
            return 1
        }
    }
}
my $i = 1;
while ($#array < $n-1) {
    push(@array,$i) if (chk($i) == 1);
    $i++;
}
print $array[$n];

I can probably do better if I thought more about it, but this is what I came up with after just a few minutes. My first time golfing, so this was pretty fun!

Thanks to @Dada and @TùxCräftîñg (and a bunch of minor byte-optimizations) for -40 bytes

Answer 22

JavaScript (ES6), 58

n=>(a=>{for(;n;)a[++i]?a[i-~i]=a[3*i-1]=--n:0})([i=0,1])|i

Less golfed

n=>{
  a=[];
  a[1] = 1;
  for(i = 0; n;)
  {
    ++i
    if (a[i])
    {
      a[2*i+1] = 1;
      a[3*i-1] = 1;
      --n;
    }
  }
  return i
}

Test

About time and memory: element 500000 in ~20 sec and 300MB used by my FireFox 64 bit alpha

F=
n=>(a=>{for(;n;)a[++i]?a[i-~i]=a[3*i-1]=--n:0})([i=0,1])|i

function test() {
  var n=+I.value, t0=+new Date
  O.textContent = F(n)
  console.log((+new Date-t0)/1000,'sec')
}  

test()

#I { width:5em}

<input id=I type=number value=10 oninput="test()"> 
<span id=O></span>