[seqfan] Re: Are we going to get anything other than 2’s and 3’s from this algorithm?
David Seal
david.j.seal at gwynmop.com
Tue Jan 21 12:06:04 CET 2020
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/
More information about the SeqFan
mailing list