Determine the smallest base ten positive palindrome with exactly 4 distinct prime factors.

We can either multiply various combinatons of primes in groups of four, or factor all palindromes in order and select the ones that have exactly four unique prime factors.

First:

DEFDBL A-Z
CLS

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

FOR tot = 10 TO 80
  FOR a = 1 TO tot / 4
    FOR b = a + 1 TO (tot - a) / 3
      FOR c = b + 1 TO (tot - a - b) / 2
        d = tot - a - b - c
        IF d > c AND d <= 20 THEN
           pa = prm(a): pb = prm(b): pc = prm(c): pd = prm(d)
           prod = pa * pb * pc * pd
           p$ = LTRIM$(STR$(prod))
           good = 1
           FOR i = 1 TO LEN(p$) / 2
             IF MID$(p$, i, 1) <> MID$(p$, LEN(p$) + 1 - i, 1) THEN good = 0: EXIT FOR
           NEXT
           IF good THEN PRINT prod, pa; pb; pc; pd: ct = ct + 1
           IF ct = 45 THEN END
        END IF
      NEXT
    NEXT
  NEXT
NEXT

finds

palindrome     prime factors
 858           2  3  11  13
 2002          2  7  11  13
 3003          3  7  11  13
 5005          5  7  11  13
 2442          2  3  11  37
 4774          2  7  11  31
 5115          3  5  11  31
 10101         3  7  13  37
 15351         3  7  17  43
 17871         3  7  23  37
 24242         2  17  23  31
 35853         3  17  19  37
 36363         3  17  23  31
 26962         2  13  17  61
 74347         7  13  19  43
 133331        11  17  23  31
 78387         3  17  29  53
 53935         5  7  23  67
 83638         2  19  31  71
 59295         3  5  59  67
 796697        11  23  47  67
 3967693       29  41  47  71
 3561653       17  53  59  67

 
so 858 is the answer to the puzzle.
 
We can also know that 2002 is the second smallest such number, as all primes up through 71 have been tried, so that all such numbers at least through 2*3*5*71 = 2130 will have been found. Beyond that we can't guarantee that the list has no gaps.
 
To get around that problem we can just test all palindromes in order, and test whether the factoring conditions exist:
 
DECLARE FUNCTION factor! (num!)
CLS
DIM SHARED fct(4)
FOR numchar = 2 TO 10
  halfchar = INT(numchar / 2)
  extra = numchar MOD 2
  strt = INT(10 ^ (halfchar - 1) + .5)
  fin = INT(10 ^ (halfchar) + .5) - 1
  FOR n = strt TO fin
    s1$ = LTRIM$(STR$(n))
    s2$ = ""
    FOR i = halfchar TO 1 STEP -1
      s2$ = s2$ + MID$(s1$, i, 1)
    NEXT i
    IF extra = 0 THEN
      IF factor(VAL(s1$ + s2$)) THEN
        PRINT s1$ + s2$, fct(1); fct(2); fct(3); fct(4): solct = solct + 1
      END IF
    ELSE
      FOR dg = 0 TO 9
        IF factor(VAL(s1$ + LTRIM$(STR$(dg)) + s2$)) THEN
         PRINT s1$ + LTRIM$(STR$(dg)) + s2$, fct(1); fct(2); fct(3); fct(4): solct = solct + 1
        END IF
      NEXT dg
    END IF
    IF solct > 42 THEN END
  NEXT n
NEXT numchar

FUNCTION factor (num)
 diffCt = 0: good = 1
 n = ABS(num): IF n > 0 THEN limit = SQR(n):  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 FUNCTION
 LOOP
 IF n > 1 THEN diffCt = diffCt + 1: IF diffCt <= 4 THEN fct(diffCt) = n
 IF diffCt = 4 THEN factor = 1:  ELSE factor = 0
 EXIT FUNCTION

DivideIt:
 count = 0
 DO
  q = INT(n / dv)
  IF q * dv = n AND n > 0 THEN
    n = q: count = count + 1: IF n > 0 THEN limit = SQR(n):  ELSE limit = 0
    IF limit <> INT(limit) THEN limit = INT(limit + 1)
   ELSE
    EXIT DO
  END IF
 LOOP
 IF count > 0 THEN
   diffCt = diffCt + 1
   IF count > 1 OR diffCt > 4 THEN good = 0: factor = 0: EXIT FUNCTION
   fct(diffCt) = dv
 END IF
 RETURN
END FUNCTION

finding

palindrome     prime factors
858            2  3  11  13
2002           2  7  11  13
2442           2  3  11  37
3003           3  7  11  13
4774           2  7  11  31
5005           5  7  11  13
5115           3  5  11  31
6666           2  3  11  101
10101          3  7  13  37
15351          3  7  17  43
17871          3  7  23  37
22422          2  3  37  101
22722          2  3  7  541
24242          2  17  23  31
26562          2  3  19  233
26962          2  13  17  61
28482          2  3  47  101
35853          3  17  19  37
36363          3  17  23  31
41314          2  7  13  227
43734          2  3  37  197
43834          2  7  31  101
45654          2  3  7  1087
47874          2  3  79  101
49494          2  3  73  113
49794          2  3  43  193
49894          2  13  19  101
51015          3  5  19  179
51315          3  5  11  311
51415          5  7  13  113
53535          3  5  43  83
53835          3  5  37  97
53935          5  7  23  67
56865          3  5  17  223
58485          3  5  7  557
59295          3  5  59  67
59595          3  5  29  137
60006          2  3  73  137
62526          2  3  17  613
62826          2  3  37  283
64246          2  7  13  353
64446          2  3  23  467
66666          2  3  41  271
66766          2  7  19  251

The first one that's not found on the first list is 6666. The first list had only 12 5-digit answers, but we see there are many more.

Posted by Charlie on 2012-09-23 12:32:14