Challenges

[SMcNeill]

What numbers between 1 and 1000 can NOT be expressed as the sum of consecutive integers?
BONUS: one number can be expressed 15 different ways as a sum of consecutive numbers what is it and list the ways.

I didn't take time to check the whole list, but it appears using the numbers from 1 to 100, that the powers of 2 are the values which can't be summed.  (2, 4, 8, 16, 32, 64..)

945, and its starting points:      2 10 17 22 35 44 56 61 90 101 132 155 187 314 472

[KingLeonidas]

Bonus points if you can calculate the O(n) eval time of SMcNeill's brutal algorithm.

Code: (Select All)

FOR n = 1 TO 945 '1000
    FOR j = 2 TO INT(n / 2)
        q = n / j
        p = INT(j / 2)
        t = 0
        trigger = 0
        IF (q > p) THEN
            IF ((j MOD 2) <> 0) THEN ' j Odd
                f = 0
                IF (q = INT(q)) THEN
                    trigger = 1
                END IF
            ELSE ' j Even
                f = .5
                IF ((n MOD 2) = 0) THEN ' n Even
                    IF (q - p) <> INT(q - p) THEN
                        IF (q * 2 = INT(q * 2)) THEN
                            trigger = 1
                        END IF
                    END IF
                ELSE ' n Odd
                    IF (q * 2 = INT(q * 2)) THEN
                        trigger = 1
                    END IF
                END IF
            END IF
            IF (trigger = 1) THEN
                PRINT j; ")"; q * j; "=";
                FOR k = q - p + f TO q + p - f
                    PRINT k;
                    t = t + k
                NEXT
                PRINT "="; t
            END IF
        END IF
    NEXT
NEXT

[bplus]

+1 Steve and KingLeonidas
   

@KingLeonidas your code would benefit from $Console:only so you can see full listing by scrolling up and down.

both of you have code radically different than mine so i will wait a couple days before posting mine, luv to see people's different approaches to same problem.

Since presenting this challenge, i found a way to write a sub (15 lines) that lists the all the ways for a number n; it does have a limit so n up to 1000 works.
BTW it found 5 numbers before 100 that had 5 ways to get consecutive numbers that sum to n.

[bplus]

since we are a page beyond the original challenge post here it is again:

What numbers between 1 and 1000 can NOT be expressed as the sum of consecutive integers?

ie 15 = 7 + 8
18 = 5 + 6 + 7

so neither one of these are in the set of numbers that can NOT be expressed as a sum of consecutive integers.

BONUS: one number can be expressed 15 different ways as a sum of consecutive numbers what is it and list the ways. Smile

here are some hints i posted elsewhere in case someone else would like to give this a shot.

hint: 1 + 2 + 3... + n = n(n+1)/2 so sum of first 100 pos integers = 100 * 101 / 2 = 50 * 101 = 5050

my first approach was to eliminate all 2 consecutive sums first then 3, then 4... up to about 40 like sieving for primes, that worked.
then i worked out a way to list all ways to get consecutive numbers to add up to any given number, that too was successful in 15 lines of code.

n + (n + 1) = sum of consecutive numbers
n + (n + 1) + (n + 2) = sum of 3 consecutive numbers
n + (n + 1) + (n + 2) + (n + 3) sum of 4 consecutive numbers

2nd day reply at another forum

yeah there are 10 from 1 to 1000 inclusive, funny i did not count them before i reread you first reply.

did you find the one that has 15 different ways to sum consecutives to it?
yes the sum of digits of the special number is 18
i didn't read that correctly the first time sorry.
In fact, what you wrote made no sense to me, but I see and appreciate you are keeping things semi-secret

more hints;
1+2 = 3
2+3 = 5
3+4 = 7
...

so all 2 consecutive number sums are odd.

1+2+3 = 6
2+3+4 = 9
3+4+5 = 12
...

so every other 3 consecutive number sums are even = 3n, n starts at 2

if 2 consecutive sums are even so likely then 4 consecutive sums
1+2+3+4 = 10
2+3+4+5 = 14
3+4+5+6 = 18
...

yeah 2 consecutives already took out all these numbers

so what's interesting to us is sum of odd number consecutive integers

last hint:

i have been thinking the pattern pretty much makes itself known in first 10 integers, by 20 it is pretty clear and by 100 solid!
but we need something for our computer programming skills to be sharpened so the BONUS number question.

i will post my code sunday, but i wonder if someone will try an approach similar to mine?

[bplus]

and the code i used for the solution was

Code: (Select All)

_Title "Sums of consecutive numbers"
' find the numbers between 1 and 1000 that can not be expressed as a sum of a consecutive number.

' ie the sum of 2 consecutives is 2n + 1 from n + (n + 1)
'    the sum of 3                 3n + 3 from n + (n + 1) + (n + 2)
'    the sum of 4                 4n + 6 from n + (n + 1) + (n + 2) + (n + 3)
'    the sum of 5                 5n + 10  from n + (n + 1) + (n + 2) + (n + 3) + (n + 4)
' ...
'    the sum of m consecutives is m*n + m*(m - 1)/2
$Console:Only
Width 140
Dim numbers(1 To 1000) As Integer
m = 2
n = 1
While m < 50
    x = m * n + m * (m - 1) / 2
    While x < 1001
        'Print m, n, x, "zzz..."
        'Sleep
        numbers(x) = numbers(x) + 1
        n = n + 1
        x = m * n + m * (m - 1) / 2
    Wend
    m = m + 1
    n = 1
Wend
Print: Print "And the numbers that can not be expressed as a sum of consecutive integers are:"
top = 1
For i = 1 To 1000
    If numbers(i) > top Then top = numbers(i)
    If numbers(i) = 0 Then Print i;
Next

' !!! result ONLY powers of 2 can not be a sum of consecutive numbers !!!
Print: Print: Print "what numbers can be expressed"; top; "ways?"
For i = 1 To 1000
    If numbers(i) = top Then save = i: Print i,
Next

' !!! result 945 is expressed 15 different ways !!!

Print: Print: Print "Here is the list of ways for consecutive numbers to sum to"; save
consecSets (save)

Sub consecSets (n)
    For i = 2 To 50
        o = n - i * (i - 1) / 2
        If o Mod i = 0 And o > 0 Then
            count = count + 1
            j = o \ i
            Print count; ":"; ts$(j); "+";
            tot = j
            For k = 1 To i - 1
                tot = tot + j + k
                If k = i - 1 Then Print ts$(j + k); " = "; ts$(tot) Else Print ts$(j + k); "+";
            Next
        End If
    Next
End Sub

Function ts$ (n)
    ts$ = _Trim$(Str$(n))
End Function