30
\$\begingroup\$

Primes are everywhere...

they hide inside Pi

3.1415926535897932384626433832795028841971693993751

Let's get those primes!

The Challenge

Given as input an integer n>0, find out how many primes are hidden inside the first n digits of Pi

Examples

For n=3 we should search for primes in [3,1,4]. There are 2 Primes (3,31), so your code should output 2
For n=10 , the first 10 digits are [3,1,4,1,5,9,2,6,5,3] and your code should output 12 because [2, 3, 5, 31, 41, 53, 59, 653, 4159, 14159, 314159, 1592653] were hidden (and found!)

Test Cases

input -> output

1->1  
3->2  
13->14  
22->28  
42->60  
50->93

150->197  
250->363  
500->895

Rules

Your code must be able to find all primes at least for n=50
Yes, you can hardcode the first 50 digits of Pi if you like
Entries hardcoding the answers are invalid

This is .Shortest answer in bytes wins!

\$\endgroup\$
  • 6
    \$\begingroup\$ "you can hardcode the first 50 digits of Pi if you like". First problem solved! Now for the golfed primality test on up to 50-digit integers... O_o (This is a nice challenge, but solid math built-ins or libraries are probably required.) \$\endgroup\$ – Arnauld Aug 24 '17 at 23:59
  • 2
    \$\begingroup\$ @totallyhuman That sequence not even in OEIS yet! Time for your claim to fame? \$\endgroup\$ – Sanchises Aug 25 '17 at 7:38
  • 3
    \$\begingroup\$ IMO allowing hardcoding of the first 50 values is detrimental to this challenge. This challenge is basically two parts, 1) try to compress the first 50 values, or 2) actually do the challenge. \$\endgroup\$ – JAD Aug 25 '17 at 8:43
  • 2
    \$\begingroup\$ Usually in these kind of challenges, where calculation becomes harder/slower/memory intensive, it is enough for the program to work theoretically, instead of setting an arbitrary cutoff and allowing hardcoding. \$\endgroup\$ – JAD Aug 25 '17 at 12:10
  • 2
    \$\begingroup\$ @BillSteihn Updating rules after there are several answers is against the spirit of this website. Have you posted this question in the Sandbox? You would have had feedback really early that hardcoded answers would come in. \$\endgroup\$ – Olivier Grégoire Aug 25 '17 at 15:58
20
\$\begingroup\$

05AB1E,  10  8 bytes

-2 bytes thanks to Adnan (p vectorises)

<žsþŒÙpO

Try it online! (will work up to n=98413 but will be very slow even for n=50 due to the need to test such large numbers for primality - TIO times out at 60 seconds for n=50.)

How?

<žsþŒÙpO - implicitly push input, n
<        - decrement = n-1
 žs      - pi to that many decimal places (i.e. to n digits)
   þ     - only the digits (get rid of the decimal point)
    Π   - all sublists
     Ù   - unique values
      p  - is prime? (vectorises) 1 if so, 0 otherwise
       O - sum
         - implicitly print the top of the stack
\$\endgroup\$
  • \$\begingroup\$ <žsþŒÙpO should work for 8 bytes \$\endgroup\$ – Adnan Aug 25 '17 at 0:21
  • \$\begingroup\$ Ah yeah p vectorises thanks! \$\endgroup\$ – Jonathan Allan Aug 25 '17 at 0:22
  • 1
    \$\begingroup\$ Yes! Finally a very short code golf answer that I actually understand! :D \$\endgroup\$ – Fabian Röling Aug 26 '17 at 9:22
11
\$\begingroup\$

Mathematica, 76 bytes

