[math-fun] Another Lex. Earliest Sequence: Scott Shannon's "Enots Wolley sequence A336957
Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names. Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version. Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ? I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem. Neil
Already posted on August 11th ?! WFL On 8/16/20, Neil Sloane <njasloane@gmail.com> wrote:
Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names.
Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version.
Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ?
I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem.
Neil _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
hihi, all - i wrote a program to generate terms to n=1000 (i still need to verify it, but it matches what was in this e-mail) it is a curious fact that the gcd of successive terms is a prime, up to a point, and mostly in any case i'll have more in a few days more later, chris On Sun, Aug 16, 2020 at 6:04 AM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Already posted on August 11th ?!
WFL
On 8/16/20, Neil Sloane <njasloane@gmail.com> wrote:
Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names.
Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version.
Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ?
I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem.
Neil _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- dr. christopher landauer topcy house consulting thousand oaks, california
Chris, what is the smallest eligible (non-prime-power) number your list leaves out? On Sun, Aug 16, 2020 at 5:55 PM Christopher Landauer <topcycal@gmail.com> wrote:
hihi, all - i wrote a program to generate terms to n=1000 (i still need to verify it, but it matches what was in this e-mail)
it is a curious fact that the gcd of successive terms is a prime, up to a point, and mostly in any case
i'll have more in a few days
more later, chris
On Sun, Aug 16, 2020 at 6:04 AM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Already posted on August 11th ?!
WFL
On 8/16/20, Neil Sloane <njasloane@gmail.com> wrote:
Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names.
Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version.
Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ?
I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem.
Neil _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- dr. christopher landauer topcy house consulting thousand oaks, california _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
hihi - i'll write a script for that, to show the largest a[n] and first missing acceptable number for values of n up to nmax for various nmax; it does look like the sequence eventually fills in all of them meanwhile, here are the first 100 values - again, not yet completely verified, but i think pretty close: it took me a while to find a good (easily computable) criterion for unacceptability, so here is what i used: for a prospective value b for a[n], if every prime dividing b also divides the previously computed a[n-1], then there would be no acceptable a[n+1], so b is unacceptable (otherwise b is acceptable, since the a[n+1] can use only the primes not also in a[n-1]) the program generates values up to n=10000 in just under a minute on a 5 year old commodity pc running freebsd, so if we get some conjectures, a lot of experimentation can be done f = gcd(a[n], a[n-1]) is prime a lot a[1] = 1 a[2] = 2 a[3] = 6 f = 2 a[4] = 15 f = 3 a[5] = 35 f = 5 a[6] = 14 f = 7 a[7] = 12 f = 2 a[8] = 33 f = 3 a[9] = 55 f = 11 a[10] = 10 f = 5 a[11] = 18 f = 2 a[12] = 21 f = 3 a[13] = 77 f = 7 a[14] = 22 f = 11 a[15] = 20 f = 2 a[16] = 45 f = 5 a[17] = 39 f = 3 a[18] = 26 f = 13 a[19] = 28 f = 2 a[20] = 63 f = 7 a[21] = 51 f = 3 a[22] = 34 f = 17 a[23] = 38 f = 2 a[24] = 57 f = 19 a[25] = 69 f = 3 a[26] = 46 f = 23 a[27] = 40 f = 2 a[28] = 65 f = 5 a[29] = 91 f = 13 a[30] = 42 f = 7b is unacceptable a[31] = 30 f = 6 NOT prime a[32] = 85 f = 5 a[33] = 119 f = 17 a[34] = 56 f = 7 a[35] = 24 f = 8 NOT prime a[36] = 75 f = 3 a[37] = 95 f = 5 a[38] = 76 f = 19 a[39] = 36 f = 4 NOT prime a[40] = 87 f = 3 a[41] = 145 f = 29 a[42] = 50 f = 5 a[43] = 44 f = 2 a[44] = 99 f = 11 a[45] = 93 f = 3 a[46] = 62 f = 31 a[47] = 52 f = 2 a[48] = 117 f = 13 a[49] = 105 f = 3 a[50] = 70 f = 35 NOT prime a[51] = 58 f = 2 a[52] = 261 f = 29 a[53] = 111 f = 3 a[54] = 74 f = 37 a[55] = 68 f = 2 a[56] = 153 f = 17 a[57] = 123 f = 3 a[58] = 82 f = 41 a[59] = 80 f = 2 a[60] = 115 f = 5 a[61] = 161 f = 23 a[62] = 84 f = 7 a[63] = 60 f = 12 NOT prime a[64] = 155 f = 5 a[65] = 217 f = 31 a[66] = 98 f = 7 a[67] = 48 f = 2 a[68] = 129 f = 3 a[69] = 215 f = 43 a[70] = 100 f = 5 a[71] = 54 f = 2 a[72] = 141 f = 3 a[73] = 235 f = 47 a[74] = 110 f = 5 a[75] = 66 f = 22 NOT prime a[76] = 147 f = 3 a[77] = 133 f = 7 a[78] = 152 f = 19 a[79] = 72 f = 8 NOT prime a[80] = 135 f = 9 NOT prime a[81] = 175 f = 5 a[82] = 112 f = 7 a[83] = 78 f = 2 a[84] = 143 f = 13 a[85] = 187 f = 11 a[86] = 102 f = 17 a[87] = 86 f = 2 a[88] = 301 f = 43 a[89] = 189 f = 7 a[90] = 90 f = 9 NOT prime a[91] = 88 f = 2 a[92] = 209 f = 11 a[93] = 171 f = 19 a[94] = 96 f = 3 a[95] = 92 f = 4 NOT prime a[96] = 253 f = 23 a[97] = 165 f = 11 a[98] = 108 f = 3 a[99] = 94 f = 2 a[100] = 329 f = 47 more later, chris On 2020-08-16 15:02, Allan Wechsler wrote:
Chris, what is the smallest eligible (non-prime-power) number your list leaves out?
On Sun, Aug 16, 2020 at 5:55 PM Christopher Landauer <topcycal@gmail.com> wrote:
hihi, all - i wrote a program to generate terms to n=1000 (i still need to verify it, but it matches what was in this e-mail)
it is a curious fact that the gcd of successive terms is a prime, up to a point, and mostly in any case
i'll have more in a few days
more later, chris
On Sun, Aug 16, 2020 at 6:04 AM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Already posted on August 11th ?!
WFL
On 8/16/20, Neil Sloane <njasloane@gmail.com> wrote:
Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names.
Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version.
Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ?
I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem.
Neil _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- dr. christopher landauer topcy house consulting thousand oaks, california _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I'm a believer now. It hits all acceptable values. I further think somebody cleverer than me will be able to prove it. Nothing about it feels "out of reach". First baby step: prove that the sequence contains an infinite number of even values. On Sun, Aug 16, 2020 at 10:25 PM christopher landauer <topcycal@gmail.com> wrote:
hihi -
i'll write a script for that, to show the largest a[n] and first missing acceptable number for values of n up to nmax for various nmax;
it does look like the sequence eventually fills in all of them
meanwhile, here are the first 100 values -
again, not yet completely verified, but i think pretty close:
it took me a while to find a good (easily computable) criterion for unacceptability, so here is what i used:
for a prospective value b for a[n], if every prime dividing b also divides the previously computed a[n-1],
then there would be no acceptable a[n+1], so b is unacceptable
(otherwise b is acceptable, since the a[n+1] can use only the primes not also in a[n-1])
the program generates values up to n=10000 in just under a minute on a 5 year old commodity pc running freebsd,
so if we get some conjectures, a lot of experimentation can be done
f = gcd(a[n], a[n-1]) is prime a lot
a[1] = 1 a[2] = 2 a[3] = 6 f = 2 a[4] = 15 f = 3 a[5] = 35 f = 5 a[6] = 14 f = 7 a[7] = 12 f = 2 a[8] = 33 f = 3 a[9] = 55 f = 11 a[10] = 10 f = 5
a[11] = 18 f = 2 a[12] = 21 f = 3 a[13] = 77 f = 7 a[14] = 22 f = 11 a[15] = 20 f = 2 a[16] = 45 f = 5 a[17] = 39 f = 3 a[18] = 26 f = 13 a[19] = 28 f = 2 a[20] = 63 f = 7
a[21] = 51 f = 3 a[22] = 34 f = 17 a[23] = 38 f = 2 a[24] = 57 f = 19 a[25] = 69 f = 3 a[26] = 46 f = 23 a[27] = 40 f = 2 a[28] = 65 f = 5 a[29] = 91 f = 13 a[30] = 42 f = 7b is unacceptable
a[31] = 30 f = 6 NOT prime a[32] = 85 f = 5 a[33] = 119 f = 17 a[34] = 56 f = 7 a[35] = 24 f = 8 NOT prime a[36] = 75 f = 3 a[37] = 95 f = 5 a[38] = 76 f = 19 a[39] = 36 f = 4 NOT prime a[40] = 87 f = 3
a[41] = 145 f = 29 a[42] = 50 f = 5 a[43] = 44 f = 2 a[44] = 99 f = 11 a[45] = 93 f = 3 a[46] = 62 f = 31 a[47] = 52 f = 2 a[48] = 117 f = 13 a[49] = 105 f = 3 a[50] = 70 f = 35 NOT prime
a[51] = 58 f = 2 a[52] = 261 f = 29 a[53] = 111 f = 3 a[54] = 74 f = 37 a[55] = 68 f = 2 a[56] = 153 f = 17 a[57] = 123 f = 3 a[58] = 82 f = 41 a[59] = 80 f = 2 a[60] = 115 f = 5
a[61] = 161 f = 23 a[62] = 84 f = 7 a[63] = 60 f = 12 NOT prime a[64] = 155 f = 5 a[65] = 217 f = 31 a[66] = 98 f = 7 a[67] = 48 f = 2 a[68] = 129 f = 3 a[69] = 215 f = 43 a[70] = 100 f = 5
a[71] = 54 f = 2 a[72] = 141 f = 3 a[73] = 235 f = 47 a[74] = 110 f = 5 a[75] = 66 f = 22 NOT prime a[76] = 147 f = 3 a[77] = 133 f = 7 a[78] = 152 f = 19 a[79] = 72 f = 8 NOT prime a[80] = 135 f = 9 NOT prime
a[81] = 175 f = 5 a[82] = 112 f = 7 a[83] = 78 f = 2 a[84] = 143 f = 13 a[85] = 187 f = 11 a[86] = 102 f = 17 a[87] = 86 f = 2 a[88] = 301 f = 43 a[89] = 189 f = 7 a[90] = 90 f = 9 NOT prime
a[91] = 88 f = 2 a[92] = 209 f = 11 a[93] = 171 f = 19 a[94] = 96 f = 3 a[95] = 92 f = 4 NOT prime a[96] = 253 f = 23 a[97] = 165 f = 11 a[98] = 108 f = 3 a[99] = 94 f = 2 a[100] = 329 f = 47
more later,
chris
On 2020-08-16 15:02, Allan Wechsler wrote:
Chris, what is the smallest eligible (non-prime-power) number your list leaves out?
On Sun, Aug 16, 2020 at 5:55 PM Christopher Landauer <topcycal@gmail.com
wrote:
hihi, all - i wrote a program to generate terms to n=1000 (i still need to verify it, but it matches what was in this e-mail)
it is a curious fact that the gcd of successive terms is a prime, up to a point, and mostly in any case
i'll have more in a few days
more later, chris
On Sun, Aug 16, 2020 at 6:04 AM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Already posted on August 11th ?!
WFL
On 8/16/20, Neil Sloane <njasloane@gmail.com> wrote:
Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names.
Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version.
Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ?
I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem.
Neil _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- dr. christopher landauer topcy house consulting thousand oaks, california _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I have a nagging suspicion that a few of you working on this are not aware that this is a sequence with lots of existing information/commentary. Neil posted the sequence number in the very long title (at the very end) and my mail program's default setting deletes that ending (replacing it with an ellipsis) so that the subject line will fit in one line. Perhaps others are in the same perceptual boat. http://oeis.org/A336957
I just committed my computational effort on github : https://github.com/snakehand/woolly_mammoth - with sample output for the sequence ( up to a[n+1] < 1,000,000 ) Some observations, the sequence is extraordinarily greedy for smaller terms. There are some comments in the code ( src/main.rs ) that describe my algorithm. I have computed more than 2,500,000 terms and I can't see why any number with at least 2 prime factors should be left out of the sequence. There is one "dead end" check to ensure that a[n+1] has at least one factor that a[n] does not have. but the probability that this check causes a number to be skipped is very small, and is not correlated to whether it should fail in future checks. Neils conjecture seems very plausible, but I don't have a proof, only some probabilistic intuition. Cheers, Frank On Mon, Aug 17, 2020 at 4:25 AM christopher landauer <topcycal@gmail.com> wrote:
hihi -
i'll write a script for that, to show the largest a[n] and first missing acceptable number for values of n up to nmax for various nmax;
it does look like the sequence eventually fills in all of them
meanwhile, here are the first 100 values -
again, not yet completely verified, but i think pretty close:
it took me a while to find a good (easily computable) criterion for unacceptability, so here is what i used:
for a prospective value b for a[n], if every prime dividing b also divides the previously computed a[n-1],
then there would be no acceptable a[n+1], so b is unacceptable
(otherwise b is acceptable, since the a[n+1] can use only the primes not also in a[n-1])
the program generates values up to n=10000 in just under a minute on a 5 year old commodity pc running freebsd,
so if we get some conjectures, a lot of experimentation can be done
f = gcd(a[n], a[n-1]) is prime a lot
a[1] = 1 a[2] = 2 a[3] = 6 f = 2 a[4] = 15 f = 3 a[5] = 35 f = 5 a[6] = 14 f = 7 a[7] = 12 f = 2 a[8] = 33 f = 3 a[9] = 55 f = 11 a[10] = 10 f = 5
a[11] = 18 f = 2 a[12] = 21 f = 3 a[13] = 77 f = 7 a[14] = 22 f = 11 a[15] = 20 f = 2 a[16] = 45 f = 5 a[17] = 39 f = 3 a[18] = 26 f = 13 a[19] = 28 f = 2 a[20] = 63 f = 7
a[21] = 51 f = 3 a[22] = 34 f = 17 a[23] = 38 f = 2 a[24] = 57 f = 19 a[25] = 69 f = 3 a[26] = 46 f = 23 a[27] = 40 f = 2 a[28] = 65 f = 5 a[29] = 91 f = 13 a[30] = 42 f = 7b is unacceptable
a[31] = 30 f = 6 NOT prime a[32] = 85 f = 5 a[33] = 119 f = 17 a[34] = 56 f = 7 a[35] = 24 f = 8 NOT prime a[36] = 75 f = 3 a[37] = 95 f = 5 a[38] = 76 f = 19 a[39] = 36 f = 4 NOT prime a[40] = 87 f = 3
a[41] = 145 f = 29 a[42] = 50 f = 5 a[43] = 44 f = 2 a[44] = 99 f = 11 a[45] = 93 f = 3 a[46] = 62 f = 31 a[47] = 52 f = 2 a[48] = 117 f = 13 a[49] = 105 f = 3 a[50] = 70 f = 35 NOT prime
a[51] = 58 f = 2 a[52] = 261 f = 29 a[53] = 111 f = 3 a[54] = 74 f = 37 a[55] = 68 f = 2 a[56] = 153 f = 17 a[57] = 123 f = 3 a[58] = 82 f = 41 a[59] = 80 f = 2 a[60] = 115 f = 5
a[61] = 161 f = 23 a[62] = 84 f = 7 a[63] = 60 f = 12 NOT prime a[64] = 155 f = 5 a[65] = 217 f = 31 a[66] = 98 f = 7 a[67] = 48 f = 2 a[68] = 129 f = 3 a[69] = 215 f = 43 a[70] = 100 f = 5
a[71] = 54 f = 2 a[72] = 141 f = 3 a[73] = 235 f = 47 a[74] = 110 f = 5 a[75] = 66 f = 22 NOT prime a[76] = 147 f = 3 a[77] = 133 f = 7 a[78] = 152 f = 19 a[79] = 72 f = 8 NOT prime a[80] = 135 f = 9 NOT prime
a[81] = 175 f = 5 a[82] = 112 f = 7 a[83] = 78 f = 2 a[84] = 143 f = 13 a[85] = 187 f = 11 a[86] = 102 f = 17 a[87] = 86 f = 2 a[88] = 301 f = 43 a[89] = 189 f = 7 a[90] = 90 f = 9 NOT prime
a[91] = 88 f = 2 a[92] = 209 f = 11 a[93] = 171 f = 19 a[94] = 96 f = 3 a[95] = 92 f = 4 NOT prime a[96] = 253 f = 23 a[97] = 165 f = 11 a[98] = 108 f = 3 a[99] = 94 f = 2 a[100] = 329 f = 47
more later,
chris
On 2020-08-16 15:02, Allan Wechsler wrote:
Chris, what is the smallest eligible (non-prime-power) number your list leaves out?
On Sun, Aug 16, 2020 at 5:55 PM Christopher Landauer <topcycal@gmail.com
wrote:
hihi, all - i wrote a program to generate terms to n=1000 (i still need to verify it, but it matches what was in this e-mail)
it is a curious fact that the gcd of successive terms is a prime, up to a point, and mostly in any case
i'll have more in a few days
more later, chris
On Sun, Aug 16, 2020 at 6:04 AM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Already posted on August 11th ?!
WFL
On 8/16/20, Neil Sloane <njasloane@gmail.com> wrote:
Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names.
Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version.
Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ?
I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem.
Neil _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- dr. christopher landauer topcy house consulting thousand oaks, california _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
hihi, frank and all - well, ya beat me 8-) my program is still running (up to about 600k so far) - it will be a good check to see how the results match i like the ``dead end check'' you describe - that is what i ended up using as the main criterion there are lotsa peculiarities in the appearance of primes but i'll wait until i have actual numbers for that wonderful, interesting, intriguing, annoying problem (the best kind) more soon, chris On 2020-08-20 05:43, Frank Stevenson wrote:
I just committed my computational effort on github : https://github.com/snakehand/woolly_mammoth - with sample output for the sequence ( up to a[n+1] < 1,000,000 )
Some observations, the sequence is extraordinarily greedy for smaller terms. There are some comments in the code ( src/main.rs ) that describe my algorithm. I have computed more than 2,500,000 terms and I can't see why any number with at least 2 prime factors should be left out of the sequence. There is one "dead end" check to ensure that a[n+1] has at least one factor that a[n] does not have. but the probability that this check causes a number to be skipped is very small, and is not correlated to whether it should fail in future checks.
Neils conjecture seems very plausible, but I don't have a proof, only some probabilistic intuition.
Cheers, Frank
On Mon, Aug 17, 2020 at 4:25 AM christopher landauer <topcycal@gmail.com> wrote:
hihi -
i'll write a script for that, to show the largest a[n] and first missing acceptable number for values of n up to nmax for various nmax;
it does look like the sequence eventually fills in all of them
meanwhile, here are the first 100 values -
again, not yet completely verified, but i think pretty close:
it took me a while to find a good (easily computable) criterion for unacceptability, so here is what i used:
for a prospective value b for a[n], if every prime dividing b also divides the previously computed a[n-1],
then there would be no acceptable a[n+1], so b is unacceptable
(otherwise b is acceptable, since the a[n+1] can use only the primes not also in a[n-1])
the program generates values up to n=10000 in just under a minute on a 5 year old commodity pc running freebsd,
so if we get some conjectures, a lot of experimentation can be done
f = gcd(a[n], a[n-1]) is prime a lot
a[1] = 1 a[2] = 2 a[3] = 6 f = 2 a[4] = 15 f = 3 a[5] = 35 f = 5 a[6] = 14 f = 7 a[7] = 12 f = 2 a[8] = 33 f = 3 a[9] = 55 f = 11 a[10] = 10 f = 5
a[11] = 18 f = 2 a[12] = 21 f = 3 a[13] = 77 f = 7 a[14] = 22 f = 11 a[15] = 20 f = 2 a[16] = 45 f = 5 a[17] = 39 f = 3 a[18] = 26 f = 13 a[19] = 28 f = 2 a[20] = 63 f = 7
a[21] = 51 f = 3 a[22] = 34 f = 17 a[23] = 38 f = 2 a[24] = 57 f = 19 a[25] = 69 f = 3 a[26] = 46 f = 23 a[27] = 40 f = 2 a[28] = 65 f = 5 a[29] = 91 f = 13 a[30] = 42 f = 7b is unacceptable
a[31] = 30 f = 6 NOT prime a[32] = 85 f = 5 a[33] = 119 f = 17 a[34] = 56 f = 7 a[35] = 24 f = 8 NOT prime a[36] = 75 f = 3 a[37] = 95 f = 5 a[38] = 76 f = 19 a[39] = 36 f = 4 NOT prime a[40] = 87 f = 3
a[41] = 145 f = 29 a[42] = 50 f = 5 a[43] = 44 f = 2 a[44] = 99 f = 11 a[45] = 93 f = 3 a[46] = 62 f = 31 a[47] = 52 f = 2 a[48] = 117 f = 13 a[49] = 105 f = 3 a[50] = 70 f = 35 NOT prime
a[51] = 58 f = 2 a[52] = 261 f = 29 a[53] = 111 f = 3 a[54] = 74 f = 37 a[55] = 68 f = 2 a[56] = 153 f = 17 a[57] = 123 f = 3 a[58] = 82 f = 41 a[59] = 80 f = 2 a[60] = 115 f = 5
a[61] = 161 f = 23 a[62] = 84 f = 7 a[63] = 60 f = 12 NOT prime a[64] = 155 f = 5 a[65] = 217 f = 31 a[66] = 98 f = 7 a[67] = 48 f = 2 a[68] = 129 f = 3 a[69] = 215 f = 43 a[70] = 100 f = 5
a[71] = 54 f = 2 a[72] = 141 f = 3 a[73] = 235 f = 47 a[74] = 110 f = 5 a[75] = 66 f = 22 NOT prime a[76] = 147 f = 3 a[77] = 133 f = 7 a[78] = 152 f = 19 a[79] = 72 f = 8 NOT prime a[80] = 135 f = 9 NOT prime
a[81] = 175 f = 5 a[82] = 112 f = 7 a[83] = 78 f = 2 a[84] = 143 f = 13 a[85] = 187 f = 11 a[86] = 102 f = 17 a[87] = 86 f = 2 a[88] = 301 f = 43 a[89] = 189 f = 7 a[90] = 90 f = 9 NOT prime
a[91] = 88 f = 2 a[92] = 209 f = 11 a[93] = 171 f = 19 a[94] = 96 f = 3 a[95] = 92 f = 4 NOT prime a[96] = 253 f = 23 a[97] = 165 f = 11 a[98] = 108 f = 3 a[99] = 94 f = 2 a[100] = 329 f = 47
more later,
chris
On 2020-08-16 15:02, Allan Wechsler wrote:
Chris, what is the smallest eligible (non-prime-power) number your list leaves out?
On Sun, Aug 16, 2020 at 5:55 PM Christopher Landauer <topcycal@gmail.com
wrote:
hihi, all - i wrote a program to generate terms to n=1000 (i still need to verify it, but it matches what was in this e-mail)
it is a curious fact that the gcd of successive terms is a prime, up to a point, and mostly in any case
i'll have more in a few days
more later, chris
On Sun, Aug 16, 2020 at 6:04 AM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Already posted on August 11th ?!
WFL
On 8/16/20, Neil Sloane <njasloane@gmail.com> wrote:
Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names.
Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version.
Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ?
I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem.
Neil _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- dr. christopher landauer topcy house consulting thousand oaks, california _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
hihi, all - here is a table of the smallest acceptable (eligible) value left out when i let the program search up to nmax; each of them is found soon after this is the smallest acceptable value that does not occur for n up to nmax, not the smallest n before which an unacceptable value does not occur (the nmax=1500 line was really confusing until i figured this out; it means that the next value that does occur is at the given n; so for nmax=1500, other acceptable values did not occur, but all were larger than 1458) nmax first missing value where it occurs 100 104 at n=49 n=103 200 204 at n=124 n=203 300 304 at n=224 n=303 400 372 at n=387 n=403 500 490 at n=458 n=503 this is weird 600 588 at n=337 n=607 700 684 at n=481 n=703 800 780 at n=516 n=807 900 858 at n=629 n=907 1000 942 at n=457 n=1003 1100 1068 at n=1078 n=1103 this is really weird 1200 1170 at n=1062 n=1210 1300 1266 at n=372 n=1303 1400 1356 at n=984 n=1411 1500 1458 at n=1499 n=1518 1600 1572 at n=1121 n=1603 1700 1678 at n=989 n=1703 ok, so i suspect my program is broken 1800 1770 at n=1229 n=1810 1900 1866 at n=1830 n=1903 2000 1938 at n=1460 n=2003 3000 2940 at n=2133 n=3007 4000 3894 at n=2970 n=4004 5000 4884 at n=3882 n=5013 6000 5864 at n=4642 n=6001 7000 6876 at n=5543 n=7009 8000 7848 at n=6130 n=8022 9000 8828 at n=7170 n=9002 10000 9790 at n=9993 n=?? curiously, they are all even but i checked the small results and they look right ok, i sort of have an explanation of these weird values - define the ``lateness'' of a[n] as a[n] - n; we know that many times that is positive, but it can also be negative; the a[n] for which a[n] < n are ``late'' (we know that many values occur early, such as 15 and 35); it is a curious phenomena that very few a[n] are very late, and most are not very late at all; it looks like only a few percent asymptotically (n-a[n]) / a[n] for n with n > a[n]; that means that you should expect the ones that were missed up to nmax to be found soon after that; the commonality of the numbers is what is scary the time complexity of the program is roughly O(nmax ^ 2) - not derived, just observed; i also have an observed relationship between nmax and the maximum prospective a[n], which i call bmax; roughly (for large enough n) bmax ~ nmax ^ 1.2 (with the exponent seeming to decrease over time, but slowly) i will have output for nmax=10^6 in a few days various graphs are really helpful more soon, chris On 2020-08-16 15:02, Allan Wechsler wrote:
Chris, what is the smallest eligible (non-prime-power) number your list leaves out?
On Sun, Aug 16, 2020 at 5:55 PM Christopher Landauer <topcycal@gmail.com> wrote:
hihi, all - i wrote a program to generate terms to n=1000 (i still need to verify it, but it matches what was in this e-mail)
it is a curious fact that the gcd of successive terms is a prime, up to a point, and mostly in any case
i'll have more in a few days
more later, chris
On Sun, Aug 16, 2020 at 6:04 AM Fred Lunnon <fred.lunnon@gmail.com> wrote:
Already posted on August 11th ?!
WFL
On 8/16/20, Neil Sloane <njasloane@gmail.com> wrote:
Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names.
Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version.
Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ?
I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem.
Neil _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- dr. christopher landauer topcy house consulting thousand oaks, california _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Since nobody had any brilliant insights overnight, I'm going to toss some ideas out, not because I have much confidence in them, but in the hopes that they will spark another Funster. First, observe that "lex. earliest" sequences can be very hard. The lexicographically earliest sequence to satisfy some constraint might not exist for many reasons. It might require intensive backtracking. It might be very hard to prove the correctness of a given term, because subsequent backtracking could dislodge it. This, in contrast, is the easy kind of lexicographically earliest sequence. It's easy to prove that any valid start can be extended indefinitely. That means that the greedy algorithm can be used to settle the next element for all time, and no backtracking will ever be necessary. (All of this follows only after realizing that prime powers are always wrong, and must be avoided.) My other observation is that in the part of the sequence that Neil has given, there are no *tri-*composite numbers. So I will sharpen his "permutation" question and ask: does 30 ever occur? On Sat, Aug 15, 2020 at 11:56 PM Neil Sloane <njasloane@gmail.com> wrote:
Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names.
Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version.
Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ?
I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem.
Neil _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
hihi - 30 does occur for n=31 42 occurs for n = 30 66 at n=75 78 for n=83 more soon, chris On 2020-08-16 06:06, Allan Wechsler wrote:
Since nobody had any brilliant insights overnight, I'm going to toss some ideas out, not because I have much confidence in them, but in the hopes that they will spark another Funster.
First, observe that "lex. earliest" sequences can be very hard. The lexicographically earliest sequence to satisfy some constraint might not exist for many reasons. It might require intensive backtracking. It might be very hard to prove the correctness of a given term, because subsequent backtracking could dislodge it.
This, in contrast, is the easy kind of lexicographically earliest sequence. It's easy to prove that any valid start can be extended indefinitely. That means that the greedy algorithm can be used to settle the next element for all time, and no backtracking will ever be necessary. (All of this follows only after realizing that prime powers are always wrong, and must be avoided.)
My other observation is that in the part of the sequence that Neil has given, there are no *tri-*composite numbers. So I will sharpen his "permutation" question and ask: does 30 ever occur?
On Sat, Aug 15, 2020 at 11:56 PM Neil Sloane <njasloane@gmail.com> wrote:
Obviously this is an inverted version of the Yellowstone sequence A098550 ! The name Enots Wolley is for personal use only, it must not be mentioned in the OEIS! We frown on such made-up names.
Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version.
Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ?
I can't even prove that every number 2*p (p prime) appears, or that there are infinitely many even terms (although I've found a dozen false proofs). It's a slippery problem.
Neil _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 16/08/2020 04:54, Neil Sloane wrote:
Definition: Lexicographically earliest sequence {a(n)} of distinct positive numbers such that, for n>2, a(n) has a common factor with a(n-1) but not with a(n-2). 1, 2, 6, 15, 35, 14, 12, 33, 55, 10, 18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ... The original idea was due to Scott, with a different sequence, but this is my (canonical!) version.
Could someone please prove the conjecture that this is a permutation of the set {1, all numbers with at least two distinct prime factors} ?
Nitpick: I can prove that it _isn't_ because 2 does not have at least two distinct prime factors. :-) I assume the correct fix is just to replace "1," with "1, 2,". -- g
Here's a proof with a gap in it. Denote the set of finite sets of primes by P, and let f:N->P be the function that maps an integer to its set of prime factors. Note that this is the set, not the multiset, so that f(30) = f(60) = {2, 3, 5} Let A be the set of numbers that occur in A098550. Define g:P-> {power set of A} as the "set inverse" of f. That is, g(Q) = f^-1(Q) = the set of all numbers x that occur in A such that f(x) = P. Call a set of primes Q "good" if g(Q) is infinite, that is, if infinitely many numbers whose set of prime factors is exactly Q occur in A. Note that if Q is good, g(Q) includes all integers n with f(n) = Q, in ascending order, since when an element of Q is eligible to be the next element of the sequence, all small elements of Q are also eligible. Given two sets of primes X and Y, we say that X is a follower of Y if it is legal for a to directly follow b in the sequence, with f(a) = X and f(b) = Y, that is, if X and Y have non-empty intersection, and X is not a subset of Y. Lemma: If X is a follower of Y, and Y is good, then X is good. Proof: choose an element z of X. After each number a with f(a) = Y, the next element of the sequence will be the smallest remaining element b such that f(b) is a follower of Y. So after at most z numbers occur that are mapped by f to Y,, one of them will be followed by z. Theorem: Every element of P containing at least 2 elements is good. Proof: Suppose Z is not good. Then for any Y such that Z is a follower of Y, Y is not good either, by the lemma. So every good set is either a subset of Z, or disjoint from Z. But if X disjoint from Z is good, choose Y containing one element of X and one element of Z. Now Z follows Y which follows X, a contradiction. Similarly, if a subset X of Z is good, choose Y to contain an element of X and an element not in X, and again, Z follows Y follows X, a contradiction. The only remaining case is if *no* element of P is good. I'm convinced this is impossible, but my attempts to prove this keep getting annoyingly long, and I'm sure there's a simple proof that this is impossible. Can anyone help me with this last step in the proof? Andy
-- Andy.Latto@pobox.com
participants (9)
-
Allan Wechsler -
Andy Latto -
christopher landauer -
Christopher Landauer
-
Frank Stevenson -
Fred Lunnon -
Gareth McCaughan -
Hans Havermann -
Neil Sloane