[seqfan] Re: An interesting sequence

[Arthur O'Dwyer]

(Adding participants-thus-far on the To: line.)

It seems it has been proven ([1]) that all natural numbers above 245 are
expressible as the sum of 5 distinct squares.
This is pretty much what you need, since (n is the mean of 5 distinct
squares) = (nx is the sum of 5 distinct squares).
I'm not sure that [1] applies to nonzero squares specifically, but the
existence of OEIS A004431–A004434 and the
absence of a corresponding OEIS A004435 seems pretty conclusive
circumstantial evidence.

The integers' expressibility-as-sums-of-distinct-squares seems to have been
pretty completely explored in OEIS already:

https://oeis.org/A004431 — numbers which are expressible as the sum of 2
distinct nonzero squares
https://oeis.org/A004432 — numbers which are expressible as the sum of 3
distinct nonzero squares
https://oeis.org/A004433 — numbers which are expressible as the sum of 4
distinct nonzero squares
https://oeis.org/A004434 — numbers which are expressible as the sum of 5
distinct nonzero squares

Is the substitution of "mean" for "sum" really a non-trivial operation, or
will this sequence be redundant with (readily derivable from) the above?

https://math.stackexchange.com/a/4021787/
https://math.stackexchange.com/a/1284951/
https://math.stackexchange.com/a/852569/
[1] — "Darstellung natürlicher Zahlen als Summe von Quadraten" (Franz
Halter-Koch, 1982) http://matwbn.icm.edu.pl/ksiazki/aa/aa42/aa4212.pdf

–Arthur

On Sun, Apr 16, 2023 at 11:31 AM Arthur O'Dwyer <arthur.j.odwyer at gmail.com>
wrote:

> On Sun, Apr 16, 2023 at 1:07 AM Yifan Xie <xieyifan4013 at 163.com> wrote:
>
>> a(n) is the smallest positive integer x such that n can be expressed as
>> the arithmetic mean of x distinct nonzero squares, or 0 if x does not
>> exist. Based on my calculation of a(1) to a(76) by hand, only a(2), a(3),
>> a(6), a(8), a(12) are 0 and no terms are larger than 5.
>> Please consider this sequence, and if possible, provide a program for me.
>>
>
> I've given it a shot in C++.  It took me a few tries to notice all the
> subtleties:
> - distinct squares (so e.g. 3 = (1+4+4)/3, but we don't count that as a
> solution)
> - nonzero squares (so e.g. 2 = (0+4)/2, but we don't count that as a
> solution)
> But after that, it can do up to about n=50'000 in a few seconds.
> Here are all the values (x==0 || x >= 5) for (n < 200'000).
>
> I notice the powers 2^(k+1) — 32, 128, 512, 2048, 8192, 32768, 131072 all
> have value 5; and so do 48, 192, 768, etc.
>
> a(0) = 0 ()
>
> a(2) = 0 ()
>
> a(3) = 0 ()
>
> a(6) = 0 ()
>
> a(8) = 0 ()
>
> a(11) = 5 (5^2 + 4^2 + 3^2 + 2^2 + 1^2)
>
> a(12) = 0 ()
>
> a(19) = 5 (7^2 + 5^2 + 4^2 + 2^2 + 1^2)
>
> a(24) = 5 (9^2 + 5^2 + 3^2 + 2^2 + 1^2)
>
> a(32) = 5 (11^2 + 5^2 + 3^2 + 2^2 + 1^2)
>
> a(33) = 5 (9^2 + 7^2 + 5^2 + 3^2 + 1^2)
>
> a(44) = 5 (13^2 + 5^2 + 4^2 + 3^2 + 1^2)
>
> a(48) = 5 (13^2 + 6^2 + 5^2 + 3^2 + 1^2)
>
> a(76) = 5 (15^2 + 9^2 + 8^2 + 3^2 + 1^2)
>
> a(96) = 5 (21^2 + 5^2 + 3^2 + 2^2 + 1^2)
>
> a(128) = 5 (23^2 + 9^2 + 5^2 + 2^2 + 1^2)
>
> a(132) = 5 (24^2 + 7^2 + 5^2 + 3^2 + 1^2)
>
> a(176) = 5 (29^2 + 5^2 + 3^2 + 2^2 + 1^2)
>
> a(192) = 5 (21^2 + 17^2 + 15^2 + 2^2 + 1^2)
>
> a(304) = 5 (37^2 + 11^2 + 5^2 + 2^2 + 1^2)
>
> a(384) = 5 (41^2 + 15^2 + 3^2 + 2^2 + 1^2)
>
> a(512) = 5 (43^2 + 25^2 + 9^2 + 2^2 + 1^2)
>
> a(528) = 5 (51^2 + 5^2 + 3^2 + 2^2 + 1^2)
>
> a(704) = 5 (59^2 + 5^2 + 3^2 + 2^2 + 1^2)
>
> a(768) = 5 (51^2 + 35^2 + 3^2 + 2^2 + 1^2)
>
> a(1216) = 5 (75^2 + 21^2 + 3^2 + 2^2 + 1^2)
>
> a(1536) = 5 (85^2 + 21^2 + 3^2 + 2^2 + 1^2)
>
> a(2048) = 5 (101^2 + 5^2 + 3^2 + 2^2 + 1^2)
>
> a(2112) = 5 (95^2 + 39^2 + 3^2 + 2^2 + 1^2)
>
> a(2816) = 5 (115^2 + 29^2 + 3^2 + 2^2 + 1^2)
>
> a(3072) = 5 (111^2 + 55^2 + 3^2 + 2^2 + 1^2)
>
> a(4864) = 5 (155^2 + 13^2 + 11^2 + 2^2 + 1^2)
>
> a(6144) = 5 (175^2 + 9^2 + 3^2 + 2^2 + 1^2)
>
> a(8192) = 5 (201^2 + 23^2 + 5^2 + 2^2 + 1^2)
>
> a(8448) = 5 (193^2 + 69^2 + 15^2 + 2^2 + 1^2)
>
> a(11264) = 5 (237^2 + 11^2 + 5^2 + 2^2 + 1^2)
>
> a(12288) = 5 (201^2 + 145^2 + 3^2 + 2^2 + 1^2)
>
> a(19456) = 5 (311^2 + 23^2 + 5^2 + 2^2 + 1^2)
>
> a(24576) = 5 (309^2 + 165^2 + 13^2 + 2^2 + 1^2)
>
> a(32768) = 5 (401^2 + 55^2 + 3^2 + 2^2 + 1^2)
>
> a(33792) = 5 (411^2 + 5^2 + 3^2 + 2^2 + 1^2)
>
> a(45056) = 5 (473^2 + 39^2 + 5^2 + 2^2 + 1^2)
>
> a(49152) = 5 (495^2 + 21^2 + 17^2 + 2^2 + 1^2)
>
> a(77824) = 5 (609^2 + 135^2 + 3^2 + 2^2 + 1^2)
>
> a(98304) = 5 (545^2 + 441^2 + 3^2 + 2^2 + 1^2)
>
> a(131072) = 5 (689^2 + 425^2 + 3^2 + 2^2 + 1^2)
>
> a(135168) = 5 (801^2 + 185^2 + 3^2 + 2^2 + 1^2)
>
> a(180224) = 5 (941^2 + 125^2 + 3^2 + 2^2 + 1^2)
>
> a(196608) = 5 (991^2 + 27^2 + 15^2 + 2^2 + 1^2)
>
> –Arthur
>
> #include <algorithm>
> #include <cassert>
> #include <cmath>
> #include <cstdio>
> #include <vector>
>
> const std::vector<int> squares = []() {
>   std::vector<int> r;
>   for (int i=1; i*i < 1'000'000'000; ++i) {
>     r.push_back(i*i);
>   }
>   return r;
> }();
> using It = std::vector<int>::const_iterator;
>
> bool n_is_sum_of_x_distinct_squares(int n, int x, It first,
> std::vector<int> *result) {
>   if (x == 1) {
>     if (std::binary_search(first, squares.end(), n)) {
>       result->push_back(n);
>       return true;
>     } else {
>       return false;
>     }
>   }
>
>   for (It it = first; it != squares.end(); ++it) {
>     int sq = *it;
>     if (sq >= n) break;
>     if (n_is_sum_of_x_distinct_squares(n - sq, x - 1, it + 1, result)) {
>       result->push_back(sq);
>       return true;
>     }
>   }
>   return false;
> }
>
> void populate(int n, std::vector<int> *result) {
>   result->resize(0);
>   int xmax = (sqrt(48*n + 1) - 1) / 4;  // from Robert Israel
> #ifndef NDEBUG
>   int testmax = xmax + 3;
> #else
>   int testmax = xmax;
> #endif
>   for (int x = 1; x <= testmax; ++x) {
>     // printf("Is %d the sum of %d distinct nonzero squares?\n", n, x);
>     if (n_is_sum_of_x_distinct_squares(n*x, x, squares.begin(), result)) {
>       assert(x <= xmax);
>       return;
>     }
>   }
>   assert(result->size() == 0);
> }
>
> int main() {
>   std::vector<int> result;
>   for (int n=0; true; ++n) {
>     populate(n, &result);
>     if (result.size() == 0 || result.size() >= 5) {
>       printf("a(%d) = %zu (", n, result.size());
>       bool first = true;
>       for (int i : result) {
>         if (!std::exchange(first, false)) {
>           printf(" + ");
>         }
>         printf("%d^2", int(sqrt(i) + 0.5));
>       }
>       printf(")\n");
>     }
>   }
> }
>