[seqfan] Re: Arithmetic progressions of numbers with the same prime signature

[Alexander P-sky]

So David - you are tacitly addressing below discussion dated by 2006 -
2007 ... - correct ?
Did you submit any changes to A113459, based on your latest email ?
====================================================
>Conjecture: For n > 1, a(n) = A007918(n). - David Wasserman >(dwasserm(AT)earthlink.net), Jan 08 2006

>I disagree with that conjecture! Ignoring the initial terms, this will agree with A007918 up to >some point and then (presumably) drop below A007918. The initial term in the arithmetic >progression (of length n) must be >= n, but it is likely to be less than A007918(n) if n is >large. - N. J. A. Sloane (njas(AT)research.att.com), Oct 18 2007
===========================================================
On 5/17/11, David Wasserman <dwasserm at earthlink.net> wrote:
> 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.
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>