Sum of digits in a very large prime number.

By listing the first six prime numbers: 2 , 3 , 5 , 7 , 11 , 2, 3, 5, 7, 11, and 13 13 , we can see that the 6th prime is 13.

Let N N be the sum of the digits of a prime (11 would be 2).

What is the value of N N for the 148937 s t 148937st prime number?


The answer is 11.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

14 solutions

Ryan Soedjak
Dec 17, 2013

Mathematica:

DigitSum[Prime[148937]]

trololololol

prime number in 148937 is 1, 3, 7. just sum this number, the answer is 11 :v

Idang Wahyuddin - 7 years, 5 months ago

Beautifully written. Thank you.

Pi Han Goh - 7 years, 5 months ago

Mathematica does not recogonise the term "DigitSum[#]"

May I ask what version of mathematica are you using?

John Karter - 7 years, 5 months ago

Log in to reply

darn oops I've been using my own functions for so long I've forgotten which ones are built in. To fix it just add

DigitSum[n_] := Total[IntegerDigits[n]]

or just do

Total[IntegerDigits[Prime[148937]]]

Ryan Soedjak - 7 years, 5 months ago

LOLOLOLOL One-line solution.

Zi Song Yeoh - 7 years, 5 months ago

That is not what was expected.. :-/

Snehal Shekatkar - 7 years, 5 months ago

BTW Mathematica is a programming language.

Ryan Soedjak - 7 years, 5 months ago

LOL wow I did it the long way =_= took 3 hours to run my program

Jerry Lee - 7 years, 4 months ago

I 'm use this site:

The Prime Data Best

pebrudal zanu - 7 years, 5 months ago

good

navdeep dhiman - 7 years, 3 months ago
Thaddeus Abiy
Dec 17, 2013

I don't know if this is the most efficient way of solving this problem but,I used the a modified version of the Sieve of Eratosthenes to solve it. For a visual understanding of this algorithm look at the animation here . It is a fairly simple method of generating primes ; this is how it works:

We will start with a list of all of the numbers from 2 to N( let us take 100 for the sake of simplicity):

     2  3  4  5  6  7  8  9 10
  11 12 13 14 15 16 17 18 19 20
  21 22 23 24 25 26 27 28 29 30
  31 32 33 34 35 36 37 38 39 40
  41 42 43 44 45 46 47 48 49 50
  51 52 53 54 55 56 57 58 59 60
  61 62 63 64 65 66 67 68 69 70
  71 72 73 74 75 76 77 78 79 80
  81 82 83 84 85 86 87 88 89 90
  91 92 93 94 95 96 97 98 99 100

We now identify 2 as a prime (it is not divisible by lesser primes), and cross out every second number after 2:

      2  3  X  5  X  7  X  9  X
  11  X 13  X 15  X 17  X 19  X
  21  X 23  X 25  X 27  X 29  X
  31  X 33  X 35  X 37  X 39  X
  41  X 43  X 45  X 47  X 49  X
  51  X 53  X 55  X 57  X 59  X
  61  X 63  X 65  X 67  X 69  X
  71  X 73  X 75  X 77  X 79  X
  81  X 83  X 85  X 87  X 89  X
  91  X 93  X 95  X 97  X 99  X

We have now identified 3 as a prime. It is not divisible by lesser primes. And we cross out every third number after 3. Some of these are already crossed out. I will just skip over those:

      2  3  X  5  X  7  X  X  X
  11  X 13  X  X  X 17  X 19  X
   X  X 23  X 25  X  X  X 29  X
  31  X  X  X 35  X 37  X  X  X
  41  X 43  X  X  X 47  X 49  X
   X  X 53  X 55  X  X  X 59  X
  61  X  X  X 65  X 67  X  X  X
  71  X 73  X  X  X 77  X 79  X
   X  X 83  X 85  X  X  X 89  X
  91  X  X  X 95  X 97  X  X  X

