29
\$\begingroup\$

We start with a blank 1-indexed sequence:

_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,...

In the nth step, we fill in every a(n) blanks with the integers greater than 1 starting at the first remaining blank, where a(n) is the nth entry in the sequence.

After the first step:

2,_,3,_,4,_,5,_,6,_,7,_,8,_,9,_,10,_,11,_,12,_,13,_,...

Note that a(1) has to be 2 because the first integer greater than 1 is 2.

In the second step, we fill in every a(2) blanks. It will be apparent that a(2) must be 2.

2,2,3,_,4,3,5,_,6,4,7,_,8,5,9,_,10,6,11,_,12,7,13,_,...

In the third step, we fill in every a(3) blanks. From the sequence, a(3) = 3.

2,2,3,2,4,3,5,_,6,4,7,_,8,5,9,3,10,6,11,_,12,7,13,_,...

In the fourth step, we fill in every a(4) blanks. From the sequence, a(4) = 2.

2,2,3,2,4,3,5,2,6,4,7,_,8,5,9,3,10,6,11,3,12,7,13,_,...

Eventually:

2,2,3,2,4,3,5,2,6,4,7,2,8,5,9,3,10,6,11,3,12,7,13,2,...

Task

Given n, return the nth element of the sequence.

The first 10,000,000 terms of the sequence can be found here.

This is . Shortest answer in bytes wins. Standard loopholes apply.

\$\endgroup\$
8
  • \$\begingroup\$ @LuisMendo Thanks, I've added it. \$\endgroup\$ – Leaky Nun Jun 20 '17 at 9:13
  • \$\begingroup\$ Just curious, what wrong did mr.One to be excluded from sequence? \$\endgroup\$ – Dead Possum Jun 20 '17 at 9:59
  • \$\begingroup\$ @DeadPossum well, if you fill in every one blank, then you're done in one step. \$\endgroup\$ – Leaky Nun Jun 20 '17 at 10:06
  • 3
    \$\begingroup\$ @DeadPossum If a(n) is 1, then the n-th step will fill in every remaining blank, terminating the generation. \$\endgroup\$ – Leaky Nun Jun 20 '17 at 10:11
  • 1
    \$\begingroup\$ @QBrute I provided a list of the first 10,000,000 linked in the question; just plot them. \$\endgroup\$ – Leaky Nun Jun 20 '17 at 14:58
26
\$\begingroup\$

Haskell, 80 67 bytes

g~(a:b)|let k!l=k:take(a-1)l++(k+1)!drop(a-1)l=2!g b
m=g m
(!!)$0:m

Try it online!

Haskell is the perfect language for defining an infinite list in terms of itself.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Given that the TIO link works as expected, I guess my question should in stead be: Could you add an explanation of how this works? \$\endgroup\$ – Julian Wolf Jun 20 '17 at 17:17
  • 2
    \$\begingroup\$ @JulianWolf It sounds like you are unfamiliar with let pattern guards. pattern1 | let pattern2 = expr2 = expr1 means the same thing as pattern1 = let pattern2 = expr2 in expr1 (for the same reason that [expr1 | let pattern2 = expr2] means the same thing as [let pattern2 = expr2 in expr1]). \$\endgroup\$ – Anders Kaseorg Jun 20 '17 at 18:02
  • 1
    \$\begingroup\$ I've got to remember let pattern guards (especially that they can do functions)! Also, m=2:2:2`drop`g m is a byte shorter. \$\endgroup\$ – Ørjan Johansen Jun 20 '17 at 18:35
  • 1
    \$\begingroup\$ (!!)$0:m is two bytes shorter. \$\endgroup\$ – Ørjan Johansen Jun 20 '17 at 18:43
  • 1
    \$\begingroup\$ Actually, you can drop the 2:2: stuff entirely with a bit more laziness: g ~(a:b)|... and m=g m. \$\endgroup\$ – Ørjan Johansen Jun 20 '17 at 18:50
11
\$\begingroup\$

C, 123 bytes

f(n){int*p=calloc(n,4),i=0,j,k;for(*p=p[1]=2;i<n;++i)for(j=0,k=i/2?0:2-i;j<n;++j)p[j]||k++%p[i]||(p[j]=k/p[i]+2);n=p[n-1];}

Try it online!

Walkthrough

