All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Consecutive Integer Sums (Posted on 2004-06-28)
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.

 See The Solution Submitted by Brian Smith Rating: 4.3333 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Computer solution | Comment 11 of 22 |

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

 Search: Search body:
Forums (0)