Tr[1^Union@Select[FromDigits/@Subsequences@#&@@RealDigits[Pi,10,#],PrimeQ]]&
\$\endgroup\$
  • \$\begingroup\$ Oh, no fair, I'm not familiar with Mathematica golf. :P (+1) \$\endgroup\$ – totallyhuman Aug 25 '17 at 0:50
  • \$\begingroup\$ @totallyhuman We posted this at the same time. this is so weird! \$\endgroup\$ – J42161217 Aug 25 '17 at 0:52
  • \$\begingroup\$ I golfed my answer using some of the syntactical tricks but I kept the functions I used before. I hope you don't mind. \$\endgroup\$ – totallyhuman Aug 25 '17 at 1:09
  • \$\begingroup\$ Tr[1^...] That is a clever way of finding the length of the list, nice! \$\endgroup\$ – numbermaniac Aug 28 '17 at 8:22
6
\$\begingroup\$

Mathematica, 104 97 90 bytes

Length@DeleteDuplicates@Select[FromDigits/@Subsequences@First@RealDigits[Pi,10,#],PrimeQ]&

Hahahaha, I managed to make this work. I have no idea how to use Mathematica. XD

Input:

[50]
\$\endgroup\$
  • 1
    \$\begingroup\$ you posted some seconds ahead of me. and our answers are very much alike! +1 \$\endgroup\$ – J42161217 Aug 25 '17 at 0:57
  • \$\begingroup\$ Are you sure about the numbers you just posted (double check the rounding of the digits) I see slightly different results using Python and sympy \$\endgroup\$ – Jonathan Allan Aug 25 '17 at 1:05
  • \$\begingroup\$ @JonathanAllan 50 96 The OP says 50 digits contain 93 primes, so Sympy's accuracy might be off..? \$\endgroup\$ – totallyhuman Aug 25 '17 at 1:06
  • \$\begingroup\$ @JonathanAllan Is Sympy using a probabilistic or a deterministic primality test? (Same question for Mathematica's PrimeQ.) \$\endgroup\$ – Arnauld Aug 25 '17 at 1:11
  • \$\begingroup\$ @Arnauld good point, not sure. \$\endgroup\$ – Jonathan Allan Aug 25 '17 at 1:13
6
\$\begingroup\$

Python 2, 73 72 70 bytes

-63 bytes with help from Jonathan Allan!

lambda n:ord("x			 !!''*,,,,,,,036<<@HJORXX]"[n])

Try it online!

Loads of unprintables... but hey, it saved a few bytes!

\$\endgroup\$
  • \$\begingroup\$ ,9,9,9, is shorter than ]+[9]*3+[ \$\endgroup\$ – Jonathan Allan Aug 25 '17 at 2:00
  • \$\begingroup\$ 84 bytes \$\endgroup\$ – Jonathan Allan Aug 25 '17 at 2:07
  • 1
    \$\begingroup\$ 70 bytes since we do not need to handle n=0. \$\endgroup\$ – Jonathan Allan Aug 25 '17 at 5:27
  • 3
    \$\begingroup\$ It looks like you hardcode tge answer and not the digits of Pi which isn't allowed \$\endgroup\$ – Roman Gräf Aug 26 '17 at 10:46
  • 1
    \$\begingroup\$ @RomanGräf That restriction wasn't there when I posted this answer and was later added through the comments. Hardcoding is, by default, allowed. So quit downvoting the hardcoding answers, because it is the challenge's fault, not the answer's. \$\endgroup\$ – totallyhuman Aug 27 '17 at 23:56
5
\$\begingroup\$

JavaScript (ES6), 80 bytes

Take that, Mathematica! :-P
Ok... not anymore...

Another boring hardcoded solution.

n=>[...`011011410030027310${3e6}410603${2e6}4336048253605`].map(v=>t+=+v,t=0)[n]

Demo

let f =

n=>[...`011011410030027310${3e6}410603${2e6}4336048253605`].map(v=>t+=+v,t=0)[n]

console.log(f(1))  // ->1  
console.log(f(3))  // ->2  
console.log(f(13)) // ->14  
console.log(f(22)) // ->28  
console.log(f(42)) // ->60  
console.log(f(50)) // ->93

\$\endgroup\$
  • 2
    \$\begingroup\$ Actually, mathematica is now 77 :P \$\endgroup\$ – user72349 Aug 25 '17 at 1:52
  • \$\begingroup\$ "Take that, Mathematica! " try harder... \$\endgroup\$ – J42161217 Aug 25 '17 at 1:53
  • \$\begingroup\$ Nah, this is way more interesting than my boring solution. :P The abuse of assignments in expressions makes this incredibly golfy. \$\endgroup\$ – totallyhuman Aug 25 '17 at 1:54
  • 1
    \$\begingroup\$ @JonathanAllan. JS allows non-printable characters in strings, so no need for -33 because it is possible to literally put exact characters we need in the string. \$\endgroup\$ – user72349 Aug 25 '17 at 2:31
  • 1
    \$\begingroup\$ @JonathanAllan: By the way, you can get the index of a string directly in JS, without needing to convert it to an array: [..."abc"][1]="abc"[1]="b". \$\endgroup\$ – Shaggy Aug 25 '17 at 9:12
2
\$\begingroup\$

Java (OpenJDK 8), 61 bytes

"_			 !!''*,,,,,,,036<<@HJORXX]"::charAt

Try it online!

Though it now seems a port of @totallyhuman's Python answer, I iteratively came there independently, as can be hinted by the history of the answer.

-5 bytes thanks to @Nevay!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can use a method reference ("_...XX]"::charAt) to save 5 bytes. \$\endgroup\$ – Nevay Aug 25 '17 at 14:48
  • 1
    \$\begingroup\$ This doesn't answer the problem (missing prime numbers), and it also encodes "answers" which is forbidden. \$\endgroup\$ – Jean-Baptiste Yunès Aug 27 '17 at 6:26
  • \$\begingroup\$ @Jean-BaptisteYunès Check the history of the challenge... My answer was correct when posted. Also, the OP said: "the spirit is freedom" after which he added rules. \$\endgroup\$ – Olivier Grégoire Aug 27 '17 at 8:02
2
\$\begingroup\$

Python 3, 274 237 207 194 189 bytes

-37 bytes thanks to Wheat Wizard! -14 bytes thanks to Mr.Xcoder.

Hardcodes the first 50 digits of pi but manually computes everything else.

x=int(input());l="31415926535897932384626433832795028841971693993751"[:x]
print(sum(all(i%m for m in range(2,i))for i in{int(i)for w in range(x)for i in[l[j:j-~w]for j in range(x-w)]}-{1}))

Try it online!

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

R, 156 123 bytes

cat(cumsum(c(1,1,0,1,1,4,1,0,0,3,0,0,2,7,3,1,0,3,0,0,0,0,0,0,4,1‌​,0,6,0,3,2,0,0,0,0,0‌​,0,4,3,3,6,0,4,8,2,5‌​,3,6,0,5))[scan()])

Super interesting solution. Working on a proper one.

Saved 33 bytes thanks to @Giuseppe.

R (+ numbers and gmp), 198 bytes

function(n,x=unique(gmp::as.bigz(unlist(sapply(1:n,function(x)substring(gsub("[.]","",numbers::dropletPi(50)),x,x:n))))))min(length(x),sum(sapply(sapply(x[x>0&!is.na(x)],gmp::factorize),length)==1))

Proper solution. Takes n as input.

Uses numbers::dropletPi(50) to generate the first 50 decimal places of pi. gsub removes the decimal point. substring takes every possible substring (surprise surprise) of pi up to n.

The returned list is flattened and converted to gmp's bigz format. This format is required to store integers of length 50. unique takes the unique values of that vector. This result gets stored in x.

Then we check for primality. This is tricky, because there are a bunch of edge-cases and annoyances:

  • For high n, there is a 0 in pi. This leads to substrings with a leading zero. as.bigz produces NAs with that, which have to be removed.

  • On a similar note, the substring "0" will crash gmp::factorize, so has to be removed as well.

  • For n=1, x = 3. Which in itself is ok, but the bigz representation of 3 is iterable, so sapply will get confused and report 16 primes. To this end we take the minimum of the length of the vector x, and the amount of primes in it.

  • gmp::isprime can't seem to reliably handle the large numbers reliably. So instead we use gmp::factorize and check of the length of the output is 1.

So in all, we remove 0 and NA from x. We factorize all of x and check for the length. We count the number of occurrences of 1 and return the min(occurences, length(x)).

\$\endgroup\$
  • \$\begingroup\$ there you are! Now let's see if someone out there can outgolf this with a more interesting solution. could be you! \$\endgroup\$ – user73398 Aug 25 '17 at 12:25
  • \$\begingroup\$ use cumsum(c(1,1,0,1,1,4,1,0,0,3,0,0,2,7,3,1,0,3,0,0,0,0,0,0,4,1,0,6,0,3,2,0,0,0,0,0,0,4,3,3,6,0,4,8,2,5,3,6,0,5)) instead of your vector for 123 bytes :) \$\endgroup\$ – Giuseppe Aug 25 '17 at 13:05
  • \$\begingroup\$ @Giuseppe Nice one. That 'compression' will definitely beat any legit solution. \$\endgroup\$ – JAD Aug 25 '17 at 13:08
  • \$\begingroup\$ I think it's impossible in R without hardcoding or introducing another package since R has only 32-bit ints, which will certainly not represent a 50-digit integer. \$\endgroup\$ – Giuseppe Aug 25 '17 at 13:14
  • 1
    \$\begingroup\$ Yeah, I may think about this some more as well. 82 hardcoded bytes \$\endgroup\$ – Giuseppe Aug 25 '17 at 14:06
0
\$\begingroup\$

Jelly, 59 32 bytes

-27 bytes thanks to Erik the Outgolfer.

“!⁶⁷¬,6½ạEC.wʠ€Ẉ!+Ẉfṭ¡’Ṿḣ³ẆVQÆPS

Try it online!

Explanation

“...’Ṿḣ³ẆVQÆPS

“...’           compressed string that evaluates to first 50 digits of pi (314159...)
     Ṿ          uneval; stringify
      ḣ³        first n characters of the string where n is the first command-line argument
        Ẇ       all sublists
         V      convert all elements to integers
          Q     deduplicate
           ÆP   convert all prime elements to 1 and others to 0
             S  sum
\$\endgroup\$
  • \$\begingroup\$ Why did you spam this with answers? \$\endgroup\$ – Zacharý Aug 25 '17 at 22:54
  • \$\begingroup\$ Because nobody else was answering, and I hit rep cap anyways. :P \$\endgroup\$ – totallyhuman Aug 25 '17 at 23:19

Your Answer

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