391. Prime-k factorial

For a prime p let S(p) = (∑(p-k)!) mod(p) for 1 ≤ k ≤ 5.

For example, if p=7,
(7-1)! + (7-2)! + (7-3)! + (7-4)! + (7-5)! = 6! + 5! + 4! + 3! + 2! = 720+120+24+6+2 = 872.
As 872 mod(7) = 4, S(7) = 4.

It can be verified that ∑S(p) = 480 for 5 ≤ p < 100.

Find ∑S(p) for 5 ≤ p < 108.

prime number of 5 ≤ p <100  = >  5, 7,  11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Case 1, assume p = 97if (p-k)!,  96! + 95! + 94! + 93!  + 92!, if use brute force method, factorial’s are very big number (infinite), time wise can’t possible to find out 108primes.

Case 2, based on the above calculation we know 5=>4, 7=>4, 11=>1, 13=>11, 17=>6, 19 =>2. let assume p = 5

p =5

k p-k ∑p-k ∑p-k mod p
5 4 4 4
4 3 7 2
3 2 9 4
4 1 10 0
1 0 10 0
p=7

k p-k ∑p-k ∑p-k mod p
7 6 6 6
6 5 11 4
5 4 15 1
4 3 18 4
3 2 20 6
2 1 21 0
1 0 21 0
p=11

k p-k ∑p-k ∑p-k mod p
11 10 10 10
10 9 19 8
9 8 27 5
8 7 34 1
7 6 40 7
6 5 45 1
5 4 49 5
4 3 52 8
3 2 54 10
2 1 55 0
1 0 55 0
From the above 3 examples, if ∑p-k mod p number
is repeated, that is solution of S(p), so in the above case
s(5) = 4, s(7) = 4, s(11) = 1, s(13) = 11.But if you see the answer will be appear in the middle of the
(red line) ∑p-k. So instead of checking every time ∑p-k mod p, calculate only ∑p-k  mod p for 1 ≤ k ≤p/2+1. so in this case within 8 seconds you will get answer for 106.Instead of loop through 1 ≤ k ≤p/2+1, to get the answer quickly(∑p-1 –  ∑p/2-1)/2 = ∑p-k.5 = > ((4 * 5) – (1 * 2)) /2 => (20 – 2 )/2 = 18/2 = 9 mod 5 = 4.
7 = > ((6 * 7) – (2 * 3)) /2 => (42 – 6 )/2 = 36/2 = 18 mod 7 = 4.
11 = > ((10 * 11) – (4 * 5)) /2 => (110 – 20 )/2 = 90/2 = 45  mod 11 = 1.so you will answer withing 6 seconds for 108.
   long l=100000000L,sum =0;
        int sb = (int) ((l-1)/2);
        int cl = (int)(Math.sqrt((double)l)-1)/2;
        boolean s[] = new boolean[sb+1];
        Arrays.fill(s, false);
        for (int i=1;i<=cl;i++) {
            if (!s[i]) {
                for (int j=(2*i*(i+1));j<=sb;j=(j+(2*i)+1)) {
                    s[j]=true;
                }
            }
        }
        for (int i=1;i<=sb;i++){
            if(!s[i]) {
                long p = 2*i+1;
                if(p>=5) {
                    long sp  = (((p*(p-1)) - (p/2*(p/2-1)))/2)%p;
                    sum+=sp;
                }
            }
        }
        System.out.println(sum);
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: