The integer 30 can be written as a sum of consecutive positive integers in three ways:
30 = 9+10+11 = 6+7+8+9 = 4+5+6+7+8.
Find the smallest positive integer which can be written as a sum of consecutive positive integers in 12 ways.
As noted before, the sums are going to be the number of terms in the series multiplied by the average value in that series. With an even number of terms, the average value will differ from an integer by .5; with an odd number of terms it will be an integer--the middle term of the series.
By factoring any number, we can divide by any factor (prime or not), and the quotient will be the average term while the chosen factor itself will be the number of terms. Two has a special status as a factor. If the number is a multiple of a power of two, then only odd factors of the number, and one higher power of two than is in the original can be used as divisors--otherwise you'd have an even number of terms but also an even average. The odd factor assures you have an odd number of terms, and the quotient is an integer. The extra power of 2 assures the quotient will be a fraction differing from an integer by .5.
The initial version of this program had a bug that led to the same answer as Thalamus. The program did not consider, for odd numbers, the possibility of dividing by 2 (or multiples of 2), just because 2 did not appear as a factor in the original number. But that just meant it appeared zero times as a factor, and we are to consider one more factor of 2 than makes up the number, as mentioned above. So the table of prime factors must be prepopulated with zero occurrences of the factor 2.
The program is designed to show the lowest number that has any given n such arithmetic series. The program is:
DECLARE SUB tryFact (where!)
DECLARE SUB factor (num!, s$)
CLEAR , , 4000
DIM SHARED prim(100), primTimes(100), primCtd(100), currP, smallVal, numb, solCt
OPEN "consec.txt" FOR OUTPUT AS #3
FOR numb = 2 TO 30000
OPEN "temp.txt" FOR OUTPUT AS #2
factor numb, s$
s$ = s$ + " "
currP = 1
prim(1) = 2
primTimes(1) = 0
DO
s$ = LTRIM$(s$)
IF s$ = "" THEN EXIT DO
ix = INSTR(s$, " ")
n$ = LEFT$(s$, ix - 1)
s$ = MID$(s$, ix)
n = VAL(n$)
IF n <> prim(currP) THEN
currP = currP + 1: prim(currP) = n
primTimes(currP) = 1
ELSE
primTimes(currP) = primTimes(currP) + 1
END IF
LOOP
solCt = 0
smallVal = 1
tryFact 1
CLOSE 2
IF solCt > prevMax THEN
OPEN "temp.txt" FOR INPUT AS #1
DO
LINE INPUT #1, l$
PRINT #3, l$
LOOP UNTIL EOF(1)
CLOSE 1
PRINT #3, numb, solCt
PRINT #3, "-"
prevMax = solCt
END IF
IF numb MOD 1000 = 0 THEN PRINT numb
NEXT
CLOSE
SUB factor (num, s$)
s$ = "": n = ABS(num): IF n > 0 THEN limit = INT(SQR(n) + .5): ELSE limit = 0
IF limit <> INT(limit) THEN limit = INT(limit + 1)
dv = 2: GOSUB DivideIt
dv = 3: GOSUB DivideIt
dv = 5: GOSUB DivideIt
dv = 7
DO UNTIL dv > limit
GOSUB DivideIt: dv = dv + 4 '11
GOSUB DivideIt: dv = dv + 2 '13
GOSUB DivideIt: dv = dv + 4 '17
GOSUB DivideIt: dv = dv + 2 '19
GOSUB DivideIt: dv = dv + 4 '23
GOSUB DivideIt: dv = dv + 6 '29
GOSUB DivideIt: dv = dv + 2 '31
GOSUB DivideIt: dv = dv + 6 '37
IF INKEY$ = CHR$(27) THEN s$ = CHR$(27): EXIT SUB
LOOP
IF n > 1 THEN s$ = s$ + STR$(n)
EXIT SUB
DivideIt:
DO
q = INT(n / dv)
IF q * dv = n AND n > 0 THEN
n = q: s$ = s$ + STR$(dv): IF n > 0 THEN limit = INT(SQR(n) + .5): ELSE limit = 0
IF limit <> INT(limit) THEN limit = INT(limit + 1)
ELSE
EXIT DO
END IF
LOOP
RETURN
END SUB
SUB tryFact (where)
IF prim(where) = 2 THEN
maxTimes = primTimes(where) + 1: stepVal = primTimes(where) + 1
ELSE
maxTimes = primTimes(where): stepVal = 1
END IF
pwrVal = 1
FOR times = 0 TO maxTimes STEP stepVal
smallVal = smallVal * pwrVal
IF smallVal > 1 THEN
bigVal = numb / smallVal
IF smallVal MOD 2 = 0 THEN
botNo = bigVal + .5 - smallVal / 2
ELSE
botNo = bigVal - (smallVal - 1) / 2
END IF
IF botNo >= 1 AND where = currP THEN
solCt = solCt + 1
PRINT #2, botNo, botNo + smallVal - 1, bigVal
END IF
END IF
IF (smallVal = 1 OR botNo >= 1) AND where < currP THEN
tryFact where + 1
END IF
smallVal = smallVal / pwrVal
IF botNo < 1 AND smallVal > 1 THEN EXIT FOR
IF prim(where) = 2 THEN
FOR i = 1 TO stepVal
pwrVal = pwrVal * (prim(where))
NEXT
ELSE
pwrVal = pwrVal * prim(where)
END IF
NEXT
END SUB
BTW smallVal is the divisor and bigVal the quotient, and bigVal need not be bigger than smallVal, just bigger than about half of smallVal.
The output columns show the low term of the series, the high term of the series and the average number in the series. Below that list is the original number and the number of series listed for that number, followed by a hyphen separator line:
1 2 1.5
3 1
-
2 4 3
4 5 4.5
9 2
-
1 5 3
4 6 5
7 8 7.5
15 3
-
7 11 9
14 16 15
1 9 5
22 23 22.5
5 10 7.5
45 5
-
12 18 15
19 23 21
34 36 35
52 53 52.5
1 14 7.5
6 15 10.5
15 20 17.5
105 7
-
43 47 45
74 76 75
8 22 15
21 29 25
112 113 112.5
18 27 22.5
35 40 37.5
4 21 12.5
225 8
-
42 48 45
61 65 63
104 106 105
5 25 15
14 28 21
31 39 35
157 158 157.5
16 29 22.5
27 36 31.5
50 55 52.5
9 26 17.5
315 11
-
132 138 135
187 191 189
10 44 27
314 316 315
35 55 45
56 70 63
101 109 105
22 48 35
472 473 472.5
61 74 67.5
90 99 94.5
155 160 157.5
2 43 22.5
17 46 31.5
44 61 52.5
945 15
-
222 228 225
313 317 315
28 62 45
51 75 63
524 526 525
65 85 75
98 112 105
171 179 175
13 57 35
787 788 787.5
106 119 112.5
153 162 157.5
7 56 31.5
260 265 262.5
17 58 37.5
38 67 52.5
79 96 87.5
1575 17
-
402 408 405
565 569 567
64 98 81
944 946 945
125 145 135
182 196 189
311 319 315
14 76 45
41 85 63
92 118 105
1417 1418 1417.5
196 209 202.5
279 288 283.5
6 75 40.5
470 475 472.5
47 88 67.5
80 109 94.5
149 166 157.5
26 79 52.5
2835 19
-
310 320 315
492 498 495
7 83 45
691 695 693
36 90 63
82 116 99
1154 1156 1155
89 121 105
155 175 165
224 238 231
381 389 385
24 86 55
55 99 77
1732 1733 1732.5
147 168 157.5
241 254 247.5
342 351 346.5
15 84 49.5
575 580 577.5
20 85 52.5
62 103 82.5
101 130 115.5
184 201 192.5
3465 23
-
940 950 945
1482 1488 1485
97 173 135
2077 2081 2079
162 216 189
280 314 297
3464 3466 3465
299 331 315
485 505 495
686 700 693
47 151 99
1151 1159 1155
56 154 105
134 196 165
209 253 231
372 398 385
10 144 77
5197 5198 5197.5
462 483 472.5
736 749 742.5
1035 1044 1039.5
40 149 94.5
114 183 148.5
1730 1735 1732.5
125 190 157.5
227 268 247.5
332 361 346.5
569 586 577.5
20 145 82.5
71 160 115.5
166 219 192.5
10395 31
-
1570 1580 1575
2472 2478 2475
187 263 225
3463 3467 3465
288 342 315
478 512 495
681 705 693
12 186 99
5774 5776 5775
509 541 525
815 835 825
1148 1162 1155
23 187 105
113 217 165
194 268 231
1921 1929 1925
126 224 175
244 306 275
363 407 385
8662 8663 8662.5
777 798 787.5
1231 1244 1237.5
36 189 112.5
1728 1737 1732.5
103 212 157.5
213 282 247.5
322 371 346.5
2885 2890 2887.5
230 295 262.5
392 433 412.5
563 592 577.5
41 190 115.5
954 971 962.5
75 200 137.5
148 237 192.5
17325 35
-
So for more than 15 ways, you need to go to 1575, which has 17 ways, and so on up to 17,325, which has 35 ways. The program stopped checking with 30,000.
|
|
Posted by Charlie
on 2004-06-28 21:20:13 |
Computer solution
