[seqfan] Re: Are we going to get anything other than 2’s and 3’s from this algorithm?

Wed Jan 22 09:38:40 CET 2020

The 2,2,3,3 pattern for the case that F(i) is the largest prime factor of i persists forever after the two exceptional cases a(1)=1 and a(2)=2. To see this, note first that i/F(i) has the same parity as i for all i > 2, because:

* if i is not a power of 2, then F(i) is an odd prime, so that the parities in F(i) * (i/F(i)) = i are either odd * odd = odd or odd * even = even, and so i/F(i) and i are either both odd or both even;

* if i is a power of 2 greater than 1, say i=2^n for n>0, then F(i) = 2 and i/F(i) = 2^(n-1), and except in the case n=1, 2^n and 2^(n-1) are both even.

Now observe in the table of A(n,m) I gave in my last post (quoted below) that for n >= 3, the parity of A(n,m) appears to follow a "checkerboard of 2x2 squares" pattern, namely that it is:

* odd if n is 1 or 2 mod 4 and m is 0 or 1 mod 4;
* even if n is 1 or 2 mod 4 and m is 2 or 3 mod 4;
* even if n is 0 or 3 mod 4 and m is 0 or 1 mod 4;
* odd if n is 0 or 3 mod 4 and m is 2 or 3 mod 4.

That pattern is easily provable by induction:

* The base case for each fixed n is that A(n,n) = n follows that pattern, which is easily verifiable for each of the four cases of n being 0, 1, 2 or 3 mod 4.

* If m<n, then we know that A(n,m+1) is at least 3, since either m+1 < n and A(n,m+1) = (m+1) + A(n,m+2)/F(A(n,m+2)) >= (1+1) + 1 = 3, or m+1 = n and A(n,m+1) = n >= 3. So A(n,m+1)/F(A(n,m+1)) has the same parity as A(n,m+1) by the above, from which it follows that A(n,m) = m + A(n,m+1)/F(A(n,m+1)) has the same parity as A(n,m+1) if m is even and the opposite parity if m is odd. Those parity relationships are exactly what the "checkerboard of 2x2 squares" pattern above produces for each fixed n, with A(n,m) having one parity if m is 0 or 1 mod 4 and the opposite parity if it is 2 or 3 mod 4.

As a special case of that pattern, it says that for n >= 3, a(n) = A(n,1) is odd if n is 1 or 2 mod 3 and even if n is 0 or 3 mod 4. Also, a(n) < 4 as proved in my last post, and a(n) = A(n,1) = 1 + A(n,2)/F(A(n,2)) >= 1+1 = 2, which only leaves one possibility for A(n) for any n >= 3: a(n) = 3 if n is 1 or 2 mod 4, 2 if n is 0 or 3 mod 4. So the 2,2,3,3 pattern will persist for all n >= 3.

David

