[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
Thu Jan 23 17:56:55 CET 2020
I've now also established that a(n) = 3 for all n >= 39 for the 'smallest prime factor' version of this sequence. This doesn't involve parity considerations as the 'largest prime factor' version did, or any other mathematically very elegant technique, just establishing that if the calculation goes through a particular stage (specifically the A(n,45) = 45 + A(n,46)/F(A(n,46)) stage), it must end up at 3, and determining which a(n) whose calculations don't go through that stage end up at 2.
>From my previous posts, we know that the elements of the triangular array A(n,m) defined in it for 1 <= m <= n have the properties that A(n,m) >= m, with equality if and only if n=m, and that A(n,m) < 2m+2. In particular, those imply that a(n) = A(n,1) is 2 or 3 in all cases except a(1) = A(1,1) = 1. Furthermore, A(n,m) is defined in such a way that the sequence of values A(n,m), A(n,m-1), A(n,m-2), ... A(n,1) is determined by A(n,m) and m, without any further dependence on n - i.e. if A(n1,m) = A(n2,m), then A(n1,i) = A(n2,i) for all i <= m, and in particular a(n1) = a(n2).
This means that for each m, we can partition the possible values of A(n,m), which range from m to 2m+1 (both ends inclusive), into the set of those that eventually lead to a(n) = 2 and the set of those that eventually lead to a(n) = 3. Let S2(m) and S3(m) be those two sets respectively.
To determine S2(2) and S3(2), look at what each of the possible values 2,3,4,5 maps to under the transformation i --> 1+i/F(i), where F(i) is the smallest prime factor of i: 2 --> 1+2/2 = 2; 3 --> 1+3/3 = 2; 4 --> 1+4/2 = 3; 5 --> 1+5/5 = 2. This says that S2(2) = {2,3,5}, S3(2) = {4}.
To determine S2(3) and S3(3), look at what each of the possible values 3,4,5,6,7 maps to under the transformation i --> 2+i/F(i), and then look at which of S2(2) and S3(2) contains the result: 3 --> 2+3/3 = 3, which is in S2(2); 4 --> 2+4/2 = 4, which is in S3(2); 5 --> 2+5/5 = 3, which is in S2(2); 6 --> 2+6/2 = 5, which is in S2(2); 7 --> 2+7/7 = 3, which is in S2(2). This says that S2(3) = {3,5,6,7}, S3(3) = {4}.
To determine S2(4) and S3(4), look at what each of the possible values 4,5,6,7,8,9 maps to under the transformation i --> 3+i/F(i), and then look at which of S2(3) and S3(3) contains the result: 4 --> 3+4/2 = 5, which is in S2(3); 5 --> 3+5/5 = 4, which is in S3(3); 6 --> 3+6/2 = 6, which is in S2(3); 7 --> 3+7/7 = 4, which is in S3(3); 8 --> 3+8/2 = 7, which is in S2(3); 9 --> 3+9/3 = 6, which is in S2(3). This says that S2(4) = {4,6,8,9}, S3(4) = {5,7}.
To determine S2(5) and S3(5), look at what each of the possible values 5,6,7,8,9,10,11 maps to under the transformation i --> 4+i/F(i), and then look at which of S2(4) and S3(4) contains the result: 5 --> 4+5/5 = 5, which is in S3(4); 6 --> 4+6/2 = 7, which is in S3(4); 7 --> 4+7/7 = 5, which is in S3(4); 8 --> 4+8/2 = 8, which is in S2(4); 9 --> 4+9/3 = 7, which is in S3(4); 10 --> 4+10/2 = 9, which is in S2(4); 11 --> 4+11/11 = 5, which is in S3(4}. This says that S2(5) = {8,10}, S3(5) = {5,6,7,9,11}.
And so on... I've written a program to calculate these sets, since the hand calculations are both tedious and error-prone, and its output starts:
S2(2) = {2,3,5}, S3(2) = {4}
S2(3) = {3,5,6,7}, S3(3) = {4}
S2(4) = {4,6,8,9}, S3(4) = {5,7}
S2(5) = {8,10}, S3(5) = {5,6,7,9,11}
S2(6) = {6,9,10}, S3(6) = {7,8,11,12,13}
S2(7) = {8,9}, S3(7) = {7,10,11,12,13,14,15}
S2(8) = {11,13,17}, S3(8) = {8,9,10,12,14,15,16}
S2(9) = {9,10,15,18}, S3(9) = {11,12,13,14,16,17,19}
S2(10) = {11,12,13,17,18,19}, S3(10) = {10,14,15,16,20,21}
S2(11) = {11,13,14,16,17,18,19,21,23}, S3(11) = {12,15,20,22}
S2(12) = {12,14,15,16,20,21,24,25}, S3(12) = {13,17,18,19,22,23}
S2(13) = {16,18,24,26,27}, S3(13) = {13,14,15,17,19,20,21,22,23,25}
S2(14) = {15,22,25,26,28}, S3(14) = {14,16,17,18,19,20,21,23,24,27,29}
S2(15) = {16,17,19,22,23,24,28,29,31}, S3(15) = {15,18,20,21,25,26,27,30}
S2(16) = {16,17,18,19,21,23,26,27,28,29,31,32}, S3(16) = {20,22,24,25,30,33}
S2(17) = {17,19,20,21,22,23,24,25,26,29,30,31,32,33,35}, S3(17) = {18,27,28,34}
S2(18) = {18,21,24,25,26,27,28,30,32,35,36}, S3(18) = {19,20,22,23,29,31,33,34,37}
S2(19) = {20,21,24,27,28,34,35,36}, S3(19) = {19,22,23,25,26,29,30,31,32,33,37,38,39}
S2(20) = {23,25,27,29,30,31,32,34,37,41}, S3(20) = {20,21,22,24,26,28,33,35,36,38,39,40}
S2(21) = {21,22,24,25,27,28,33,34,35,42}, S3(21) = {23,26,29,30,31,32,36,37,38,39,40,41,43}
S2(22) = {23,24,26,28,29,31,35,37,39,41,42,43}, S3(22) = {22,25,27,30,32,33,34,36,38,40,44,45}
S2(23) = {23,26,27,29,30,31,34,35,37,38,39,40,41,42,43,45,47}, S3(23) = {24,25,28,32,33,36,44,46}
S2(24) = {24,28,30,32,33,34,35,36,38,40,44,45,48,49}, S3(24) = {25,26,27,29,31,37,39,41,42,43,46,47}
S2(25) = {27,28,32,33,40,42,48,50}, S3(25) = {25,26,29,30,31,34,35,36,37,38,39,41,43,44,45,46,47,49,51}
S2(26) = {30,34,35,45,46,49,50,51}, S3(26) = {26,27,28,29,31,32,33,36,37,38,39,40,41,42,43,44,47,48,52,53}
S2(27) = {27,38,40,46,48,50}, S3(27) = {28,29,30,31,32,33,34,35,36,37,39,41,42,43,44,45,47,49,51,52,53,54,55}
S2(28) = {33,38,39,42,46,55,57}, S3(28) = {28,29,30,31,32,34,35,36,37,40,41,43,44,45,47,48,49,50,51,52,53,54,56}
S2(29) = {33,36,54,55,58}, S3(29) = {29,30,31,32,34,35,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,56,57,59}
S2(30) = {35,49,50,52,58}, S3(30) = {30,31,32,33,34,36,37,38,39,40,41,42,43,44,45,46,47,48,51,53,54,55,56,57,59,60,61}
S2(31) = {38,40,44,56,57}, S3(31) = {31,32,33,34,35,36,37,39,41,42,43,45,46,47,48,49,50,51,52,53,54,55,58,59,60,61,62,63}
S2(32) = {35,39,49,50,52,65}, S3(32) = {32,33,34,36,37,38,40,41,42,43,44,45,46,47,48,51,53,54,55,56,57,58,59,60,61,62,63,64}
S2(33) = {34,35,36,40,49,51,66}, S3(33) = {33,37,38,39,41,42,43,44,45,46,47,48,50,52,53,54,55,56,57,58,59,60,61,62,63,64,65,67}
S2(34) = {35,36,37,41,43,47,49,53,59,61,66,67}, S3(34) = {34,38,39,40,42,44,45,46,48,50,51,52,54,55,56,57,58,60,62,63,64,65,68,69}
S2(35) = {35,37,38,39,41,43,45,47,49,50,53,54,57,59,61,64,65,66,67,71}, S3(35) = {36,40,42,44,46,48,51,52,55,56,58,60,62,63,68,69,70}
S2(36) = {36,38,44,45,48,52,57,58,60,62,64,72}, S3(36) = {37,39,40,41,42,43,46,47,49,50,51,53,54,55,56,59,61,63,65,66,67,68,69,70,71,73}
S2(37) = {42,44,48,52,56,63,72}, S3(37) = {37,38,39,40,41,43,45,46,47,49,50,51,53,54,55,57,58,59,60,61,62,64,65,66,67,68,69,70,71,73,74,75}
S2(38) = {38,45,49,52,55,57,70,77}, S3(38) = {39,40,41,42,43,44,46,47,48,50,51,53,54,56,58,59,60,61,62,63,64,65,66,67,68,69,71,72,73,74,75,76}
S2(39) = {49,51,55,57,64,77,78}, S3(39) = {39,40,41,42,43,44,45,46,47,48,50,52,53,54,56,58,59,60,61,62,63,65,66,67,68,69,70,71,72,73,74,75,76,79}
S2(40) = {50,75,76,78}, S3(40) = {40,41,42,43,44,45,46,47,48,49,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,77,79,80,81}
S2(41) = {70,72,76}, S3(41) = {41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,71,73,74,75,77,78,79,80,81,82,83}
S2(42) = {58,62,70}, S3(42) = {42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,59,60,61,63,64,65,66,67,68,69,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85}
S2(43) = {56}, S3(43) = {43,44,45,46,47,48,49,50,51,52,53,54,55,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87}
S2(44) = {65}, S3(44) = {44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89}
S2(45) = {63}, S3(45) = {45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91}
S2(46) = {}, S3(46) = {46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93}
And the fact that S2(46) is the empty set is basically the answer to the question: none of the possible values going into the A(n,45) = 45 + A(n,46)/F(A(n,46)) stage of the algorithm end up with the algorithm producing a result of a(n) = 2. Since a(n) must be 2 or 3 for all n > 1, this implies that a(n) = 3 for n >= 46. And we can read off the smaller values of n for which a(n) = 2 from these results: they are the ones for which S2(n) contains n, which are 2, 3, 4, 6, 9, 11, 12, 16, 17, 18, 21, 23, 24, 27, 35, 36 and 38.
So in fact a(n) = 3 for all n >= 39.
David
> On 22 January 2020 at 08:38 David Seal <david.j.seal at gwynmop.com> wrote:
>
>
> 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/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list