The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^69725931; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 284332^7830457+1.

Find the last ten digits of this prime number.

+-;pow
(defn pow [a b]
  (loop [res 1 mult a shift b]
    (if (= 0 shift)
      res
      (if (= 1 (rem shift 2))
        (recur (* res mult) (* mult mult) (bit-shift-right shift 1))
        (recur res (* mult mult) (bit-shift-right shift 1))
      )
    )
  )
)

+-;pow-mod
(defn pow-mod [a b m]
  (loop [res 1 mult a shift b]
    (if (= 0 shift)
      (rem res m)
      (if (= 1 (rem shift 2))
        (recur (rem (* res mult) m) (rem (* mult mult) m) (bit-shift-right shift 1))
        (recur res (rem (* mult mult) m) (bit-shift-right shift 1))
      )
    )
  )
)

(defn p97 []
  (println
    (let [mod (pow 10 10)]
      (rem (+ 1 (* 28433 (pow-mod 2 7830457 mod))) mod)
    )
  )
)

+-%pow
pow(_,0)->1;
pow(1,_)->1;
pow(A,B)->pow(A,B,1).
pow(_,0,Res)->Res;
pow(Mult,B,Res) when B band 1 == 1 ->
	pow(Mult*Mult,B bsr 1, Res*Mult);
pow(Mult,B,Res)->pow(Mult*Mult,B bsr 1, Res).

+-%pow_mod
pow_mod(_,_,1)->0;
pow_mod(_,0,_)->1;
pow_mod(1,_,_)->1;
pow_mod(A,B,M)->pow_mod(A,B,M,1).
pow_mod(_,0,_,Res)->Res;
pow_mod(Mult,B,M,Res) when B band 1 ==1 ->
	pow_mod((Mult*Mult) rem M, B bsr 1, M, (Res*Mult) rem M);
pow_mod(Mult,B,M,Res)->pow_mod((Mult*Mult) rem M, B bsr 1, M, Res).

p97()->
	M=pow(10,10),
	io:format("~w~n",[(1+28433*pow_mod(2,7830457,M))rem M]).

+-#power_mod
def power_mod(a,b,m)
  b=b.to_s(2).reverse.split("").map{|c| c=="1"}
  acc=1
  while(b.length>0)
    c=b.shift
    acc=(acc*a)%m if c
    a=(a**2)%m
  end
  acc
end

def p97
  puts (power_mod(2,7830457,10**10)*28433+1)%(10**10)
end