We do the same thing with 5, and then 7:

      2  3  X  5  X  7  X  X  X
  11  X 13  X  X  X 17  X 19  X
   X  X 23  X  X  X  X  X 29  X
  31  X  X  X  X  X 37  X  X  X
  41  X 43  X  X  X 47  X  X  X
   X  X 53  X  X  X  X  X 59  X
  61  X  X  X  X  X 67  X  X  X
  71  X 73  X  X  X  X  X 79  X
   X  X 83  X  X  X  X  X 89  X
   X  X  X  X  X  X 97  X  X  X

We could also go on to 11 but the algorithm only requires us to use the primes less than N \sqrt{N} . Of all the implementations of the sieve of Eratosthenes this is the one I know to be fastest.

  def primesbelow(N):
      # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
      #""" Input N>=6, Returns a list of primes, 2 <= p < N """
      correction = N % 6 > 1
      N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
      sieve = [True] * (N // 3)
      sieve[0] = False
      for i in range(int(N ** .5) // 3 + 1):
          if sieve[i]:
              k = (3 * i + 1) | 1
              sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
              sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
      return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

So for this problem , I took an arbitrarily large upper bound 1 0 7 10^7 (It can be found more accurately with approximations such as the Prime Counting Function ).But 1 0 7 10^7 was sufficient for this problem so I used it.

#Final code to get the answer
print primesbelow(10**7)[148937 - 1]

Here is the animation Here is the animation

Here is the animation!

Thaddeus Abiy - 7 years, 4 months ago

Log in to reply

I LOVE THIS!!!

Gian Franco Dy - 7 years, 4 months ago

very terrific

Daniel Lim - 7 years, 3 months ago

"very terrific" is very bad English haha

Daniel Lim - 7 years, 3 months ago

Very unique solution. Nice.

A Brilliant Member - 7 years, 5 months ago

How much time did it take you to compute this? I made this using C# (http://archives.somee.com). The problem with prime numbers is always the time it will take to compute your number.

Mateo Torres - 7 years, 5 months ago

Log in to reply

Around 1.48 seconds on my computer.I know that is kind of slow but I prefer the Sieve way of approaching the problem. That is basically the magic going behind the scenes in the Prime function in the Mathematica oneliner above. This is the fastest way I know to generate primes.Unless you already have a pre-generated list , I don't see a faster way..

Thaddeus Abiy - 7 years, 5 months ago

Superb and unique.

Soham Dibyachintan - 7 years, 5 months ago
Aamira Shabnam
Dec 22, 2013

JAVA code using Sieve Method:

public class VeryLargePrime {

static int SIZE_N = 10000000;
static int SIZE_P = 10000000;
static boolean flag[] = new boolean[SIZE_N + 5];
static int primes[] = new int[SIZE_P + 5];

public static void main(String[] args) {
    int total = sieve();

    Integer pr = (Integer) primes[total - 1];
    String str = pr.toString();
    char[] arr = str.toCharArray();


    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += (arr[i] - 48);
    }
    System.out.println(sum);
}

static int sieve() {
    int total = 0, val;

    for (int i = 2; i <= SIZE_N; i++) {
        flag[i] = true;
    }

    val = (int) Math.sqrt(SIZE_N) + 1;

    for (int i = 2; i < val; i++) {
        if (flag[i]) {
            for (int j = i; j * i <= SIZE_N; j++) {
                flag[i * j] = false;
            }
        }
    }

    for (int i = 2; i < SIZE_N; i++) {
        if (flag[i]) {
            primes[total++] = i;
        }
        if (total == 148937) {
            break;
        }

    }
    return total;

}

}

Good.

Soham Dibyachintan - 7 years, 5 months ago
Prasad Nikam
Feb 3, 2014

In 148937, the prime nos. are 1,3 and 7. therefore, 1+3+7 = 11

why include 1?

computer computer - 7 years, 3 months ago
Mharfe Micaroz
Dec 18, 2013

In python:

from sympy import prime

sum(int(x) for x in str(prime(148937)))

-->11

(Java Code)

import java.lang.Math;

public class brilliant{

public static void main(String[] args){
    int counter=0, n=1;
    while(counter<=148937){
        if(isPrime(n))
            System.out.println(counter++ + " " + n);
        n++;
    }
}

public static boolean isPrime(int n){
    for(int i=2;i<=Math.sqrt(n);i++){
        if(n%i==0)
            return false;
    }
    return true;
}

}

The final line this outputs is:

148937 2000081

Which signifies that the 148937th prime is 2000081.

Therefore the answer is: 2 + 0 + 0 + 0 + 0 + 8 + 1 = = 11 2 + 0 + 0 + 0 + 0 + 8 + 1 == 11

simply use matlab obtain prime function sum[]

Bhavik Doshi - 7 years, 5 months ago

I found this vr helpful and interesting http://en.wikibooks.org/wiki/Efficient Prime Number Generating Algorithms

Shree Krishnamoorthy - 7 years, 4 months ago
Brian Yao
Dec 17, 2013

Here is a solution using Java:

import java.util.ArrayList;
public class A {
    public static void main(String[] args){
        int n=148937;
        ArrayList<Long> a = new ArrayList<>();
        a.add(2L);
        long b=3L;
        while(a.size()<n){
            if(isPrime(b))
                a.add(b);
            b+=2;
        }
        System.out.println(sumdigits(a.get(n-1)));
    }
    public static boolean isPrime(long a){
        for(int i=2;i<=Math.sqrt(a);i++){
            if(a%i==0)
                return false;
        }
        return true;
    }
    public static int sumdigits(long a){
        int b=0;
        while(a>0){
            b+=a%10;
            a/=10;
        }
        return b;
    }
}

whoa mate! you're simply complicating things by using the ArrayList class. A simple for-loop, with a function to determine whether a number is prime or not is more than enough. The 148937th prime number can be held in an int variable!

SR Somayaji - 7 years, 5 months ago
Rohti Vaidya
Mar 30, 2014

Java code

             int count,primecount=0;
    count=0;

    for(double i=1;;i++)
    {
       for(double j=2;j<=Math.sqrt(i);j++)
       {
           if(i%j==0)
              count++;
       }
      if(count==0&&i!=1)
          {primecount++;}
      count=0;
      if(primecount==148937){System.out.println(i+" ");break;}      
    }

Got answer 2000081: Added up the numbers to 11

Code

def findSumOfDigits(number):
    return sum([int(number) for number in list(str(number))])

def prime(ordinal):
    iOrdinal=0
    index=1
    while True:
        if isPrime(index):
            iOrdinal= iOrdinal+1
        if iOrdinal==ordinal:
            return index
        index = index+1
    return None

def isPrime(number):
    if number <2 or number%2==0 or number %3==0:
        return False
    if  number==2 or number == 3:
        return True
    looper= math.floor(math.sqrt(number))
    index=4
    while index<looper:
        if number % index==0:
            return False
        index=index+1
    return True

print findSumOfDigits(prime(148937))
Sandeep Thakur
Mar 1, 2014
var range =148937;
var count = 0;
var num = 2;

while(1){

  var flag = false;
  for(var i = 2; i<=Math.sqrt(num); i++){
    if(num % i == 0){
      flag = true;
      break;
   }
  }
if(!flag){
     count++;
}

if(count>=range){
   break;
}

    num++;
}
 alert(num);
Ahmad Razis
Feb 27, 2014

http://www.numberempire.com/148937

The 148937th prime number is 2000081

The sum of the digits is 11

Kaveri Kale
Jan 23, 2014

using System;

namespace Prime number sum { class Program { static void Main(string[] args) { int count=1; //2 is prime number so count starts with 1 int n=3,i; int sum = 0; while (count < 148937) {
for (i = 2; i <= (n / 2); i++) { if (n % i == 0) break; } if (i == ((n / 2) + 1))
count++;
n++; } n = n - 1;


        while (n > 0)
        {
            sum = sum + (n % 10);
            n = n / 10;
        }
        Console.WriteLine("Sum of digits of 148937th prime number = {0}", sum);
        Console.Read();           //wait for user
    }
}

}

Output:Sum of digits of 148937th prime number = 11

Stefan Stankovic
Dec 18, 2013

Mathematica does this easily with:

Total@IntegerDigits@Prime@148937

11

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...