f(n){int*p=calloc(n,4),

Allocate an array of n integers to store the first n elements of the sequence. This hardcodes sizeof(int) as 4, which is a safe assumption in most cases and certainly one I'm willing to make in the context of code golf. :)

i=0,j,k;

These are all counters: i for the index of the step we're on, j to loop through the sequence looking for empty spaces, and k to count how many empty spaces have been seen.

for(*p=p[1]=2;i<n;++i)

Before we start our main loop, we sneak in an initialization of the first two elements of the sequence to 2. (p[0] = *(p + 0) = *p.) This throws off the count for k, though, but...

for(j=0,k=i/2?0:2-i;j<n;++j)

... we also do a sneaky initialization of k, which tests to see if i is less than 2 and corrects the starting value of k if so. The inner loop also starts here, which iterates over the entire sequence-so-far during each step.

p[j]||k++%p[i]||(p[j]=k/p[i]+2);

This line could really use some explaining. We can expand this to:

if (!(p[j] || ((k++) % p[i]))) {
    p[j] = k / p[i] + 2;
}

by short circuiting, and then by De Morgan's laws and the fact that 0 is falsy in C:

if (p[j] == 0 && ((k++) % p[i]) == 0) {
    p[j] = k / p[i] + 2;
}

This essentially states: "if this space is empty, increment k. And if k was previously a multiple of the step size, run the following statement." Hence, we run the statement on every step size elements, which is exactly how the sequence is described. The statement itself is simple; all it does is generate 2, 3, 4, ....

n=p[n-1];}

Using the tricky-return-without-a-return that works with gcc, we "return" the last element of the first n terms in the sequence, which happens to be the nth term.

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

Pyth, 29 bytes

M?tH?eJ.DtHg1GghG-tHhJ+2hJ2g1

Try it online

How it works

Instead of fooling around with lists, this uses a plain recursive formula.

M                                def g(G, H):
 ?tH                                 if H - 1:
      J.DtHg1G                           J = divmod(H - 1, g(1, G))
    ?e                                   if J[-1]:
              ghG-tHhJ                       return g(G + 1, H - 1 - J[0])
                                         else:
                      +2hJ                   return 2 + J[0]
                                     else:
                          2              return 2
                           g1Q   print(g(1, eval(input())))
\$\endgroup\$
3
\$\begingroup\$

Haskell, 67 bytes

0%j=2
i%j|d<-div i$f j=last$d+2:[(i-d-1)%(j+1)|d*f j<i]
f=(%1).pred

Try it online!

A recursive arithmetical solution that turned out basically the same method as Anders Kaseorg's Pyth answer.

This code is covered in warts -- ugly parts that look like they could be golfed away, but I didn't see how.

The function i%j really wants to use a guard to check whether mod i(f j)>0 and evaluate one of corresponding two expression. But, both expressions use div i(f j). Binding that in a guard won't make it apply to both sides. As far as I know, a guard can't be made to "distribute" over other guards. let and where are too long. So, the code uses last to pick one of two expressions while the guard binds the variable. Ugh.

Ideally we'd use divMod because both the div and mod are used, but (d,m)<-divMod ... is a long expression. We instead hackily check of the mod is nonzero by seeing if the div value times the divisor falls short of the original value.

The 0%j=2 case would not be needed if Haskell short-circuited div 0, which it doesn't. The .pred converts the 1-indexed input to zero-indexed, or else there would be -1 corrections everywhere.

\$\endgroup\$
4
  • \$\begingroup\$ If you turn % 1-indexed, then you need five bytes correction - which just ties. However, you can then inline f into % at no cost, and then f becomes anonymous so you save two bytes overall. \$\endgroup\$ – Ørjan Johansen Jun 21 '17 at 0:29
  • \$\begingroup\$ @ØrjanJohansen What do you mean here by inline? I don't see how to change the references to f without losing bytes. \$\endgroup\$ – xnor Jun 21 '17 at 0:48
  • \$\begingroup\$ divMod seems to be one byte cheaper, because it allows branching with !!(0^m). So far I've got: 1%j=2;i%j|(d,m)<-divMod(i-1)$j%1=[(i-d-1)%(j+1),d+2]!!(0^m);(%1) \$\endgroup\$ – Ørjan Johansen Jun 21 '17 at 0:53
  • \$\begingroup\$ As you see, the inlining presupposes the 1-reindexing, which removes the .pred. \$\endgroup\$ – Ørjan Johansen Jun 21 '17 at 0:58
3
\$\begingroup\$

Husk, 20 16 bytes

