|
%I #20 Jan 16 2017 14:26:26
%S 1,1,2,2,3,3,4,5,5,6,7,7,8,8,9,9,10,11,11,12,13,13,14,14,15,15,16,17,
%T 17,18,19,19,20,20,21,21,22,23,23,24,25,25,26,26,27,27,28,29,30,30,31,
%U 31,32,32,33,33,34,35,36,36,37,37,38,38,39,40,40,41,42
%N The maximum number of squares among the partial sums of any permutation of the integers [1..n].
%H Li Zhou et al., <a href="https://www.awesomemath.org/wp-pdf-files/math-reflections/mr-2016-04/mr_3_2016_solutions.pdf">Solution to Problem O376</a>, Mathematical Reflections 4 (2016) p. 23.
%F Conjecture: a(n) = floor((n + n mod 2 + (n+1/2)*sqrt(2))/4), so lim_{n->inf} a(n)/n = (1 + sqrt(2))/4 = A020765 + 1/4 = 0.60355339059327376... - _Jon E. Schoenfield_, Jan 09 2017
%F From _Jon E. Schoenfield_, Jan 13 2017: (Start)
%F The sum of all the integers in [1..n] is the n-th triangular number, A000217(n) = n*(n+1)/2, so none of the partial sums can exceed n*(n+1)/2, and floor(sqrt(n*(n+1)/2)) provides an upper bound on a(n).
%F Since k^2 - (k-1)^2 is an odd number for any k, the number of squares k^2 such that both k^2 and (k-1)^2 are among the partial sums (including k^2 = 1^2, since (k-1)^2 = 0^2 = 0 would be the empty sum) cannot exceed the number of odd numbers in [1..n]; i.e., obtaining the next partial sum s(m+1) by adding a number j from [1..n] to the partial sum s(m) can advance the partial sum from one square to another square only if (1) j is odd or (2) at least one square is skipped between s(m) and s(m+1). (E.g., 5, an odd number, can advance the partial sum from 4 = 2^2 to 9 = 3^2, but 12, an even number, is not the difference between two consecutive squares (k-1)^2 and k^2; 12 can advance the partial sum from one square to another only by being used immediately after a partial sum of 4 = 2^2 to reach 4 + 12 = 16 = 4^2.) As a result, every even number in [1..n] corresponds to at least one square in {1, 4, 9, ..., floor(sqrt(n*(n+1)/2))^2} that does not appear among the set of n partial sums obtained.
%F The number of squares among the partial sums will be maximized if the numbers in [1..n] are arranged with all the odd numbers first, placed in increasing order, so that the j-th partial sum is j^2 for every j in [1..ceiling(n/2)], and then the even numbers are placed after them in any order such that every remaining square having the same parity as j^2 is reached. E.g., for n=20, since n*(n+1)/2 = 210, the available squares are 1, 4, 9, ..., 196, and we can build the partial sums using the odd numbers 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 first to get partial sums 1, 4, 9, ..., 81, 100 (all 10 are squares), after which, proceeding from 100, we have only even numbers to add, so we can reach only the even squares in the half-open interval (100,196], i.e., 144 and 196; one way (of many) to do this is to arrange the even numbers as 20, 18, 6 (bringing the partial sum to 100+20+18+6 = 144), 16, 14, 12, 10 (bringing the partial sum to 144+16+14+12+10 = 196), 8, 4, 2 (reaching the full sum of 196+8+4+2 = 210).
%F It seems very likely that this approach (using the even numbers in some order) will work for any value of n. If so, then a(n) is ceiling(n/2) (the number of odd numbers in [1..n]) plus the number of squares of the same parity as ceiling(n/2)^2 in the half-open interval (ceiling(n/2)^2, n*(n+1)/2]; it can be shown that this yields a(n) = floor((n + n mod 2 + (n+1/2)*sqrt(2))/4) (the formula conjectured above). (End)
%e Let n=5. A permutation is [1, 5, 3, 4, 2] with partial sums [1, 6, 9, 13, 15], two squares (1 and 9). Another permutation is [2, 1, 4, 5, 3] with partial sums [2, 3, 7, 12, 15], no square. The maximum of a(5)=3 is achieved for example by the permutation [1, 3, 5, 2, 4] with partial sums [1, 4, 9, 11, 15] and three squares (1, 4 and 9). - _R. J. Mathar_, Jan 10 2017
%o (PARI) nbsq(perm, n) = {v = vector(n, k, perm[k]); w = vector(n); for (k=1, n, w[k] = sum(j=1, k, v[j]);); sum(k=1, n, issquare(w[k]));}
%o a(n) = {nbmax = 0; for (j=0, n!-1, perm = numtoperm(n, j); nb = nbsq(perm, n); if (nb > nbmax, nbmax = nb;);); nbmax};
%Y Cf. A020765.
%K nonn
%O 1,3
%A _Michel Marcus_, Jan 08 2017
%E a(12)-a(69) from _Jon E. Schoenfield_, Jan 09 2017
|
