Consecutive Integers Challenge

[plus]

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.


I will post my solution in couple of days but fun to see peoples different approaches to the problem in code.

b = b + ...

[tsh73]

I've got 17 numbers (including 1)
EDIT 16, one-by-off error in code
and I found that specual number,
let's say sum of special number digits is 18
(but how to get these ways I would need yet to think)
EDIT
Pinned it

[plus]

tsh73 if you haven't gotten it yet, you probably don't understand problem? you, john, rod, xxgeek was my bet

to be clear there is a certain kind of number that can not be expressed as a sum of consecutive numbers, not many between 1 and 1000 but enough for a pattern to jump out at you once you see what are left behind.

two people have answered correctly on another forum.

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

b = b + ...

[tsh73]

tsh73 if you haven't gotten it yet, you probably don't understand problem?

LOL
just another one-off error
now 10 numbers

[plus]

tsh73 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

b = b + ...

[plus]

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.

b = b + ...

[plus]

well i guess no one else is going to try, here is my code solution
'_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
Dim numbers(1000)
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 Print i;" ";
Next
' !!! result 945 is expressed 15 different ways !!!

Print: Print: Print "Here is the list the ways for consecutive numbers to sum to "; top
call consecSets 945

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; ":"; j; "+";
           tot = j
           For k = 1 To i - 1
               tot = tot + j + k
               If k = i - 1 Then Print (j + k); "="; tot Else Print (j + k); "+";
           Next
       End If
   Next
End Sub


And the numbers that can not be expressed as a sum of consecutive integers are:
1 2 4 8 16 32 64 128 256 512

what numbers can be expressed 15 ways?
945

Here is the list the ways for consecutive numbers to sum to 15
1:472+473=945
2:314+315+316=945
3:187+188+189+190+191=945
4:155+156+157+158+159+160=945
5:132+133+134+135+136+137+138=945
6:101+102+103+104+105+106+107+108+109=945
7:90+91+92+93+94+95+96+97+98+99=945
8:61+62+63+64+65+66+67+68+69+70+71+72+73+74=945
9:56+57+58+59+60+61+62+63+64+65+66+67+68+69+70=945
10:44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60+61=945
11:35+36+37+38+39+40+41+42+43+44+45+46+47+48+49+50+51+52+53+54+55=945
12:22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+42+43+44+45+46+47+48=945
13:17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+42+43+44+45+46=945
14:10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+42+43+44=945
15:2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+41+42+43=945


b = b + ...

[tsh73]

No wonder I started the same
with a bit different notation
If we start from k and write n consequent numbers, that number would be
k+n-1
Each pair (first+last), (second+one before last ), ... has sum 2*k+n-1
and there is n/2 pairs

So that give us sum
(2*k+n-1)*(n/2)
After some rewriting , got
k*n+(n-1)*(n)/2
- this is exactly
m*n + m*(m - 1)/2 bplus got!

so I created same array(1000) and increase it by one each time formula gave me a number in 1..1000
and I noted special number (945)

For printing ways of splitting this number, I reuse same code to get k and n
and for m = 945 just ptinted n numbers starting from k.
if m = 945 then
           for j = 0 to n
               print using("####",k+j);
           next
           print
       end if


My resuls look a buit backwards, but it is still same numbers.
one number can be expressed 15 different ways
what is it
945
numbers between 1 and 1000 can NOT be expressed as the sum of consecutive integers
how much?
---------------------
10
which numbers?
1
2
4
8
16
32
64
128
256
512
one number can be expressed 15 different ways
what is it
...and list the ways
---------------------
Now what is 15 ways of geting number 945?
  2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44
 10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45
 17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47
 22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49
 35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56
 44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62
 56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71
 61  62  63  64  65  66  67  68  69  70  71  72  73  74  75
 90  91  92  93  94  95  96  97  98  99 100
101 102 103 104 105 106 107 108 109 110
132 133 134 135 136 137 138 139
155 156 157 158 159 160 161
187 188 189 190 191 192
314 315 316 317
472 473 474


