login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A280814 The maximum number of squares among the partial sums of any permutation of the integers [1..n]. 0
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, 17, 18, 19, 19, 20, 20, 21, 21, 22, 23, 23, 24, 25, 25, 26, 26, 27, 27, 28, 29, 30, 30, 31, 31, 32, 32, 33, 33, 34, 35, 36, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

LINKS

Table of n, a(n) for n=1..69.

Li Zhou et al., Solution to Problem O376, Mathematical Reflections 4 (2016) p. 23.

FORMULA

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

From Jon E. Schoenfield, Jan 13 2017: (Start)

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).

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.

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).

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)

EXAMPLE

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

PROG

(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])); }

a(n) = {nbmax = 0; for (j=0, n!-1, perm = numtoperm(n, j); nb = nbsq(perm, n); if (nb > nbmax, nbmax = nb; ); ); nbmax};

CROSSREFS

Cf. A020765.

Sequence in context: A247911 A103355 A029092 * A319433 A253671 A209081

Adjacent sequences:  A280811 A280812 A280813 * A280815 A280816 A280817

KEYWORD

nonn

AUTHOR

Michel Marcus, Jan 08 2017

EXTENSIONS

a(12)-a(69) from Jon E. Schoenfield, Jan 09 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 15 13:37 EDT 2021. Contains 342977 sequences. (Running on oeis4.)