My Mersenne Primality Testing Algorithm

I'm not sure how fast it is compared to GIMPS, but it is acurate for all Mersenne or Fermat primes. See my article Value-Counting Up to N for why.

import sys
import time

# Remove the limit
sys.set_int_max_str_digits(0)

i = 0

def signal_handler(sig, frame):
	global i
	if sig == signal.SIGINT:
		print("index = %i" % (i))
	sys.exit(0)

def int_sqrt(n):
	"""
	Calculate the integer square root of a non-negative integer n.
	This function returns the largest integer whose square is less than or equal to n.
	"""
	if n < 0:
		raise ValueError("Cannot calculate square root of a negative number.")
	if n == 0:
		return 0
	x = n
	y = 1
	i = 0
	while x > y:
		x = (x + y) // 2
		y = n // x
	return x

def prime_power(n):
	signal.signal(signal.SIGINT, signal_handler)
	total = 0
	half_n = (n + 1) // 2
#	limit = half_n
#	limit = math.ceil((half_n*(half_n + 1) // 2 + 1) / n)
	limit = (n + 13)//8
	start_time = time.perf_counter()
	end_time = start_time

	global i
	for i in range(2, limit):
		# border_value represents the number that ends on the last
		# column when all numbers up to it are added and wrapped.
		border_value = int((int_sqrt(8 * i * n + 1) - 1)/2)
		total = (border_value * (border_value + 1)//2)
		elapsed_time = end_time - start_time
		if (total == (i * n)):# or (total + (border_value + 1)//2 == (i * n)):
			print("%i" % (border_value))
			return
		end_time = time.perf_counter()
		elapsed_time = end_time - start_time
		if elapsed_time > WAIT_TIME:
			start_time = end_time
			end_time = time.perf_counter()
	print("\tprime_power")

print("p\tborder\tprime power")

prime_power(2**89-1)

Permutation Rotations

In this paper, we discuss certain properties of permutation rotations on each other.

Click here to read my paper.

The Golden Ratio's Siblings

On real numbers whose fractional part remain constant after squaring.

Click here to read my paper.

Value-Counting Up to N

Some interesting properties arise when value-counting the integers sequentially up to N using N digits or fingers and comparing the number of values to the prime-exact equation; with a simple method for testing primes and prime powers (particularly Mersenne and Fermat primes).

Click here to read my paper.

Primality Testing and Factoring Using Pascal's Triangle

An interesting if not impractical way of primality testing and factoring a number using Pascal’s Triangle.

Click here to read my paper.

Minimal Set for Powers of 2

The minimal set for powers of 2 is currently nondeterministic and can be shown to be more complex than previously proposed.

Click here for my analysis on it.

Extended Midy's Theorem

This is my proof, and an extension, of Midy's Theorem. Someone had referenced this in Wikipedia almost six years ago, but it was recently removed (still in the history) to make Wikipedia more official. Since this blog came about after my proof, I never went back and added it.

Not So Fortunate Numbers

A Fortunate number, named after Reo Fortune, for a given positive integer n is the smallest integer m > 1 such that p_n# + m is a prime number, where the primorial p_n# is the product of the first n prime numbers.

For example, p₇# = 2×3×5×7×11×13 = 510,510. The smallest prime number after 510,511 is 510,529. Thus, 510,529 - 510,510 = 29 is a Fortunate number.

Fortune's conjecture states that no Fortunate number is composite. A Fortunate prime is a Fortunate number which is also a prime number. As of 2009, all the known Fortunate numbers are also Fortunate primes.

------------------------------------------------------------

Instead of only using primorial numbers in our sequence, what happens when we use all numbers such that for the largest prime dividing each number in our sequence, the primorial of that prime also divides that number (i.e., 630 = 2×3²×5×7 belongs to the sequence since p₄# = 210 divides 630)?

512 → 2⁵, 16,384 → 2⁹, and 524,288 → 2¹⁴ fail to generate Fortunate primes.

Do only perfect powers of two fail to generate Fortunate primes? Is there a pattern?

------------------------------------------------------------

For all numbers less than a billion in our sequence, the following fail to generate a Fortunate prime:

F#  Generator
9      512
9      8,388,608
15    4,194,304
15    67,108,864
21    524,288
25    147,456
25    373,248
25    393,216
25    1,062,882
25    1,259,712
25    4,251,528
25    4,718,592
25    5,308,416
25    5,971,968
25    10,077,696
25    17,915,904
25    21,233,664
25    35,831,808
25    42,467,328
25    172,186,884
27    16,384
35    1,119,744
35    1,492,992
35    33,554,432
35    47,775,744
35    150,994,944
35    362,797,056
49    22,118,400
49    31,104,000
49    32,805,000
49    42,187,500
49    56,623,104
49    90,000,000
49    286,654,464
49    364,500,000
49    720,000,000
49    859,963,392
55    679,477,248
65    10,616,832
77    159,252,480
77    188,956,800
85    322,486,272
119  314,572,800

Security Codes

I was entering the four-digit security code to our house, and I realized that it doesn't end with an ENTER (E) key to accept it. The problem with that is you can keep pressing numbers until the right combination is found. Since most keypads use all ten digits (0-9), the total number of combinations should be $10^n$. However, it is the ENTER key that makes it so difficult.

Let D equal the number of digits for the security code. Let K equal the number of digits on the keypad.

For a binary keypad (0, 1) and a three-digit code, our set consists of (000E, 001E, 010E, 011E, 100E, 101E, 110E, 111E). Thus, we have at most $2^3 \times (3+1)$ possible keys to enter, where the plus one is for the ENTER key. Generally speaking, we'd have $K^D \times (D+1)$ possible keys to enter.

Without the ENTER key, we could keep pressing the keypad until all combinations have formed. The minimum number of keys required would be $K^D + D$.

So for a binary keypad, we'd have:

D	String	Keys (wo/ E)	Keys (w/ E)
1	01	2	4
2	00110	5	12
3	0001110100	10	32
4	0000111100101101000	19	80
5	000001111100010010101110110011010000	36	192

Thus, one only needs to know the string concatenations to be able to guess the right combination if no ENTER or code-stopper key is required.

Update: See De Bruijn Sequence and ProjectEuler #265 for a related problem.

ABC Conjecture

Conjecture

The ABC conjecture is a conjecture due to Oesterlé and Masser in 1985. For any three relatively prime numbers A, B, and C, such that A + B = C, and any infinitesimal $\epsilon$ > 0, there exists a constant c_$\epsilon$ such that $sqp(ABC)^{1 + \epsilon} \ge c_{\epsilon} \times C$, where sqp(n) is the square-free product of all primes dividing n.

Modified ABC Conjecture

Given a fixed set of distinct primes $p_i$ and $q_j$.
Let C = $\prod_{i=1}^n p_i, B = \prod_{j=1}^m q_j$, where ($p_i$, $q_j$) = 1.
Let O(C) = {$C_k$} = {$\prod p_i^{c_i}, c_i \ge 1$}, be the infinite ordered set of all numbers such that C | C_k.
Let O(B) = {$B_l$} = {$\prod q_j^{b_j}, b_j \ge 1$}, be the infinite ordered set of all numbers such that B | $B_l$.
Let $A_k$ = min {C_k - B_l} > 0, ∀ l.
Let $k^'$ = {k | $A_{k^'}$ = inf($A_k$)}.

