(This Subject reminds me of Hofstadter's yields FALSE when preceded by its quotation.) Just an aside: Mathematica makes it ridiculously easy to "bisect" formal sums of numbers: haf[L_List] := Block[{t = Total@L/2}, If[True, Select[Subsets@L, Total@# == t &], {}]] (To speed up our integer case, replace True with IntegerQ@t .) E.g., instead of Allan's seven squares, In[439]:=√haf[Range@7^2] Out[439]= {{3, 5, 6}, {1, 2, 4, 7}} (one solution), you need at least 24 5th powers: {{1, 2, 4, 10, 11, 13, 14, 15, 16, 18, 22, 24}, {1, 2, 5, 6, 10, 14, 15, 16, 18, 19, 20, 24}, {1, 2, 5, 7, 10, 13, 14, 15, 19, 20, 21, 23}, {3, 4, 6, 8, 9, 11, 12, 16, 17, 18, 22, 24} {3, 4, 7, 8, 9, 11, 12, 13, 17, 21, 22, 23}, {3, 5, 6, 7, 8, 9, 12, 17, 19, 20, 21, 23}} (three solutions, book-matched) Next come eight solutions with 28 5th powers: {{1, 4, 7, 14, 15, 19, 21, 22, 27, 28}, {1, 4, 11, 12, 15, 17, 19, 24, 27, 28}, {2, 4, 5, 12, 13, 15, 18, 21, 22, 24, 25, 27}, {2, 5, 8, 11, 12, 16, 18, 19, 20, 23, 26, 28}, {3, 5, 6, 12, 13, 14, 18, 20, 21, 22, 26, 28}, {3, 6, 8, 10, 14, 15, 16, 17, 22, 23, 26, 28}, {1, 2, 3, 7, 8, 9, 10, 15, 16, 18, 22, 23, 26, 28}, {1, 5, 7, 8, 12, 14, 17, 18, 19, 20, 22, 24, 25, 26}, ...} (half-shown; obvious DIY). —rwg -------- Original Message -------- Date: 2019-08-29 11:30 From: Tomas Rokicki <rokicki@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Reply-To: math-fun <math-fun@mailman.xmission.com> 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? > _______________________________________________