Digital Sum part 2

The problem can be easily solved by generating the primes using a sieve of Eratosthenes. and checking if Digit Root is equal to $2$ . For $N<2.0 \times 10^6$ we get that around $16.684$ % of the primes have a digit root of $2$ .

pic

It is interesting to Note that the digital root of a prime number (except $3$ ) is $1$ , $2$ , $4$ , $5$ , $7$ . And the distribution of the digit root is around $16.6$ for all of them.

Here is the code I used:

 1
 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

def DigitRoot(n):
    if n==0:
        return 0
    if n%9==0:
        return 9
    return n%9

def prime_sieve(limit):
    limitn = limit+1
    not_prime = set()
    primes = []
    for i in range(2, limitn):
        if i in not_prime:
            continue
        for f in range(i*2, limitn, i):
            not_prime.add(f)
        primes.append(i)
    return primes

Primes = prime_sieve( 2*(10**6) )
Count = 0
for p in Primes:
    if DigitRoot(p) == 2:
        Count += 1.0

Percentage = (Count/len(Primes))*100
print int( Percentage * 1000 )

Source of image and data: http://people.revoledu.com/kardi

The digital root of a number can be calculated quickly using modulo 9 (http://en.wikipedia.org/wiki/Digital_root), and we are left with the primes problem that can be solved quickly by generating the primes using the Sieve of Eratosthenes.

my C++ code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <bits/stdc++.h>
using namespace std;
bool prime[2000000];
long long i,j;
double primes,primeD2;
//let primes be the number of primes below two million.
//let primeD2 be the number of primes that has digital root 2.
int main() {
    primes=primeD2=0; // initialize both variables.
    for(i=0;i<2000000;i++) prime[i]=true; // initialize all elements of the array.
    for (i=2;i<2000000;i++) { // Sieve of Eratosthenes
        if (prime[i]) { // if i is a prime number
            primes++; // add primes by 1
            if (i%9==2) primeD2++; // if i has digital root of 2, add primeD2 by 1.
            for (j=i*i;j<2000000;j+=i) prime[j]=false; // mark multiples of i as not prime.
        }
    }
    cout << floor(primeD2/primes*100*1000); // print the solution.
    return 0;
}

Output: 16684

Here is my solution in C#

Here is the recursive function :

private void GetDigitalSum(double num, ref double num2)
    {
        //digital sum

        double sum = 0;

        for (int r = 0; r <= num.ToString().Length - 1; r++)
        {
            sum += double.Parse(num.ToString().Substring(r, 1));

        }

        if (sum.Equals(2))
        {
            num2 = -8;
            return;
        }
        else
        {
            if (sum > 9)
            {
                GetDigitalSum(sum, ref num2);
            }
            else
            {
                num2 = sum;
            }
        }


    }

   //Here is the calling subroutine :

        double no = 1;
        double no2 = 0;
        double pnum = 0;
        double sumr = 0;

        bool IsPrm = false;

        ArrayList ar = new ArrayList();

        while (no < 2000000)
        {
            IsPrm = IsPrimeNumber(no);
            if (IsPrm.Equals(false))
            {
                no += 1;
                continue;
            }

            Application.DoEvents();
            lblCounter.Text = no.ToString();

            GetDigitalSum(no, ref no2);

            if (no2.Equals(-8))
            {
                ar.Add(no);
                sumr += double.Parse(no.ToString());
            }

            no += 1;
            pnum += 1;
        }


        //GetDigitalSum(ar.Count, ref no2);

        double P = double.Parse(((ar.Count / pnum) * 100).ToString());

        //Floor
        double x = Math.Floor(1000 * P);

        MessageBox.Show(x.ToString());


  Here is the function to check a number for prime :

   static bool IsPrimeNumber(double num)
    {
        bool bPrime = true;
        double factor = num / 2;

        int i = 0;

        for (i = 2; i <= Math.Sqrt(num); i++)
        {
            if ((num % i) == 0)
            {
                bPrime = false;
                break;
            }
        }
        return bPrime;
    }

Answer : 16684

def is_prime(n): for i in range(3, n): if n % i == 0: return False return True

def digitalRoot(n): return 0 if n==0 else 1+((n-1)%9)

def fun() : P = 0 R = 0 for x in range (0,2000000): if is_prime(x) == True : P = P+1 #print P if digitalRoot(x) == 2: R = R +1 #print R print P print R return R

print fun() percent = (R/P)*100 print percent *1000