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

 Oodles of Factors (Posted on 2005-07-08)
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

 Search: Search body:
Forums (0)