19
\$\begingroup\$

We are searching for a sequence

Take the natural numbers
1,2,3,4,5,6,7,8,9,10,11,12,13,14...

Convert to base-2
1,10,11,100,101,110,111,1000,1001,1010,1011,1100,1101,1110...

Concatenate the above numbers
110111001011101111000100110101011110011011110...

Partition this number in Prime-Chunks
(chunks containing a prime number of digits)
Primes are taken in asceding order 2,3,5,7,11,13,17...

[11][011][10010][1110111][10001001101][0101111001101][1110...]

and find the Sum of the digits of each chunk

Primes 2 3 5 7 11 13 17
Chunks [11][011][10010][1110111][10001001101][0101111001101][1110...]
SumOfDigits 2 2 2 6 5 8

The Sequence

2, 2, 2, 6, 5, 8, 9, 10, 14, 22, 11, 18, 25, 27, 32, 21, 28, 32, 40, 40, 49, 49, 32, 41, 49, 53, 63, 55, 63, 70, 87, 73, 51, 63, 71, 78, 78, 90, 107, 86, 96, 108, 115, 128, 138, 92, 83, 95, 102, 110, 130, 106, 122, 141, 149, 163, 130, 140, 151, 165, 181, 165, 204, 200, 234, 100, 130, 138, 167, 149, 169, 180, 209, 166, 189, 194, 222, 205, 234, 260, 216, 206, 217, 241, 240, 267, 289, 242, 274, 308, 286, 329, 338, 155, 189, 225, 197, 240, 272, 217, 254, 282, 287, 317, 281, 256, 299, 286, 331, 337, 316, 350, 354, 391, 367, 282, 327, 313, 364, 358, 348, 397, 406, 466...

The Challenge

Find the nth term of the above sequence

Input

An integer n>0

Test Cases

1->2   
3->2    
6->8    
36->78 
60->165    
160->581     
260->1099    
350->1345

This is .Shortest answer in bytes wins!

\$\endgroup\$
  • 2
    \$\begingroup\$ Related (first three steps are the same) \$\endgroup\$ – Laikoni Oct 21 '17 at 3:57
  • 4
    \$\begingroup\$ Downvoted because this feels too much like a bunch of challenges mashed together. \$\endgroup\$ – Esolanging Fruit Oct 22 '17 at 3:58

14 Answers 14

14
\$\begingroup\$

Husk, 8 bytes

Σ!CİpṁḋN

Try it online!

Explanation

Σ!CİpṁḋN
       N   Start with the infinite list of natural numbers.
     ṁḋ    Convert each to its binary representation and join them all together. (A)
   İp      Get the infinite list of primes. (B)
  C        Split (A) into chunks of lengths (B).
 !         Retrieve the nth chunk (where n is the input).
Σ          Sum the bits in this chunk.
\$\endgroup\$
6
\$\begingroup\$

Jelly, 12 bytes

RÆNµSRBFṁRṪS

Try it online!

How it works

RÆNµSRBFṁRṪS  Main link. Argument: n

R             Range; yield [1, ..., n].
 ÆN           N-th prime; yield P := [p(1), ..., p(n)].
   µ          Begin a new, monadic chain with argument P.
    S         Take the sum of P, yielding s := p(1) + ... + p(n).
     R        Range; yield [1, ..., s].
      B       Binary; convert all integers from 1 to s to base 2.
       F      Flatten the resulting array.
         R    Range; yield [[1, ..., p(1)], ..., [1, ..., p(n)]].
        ṁ     Mold; reshape the result to the left like the result to the right.
          Ṫ   Tail; take the last chunk.
           S  Take the sum, counting the set digits.
\$\endgroup\$
5
\$\begingroup\$

05AB1E, 12 bytes

Code

Can get pretty slow for large numbers:

ÅpDOLbJs£`SO

Uses the 05AB1E-encoding. Try it online!

Explanation

Åp              # Get a list of the first <input> primes
  DO            # Duplicate and sum the primes
    L           # Create the list [1, .., <sum>]
     bJ         # Convert to binary and join into a single string
       s£       # Get the slices [a[0:2], a[2:2+3], a[2+3:2+3+5], a[2+3+5:2+3+5+7], ...] 
                  corresponding to the list of primes
         `SO    # Get the last one and sum up it's digits
\$\endgroup\$
4
\$\begingroup\$

Mathematica, 71 bytes

