+- QB64 Phoenix Edition (https://qb64phoenix.com/forum)
+-- Forum: QB64 Rising (https://qb64phoenix.com/forum/forumdisplay.php?fid=1)
+--- Forum: Prolific Programmers (https://qb64phoenix.com/forum/forumdisplay.php?fid=26)
+---- Forum: bplus (https://qb64phoenix.com/forum/forumdisplay.php?fid=36)
+---- Thread: Challenges (/showthread.php?tid=233)
RE: Challenges - SMcNeill - 06-19-2024
(06-18-2024, 10:42 PM)bplus Wrote: 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
RE: Challenges - KingLeonidas - 06-19-2024
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
NEXTRE: Challenges - bplus - 06-19-2024
+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.
RE: Challenges - bplus - 06-21-2024
since we are a page beyond the original challenge post here it is again:
Quote: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.
Quote: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
Quote: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:
Quote: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?
RE: Challenges - bplus - 06-23-2024
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