Determine the maximum value of a (base ten) positive integer N (with non leading zeroes) such that each of the digits of N, with the exception of the first digit and the last digit, is less than the geometric mean of the two neighboring digits.

*** For an extra challenge, solve this puzzle without the aid of a computer program.

Of the 949 such numbers that can't be extended farther on the right or to the left (such as the short 96557 or 75569, for which no possible next--or previous--digit would allow the 7 to continue to be valid), the largest is 95322359, found by:

DECLARE SUB addOn ()
DIM SHARED dig(25), sizeNow, ansCt, maxTot, digMax(25), maxSize

FOR a = 1 TO 9
 dig(0) = a
FOR b = 0 TO 9
 dig(1) = b
 sizeNow = 2
 addOn

NEXT
NEXT
PRINT
PRINT ansCt
FOR i = 0 TO maxSize - 1
  PRINT digMax(i);
NEXT
PRINT

SUB addOn
  IF dig(sizeNow - 2) = 0 THEN
    minDig = 10
  ELSE
    minDig = INT(dig(sizeNow - 1) * dig(sizeNow - 1) / dig(sizeNow - 2) + 1)
  END IF
  IF minDig > 9 THEN
   IF dig(1) * 9 <= dig(0) * dig(0) AND sizeNow >= 3 THEN
    tot = 0
    FOR i = 0 TO sizeNow - 1
       PRINT dig(i);
       tot = tot * 10 + dig(i)
    NEXT i
    PRINT
    IF tot > maxTot THEN
      maxTot = tot
      maxSize = sizeNow
      FOR i = 0 TO sizeNow - 1
        digMax(i) = dig(i)
      NEXT
    END IF
    ansCt = ansCt + 1
   END IF
  ELSE
    FOR newDig = minDig TO 9
      dig(sizeNow) = newDig
      sizeNow = sizeNow + 1
      addOn
      sizeNow = sizeNow - 1
    NEXT
  END IF
END SUB

 

Posted by Charlie on 2011-10-21 15:09:42