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

 Palindrome ponder (Posted on 2012-09-23)
Determine the smallest base ten positive palindrome with exactly 4 distinct prime factors.

 No Solution Yet Submitted by K Sengupta Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution | Comment 2 of 8 |

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 factors858            2  3  11  132002           2  7  11  132442           2  3  11  373003           3  7  11  134774           2  7  11  315005           5  7  11  135115           3  5  11  316666           2  3  11  10110101          3  7  13  3715351          3  7  17  4317871          3  7  23  3722422          2  3  37  10122722          2  3  7  54124242          2  17  23  3126562          2  3  19  23326962          2  13  17  6128482          2  3  47  10135853          3  17  19  3736363          3  17  23  3141314          2  7  13  22743734          2  3  37  19743834          2  7  31  10145654          2  3  7  108747874          2  3  79  10149494          2  3  73  11349794          2  3  43  19349894          2  13  19  10151015          3  5  19  17951315          3  5  11  31151415          5  7  13  11353535          3  5  43  8353835          3  5  37  9753935          5  7  23  6756865          3  5  17  22358485          3  5  7  55759295          3  5  59  6759595          3  5  29  13760006          2  3  73  13762526          2  3  17  61362826          2  3  37  28364246          2  7  13  35364446          2  3  23  46766666          2  3  41  27166766          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

 Search: Search body:
Forums (0)