> On 21 January 2020 at 11:06 David Seal <david.j.seal at gwynmop.com> wrote:
> 
> 
> To make it possible for me to refer to all the integers obtained during this, I need to define the numbers obtained during the algorithm more formally. Define A(n,m) for n >= m >= 1 by:
> 
> A(n,n) = n
> A(n,m) = m + A(n,m+1)/F(A(n,m+1)) if m < n
> 
> where F(i) is a function that produces a prime factor of i (the functions producing the largest prime factor and the smallest prime factor are your two specific cases). A(n,m) for fixed n and variable m is the finite sequence of integers obtained during your algorithm to calculate a(n), in reverse order, and so a(n) = A(n,1). The triangular array of integers A(n,m) starts (for n on the vertical axis, m on the horizontal axis):
> 
>   1
>   2  2
>   2  3  3
>   2  3  5  4
>   3  4  4  5  5
>   3  4  4  5  7  6
>   2  3  5  6  6  7  7
>   2  3  5  6  6  7 11  8
>   3  4  4  5  7 10  8 11  9
>   3  4  4  7  9  8 10  9 11 10
>   2  3  7  8  8  9  9 10 10 11 11
>   2  3  7  8  8  9  9 10 10 13 15 12
>   3  4  4  7  9  8 10  9 11 14 12 13 13
>   3  4  4  7  9  8 10  9 13 12 14 15 15 14
>   2  3  7  8  8  9  9 10 10 11 13 14 14 17 15
>   2  3  7  8  8  9  9 10 10 13 15 20 16 15 23 16
>   :  :  :  :  :  :  :  :  :  :  :  :  :  :  :  : .
> 
> The question is whether we're ever going to get a value A(n,1) >= 4 in the first column. We don't for A(1,1) = 1, and for n>1, A(n,1) = 1 + A(n,2)/F(A(n,2)). So that's equivalent to asking whether we're ever going to get a value A(n,2) in the second column such that A(n,2)/F(A(n,2)) >= 4-1 = 3, which together with F(A(2,n)) >= 2 implies that A(2,n) >= 6. So to get a value A(n,1) > 3 in the first column, we must get a value A(n,2) >= 6 in the second column (note this is only a necessary condition, not a sufficient one - e.g. if we were to get a value A(n,2) = 7 in the second column, it would produce A(n,1) = 1+1 = 2, which is not > 3).
> 
> A similar argument observes that A(2,2) = 2 is not >= 6 and that A(n,2) = 2 + A(n,3)/F(A(n,3)) for n > 2 shows that in order to get a value A(n,2) > 5, we must get a value A(n,3) in the third column such that A(n,3)/F(A(n,3)) > 6-2 = 4, which together with F(A(n,3)) >= 2 implies that A(n,3) >= 8. So to get a value A(n,2) >= 6 in the second column, we must get a value A(n,3) >= 8 in the third column. And that argument fairly clearly generalises to say that we must get a value A(n,4) >= 10 in the fourth column, a value A(n,5) >= 12 in the fifth column, etc, until we run into the contradiction that A(n,n) = n isn't big enough.
> 
> That's basically how I worked out to my satisfaction that we won't ever get a value >= 4 for a(n) = A(n,1), or more generally a value >= 2m+2 for A(n,m). Turning the argument around to make it into a formal proof by induction of the latter, i.e. that A(n,m) < 2m+2 in all cases, we need to show:
> 
> * The base case A(n,n) < 2n+2. Since A(n,n) is defined to be n and n >= 1, this is trivial.
> 
> * That for m < n, A(n,m) < 2m+2 follows from the inductive hypothesis that A(n,m+1) < 2(m+1)+2 = 2m+4. To see this, note that A(n,m+1) >= m+1 > 1 by definition, so must have prime factors, and F(A(n,m+1)) is a prime factor of A(n,m+1), so must be >= 2. So the inductive hypothesis implies that A(n,m+1)/F(A(n,m+1)) < (2m+4)/2 = m+2, which in turn implies that A(n,m) = m + A(n,m+1)/F(A(n,m+1)) < m + (m+2) = 2m+2. That completes the proof.
> 
> I conclude that no matter what prime-factor-picking function F() is used, all values of a(n) are <= 3. This implies that either I've misunderstood what you're doing or there's an error in your calculation that a(273) = 4 for the case that F(i) is the least prime factor of i.
> 
> Lars Blomberg seems to have come to a similar conclusion, though by calculations rather than proofs.
> 
> David
> 
> 
> > On 20 January 2020 at 04:08 Ali Sada via SeqFan <seqfan at list.seqfan.eu> wrote:
> > 
> > 
> > Hi Everyone,
> > 
> > Please consider the following algorithm: Divide n by its largest prime factor and add the result to n-1. Continue with the same algorithm until we go back to 1. 
> > 
> > For example, to find a(6):
> > 6/3 = 2
> > 5+2 = 7, 7/7 = 1
> > 4+1 = 5, 5/5 = 1
> > 3+1 = 4, 4/2 = 2
> > 2+2 = 4, 4/2 = 2
> > 1+2 = 3 --> a(6) = 3
> > 
> > The routes to reach the terms produce interesting numbers, but the sequence itself is not that diverse. 
> > 
> > After a(1) = 1, the sequence's terms are either 2’s or 3’s. (The 2 means that the number in the semifinal step is a prime.) Between n = 3 and n = 950, the combination 2, 2, 3, 3 was constant. But it changed after that. The semifinal numbers were 2 if a(n) = 3, and 3 if a(n)= 2. 
> > 
> > I couldn’t go beyond n = 1000 because of problems with the software I am using. I would really appreciate it if you could help me find more terms. 
> > 
> > It seemed logical to try to find what it would need to make a(n) = 4, for example, using a counter-algorithm. But in this case, I had to guess what the prime factors were. Even if the prime factor were 2 in every step, the counter-algorithm goes to high numbers very quickly. 
> > 
> > When I used the same algorithm, replacing “the largest prime factor” with “the least prime factor”, the results were also interesting. After a(1) = 1, The first terms are either 2’s or 3’s. Then, at n = 39, 2 disappears and we get a string of 3’s. The first 4 appears at n = 273. Then, 3 becomes less frequent. Between n = 675 and 1000, there are only 4’s. It seems like we are going to see 5, 6, 7, etc. in this version, but I am not sure. 
> > 
> > 
> > Best,
> > 
> > Ali
> > 
> >  
> > 
> > 
> > 
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/