Conference rusure::math

If there are an odd number of integers, they are:

	n-k, n-k+1, n-k+2, ..., n+k-1, n+k

and their sum is

	(2k+1) * n = 10000

So (2k+1) is an odd factor of 10000, i.e. 1, 5, 25, 125, or 625:

	2k+1	k	n	integers		OK?

	1	0	10000	10000			y
	5	2	2000	1998, ..., 2000		y
	25	12	400	388, ..., 412		y
	125	62	80	16, ..., 144		y
	625	312	16	some are negative	n

If there are an even number of integers, they are:

	n-k, n-k+1, n-k+2, ..., n+k-1

and their sum is

	2k * (n - 1/2) = k * (2n-1) = 10000

So (2n-1) is an odd factor of 10000, i.e. 1, 5, 25, 125, or 625:

	2n-1	n	k	integers		OK?

	1	1	10000	some are negative	n
	5	3	2000	some are negative	n
	25	13	400	some are negative	n
	125	63	80	some are negative	n
	625	313	16	297, ..., 328		y

John

reply .1 is correct in enumerating the solutions. The 'some terms are 
negative' part of the enumeration turns out to count duplicates.

For the moment assume there are an odd number, 2m+1, of terms in the
sequence and call the middle number n. On either side of the middle there
are m terms. Add the numbers from both sides (...,n-1,n,n+1,...) and the
constant terms cancel so the sum is (2m+1)n = 10000. Since 2m+1 is odd and
the only odd divisors of 10000 are powers of 5 (5^0,5^1,5^2,5^3,5^4) there
are just 5 cases to consider: 
	m	2m+1	n	seq
	0	1	10000	{10000}
	2	5	2000	{2000-2..2000+2}={1998..2002}
	12	25	400	{400-12..400+12}={388..412}
	62	125	80	{80-62..80+62}={18..142}
	312	625	16	(16-312..16+312}={-296..328}
In the last case, {-296..328}, the numbers from -296..296 sum to zero, so
the fifth solution is {297..328}. Note that the fifth solution has an even
number of terms. 

If we start by assuming the number of terms is even, 2m, let the central
pair of m pairs be n and n+1; then we have m(2n+1) = 10000: the same set
of powers of 5 are involved, and exactly the same solution set is produced 
by different arithmetic.
	n	2n+1	m	seq
	0	1	10000	{1-10000..10000}={10000}
	2	5	2000	{5-2002..2002}={1998..2002}
	12	25	400	{25-412..412}={388..412}
	62	125	80	{125-142..142}={18..142}
	312	625	16	{625-328..328}={297..328}

Lynn Yarbrough 

Let S(G) be the set of solutions (n,k) to the equation:

    n+k-1
     Sum  i = G,  k >= 1,  n >= 1,  G,n,k all integers.
     i=n

Similarly, let s(G) be the set of k values.

For example, S(10000) = { (10000,1), (1998,5), (388,25), (16,125), (297,32) },
and s(10000) = { 1, 5, 25, 125, 32 }.  |S(G)| = cardinality of S(G) = 5.


Problem #1: (medium)

    For what value(s) of G <= 10^9 is |S(G)| maximized?

Problem #2: (easy)

    Let g(k) be the smallest G such that 1,2,...,k are are all members of s(G).
    Determine g(k).

Problem #3: (hard)

    Let g(s,t,k) be the smallest G such that { s, s+t, s+2*t, ..., s+(k-1)*t }
    is a subset of s(G).  Determine g(s,t,k) for k < 8.

Skimming the cream...

#2: If 2 is in s(G) then G is of the form

		n + (n+1) = 2n+1			so G is odd

    If 4 is in s(G) then G is of the form

		n + (n+1) + (n+2) + (n+3) = 4n+6	so G is even


so g(k) is undefined for k >= 4

g(1) = 1, g(2) = 3, g(3) = 9

Since |S(G)| is equal to the number of distinct odd factors of G, maximizing
the number of factors will maximize |S(G)|.

It appears that the maximal |S(G)| is 480, and the values of G for which it
attains this value are:

 4   2
3 x 5 x 7 x 11 x 13 x 17 x 19  = 654729075

 4       2
3 x 5 x 7 x 11 x 13 x 17 x 19  = 916620705

 4   2
3 x 5 x 7 x 11 x 13 x 17 x 23  (I'm too lazy to calculate this)

 4   2
3 x 5 x 7 x 11 x 13 x 19 x 23  (")

    Here is a related pair of problems...
    
    1. Which integers cannot be expressed as the sum of two or more
    consecutive integers? [very easy]
    
    2. Which positive integers cannot be expressed as the sum of two or more
    consecutive positive integers? [easy, I think]

>    1. Which integers cannot be expressed as the sum of two or more
>    consecutive integers? [very easy]
    
>    2. Which positive integers cannot be expressed as the sum of two or more
>    consecutive positive integers? [easy, I think]

I'm not sure why the two questions are different. If negative integers are 
admitted, then the solution to (1) is 'none', since for any n,
	n = n+(n-1)+...+(1-n).

Barring negative numbers: Any n that has an odd prime divisor p can be 
written p*m, m=[n/p], so 
	n = ... + (m-1) + m + (m+1) + ...  using p terms.

So the only remaining candidates are n = 2^m, m>=0. These are expressible
as a CPI sum iff n >2 and n is the difference of two nonconsecutive
triangular numbers, T(k) = k(k+1)/2. Right now I'm too tired to attack that
one. Left as an EFTR :-) 

> Barring negative numbers: Any n that has an odd prime divisor p can be 
> written p*m, m=[n/p], so 
> 	n = ... + (m-1) + m + (m+1) + ...  using p terms.
    
    The rhs may include some negative numbers. However these can be paired
    off with the low positives.
    
    eg 14 = 7*2
          = -1 + 0 + 1 + 2 + 3 + 4 + 5
          = 2 + 3 + 4 + 5

>>the solution to (1) is 'none', since for any n,
>>	n = n+(n-1)+...+(1-n).
>    
>    Yep. One minor nit is that n=0 is a special case not covered by the
>    above. 

Eh? Is not 0 = 0 + (-1) + 1?

The rest of the proof is neat. One of the joys of this conference is to see 
how, when one person can't complete the job, another picks up the pieces.

>the solution to (1) is 'none', since for any n,
>	n = n+(n-1)+...+(1-n).
>
>Eh? Is not 0 = 0 + (-1) + 1?

OK.

I misinterpretted your '...' notation.

I read the above as summing the elements of the sequence {n,...,1-n} which
doesn't work for n=0.

Now I see my error in that you meant (I think) n + the sum of the elements in
the sequence {n-1,...,1-n}. n=0 is still a slightly unusual case because the
sum to be made is actually 0 + (-1) + 0 + 1.

For n > 0 there is no difference between the two interpretations.