25
\$\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\$
  • \$\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
  • 2
    \$\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
20
\$\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\$
  • 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
10
\$\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\$
  • \$\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
2
\$\begingroup\$

JavaScript (ES6), 98 93 91 bytes

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

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

Alternate version, 90 bytes

Suggested by Shaggy for -1 byte

This one must be called with f(n)(). Although the corresponding post in meta currently gives a positive score, this syntax is apparently disputed.

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

Demo

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

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

\$\endgroup\$
  • \$\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\$ @Shaggy Thanks! Added as an alternate version. \$\endgroup\$ – Arnauld Jun 20 '17 at 10:47
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\$

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.