27
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ You should add larger test cases. \$\endgroup\$ – mbomb007 Jul 14 '16 at 14:14
  • 6
    \$\begingroup\$ Can you explain this a little more clearly? I'm a native English speaker and I have no idea what "... and if x is in a then 2x+1 and 3x-1 are in a." is supposed to mean. \$\endgroup\$ – cat Jul 14 '16 at 16:13
  • 1
    \$\begingroup\$ @cat x ϵ A → (2*x) + 1 ϵ A and x ϵ A → (3*x)-1 ϵ A, where ϵ means "is a member of" and can be understood as "implies". \$\endgroup\$ – Steven H. Jul 14 '16 at 16:35
  • 2
    \$\begingroup\$ Implied condition: The sequence does not contain numbers not required by the other rules. (Otherwise $a(i)=i$ would be a valid sequence) \$\endgroup\$ – Stig Hemmer Jul 15 '16 at 7:05
  • 1
    \$\begingroup\$ And you get free Mathematica and Haskell answers to start from :) \$\endgroup\$ – OrangeDog Jul 15 '16 at 12:44

22 Answers 22

9
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ That may be 16 characters, but I don't know of any encoding that represents that in less than 30 bytes. \$\endgroup\$ – rich remer Jul 14 '16 at 22:01
  • 18
    \$\begingroup\$ Jelly has it's own codepage which allows for these characters being 1 byte each. \$\endgroup\$ – mid Jul 14 '16 at 22:09
15
\$\begingroup\$

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

\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ That doesn't really define a function or a valid code snippet, does it? \$\endgroup\$ – Zeta Jul 15 '16 at 7:30
  • \$\begingroup\$ @Zeta The last line evaluates to an unnamed function. \$\endgroup\$ – Zgarb Jul 15 '16 at 8:51
  • \$\begingroup\$ @Zgarb Which is an error in a Haskell file, and no interpreter I'm aware off supports this kind of feature. So, please, enlighten me, how is a user supposed to use this without modifying the code above in any way? Or could you point me to a meta post that allows this kind of code? \$\endgroup\$ – Zeta Jul 15 '16 at 10:15
  • 2
    \$\begingroup\$ @Zgarb I think for the last line, assign it to a binding (like f=filter t[1..]!!), because I don't think this is correct. \$\endgroup\$ – TuxCopter Jul 15 '16 at 10:52
  • 1
    \$\begingroup\$ @TùxCräftîñg On this Meta post, it was determined that additional helper functions are acceptable by default in this situation. This is also the format that I usually see for Haskell answers here. Of course, you as the challenge author have the final authority. \$\endgroup\$ – Zgarb Jul 15 '16 at 10:57
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "One does not simply outgolf Dennis"... I wish I'd thought of using set literals. It seems so obvious now. Is this answer even faster than my "fast" program if you change from executing a string to actual code? \$\endgroup\$ – mbomb007 Jul 14 '16 at 18:27
  • \$\begingroup\$ Nope. It's slower. Set operations are more expensive. \$\endgroup\$ – mbomb007 Jul 14 '16 at 18:37
  • \$\begingroup\$ Yeah, min is O(n) while list indexing is O(1), so this solution is at least O(n²)... \$\endgroup\$ – Dennis Jul 15 '16 at 16:37
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Why not y instead of xs to save two bytes? Also, I believe that you may be able to cut down the last line to something like (!!)$nub.f[1] \$\endgroup\$ – Michael Klein Jul 15 '16 at 7:02
  • \$\begingroup\$ @MichaelKlein: I'm just too used to (x:xs), completely forgot that, thanks. \$\endgroup\$ – Zeta Jul 15 '16 at 7:29
6
\$\begingroup\$

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.

\$\endgroup\$
  • 13
    \$\begingroup\$ You're a pro at turning something simple into something unreadable. \$\endgroup\$ – mbomb007 Jul 14 '16 at 14:58
6
\$\begingroup\$

Pyth, 20 19 bytes

hutS{+G,hyhGt*3hGQ0

Try it online. Test suite.

Uses zero-based indexing.

\$\endgroup\$
  • 1
    \$\begingroup\$ @Jakube Thanks. I wonder how I didn't figure that out when I tried just 1 and it obviously didn't work. \$\endgroup\$ – PurkkaKoodari Jul 15 '16 at 20:32
4
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ @LuisMendo Thanks for the tip! How would you rewrite this with a while loop instead of the for loop? (Maybe that would be a better question for the MATL chat room) \$\endgroup\$ – DJMcMayhem Jul 14 '16 at 15:15
  • \$\begingroup\$ It could be done this way: 1`tEQy3*qvuStnG<]G). The loop condition is tnG< (exit when the array already has the required size) \$\endgroup\$ – Luis Mendo Jul 14 '16 at 15:36
  • \$\begingroup\$ Not sure how much cheating it is, but in the for-loop version you can take the input in unary as a string and remove the : \$\endgroup\$ – Luis Mendo Jul 14 '16 at 15:41
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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

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.

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Slightly shorter (97) using set and initializer lists: [](int i){int t;set<int>k{1};for(;i--;k.erase(t))t=*k.begin(),k.insert({t*2+1,t*3-1});return t;};. \$\endgroup\$ – nwn Jul 15 '16 at 14:35
3
\$\begingroup\$

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

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 22: 1ari{(_2*)\3*(@||$}*0= (Also a lot more efficient.) \$\endgroup\$ – Martin Ender Jul 15 '16 at 6:41
2
\$\begingroup\$

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

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]
}
\$\endgroup\$
  • 1
    \$\begingroup\$ That *1 trick is neat \$\endgroup\$ – TuxCopter Oct 20 '16 at 18:05
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You can remove the final ;end \$\endgroup\$ – Luis Mendo Jul 16 '16 at 16:22
  • \$\begingroup\$ On the version I use, at least (4.0.0) you cannot... \$\endgroup\$ – dcsohl Jul 18 '16 at 14:39
1
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you can drop the spaces after the mys, the return and the print (Can't test, don't have perl) \$\endgroup\$ – TuxCopter Oct 18 '16 at 21:39
  • 1
    \$\begingroup\$ @TùxCräftîñg is right about the return. The print can be replace by a say. Most of the my aren't needed (you need only the one before $a in the function I think. Don't initialize nor declare @b. You can probably drop the initialisation of $i if you do $i++ at the start of the while instead of at the end. pop is shorter than shift. Keep in mind than there is much more to perl golfing than just removing whitespaces and newlines... \$\endgroup\$ – Dada Oct 20 '16 at 7:32
0
\$\begingroup\$

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

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>

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