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

Home > Numbers
Consecutive Integer Sums (Posted on 2004-06-28) Difficulty: 3 of 5
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.)
Solution 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information