[seqfan] Re: An interesting sequence

Sun Apr 16 17:31:51 CEST 2023

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");
    }
  }
}