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

Home > Just Math
Oodles of Factors (Posted on 2005-07-08) Difficulty: 2 of 5
A. What is the lowest number that has exactly 10 distinct positive factors?

B. Exactly 1,000 distinct positive factors?

C. Exactly 1,000,000 distinct positive factors?

Example: The distinct factors of 72 are 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, and 72. Thus 72 has 12 distinct factors.

See The Solution Submitted by Leming    
Rating: 2.8571 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
computer exhaustive search | Comment 6 of 7 |
(In reply to re: general(ish) sol'n (w/o computer) -correction by Josh70679)

The following program verifies that Josh70679's constant B is indeed the smallest:

DECLARE SUB alct ()
DEFDBL A-Z
CLEAR , , 5000
CLS
OPEN "factors2.txt" FOR OUTPUT AS #2

DIM SHARED xRemain, yRemain

xRemain = 6: yRemain = 6

DIM SHARED level

DIM SHARED pair(15, 2)

alct

CLOSE

 

best = 9D+300

DIM prm(15)
DATA 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47
FOR i = 1 TO 15: READ prm(i): NEXT

OPEN "factors2.txt" FOR INPUT AS #1

DIM pwr(15)

DO
 LINE INPUT #1, l$
 l$ = LTRIM$(l$) + " "
 FOR i = 1 TO 15
   DO
     ix = INSTR(l$, " ")
     n = VAL(LEFT$(l$, ix - 1))
     l$ = LTRIM$(MID$(l$, ix))
   LOOP UNTIL n > 0
   pwr(i) = n
   IF l$ = "" THEN EXIT FOR
 NEXT
 n = i
 DO
  flag = 0
  FOR i = 1 TO n - 1
    IF pwr(i) < pwr(i + 1) THEN SWAP pwr(i), pwr(i + 1): flag = 1
  NEXT
 LOOP UNTIL flag = 0
 t = 1
 ON ERROR GOTO catch
 FOR i = 1 TO n
   t = t * prm(i) ^ pwr(i)
 NEXT
 ON ERROR GOTO 0
 IF t < best THEN
  best = t
  FOR i = 1 TO n: PRINT pwr(i); : NEXT
  PRINT : PRINT best
 END IF
aftCatch:
ON ERROR GOTO 0
LOOP UNTIL EOF(1)

CLOSE

END

catch:
 RESUME aftCatch

SUB alct
 IF xRemain = 0 AND yRemain = 0 THEN
   FOR i = 1 TO level
     PRINT #2, INT(2 ^ pair(i, 1) * 5 ^ pair(i, 2) - 1 + .5);
     PRINT pair(i, 1); pair(i, 2); "|";
   NEXT
   PRINT #2,
   PRINT
 ELSE
   level = level + 1
   IF level = 1 THEN
     xS = 0: yS = 0
   ELSE
     xS = pair(level - 1, 1): yS = pair(level - 1, 2)
     IF xS = 0 AND yS = 0 THEN yS = 1
     IF yS > yRemain THEN
       yS = 0: xS = xS + 1
     END IF
   END IF
   xR = xRemain: yR = yRemain
   FOR x = xS TO xR
     IF x = xS THEN yS1 = yS:  ELSE yS1 = 0
     FOR y = yS1 TO yR
      xRemain = xRemain - x: yRemain = yRemain - y
      pair(level, 1) = x: pair(level, 2) = y
      alct
      xRemain = xRemain + x: yRemain = yRemain + y
     NEXT y
   NEXT x
   level = level - 1
 END IF
END SUB

It outputs:

4  4  4  4  4  4  1  1  1  1  1  1
2.009616107089385D+26
9  4  4  4  4  4  1  1  1  1  1
1.738046362888116D+26

as it tries all the factorizations and outputs the best so far (the powers on one line and the result on the next).  The bottom line is Josh's constant.


  Posted by Charlie on 2005-07-08 20:34:02
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 (3)
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