(Tr/@TakeList[Join@@IntegerDigits[Range[#^2+1],2],Prime~Array~#])[[#]]&   

Try it online!

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

Jelly, 21 bytes

RÆNSRBF
RÆN+\‘ṬœṗÇ⁸ịS

Try it online!

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

Jelly, 16 bytes

RBFṁ
RÆNSÇṫÆNC$S

Try it online!

Explanation

RBFṁ  Helper link. Input: integer k
R     Range, [1, 2, ..., k]
 B    Convert each to a list of its binary digits
  F   Flatten
   ṁ  Shape it to length k

RÆNSÇṫÆNC$S  Main link. Input: integer n
R            Range, [1, 2, ..., n]
 ÆN          Get i'th prime for each
   S         Sum
    Ç        Call helper link
         $   Monadic chain
      ÆN       Get n'th prime
        C      Complement, 1 - n'th prime
     ṫ       Tail, take the last n'th prime digits
          S  Sum
\$\endgroup\$
2
\$\begingroup\$

R, 206 200 bytes

function(n){a=p=j=y=2
for(i in 2:n-1){while(sum(y)<4*a){x=as.double(rev(intToBits(j)))
y=c(y,x[cumsum(x)>0])
j=j+1}
b=1:a
y=y[-b]
z=outer(k<-b+a,p,'%%')
p=c(a<-k[!apply(z<1,1,sum)][1],p)}
sum(y[1:a])}

Try it online!

The algorithm tries also to "save" on space by iteratively removing bits as it cycles through the primes. I feel that the decimal to bit conversion could probably be shorter, but I could not figure out other alternatives.

Saved 6 bytes thanks to Jonathan French.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think R supports chained assignment; p=j=2 is two bytes shorter than p=2;j=2. \$\endgroup\$ – Jonathan Frech Oct 20 '17 at 23:04
  • \$\begingroup\$ ...which can probably also be done for a=p, saving yet another two bytes. \$\endgroup\$ – Jonathan Frech Oct 20 '17 at 23:05
  • 1
    \$\begingroup\$ ...and -- I do not know why -- it also seems to work for y=1, replaced with y=2, resulting in 200 bytes. \$\endgroup\$ – Jonathan Frech Oct 20 '17 at 23:08
  • \$\begingroup\$ Thank you. The y=2 replaces the bit for numeral 1. It works because for n>1, it is pruned away at the first iteration, and for n=1, the for loop loops backward, thus providing the answer for n=3, which is still 2 (not that bad of a luck). \$\endgroup\$ – NofP Oct 21 '17 at 0:19
2
\$\begingroup\$

JavaScript (ES6), 144 bytes

n=>eval("s=o=j=0;for(i=p=1;n;d>p&&(n--,s+=p))for(p++,d=2;p%d++;);while(b=Math.log2(++j)+1|0,i<=s)for(x=0;x++<b&i<=s;)o+=i++>s-p&&j<<x&1<<b?1:0")

Ungolfed

n=>{
    s=o=j=0;
    for(i=p=1;n;d>p&&(n--,s+=p))
        for(p++,d=2;p%d++;);
    while(b=Math.log2(++j)+1|0,i<=s)
        for(x=0;x++<b&i<=s;)
            o+=i++>s-p&&j<<x&1<<b?1:0
    return o
}

Test Cases

f=
n=>eval("s=o=j=0;for(i=p=1;n;d>p&&(n--,s+=p))for(p++,d=2;p%d++;);while(b=Math.log2(++j)+1|0,i<=s)for(x=0;x++<b&i<=s;)o+=i++>s-p&&j<<x&1<<b?1:0")

;[1,3,6,36,60,160,260,350].forEach(t=>console.log(t,"->",f(t)))
.as-console-wrapper{max-height:100%!important}

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

Python 2, 114 bytes

n=input();k=m=1;p=[0];s=''
exec's+=bin(k)[2:];p+=m%k*[k+p[-1]];m*=k*k;k+=1;'*n*n*2
print s[p[n-1]:p[n]].count('1')

Try it online!

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

JavaScript (ES6), 138 132 123 bytes

N=>(n=k=1,g=s=>N?g((P=n=>n%--x?P(n):x<2)(x=++n)?s[n]?s.slice(--N&&n,n/!N):s+(n--,k++).toString(2):s):s.split`1`.length-1)``

Test cases

Try it online!

Demo

NB: Only 'safe' test cases are included here (guaranteed to work on Chrome, Firefox and Edge). You may have to increase the call stack size of your engine to pass the other ones.

let f =

N=>(n=k=1,g=s=>N?g((P=n=>n%--x?P(n):x<2)(x=++n)?s[n]?s.slice(--N&&n,n/!N):s+(n--,k++).toString(2):s):s.split`1`.length-1)``

console.log(f(1))   // 2
console.log(f(3))   // 2
console.log(f(6))   // 8
console.log(f(36))  // 78
console.log(f(60))  // 165

Formatted and commented

N => (                            // given N = index of the expected term
  n = k = 1,                      // n = current prime, k = current natural number
  g = s =>                        // g = recursive function taking s = binary string
    N ?                           //   if we haven't reached the correct chunk yet:
      g(                          //     do a recursive call to g():
        (P = n =>                 //       P() returns: true for prime
          n % --x ? P(n) : x < 2) //                    false for composite
        (x = ++n) ?               //       increment n; if n is prime:
          s[n] ?                  //         if s is long enough:
            s.slice(--N && n,     //           either remove this chunk (if N > 0)
                    n / !N)       //           or truncate it to the correct size (if N = 0)
          :                       //         else:
            s + (n--, k++)        //           append the next natural number to s
                .toString(2)      //           in binary format
        :                         //       else:
          s                       //         just look for the next prime
      )                           //     end of recursive call
    :                             //   else:
      s.split`1`.length - 1       //     return the number of 1's in the last chunk
)``                               // initial call to g() with an empty string
\$\endgroup\$
1
\$\begingroup\$

Perl 6, 67 bytes

{(1..*).map(|*.base(2).comb).rotor(grep *.is-prime,2..*)[$_-1].sum}

Test it

Expanded:

{  # bare block lambda with implicit parameter 「$_」

  (

    1 .. *                # Range of all numbers starting with 1

  ).map(

    # WhateverCode lambda
    |                     # Slip each of these values into the outer list individually
      *                   # this is the parameter
      .base(2)            # convert base
      .comb               # split into digits


  ).rotor(                # split into chunks

    grep *.is-prime, 2..* # the sequence of prime numbers


  )[ $_ - 1]              # index into it using 1 based indexing

  .sum                    # find the sum
}
\$\endgroup\$
1
\$\begingroup\$

Python 2, 143 139 133 bytes

-4 bytes thanks to @ErikTheOutgolfer

s='1';i=x=1
exec"s=s[i:];i+=1\nwhile~-all(i%x for x in range(2,i)):i+=1\nexec's+=bin(x)[2:];x+=1;'*i;"*input()
print s[:i].count('1')

Try it online!

\$\endgroup\$
  • \$\begingroup\$ -2 bytes by removing incompatible test harness. Another -2 by rearranging some stuff. \$\endgroup\$ – Erik the Outgolfer Oct 21 '17 at 6:52
  • \$\begingroup\$ @EriktheOutgolfer thanks a lot. I was still able to add my old tests back. \$\endgroup\$ – ovs Oct 21 '17 at 7:07
1
\$\begingroup\$

J, 48 bytes

([:+/-@{:{.+/{.[:}:[:(#:@[,])/1+[:i.1++/)@:p:@i.

explained

(                                                         )@:p:@i.  the first n primes, passed to...
       -@{: {.                    ...                               take "nth prime" elements from the tail of...
               +/                                                   sum the first n primes and...
                  {.                                                take that number of elements from...
                     [: }:                                          all but the last element of...   <----------------<
                                          1 + [: i. 1 + +/          sum first n primes, add 1 (so we have enough      |
                                                                    for case n=1) -- make that many natural numbers   |
                           [: (#:@[ , ])/                           reduce them by turning into lists of binary       |
                                                                    digits and catting, however the rightmost number  |
                                                                    won't get reduced, hence the need for ------------^
([: +/                                                              and sum those digits

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 30 bytes using key (/.): _1({]+//.$$&;<@#:@#\)[:#~p:@i. \$\endgroup\$ – miles Dec 1 '17 at 1:01
  • \$\begingroup\$ super clever. thanks miles. \$\endgroup\$ – Jonah Dec 1 '17 at 6:17
0
\$\begingroup\$

JavaScript 1+ + substr, 135 bytes

for(n=prompt(s=P=0),i=n*n*n*8;--i;)s=i.toString(2)+s;for(p=1;n;e=j?s:--n?P+=p:s.substr(P,p))for(j=p++;p%j--;);eval([].join.call(e,'+'))
\$\endgroup\$
  • \$\begingroup\$ What do you mean by "4?" are you unsure of the version? Expanding on what you mean in the body would help make this post better. \$\endgroup\$ – FryAmTheEggman Nov 30 '17 at 5:45
  • \$\begingroup\$ I know it runs when JS5 didn't come, but not that sure exactly when \$\endgroup\$ – l4m2 Nov 30 '17 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy