[seqfan] Arithmetic progressions of numbers with the same prime signature
David Wasserman
dwasserm at earthlink.net
Tue May 17 09:20:46 CEST 2011
Throughout I will use APPS as an abbreviation for "increasing arithmetic progression of numbers with the same prime signature".
http://oeis.org/A113459 gives the least number that begins an APPS of length n. This sequence begins 1, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11, 13. Observe that terms 2 through 12 agree with A007918 (nextprime(n)). I now have strong evidence for this pattern continuing.
Dickson's conjecture (http://primes.utm.edu/glossary/xpage/DicksonsConjecture.html; http://en.wikipedia.org/wiki/Dickson%27s_conjecture) implies that for p prime, there is an APPS of length p beginning with p, which implies that A113459(n) <= nextprime(n). To get a lower bound, consider this sequence:
a(n) = length of longest APPS starting with n.
This sequence begins 1, 2, 3, 2, 5, 3, 7, 2, 2, 5, 11, 3, 13, 7, 6, 2, 17, 3. Note that "A113459(n) >= nextprime(n) for all n > 1" is equivalent to "a(n) <= precprime(n) for all n > 1".
I have theorems (below) that give upper bounds on a(n) for all n > 1. We always have a(n) <= n, and equality is possible only when n is prime. For n composite, the closest a(n) can be to n is when n is a product of twin primes p < q. In this case the upper bound is a(n) <= p*(p - 1), so n - a(n) >= 3p. Therefore A113459(n) > nextprime(n) is possible only if there is a prime p followed by a prime gap larger than 3*sqrt(p).
Also, I believe that for squarefree n, my upper bound for a(n) given in Corollary 2 is an equality, because modular arithmetic provides no obstacle to the existence of an APPS of that length.
Here are the theorems. Throughout we assume n > 1.
Theorem 1: Let n = p_1^e_1*...*p_k^e_k, and let e = max(e_1, ..., e_k). Then a(n) <= max(p_1^(e+1) - p_1^e_1, a(n/p_1^e_1)).
Proof: Let f be the highest integer such that p_1^f divides d.
Case 1: f > e_1 Then all terms of S are divisible by p_1^e_1 but not by p_1^(e_1 + 1). Therefore S/p_1^e_1 is an APPS beginning with n/p_1^e_1, so its length is at most a(n/p_1^e_1)).
Case 2: f <= e_1. d/p_1^f is not divisible by p, so it has an inverse modulo p_1^(e + 1 - f); let a be this inverse, so 0 < a < p_1^(e + 1 - f), a is not divisible by p, and ad/p_1^f = 1 mod p_1^(e + 1 - f). Let b = -n/p_1^f mod p_1^(e + 1 - f). Since p_1^(e + 1) does not divide n, p_1^(e + 1 - f) does not divide -n/p_1^f, so 0 < b < p_1^(e + 1 - f). Then since a is not divisible by p and b is not divisible by p_1^(e + 1 - f), ab is not divisible by p_1^(e + 1 - f). Let c = ab mod p_1^(e + 1 - f); then 0 < c <= p_1^(e + 1 - f) - 1 and cd = -n/p_1^f mod p_1^(e + 1 - f). Let g = c*p_1^f; then g <= p_1^f(p_1^(e + 1 - f) - 1) = p_1^(e + 1) - p_1^f <= p_1^(e + 1) - p_1^e_1, and gd = -n mod p_1^(e + 1). Therefore S_g = n + gd = 0 mod p_1^(e + 1); in other words S_g is divisible by p_1^(e + 1), but e + 1 is greater than any exponent in the prime signature of n, so S has length at most g, and g <= p_1^(e + 1) - p_1^e_1.
Corollary 2: If n is a product of distinct primes p_1 <= ... <= p_k, then a(n) <= max(p_(k - 1)^2 - p_(k - 1), p_k).
Proof: Theorem 1 shows a(p_(k - 1)*p_k) <= max(p_(k - 1)^2 - p_(k - 1), p_k). Then repeated applications of Theorem 1 show that the smaller prime factors do not increase this maximum.
Theorem 3: Let p_1^e_1*...*p_k^e_k. Then a(n) <= p_1*...*p_k*k!.
Proof: Let x = p_1*...*p_k. Then S_mx = n + mxd. Since both n and mx are divisible by x, S_mx is divisible by x. Since S_mx is divisible by all prime factors of n and has the same prime signature as n, it must be f(p_1)^e_1*...*f(p_k)^e_k for some non-identity permutation f of {1, ..., k}. Then S can not extend to S_(k!*x), because that would require S_x, S_2x, ... S_(k!*x) to correspond to k! different non-identity permutations. In fact a(n) = p_1*...*p_k*k! is possible only if the e_i are all distinct. A better bound is p_1*...*p_k*c where c is the number of distinct permutations of (e_1, ..., e_k).
Theorem 4: a(n) <= n, with equality possible only if n is prime.
Proof: By induction on the number of distinct primes dividing n. If n = p^e, then by Theorem 3, a(n) <= p <= p^e. If n = p_1^e_1*...*p_k^e_k with k > 1, then renumber the p_i's so p_1 is the smallest. By the induction hypothesis a(n/p_1^e_1) <= n/p_1^e_1 < n. Now let e = max(e_1, ..., e_k).
Case 1: e = e_1. Then p_1^(e+1) - p_1^e_1= p_1^(e_1+1) - p_1^e_1 = p_1^e_1*(p_1 - 1) < p_1^e_1*p_2 <= n.
Case 2: e > e_1. Then there is i > 1 such that e_i = e. Then p_1^(e+1) - p_1^e_1 = p_1^e_1*(p_1^(e - e_1 + 1) - 1) < p_1^e_1*p_1^e < p_1^e_1*p_i^e_i <= n.
In both cases p_1^(e+1) - p_1^e_1 < n, and we already showed a(n/p_1^e_1) < n, so by Theorem 1 a(n) < n.
Theorem 5: If n is composite then either n >= 2a(n) or n > a(n) + 3*sqrt(a(n)).
Proof:
Case 1: n = p^e for e > 1. Then a(n) <= p <= n/p <= n/2. So n >= 2a(n)
Case 2: n = p_1^e_1*...*p_k^e_k with k > 1. Renumber the p_i's so p_1 is the smallest. Let e = max(e_1, ..., e_k). By Theorem 1 either a(n) <= p_1^(e+1) - p_1^e_1 or a(n) <= a(n/p_1^e_1).
Case 2a: a(n) <= p_1^(e+1) - p_1^e_1.
Case 2a(i): e = e1. Then a(n) <= p_1^(e+1) - p_1^e_1= p_1^(e_1+1) - p_1^e_1 = p_1^e_1*(p_1 - 1). If k > 2 or e_2 > 1, then n/2 >= n/e_k >= p_1^e_1*p_2 > p_1^e_1*(p_1 - 1) >= a(n) and we are done with this case. So assume n = p_1^e_1*p_2. Then n - a(n) >= p_1^e_1*p_2 - p_1^(e_1+1) + p_1^e_1 = p_1^e_1(p_2 + 1 - p1) >= 3*p_1^e_1 = 3*sqrt(p_1^(2e_1)) >= 3*sqrt(p_1^(e_1 + 1)) > 3*sqrt(p_1^(e_1 + 1) - p_1^e_1) >= 3*sqrt(a(n)). So n > a(n) + 3*sqrt(a(n)).
Case 2a(ii): e > e_1. Let e = e_j. If k > 2 or e_1 > 1, then n >= 2*p_1*p_j^e > 2*p_1^(e+1) > 2*a(n) and we are done with this case. So assume n = p_1*p_2^e. Then n - a(n) >= p_1*(1 + p_2^e - p_1^e) > p_1*(p_2^e - p_1^e) = p_1*(p_2 - p_1)*(p_2^(e - 1) + p_1*p_2^(e - 2) + ... + p_1^(e - 2)*p_2 + p_1^(e - 1)) >= 2p_1*(p_2^(e - 1) + p_1^(e - 1)) > 4p_1^e = 4*sqrt(p1^(2e)) >= 4*sqrt(p1^(e + 1)) > 4*sqrt(a(n)).
Case 2b: a(n) <= a(n/p_1^e_1). Then by Theorem 4 a(n) <= n/p_1^e_1 <= n/2.
More information about the SeqFan
mailing list