Strong Pseudoprimes & Miller-Rabin primality test.

What is the “Strong Pseudoprime”?

https://en.wikipedia.org/wiki/Strong_pseudoprime
http://mathworld.wolfram.com/StrongPseudoprime.html

https://www.saylor.org/site/wp-content/uploads/2012/07/Strong-pseudoprime.pdf
What is Miller-Rabin primality test?

http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

Deterministic Variant of Miller-Rabin Algorithm:
https://github.com/Abdullahalabd/algorithms-lib/blob/master/Miller%E2%80%93Rabin.cpp
The theoretical part of the algorithm above is mentioned in Wikipedia  here.

Advertisements

Famous Sequences of Grundy values.

Seq id: A025480.
Seq definition: a(2n) = n, a(2n+1) = a(n).

Seq first terms: 0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 9, 19, 2, 20, 10, 21, 5, 22, 11, 23, 1, 24, 12, 25, 6, 26, 13, 27, 3, 28, 14, 29, 7, 30, 15, 31, 0, 32, 16, 33, 8, 34, 17, 35, 4, 36, 18, 37, 9, 38, 19, 39, 2, 40, 20, 41, 10

https://oeis.org/A025480