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

[Ali Sada]

 Hi David,
Nice work! It is a good thing that you, Lars, and other Seqfan scholars check the results I find. Otherwise, the world would have had a totally different kind of math :)
The remaining questions are related to Lars's findings: Why do we have a continuous  2 2 3 3 pattern in the first version? And why do we have only 3's after n = 38 in the second version? 

Also, if that was fine with the OEIS team, would you please add your array to the OEIS? I could add it myself, but I would need help with the right definition.
Best,
Ali


    On Tuesday, January 21, 2020, 10:35:39 AM EST, 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/