32
\$\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!

Improve this question
\$\endgroup\$
14
  • 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
    Commented Aug 24, 2017 at 23:59
  • 3
    \$\begingroup\$ @totallyhuman That sequence not even in OEIS yet! Time for your claim to fame? \$\endgroup\$
    – Sanchises
    Commented Aug 25, 2017 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
    Commented Aug 25, 2017 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
    Commented Aug 25, 2017 at 12:10
  • 3
    \$\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
    Commented Aug 25, 2017 at 15:58

7 Answers 7

Reset to default
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
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ <žsþŒÙpO should work for 8 bytes \$\endgroup\$
    – Adnan
    Commented Aug 25, 2017 at 0:21
  • \$\begingroup\$ Ah yeah p vectorises thanks! \$\endgroup\$
    – Jonathan Allan
    Commented Aug 25, 2017 at 0:22
  • 2
    \$\begingroup\$ Yes! Finally a very short code golf answer that I actually understand! :D \$\endgroup\$
    – Fabian Röling
    Commented Aug 26, 2017 at 9:22
11
\$\begingroup\$

Mathematica, 76 bytes

Tr[1^Union@Select[FromDigits/@Subsequences@#&@@RealDigits[Pi,10,#],PrimeQ]]&
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Oh, no fair, I'm not familiar with Mathematica golf. :P (+1) \$\endgroup\$
    – totallyhuman
    Commented Aug 25, 2017 at 0:50
  • \$\begingroup\$ @totallyhuman We posted this at the same time. this is so weird! \$\endgroup\$
    – ZaMoC
    Commented Aug 25, 2017 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
    Commented Aug 25, 2017 at 1:09
  • \$\begingroup\$ Tr[1^...] That is a clever way of finding the length of the list, nice! \$\endgroup\$
    – numbermaniac
    Commented Aug 28, 2017 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]
Improve this answer
\$\endgroup\$
10
  • 1
    \$\begingroup\$ you posted some seconds ahead of me. and our answers are very much alike! +1 \$\endgroup\$
    – ZaMoC
    Commented Aug 25, 2017 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
    Commented Aug 25, 2017 at 1:05
  • \$\begingroup\$ @JonathanAllan 50 96 The OP says 50 digits contain 93 primes, so Sympy's accuracy might be off..? \$\endgroup\$
    – totallyhuman
    Commented Aug 25, 2017 at 1:06
  • \$\begingroup\$ @JonathanAllan Is Sympy using a probabilistic or a deterministic primality test? (Same question for Mathematica's PrimeQ.) \$\endgroup\$
    – Arnauld
    Commented Aug 25, 2017 at 1:11
  • \$\begingroup\$ @Arnauld good point, not sure. \$\endgroup\$
    – Jonathan Allan
    Commented Aug 25, 2017 at 1:13
3
\$\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!

Improve this answer
\$\endgroup\$
5
1
\$\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
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Why did you spam this with answers? \$\endgroup\$
    – Adalynn
    Commented Aug 25, 2017 at 22:54
  • \$\begingroup\$ Because nobody else was answering, and I hit rep cap anyways. :P \$\endgroup\$
    – totallyhuman
    Commented Aug 25, 2017 at 23:19
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)).

Improve this answer
\$\endgroup\$
12
  • \$\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
    Commented Aug 25, 2017 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
    Commented Aug 25, 2017 at 13:05
  • \$\begingroup\$ @Giuseppe Nice one. That 'compression' will definitely beat any legit solution. \$\endgroup\$
    – JAD
    Commented Aug 25, 2017 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
    Commented Aug 25, 2017 at 13:14
  • 1
    \$\begingroup\$ Yeah, I may think about this some more as well. 82 hardcoded bytes \$\endgroup\$
    – Giuseppe
    Commented Aug 25, 2017 at 14:06
1
\$\begingroup\$

Husk, 9 bytes

#ṗumdQ↑İπ

Try it online!

Freezes beyond n=10 on tio. Reverse of the 05AB1E program.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.