[math-fun] Returns to zero when subtracting and adding squares
A recent discussion on "Sequence Fanatics" has me thinking about a general process. Let An be any non-negative integer sequence. Derive Bn with the rule: B0 = A0 and for n > 0 Bn = B(n-1) - An if this is non-negative Bn = B(n-1) + An otherwise. If An is the non-negative integers (A001477), then Bn is A008344. If An is the perfect squares (A000290), then Bn is A076042. Question: Does A076042 ever revisit 0? If you play with it, you will see that the sequence is divided into eras where adding and subtracting strictly alternate. These eras are punctuated by an extra add when subtracting would go negative. The sequence reaches a local minimum just at the end of each era. If we define these minima as the last value in the sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first few truncations. The indices of the minima are not present either. Intuitively, this sequence is aiming at 0 from greater and greater distances, and is unlikely to ever hit the bullseye. But I think the problem is amenable to more rigorous analysis. Can any funsters contribute additional insight?
Empirically, this does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000). On Thu, Aug 29, 2019 at 7:29 AM Allan Wechsler <acwacw@gmail.com> wrote:
A recent discussion on "Sequence Fanatics" has me thinking about a general process. Let An be any non-negative integer sequence. Derive Bn with the rule:
B0 = A0
and for n > 0
Bn = B(n-1) - An if this is non-negative Bn = B(n-1) + An otherwise.
If An is the non-negative integers (A001477), then Bn is A008344.
If An is the perfect squares (A000290), then Bn is A076042.
Question: Does A076042 ever revisit 0? If you play with it, you will see that the sequence is divided into eras where adding and subtracting strictly alternate. These eras are punctuated by an extra add when subtracting would go negative. The sequence reaches a local minimum just at the end of each era. If we define these minima as the last value in the sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first few truncations. The indices of the minima are not present either.
Intuitively, this sequence is aiming at 0 from greater and greater distances, and is unlikely to ever hit the bullseye. But I think the problem is amenable to more rigorous analysis.
Can any funsters contribute additional insight? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Tomas, You said (quote) Empirically, [A076042] does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000). (end quote) Very interesting! Could you explain what you mean? And could you add it as a comment to the sequence? Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Thu, Aug 29, 2019 at 1:26 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Empirically, this does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000).
On Thu, Aug 29, 2019 at 7:29 AM Allan Wechsler <acwacw@gmail.com> wrote:
A recent discussion on "Sequence Fanatics" has me thinking about a general process. Let An be any non-negative integer sequence. Derive Bn with the rule:
B0 = A0
and for n > 0
Bn = B(n-1) - An if this is non-negative Bn = B(n-1) + An otherwise.
If An is the non-negative integers (A001477), then Bn is A008344.
If An is the perfect squares (A000290), then Bn is A076042.
Question: Does A076042 ever revisit 0? If you play with it, you will see that the sequence is divided into eras where adding and subtracting strictly alternate. These eras are punctuated by an extra add when subtracting would go negative. The sequence reaches a local minimum just at the end of each era. If we define these minima as the last value in the sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first few truncations. The indices of the minima are not present either.
Intuitively, this sequence is aiming at 0 from greater and greater distances, and is unlikely to ever hit the bullseye. But I think the problem is amenable to more rigorous analysis.
Can any funsters contribute additional insight? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sure, I'll do that. It's easy to write a Python program that walks the sequence, calculating the lengths of the epochs and doing each in one computational step. Since the length of the epochs increases exponentially, the resulting program gives you a polynomial algorithm to calculate a given term (polynomial in the bit length of the input). I will say further that it is rare for the b(n) to be less than n; this only happens at the end of epochs. Indeed, b(n) does not appear to get below 1e9 between about n=2^32 .. n^5000. I'm fairly certain a simple probabilistic argument can be made that this sequence returns to zero with probably less than 2^5000 or some such if you make some fairly broad and tenuous assumptions about the distribution of values seen. On Thu, Aug 29, 2019 at 10:44 AM Neil Sloane <njasloane@gmail.com> wrote:
Tomas, You said
(quote) Empirically, [A076042] does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000). (end quote)
Very interesting! Could you explain what you mean? And could you add it as a comment to the sequence?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Thu, Aug 29, 2019 at 1:26 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Empirically, this does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000).
On Thu, Aug 29, 2019 at 7:29 AM Allan Wechsler <acwacw@gmail.com> wrote:
A recent discussion on "Sequence Fanatics" has me thinking about a general process. Let An be any non-negative integer sequence. Derive Bn with the rule:
B0 = A0
and for n > 0
Bn = B(n-1) - An if this is non-negative Bn = B(n-1) + An otherwise.
If An is the non-negative integers (A001477), then Bn is A008344.
If An is the perfect squares (A000290), then Bn is A076042.
Question: Does A076042 ever revisit 0? If you play with it, you will see that the sequence is divided into eras where adding and subtracting strictly alternate. These eras are punctuated by an extra add when subtracting would go negative. The sequence reaches a local minimum just at the end of each era. If we define these minima as the last value in the sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first few truncations. The indices of the minima are not present either.
Intuitively, this sequence is aiming at 0 from greater and greater distances, and is unlikely to ever hit the bullseye. But I think the problem is amenable to more rigorous analysis.
Can any funsters contribute additional insight? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
-- -- http://cube20.org/ -- http://golly.sf.net/ --
I suspect that, more generally, a sum a_1 + ... + a_n with each a_k being either k^2 or -k^2 can never be zero? On Thu, Aug 29, 2019 at 12:10 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Sure, I'll do that. It's easy to write a Python program that walks the sequence, calculating the lengths of the epochs and doing each in one computational step. Since the length of the epochs increases exponentially, the resulting program gives you a polynomial algorithm to calculate a given term (polynomial in the bit length of the input).
I will say further that it is rare for the b(n) to be less than n; this only happens at the end of epochs. Indeed, b(n) does not appear to get below 1e9 between about n=2^32 .. n^5000.
I'm fairly certain a simple probabilistic argument can be made that this sequence returns to zero with probably less than 2^5000 or some such if you make some fairly broad and tenuous assumptions about the distribution of values seen.
On Thu, Aug 29, 2019 at 10:44 AM Neil Sloane <njasloane@gmail.com> wrote:
Tomas, You said
(quote) Empirically, [A076042] does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000). (end quote)
Very interesting! Could you explain what you mean? And could you add it as a comment to the sequence?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Thu, Aug 29, 2019 at 1:26 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Empirically, this does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000).
On Thu, Aug 29, 2019 at 7:29 AM Allan Wechsler <acwacw@gmail.com> wrote:
A recent discussion on "Sequence Fanatics" has me thinking about a general process. Let An be any non-negative integer sequence. Derive Bn with the rule:
B0 = A0
and for n > 0
Bn = B(n-1) - An if this is non-negative Bn = B(n-1) + An otherwise.
If An is the non-negative integers (A001477), then Bn is A008344.
If An is the perfect squares (A000290), then Bn is A076042.
Question: Does A076042 ever revisit 0? If you play with it, you will see that the sequence is divided into eras where adding and subtracting strictly alternate. These eras are punctuated by an extra add when subtracting would go negative. The sequence reaches a local minimum just at the end of each era. If we define these minima as the last value in the sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first few truncations. The indices of the minima are not present either.
Intuitively, this sequence is aiming at 0 from greater and greater distances, and is unlikely to ever hit the bullseye. But I think the problem is amenable to more rigorous analysis.
Can any funsters contribute additional insight? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Ah, no, I thought of that, and there are examples! 1 + 4 - 9 + 16 - 25 - 36 + 49 = 0 On Thu, Aug 29, 2019 at 2:17 PM Michael Collins <mjcollins10@gmail.com> wrote:
I suspect that, more generally, a sum a_1 + ... + a_n with each a_k being either k^2 or -k^2 can never be zero?
On Thu, Aug 29, 2019 at 12:10 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Sure, I'll do that. It's easy to write a Python program that walks the sequence, calculating the lengths of the epochs and doing each in one computational step. Since the length of the epochs increases exponentially, the resulting program gives you a polynomial algorithm to calculate a given term (polynomial in the bit length of the input).
I will say further that it is rare for the b(n) to be less than n; this only happens at the end of epochs. Indeed, b(n) does not appear to get below 1e9 between about n=2^32 .. n^5000.
I'm fairly certain a simple probabilistic argument can be made that this sequence returns to zero with probably less than 2^5000 or some such if you make some fairly broad and tenuous assumptions about the distribution of values seen.
On Thu, Aug 29, 2019 at 10:44 AM Neil Sloane <njasloane@gmail.com> wrote:
Tomas, You said
(quote) Empirically, [A076042] does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000). (end quote)
Very interesting! Could you explain what you mean? And could you add it as a comment to the sequence?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Thu, Aug 29, 2019 at 1:26 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Empirically, this does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000).
On Thu, Aug 29, 2019 at 7:29 AM Allan Wechsler <acwacw@gmail.com> wrote:
A recent discussion on "Sequence Fanatics" has me thinking about a general process. Let An be any non-negative integer sequence. Derive Bn with the rule:
B0 = A0
and for n > 0
Bn = B(n-1) - An if this is non-negative Bn = B(n-1) + An otherwise.
If An is the non-negative integers (A001477), then Bn is A008344.
If An is the perfect squares (A000290), then Bn is A076042.
Question: Does A076042 ever revisit 0? If you play with it, you will see that the sequence is divided into eras where adding and subtracting strictly alternate. These eras are punctuated by an extra add when subtracting would go negative. The sequence reaches a local minimum just at the end of each era. If we define these minima as the last value in the sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first few truncations. The indices of the minima are not present either.
Intuitively, this sequence is aiming at 0 from greater and greater distances, and is unlikely to ever hit the bullseye. But I think the problem is amenable to more rigorous analysis.
Can any funsters contribute additional insight? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
Here is another: 1 - 4 - 9 + 16 - 25 + 36 + 49 - 64 = 0 On Thu, Aug 29, 2019 at 2:21 PM Allan Wechsler <acwacw@gmail.com> wrote:
Ah, no, I thought of that, and there are examples!
1 + 4 - 9 + 16 - 25 - 36 + 49 = 0
On Thu, Aug 29, 2019 at 2:17 PM Michael Collins <mjcollins10@gmail.com> wrote:
I suspect that, more generally, a sum a_1 + ... + a_n with each a_k being either k^2 or -k^2 can never be zero?
On Thu, Aug 29, 2019 at 12:10 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Sure, I'll do that. It's easy to write a Python program that walks the sequence, calculating the lengths of the epochs and doing each in one computational step. Since the length of the epochs increases exponentially, the resulting program gives you a polynomial algorithm to calculate a given term (polynomial in the bit length of the input).
I will say further that it is rare for the b(n) to be less than n; this only happens at the end of epochs. Indeed, b(n) does not appear to get below 1e9 between about n=2^32 .. n^5000.
I'm fairly certain a simple probabilistic argument can be made that this sequence returns to zero with probably less than 2^5000 or some such if you make some fairly broad and tenuous assumptions about the distribution of values seen.
On Thu, Aug 29, 2019 at 10:44 AM Neil Sloane <njasloane@gmail.com> wrote:
Tomas, You said
(quote) Empirically, [A076042] does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000). (end quote)
Very interesting! Could you explain what you mean? And could you add it as a comment to the sequence?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Thu, Aug 29, 2019 at 1:26 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Empirically, this does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000).
On Thu, Aug 29, 2019 at 7:29 AM Allan Wechsler <acwacw@gmail.com> wrote:
A recent discussion on "Sequence Fanatics" has me thinking about a general process. Let An be any non-negative integer sequence. Derive Bn with the rule:
B0 = A0
and for n > 0
Bn = B(n-1) - An if this is non-negative Bn = B(n-1) + An otherwise.
If An is the non-negative integers (A001477), then Bn is A008344.
If An is the perfect squares (A000290), then Bn is A076042.
Question: Does A076042 ever revisit 0? If you play with it, you will see that the sequence is divided into eras where adding and subtracting strictly alternate. These eras are punctuated by an extra add when subtracting would go negative. The sequence reaches a local minimum just at the end of each era. If we define these minima as the last value in the sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first few truncations. The indices of the minima are not present either.
Intuitively, this sequence is aiming at 0 from greater and greater distances, and is unlikely to ever hit the bullseye. But I think the problem is amenable to more rigorous analysis.
Can any funsters contribute additional insight? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
In one case, you have 2^n choices of sign assignment, and when the numbers are big enough and the parity is right, you are pretty much sure to find a winner. In the other case, God chooses the signs for you, with only a vague incentive to keep the sum near zero. It looks very much as if that isn't good enough to win. On Thu, Aug 29, 2019 at 2:26 PM Allan Wechsler <acwacw@gmail.com> wrote:
Here is another: 1 - 4 - 9 + 16 - 25 + 36 + 49 - 64 = 0
On Thu, Aug 29, 2019 at 2:21 PM Allan Wechsler <acwacw@gmail.com> wrote:
Ah, no, I thought of that, and there are examples!
1 + 4 - 9 + 16 - 25 - 36 + 49 = 0
On Thu, Aug 29, 2019 at 2:17 PM Michael Collins <mjcollins10@gmail.com> wrote:
I suspect that, more generally, a sum a_1 + ... + a_n with each a_k being either k^2 or -k^2 can never be zero?
On Thu, Aug 29, 2019 at 12:10 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Sure, I'll do that. It's easy to write a Python program that walks the sequence, calculating the lengths of the epochs and doing each in one computational step. Since the length of the epochs increases exponentially, the resulting program gives you a polynomial algorithm to calculate a given term (polynomial in the bit length of the input).
I will say further that it is rare for the b(n) to be less than n; this only happens at the end of epochs. Indeed, b(n) does not appear to get below 1e9 between about n=2^32 .. n^5000.
I'm fairly certain a simple probabilistic argument can be made that this sequence returns to zero with probably less than 2^5000 or some such if you make some fairly broad and tenuous assumptions about the distribution of values seen.
On Thu, Aug 29, 2019 at 10:44 AM Neil Sloane <njasloane@gmail.com> wrote:
Tomas, You said
(quote) Empirically, [A076042] does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000). (end quote)
Very interesting! Could you explain what you mean? And could you add it as a comment to the sequence?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Thu, Aug 29, 2019 at 1:26 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Empirically, this does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000).
On Thu, Aug 29, 2019 at 7:29 AM Allan Wechsler <acwacw@gmail.com> wrote:
> A recent discussion on "Sequence Fanatics" has me thinking about a general > process. Let An be any non-negative integer sequence. Derive Bn with the > rule: > > B0 = A0 > > and for n > 0 > > Bn = B(n-1) - An if this is non-negative > Bn = B(n-1) + An otherwise. > > If An is the non-negative integers (A001477), then Bn is A008344. > > If An is the perfect squares (A000290), then Bn is A076042. > > Question: Does A076042 ever revisit 0? If you play with it, you will see > that the sequence is divided into eras where adding and subtracting > strictly alternate. These eras are punctuated by an extra add when > subtracting would go negative. The sequence reaches a local minimum just at > the end of each era. If we define these minima as the last value in the > sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, > 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first > few truncations. The indices of the minima are not present either. > > Intuitively, this sequence is aiming at 0 from greater and greater > distances, and is unlikely to ever hit the bullseye. But I think the > problem is amenable to more rigorous analysis. > > Can any funsters contribute additional insight? > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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 there are 2^n ways to assign signs, and since the maximum sum is O(n^3), I expect the number of ways to assign signs that sum to zero to increase exponentially with n. On Thu, Aug 29, 2019 at 11:26 AM Allan Wechsler <acwacw@gmail.com> wrote:
Here is another: 1 - 4 - 9 + 16 - 25 + 36 + 49 - 64 = 0
On Thu, Aug 29, 2019 at 2:21 PM Allan Wechsler <acwacw@gmail.com> wrote:
Ah, no, I thought of that, and there are examples!
1 + 4 - 9 + 16 - 25 - 36 + 49 = 0
On Thu, Aug 29, 2019 at 2:17 PM Michael Collins <mjcollins10@gmail.com> wrote:
I suspect that, more generally, a sum a_1 + ... + a_n with each a_k being either k^2 or -k^2 can never be zero?
On Thu, Aug 29, 2019 at 12:10 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Sure, I'll do that. It's easy to write a Python program that walks the sequence, calculating the lengths of the epochs and doing each in one computational step. Since the length of the epochs increases exponentially, the resulting program gives you a polynomial algorithm to calculate a given term (polynomial in the bit length of the input).
I will say further that it is rare for the b(n) to be less than n; this only happens at the end of epochs. Indeed, b(n) does not appear to get below 1e9 between about n=2^32 .. n^5000.
I'm fairly certain a simple probabilistic argument can be made that this sequence returns to zero with probably less than 2^5000 or some such if you make some fairly broad and tenuous assumptions about the distribution of values seen.
On Thu, Aug 29, 2019 at 10:44 AM Neil Sloane <njasloane@gmail.com> wrote:
Tomas, You said
(quote) Empirically, [A076042] does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000). (end quote)
Very interesting! Could you explain what you mean? And could you add it as a comment to the sequence?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Thu, Aug 29, 2019 at 1:26 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Empirically, this does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000).
On Thu, Aug 29, 2019 at 7:29 AM Allan Wechsler <acwacw@gmail.com> wrote:
> A recent discussion on "Sequence Fanatics" has me thinking about a general > process. Let An be any non-negative integer sequence. Derive Bn with the > rule: > > B0 = A0 > > and for n > 0 > > Bn = B(n-1) - An if this is non-negative > Bn = B(n-1) + An otherwise. > > If An is the non-negative integers (A001477), then Bn is A008344. > > If An is the perfect squares (A000290), then Bn is A076042. > > Question: Does A076042 ever revisit 0? If you play with it, you will see > that the sequence is divided into eras where adding and subtracting > strictly alternate. These eras are punctuated by an extra add when > subtracting would go negative. The sequence reaches a local minimum just at > the end of each era. If we define these minima as the last value in the > sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, > 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first > few truncations. The indices of the minima are not present either. > > Intuitively, this sequence is aiming at 0 from greater and greater > distances, and is unlikely to ever hit the bullseye. But I think the > problem is amenable to more rigorous analysis. > > Can any funsters contribute additional insight? > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Okay, let's flesh out the epoch argument. Epoch lengths increase by the square root of 3. Epoch n has length c 3^(n/2) The number of bits in the low value of that epoch is about log(3)/log(2) n. The probability they are all zero is about 0.5 to that power, which is about (1/3)**n. The infinite sum converges and if we check the leading terms we can reduce the "probability" arbitrarily. Since I've already checked thousands of the first terms, it looks likely we won't see a zero. On Thu, Aug 29, 2019 at 11:30 AM Tomas Rokicki <rokicki@gmail.com> wrote:
Since there are 2^n ways to assign signs, and since the maximum sum is O(n^3), I expect the number of ways to assign signs that sum to zero to increase exponentially with n.
On Thu, Aug 29, 2019 at 11:26 AM Allan Wechsler <acwacw@gmail.com> wrote:
Here is another: 1 - 4 - 9 + 16 - 25 + 36 + 49 - 64 = 0
On Thu, Aug 29, 2019 at 2:21 PM Allan Wechsler <acwacw@gmail.com> wrote:
Ah, no, I thought of that, and there are examples!
1 + 4 - 9 + 16 - 25 - 36 + 49 = 0
On Thu, Aug 29, 2019 at 2:17 PM Michael Collins <mjcollins10@gmail.com> wrote:
I suspect that, more generally, a sum a_1 + ... + a_n with each a_k being either k^2 or -k^2 can never be zero?
On Thu, Aug 29, 2019 at 12:10 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Sure, I'll do that. It's easy to write a Python program that walks the sequence, calculating the lengths of the epochs and doing each in one computational step. Since the length of the epochs increases exponentially, the resulting program gives you a polynomial algorithm to calculate a given term (polynomial in the bit length of the input).
I will say further that it is rare for the b(n) to be less than n; this only happens at the end of epochs. Indeed, b(n) does not appear to get below 1e9 between about n=2^32 .. n^5000.
I'm fairly certain a simple probabilistic argument can be made that this sequence returns to zero with probably less than 2^5000 or some such if you make some fairly broad and tenuous assumptions about the distribution of values seen.
On Thu, Aug 29, 2019 at 10:44 AM Neil Sloane <njasloane@gmail.com> wrote:
Tomas, You said
(quote) Empirically, [A076042] does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000). (end quote)
Very interesting! Could you explain what you mean? And could you add it as a comment to the sequence?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Thu, Aug 29, 2019 at 1:26 PM Tomas Rokicki <rokicki@gmail.com> wrote:
> Empirically, this does not appear to return to zero within > at least 2^4000 terms. I can easily increase the exponent > (perhaps up to 40,000). > > On Thu, Aug 29, 2019 at 7:29 AM Allan Wechsler <acwacw@gmail.com
wrote:
> > > A recent discussion on "Sequence Fanatics" has me thinking about a > general > > process. Let An be any non-negative integer sequence. Derive Bn with the > > rule: > > > > B0 = A0 > > > > and for n > 0 > > > > Bn = B(n-1) - An if this is non-negative > > Bn = B(n-1) + An otherwise. > > > > If An is the non-negative integers (A001477), then Bn is A008344. > > > > If An is the perfect squares (A000290), then Bn is A076042. > > > > Question: Does A076042 ever revisit 0? If you play with it, you will see > > that the sequence is divided into eras where adding and subtracting > > strictly alternate. These eras are punctuated by an extra add when > > subtracting would go negative. The sequence reaches a local minimum just > at > > the end of each era. If we define these minima as the last value in the > > sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, > > 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first > > few truncations. The indices of the minima are not present either. > > > > Intuitively, this sequence is aiming at 0 from greater and greater > > distances, and is unlikely to ever hit the bullseye. But I think the > > problem is amenable to more rigorous analysis. > > > > Can any funsters contribute additional insight? > > _______________________________________________ > > math-fun mailing list > > math-fun@mailman.xmission.com > > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > > -- > -- http://cube20.org/ -- http://golly.sf.net/ -- > _______________________________________________ > 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
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
-- -- http://cube20.org/ -- http://golly.sf.net/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Yes, and in general if you choose the signs according to the first 2^n terms of the Thue-Morse aperiodic sequence, it will work for all polynomials p(x) of degree <= n-1. Wechsler's example is the special case where n = 3 and p(x) = x^2. Best wishes, Adam P. Goucher
Sent: Thursday, August 29, 2019 at 7:26 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Returns to zero when subtracting and adding squares
Here is another: 1 - 4 - 9 + 16 - 25 + 36 + 49 - 64 = 0
On Thu, Aug 29, 2019 at 2:21 PM Allan Wechsler <acwacw@gmail.com> wrote:
Ah, no, I thought of that, and there are examples!
1 + 4 - 9 + 16 - 25 - 36 + 49 = 0
On Thu, Aug 29, 2019 at 2:17 PM Michael Collins <mjcollins10@gmail.com> wrote:
I suspect that, more generally, a sum a_1 + ... + a_n with each a_k being either k^2 or -k^2 can never be zero?
On Thu, Aug 29, 2019 at 12:10 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Sure, I'll do that. It's easy to write a Python program that walks the sequence, calculating the lengths of the epochs and doing each in one computational step. Since the length of the epochs increases exponentially, the resulting program gives you a polynomial algorithm to calculate a given term (polynomial in the bit length of the input).
I will say further that it is rare for the b(n) to be less than n; this only happens at the end of epochs. Indeed, b(n) does not appear to get below 1e9 between about n=2^32 .. n^5000.
I'm fairly certain a simple probabilistic argument can be made that this sequence returns to zero with probably less than 2^5000 or some such if you make some fairly broad and tenuous assumptions about the distribution of values seen.
On Thu, Aug 29, 2019 at 10:44 AM Neil Sloane <njasloane@gmail.com> wrote:
Tomas, You said
(quote) Empirically, [A076042] does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000). (end quote)
Very interesting! Could you explain what you mean? And could you add it as a comment to the sequence?
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Thu, Aug 29, 2019 at 1:26 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Empirically, this does not appear to return to zero within at least 2^4000 terms. I can easily increase the exponent (perhaps up to 40,000).
On Thu, Aug 29, 2019 at 7:29 AM Allan Wechsler <acwacw@gmail.com> wrote:
> A recent discussion on "Sequence Fanatics" has me thinking about a general > process. Let An be any non-negative integer sequence. Derive Bn with the > rule: > > B0 = A0 > > and for n > 0 > > Bn = B(n-1) - An if this is non-negative > Bn = B(n-1) + An otherwise. > > If An is the non-negative integers (A001477), then Bn is A008344. > > If An is the perfect squares (A000290), then Bn is A076042. > > Question: Does A076042 ever revisit 0? If you play with it, you will see > that the sequence is divided into eras where adding and subtracting > strictly alternate. These eras are punctuated by an extra add when > subtracting would go negative. The sequence reaches a local minimum just at > the end of each era. If we define these minima as the last value in the > sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, > 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first > few truncations. The indices of the minima are not present either. > > Intuitively, this sequence is aiming at 0 from greater and greater > distances, and is unlikely to ever hit the bullseye. But I think the > problem is amenable to more rigorous analysis. > > Can any funsters contribute additional insight? > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ 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
Have you tried backtracking from a presumptive Bn = 0 for n > 0? I did some experiments last night, and using that Bn < 2n^2 (provided n > 0) forces Bn-k into an alternating sequence of additions and subtractions. Some of the terms have n^2 components, some do not. Perhaps that can be pushed into violating an epoch length, or having the sequence contradict itself somehow. On 8/29/19 7:28 , Allan Wechsler wrote:
A recent discussion on "Sequence Fanatics" has me thinking about a general process. Let An be any non-negative integer sequence. Derive Bn with the rule:
B0 = A0
and for n > 0
Bn = B(n-1) - An if this is non-negative Bn = B(n-1) + An otherwise.
If An is the non-negative integers (A001477), then Bn is A008344.
If An is the perfect squares (A000290), then Bn is A076042.
Question: Does A076042 ever revisit 0? If you play with it, you will see that the sequence is divided into eras where adding and subtracting strictly alternate. These eras are punctuated by an extra add when subtracting would go negative. The sequence reaches a local minimum just at the end of each era. If we define these minima as the last value in the sequence before a double add, they are: 1, 5, 5, 7, 4, 19, 104, 74, 193, 515, 725, 241 ... This sequence is not in OEIS, nor are any of its first few truncations. The indices of the minima are not present either.
Intuitively, this sequence is aiming at 0 from greater and greater distances, and is unlikely to ever hit the bullseye. But I think the problem is amenable to more rigorous analysis.
Can any funsters contribute additional insight? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun .
participants (6)
-
Adam P. Goucher -
Allan Wechsler -
Andres Valloud -
Michael Collins -
Neil Sloane -
Tomas Rokicki