5
\$\begingroup\$

This question already has an answer here:

One of the Klarner-Rado sequences is defined as follows:

  • the first term is \$1\$
  • for all subsequent terms, the following rule applies: if \$x\$ is present, so are \$2x+1\$ and \$3x+1\$
  • the sequence is strictly increasing

This is A002977.

The first few terms are:

1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...

(\$3\$ is present because it's \$2\times1+1\$, \$4\$ is present because it's \$3\times1+1\$, \$7\$ is present because it's \$2\times3+1\$, etc.)

Your task

Given \$n\$, you must return the \$n\$th element of the sequence. You may use either 0-based or 1-based indexing. (Please specify your choice in your answer.)

0-indexed example:

input = 10
output = 22

Let's see who can get less bytes...

Also featured on codewars

\$\endgroup\$

marked as duplicate by Grimmy, caird coinheringaahing, Luis Mendo, Wheat Wizard, Jonathan Allan code-golf Oct 11 at 20:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ Why is this tagged [javascript]? Is this restricted to it? How is this related to array manipulation and linear algebra? Does "ordered with <" mean "ascending"? \$\endgroup\$ – my pronoun is monicareinstate Oct 11 at 11:46
  • 5
    \$\begingroup\$ @user89702 It's not yours, so you can't post it, especially without any attribution. \$\endgroup\$ – my pronoun is monicareinstate Oct 11 at 12:30
  • 2
    \$\begingroup\$ However, I do believe this is a rather interesting challenge that would be worth rephrasing properly for Code Golf. There's nothing wrong on posting a challenge about this sequence (which is A002977, btw), but you can't copy from an external site without any authorization or credits. \$\endgroup\$ – Arnauld Oct 11 at 12:38
  • 1
    \$\begingroup\$ I've rephrased your post so that it better fits our standard and is not a copy of codewars anymore. Feel free to edit further if needed. \$\endgroup\$ – Arnauld Oct 11 at 13:36
  • 2
    \$\begingroup\$ @Graham, if you've taken the time to work up a solution then absolutely post it to the dupe target. If your solution cannot be trivially modified to fit the dupe target then you have a case to reopen this one and you should cast your vote accordingly. \$\endgroup\$ – Shaggy Oct 12 at 0:38
3
\$\begingroup\$

05AB1E, 15 14 bytes

$FDx>DŠ+)˜ê}sè

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Times out for me on TIO for inputs of 14 and above \$\endgroup\$ – Graham Oct 11 at 16:29
  • \$\begingroup\$ @Graham Well this is code golf, not fastest code, so that’s not an issue. \$\endgroup\$ – Grimmy Oct 11 at 17:18
  • \$\begingroup\$ @Graham, for the purposes of code golf, we may assume infinite memory & time. \$\endgroup\$ – Shaggy Oct 11 at 18:28
  • \$\begingroup\$ @Grimy Thanks to you and Shaggy for this information which I had not appreciated. All solutions I have offered in the past have worked efficiently within the capabilities of my machine. This opens up some wacky impractical solutions ;) \$\endgroup\$ – Graham Oct 11 at 18:40
2
\$\begingroup\$

JavaScript (ES6),  53  50 bytes

1-indexed.

n=>(g=k=>n?g(g[k]|!k++?g[n--,k*2]=g[k*3]=k:k):k)``

Try it online!

Commented

Note: On the first iteration, we have k = [''], which is zero-ish but truthy. By doing !k++, we force k to be coerced to \$0\$ right away (and not just before it's incremented), which makes the test work as expected.

n => (                    // n = requested index
  g = k =>                // h is a recursive function taking k, starting at 0
    n ?                   // if n is not equal to 0:
      g(                  //   do a recursive call:
        g[k] |            //     if g[k] is defined
        !k++ ?            //     or k = 0 (increment k after the test):
          g[n--, k * 2] = //       decrement n; set g[k * 2]
          g[k * 3] = k    //       and g[k * 3] and pass k
        :                 //     else:
          k               //       just pass k
      )                   //   end of recursive call
    :                     // else:
      k                   //   stop recursion and return k
)``                       // initial call to g with k = [''] (zero-ish)

JavaScript (ES6), 65 bytes

I thought the '11'[k/x-2] trick was neat, but overall this initial approach is far too long.

0-indexed.

n=>(g=k=>a[n]||g(-~k,a.some(x=>'11'[k/x-2])&&a.push(k+1)))(a=[1])

Try it online!

Commented

n => (                  // n = requested index
  g = k =>              // g is a recursive function taking k (starting at 1)
    a[n] ||             // if a[n] is defined, return it and stop
    g(                  // otherwise, do a recursive call:
      -~k,              //   with k + 1
      a.some(x =>       //   if there exists some x in a[]
        '11'[k / x - 2] //   such that k / x is either 2 or 3 ...
      )                 //
      && a.push(k + 1)  //   ... then push k + 1 in a[]
    )                   // end of recursive call
)(a = [1])              // initial call to g with k = a = [1]
\$\endgroup\$
1
\$\begingroup\$

R, 57 bytes

n=scan();for(i in 1:n)T=sort(unique(c(T,T%o%2:3+1)));T[n]

Try it online!

1-based index.

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

APL+WIN, 54 bytes

Index origin 1

Prompts for the index of required value. Given the response that I received from Grimy and Shaggy that I can assume infinite memory and time then it is trivial to modify this function to work with a series up to the limit of your machine by increasing the value 20 in the function below. This version is limited to index position 1901981

m←1⋄(⍎∊20⍴⊂'m←(0≠1,-2-/m)/m←m[⍋m←m,∊1+mר⊂2 3]⋄')⋄m[⎕]

For some reason this function will not run on Dyalog Classic in TIO which is what I usually use.

On my machine 1 => 1, 11 => 22 and 61 => 237 (checked on http://oeis.org)

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

JavaScript (ES6), 99 bytes

x=>eval("a=[i=1],a.b=a.includes;while(i++,c=i-1,x)a.b(i)||!a.b(c/2)&&!a.b(c/3)||(a.push(i),x--);c")
\$\endgroup\$
0
\$\begingroup\$

Python 3, 73 bytes

f=lambda n,i=0,k=[1]:(i==n)*k[i]or f(n,i+1,sorted(k+[2*k[i]+1,3*k[i]+1]))

Try it online!

\$\endgroup\$

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