マーティン・ガードナーの最難問

というのを見つけた。

 cf. 数学の粘度のやつ – arik_egaのノート

ある数の粘度は、すべての桁を掛けて出る答えが1桁になるまでにかかる積算の回数で表す。それぞれの桁の数を掛け算して出るのが2番目の数で、そのまた全桁の数を掛けて出るのが3番目の数…こうして1桁の数が出るまでやり、出るまでに重ねた掛け算の回数を数えるのだ。

例えば、77は粘度4だ。なぜなら1桁になるまで4回掛け算しなきゃならないからね(77-49-36-18-8)。粘度1で一番小さい数は10、粘度2で一番小さい数は25、粘度3で一番小さい数は39、粘度4の最小数は77だ。では、粘度5で一番小さい数は何?

Scheme でやってみた。特に何の工夫もなく力任せに1から順に試していって粘度が5になる数を見つけたらそれを返すだけ。

(define divmod
  (lambda (n m)
    (list (div n m) (modulo n m))))

(define mul
  (lambda (n)
    (let loop ((dm (divmod n 10)) (l '()))
      (if (= (car dm) 0)
          (apply * (cons (cadr dm) l))
          (loop (divmod (car dm) 10) (cons (cadr dm) l))))))

(define nend
  (lambda (n)
    (let loop ((x n) (i 0))
      (if (< x 10)
          i
          (loop (mul x) (+ i 1))))))

(define nend_smallest
  (lambda (n)
    (let loop ((i 1))
      (if (= (nend i) n)
          i
          (loop (+ i 1))))))

(print (nend_smallest 5))

実行結果:

^o^ > gosh nend.scm
679