'k k+1 k+2 k+n-1
'//n
'(2*k+n-1)*(n/2)
'k*n+(n-1)*(n)/2


'print 7,8,9
'print 7+8+9
'print (2*7+3-1)*(3/2)
'print 7*3 + 3*(3-1)/2


N=1000
dim a(N)

'n>=2, then k<=N/2
for k = 1 to int(N/2)
   for n =2 to int(N/2)
       m=k*n+(n-1)*(n)/2   'obviously grows with n?
       if m<=N then a(m)=a(m)+1 else exit for   'break
   next
next

print "one number can be expressed 15 different ways"
print "what is it"

for i = 1 to N
   'print i, a(i)
   if a(i)=0 then c=c+1
   if a(i)=15 then print i 'that very number with 15 ways
next

print "numbers between 1 and 1000 can NOT be expressed as the sum of consecutive integers"
print "how much?"
print "---------------------"
print c

print "which numbers?"
for i = 1 to N
   if a(i)=0 then print i
next

print "one number can be expressed 15 different ways"
print "what is it"
print "...and list the ways"

print "---------------------"
print "Now what is 15 ways of geting number 945?"

for k = 2 to int(N/2)
   for n =2 to int(N/2)
       m=k*n+(n-1)*(n)/2   'obviously grows with n?
       'if m>=N else exit for   'break
       if m>N then exit for
       if m = 945 then
           for j = 0 to n
               print using("####",k+j);
           next
           print
       end if
   next
next



[plus]

tsh73 i was looking over your ways to 945 and it looks like you have an extra sequential number in the listings.

check the smallest

472 473 474

they all do start on correct digit, so just showing one too many sequential numbers.


b = b + ...

[tsh73]

Thanks bplus
sure for j = 0 to n is n+1 number, not n...
after fix
one number can be expressed 15 different ways
what is it
945
numbers between 1 and 1000 can NOT be expressed as the sum of consecutive integers
how much?
---------------------
10
which numbers?
1
2
4
8
16
32
64
128
256
512
one number can be expressed 15 different ways
what is it
...and list the ways
---------------------
Now what is 15 ways of geting number 945?
  2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43
 10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44
 17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46
 22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48
 35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55
 44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61
 56  57  58  59  60  61  62  63  64  65  66  67  68  69  70
 61  62  63  64  65  66  67  68  69  70  71  72  73  74
 90  91  92  93  94  95  96  97  98  99
101 102 103 104 105 106 107 108 109
132 133 134 135 136 137 138
155 156 157 158 159 160
187 188 189 190 191
314 315 316
472 473



'k k+1 k+2 k+n-1
'//n
'(2*k+n-1)*(n/2)
'k*n+(n-1)*(n)/2


'print 7,8,9
'print 7+8+9
'print (2*7+3-1)*(3/2)
'print 7*3 + 3*(3-1)/2


N=1000
dim a(N)

'n>=2, then k<=N/2
for k = 1 to int(N/2)
   for n =2 to int(N/2)
       m=k*n+(n-1)*(n)/2   'obviously grows with n?
       if m<=N then a(m)=a(m)+1 else exit for   'break
   next
next

print "one number can be expressed 15 different ways"
print "what is it"

for i = 1 to N
   'print i, a(i)
   if a(i)=0 then c=c+1
   if a(i)=15 then print i 'that very number with 15 ways
next

print "numbers between 1 and 1000 can NOT be expressed as the sum of consecutive integers"
print "how much?"
print "---------------------"
print c

print "which numbers?"
for i = 1 to N
   if a(i)=0 then print i
next

print "one number can be expressed 15 different ways"
print "what is it"
print "...and list the ways"

print "---------------------"
print "Now what is 15 ways of geting number 945?"

for k = 2 to int(N/2)
   for n =2 to int(N/2)
       m=k*n+(n-1)*(n)/2   'obviously grows with n?
       'if m>=N else exit for   'break
       if m>N then exit for
       if m = 945 then
           for j = 0 to n-1
               print using("####",k+j);
           next
           print
       end if
   next
next