Then, $k^'$ > 0 and sqp($A_k B_l C_k$) = $B C \times sqp(A_k) \ge C_k \times \epsilon$, where $\epsilon = B C \times sqp(A_{k^'})$ / $C_(k^'}$.

The original ABC conjecture states that for a given $\epsilon$, there is a constant $c_\epsilon$ that is based only on $\epsilon$ such that the inequality holds.

The modified conjecture states that for fixed distinct primes dividing B and C, we can find a constant $c_{p,q}$ that depends only on p and q that also satisfies the inequality.

Fortunate Primes

Conjecture (Original)

A conjecture made by Reo F. Fortune that if $E_k$ = $p_k$# + 1, where $p_k$# is the $k^{th}$ prime and p# is primorial, and assuming $q_k$ is the next prime after $E_k$ (i.e., the smallest prime greater than $E_k$), then $F_k$ = $q_k$ - $E_k$ + 1 is prime for all k. The first values of $F_k$ are 3, 5, 7, 13, 23, 17, 19, 23, ….

Conjecture

Let S₀ = $p_k$# + $p_{k+1}$. If $S_0$ is composite, let $q_0$ be the smallest prime dividing $S_0$. Let $S_i = p_k# + q_{i-1}$, where $q_{i-1}$ is the smallest prime dividing $S_i$.

Assuming $S_0 \lt M^2$, then $S_i \lt {M + 1}^2 \forall$ i. Then $S_n$ is prime for some n ≥ 0. Otherwise, $S_i$ = $S_j$ for some 0 ≤ i < j.

Extended Midy's Theorem

Theorem (Original)

If the period of a repeating decimal for $a/p$, where p is prime and $a/p$ is a reduced fraction, has an even number of digits, then dividing the repeating portion into halves and adding gives a string of 9s. For example, $1/7$ = 0.142857…, and 142 + 857 = 999.

Theorem (Extended)

If the period of a repeating decimal for $a/p$, where p is prime and $a/p$ is a reduced fraction, is h = $m \times n$, then dividing the repeating portion into n parts and adding gives $c_n(a,p)$ × 9 m's, where c is a constant depending on p, a and n.

Click here for my proof.