!ƒψΣz`:tNΘC←←¹²t

Try it online!

A golfed port of the mind-bending Haskell answer by Anders Kaseorg

Explanation

This answer builds this meta list with a self-referential process.

Let's get a few things out of the way before we can look at how the list is actually built: ! simply takes an item from the list, since the challenge asks to return the element at a given list. ƒ is the fixpoint operator, it takes a function and applies the function to itself ad infinity, i.e. ƒg = g(g(g(g(g(g(...; this is what allows us to define the list in terms of the list itself. ψ is a way to write a recursive function in Husk: the following commands define a function of one argument where (or ¹) marks the argument, and ² marks the function itself.

The inner code (with implicit parameters made explicit) is this:

Σz`:tNΘC←←⁰²t⁰    Takes an infinite list as input, returns an infinite list
           ²      Apply the function recursively
            t⁰      to the tail of the list
         ←⁰       then take the head of the input list
        ←          -1
       C          and cut the resulting list in groups of that length
      Θ           Prepend an empty group
 z           For each group
  `:          append
    tN        a natural number (starting from 2)
Σ            Then concatenate all groups together

What this function does is taking the current a(n) and the list of values that are marked as blanks in step n, and add 2,3,4,5... at the right locations between those "blanks".

It would be shorter (and more natural) to prepend a number to each group (each value 2,3,4... goes at the beginning of the group of a(n) blanks, after all), but to do that we wouldn't be able to generate the first element of the list until we generate the first group of blanks, and since this definition is self-referential we couldn't generate the first element of the first group of blanks until we generate the first group of blanks after that, and so on forever. By adding an empty group at the beginning and putting values at the end of groups instead, we can generate the initial 2 without having to look at the rest of the list, and this is enough to kickstart the whole process that will generate the infinite list recursively.

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

JavaScript (ES6),  98 93 91 87 bytes

Saved 4 bytes thanks to @l4m2

A recursive function that stops as soon as the result is available.

f=(n,p,a=[])=>a[n-1]++||f(n,-~p,[...a].map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%k?c:++v:(i=1,v=2),i=0,k=a[p]||2)) should work for 92 bytes. Call it with f(n)(). \$\endgroup\$ – Shaggy Jun 20 '17 at 10:39
  • \$\begingroup\$ f=(n,p,a=[])=>a[n-1]++||f(n,-~p,[...a].map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0)) \$\endgroup\$ – l4m2 Mar 17 at 7:44
1
\$\begingroup\$

Java 8, 124 bytes

(i)->{int j=1,a[]=new int[i+1],k,s,n;for(;a[i]<2;){for(k=0,n=2;a[++k]>0;);for(s=a[j++]|2*k;k<=i;k+=s)a[k]=n++;}return a[i];}

Lambda expression.

Creates an integer array and continually populates it until the nth value gets populated.

Pre-declaring variables at the top to cut down on as many declarations as possible as each int costs 4 bytes of space as opposed to adding ,n which is 2.

On the j'th iteration of calculation, the number of 'blanks' one has to skip is equal to a[j] (or 2, if blank). It works out that if the first blank space we have to fill in is at position k, k * a[j] gives us the 'step' (s).

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

C (gcc), 104 bytes

j;k;f(n){int*p=calloc(n,4)-4,i=1,y;for(;j=k=p[n],!j;++i)for(y=p[i]?:2;j++<n;)p[j]||k++%y||(p[j]=k/y+2);}

Try it online!

Trying to golf the last C solution but it's just too hard to understand

f(n){
    int*p=calloc(n,4)-4,i=0,j,k,y;         // p as Array[1..n]
    for(;j=k=p[n],!j;++i)                  // Once p[n] is filled we're over
                                           // and that's what we want
                                           // Otherwise j and k are inited to 0
        for(;j++<n;) p[j]||                // For zeros
            k++%(y=p[i]?:2)||(p[j]=k/y+2); // On correct time fill them
}
\$\endgroup\$
1
\$\begingroup\$

Stax, 23 bytes

ü→è«wε⌠╒└I◄►¼═Öà=╬à╞⌐-Ω

Run and debug it

A direct implementation of the procedure.

Uses zeroes as placeholders till the array is fully filed, and take the last element.

Explanation

z({c:0ni@i1>s2?::{i^^&F}x*H Input: x
z                           empty list
 (                          pad with x zeroes (call this S)
  {                    }x*  perform the following x times:
   c:0                      get the falsy indices
         i1>  ?             if iteration index >1 :
      ni@                   get nth element of S
            2               else push 2
               ::           get every nth element of the falsy indices
                 {    F     for each index:
                  i^^&      replace with iteration index + 2
\$\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.