#:g1: HAKMEM: ITEM 59 (Schroeppel)

Posted 2021-05-07 23:52:11 GMT

このブログのためのネタ帳をひっくり返して眺めてみると5年位放置しているネタで、HAKMEM: ITEM 59 (Schroeppel)というメモがありました。

HAKMEMはMIT AIラボの人達のメモ集ですが、割合に雑多なメモです。
HAKMEM ITEM 59は、数字の関係だけが記述されていて、メモを残した理由も記述されていません。

                                               2
91038 90995 89338 00226 07743 74008 17871 09376  =

82880 83126 51085 58711 66119 71699 91017 17324 91038 90995 89338 00226 07743 74008 17871 09376

とりあえず、

ような数を探してみろということなのかなと思い、例題の40桁の倍の80桁のものを探してみることにします。

(defun fig (x)
  (length (princ-to-string x)))

(defun test-it (x) (multiple-value-bind (q r) (floor (expt x 2) (expt 10 (fig x))) (= x r)))

(defun pp (x &optional (out *standard-output*)) (let ((xx (format nil "~,,' ,5:D" x))) (format out "~%~VD~%~A =~2%~{~V,,' ,5:D~%~}" (1+ (length xx)) 2 xx (multiple-value-bind (q r) (floor (expt x 2) (expt 10 (fig x))) (list (length xx) q (length xx) r)))))

(defun compose-num (x base) (parse-integer (format nil "~D~D" x base)))

(defun decompose-num (x) (maplist (lambda (ns) (parse-integer (coerce ns 'string))) (coerce (princ-to-string x) 'list)))

(defun hakmem59 (n &optional (limit 80)) ;;雑な生成 (loop (when (>= (fig n) limit) (return)) (dotimes (x 1001) ;雑な連続する0への対策 (let ((xn (compose-num x n))) (when (test-it xn) (setq n xn))))) ;;limit桁に切り詰め (setq n (rem n (expt 10 limit))) ;;表示 (dolist (x (reverse (decompose-num n))) (when (= (fig (expt x 2)) (* 2 (fig x))) (pp x))))

2乗した場合に、下一桁に自身の数字が出現する数は、0、1、5、6ですが、下半分の桁に自分自身が現われるとなると、5、6しかありません。
ということで、5か6から出発して一桁ずつ数を当て嵌めて探していけば、簡単にみつかります。

(hakmem59 6 80)
...
 ...
                                                                                               2
61490 10993 78334 90419 13618 89994 42576 57676 91038 90995 89338 00226 07743 74008 17871 09376  =

37810 33620 16684 89789 77935 64658 06599 50861 58235 23230 14798 96610 06702 69587 17457 60530 61490 10993 78334 90419 13618 89994 42576 57676 91038 90995 89338 00226 07743 74008 17871 09376

(hakmem59 5 80) ... ... 2 38509 89006 21665 09580 86381 10005 57423 42323 08961 09004 10661 99773 92256 25991 82128 90625 =

14830 11632 60015 08951 50697 84669 21446 35507 76157 41238 36122 96157 91215 21570 81715 41779 38509 89006 21665 09580 86381 10005 57423 42323 08961 09004 10661 99773 92256 25991 82128 90625

まとめ

以上、雑な探索をしてみましたが、多分探索しなくても一発でみつかる式があったりするんでしょうね。


HTML generated by 3bmd in LispWorks 7.0.0

comments powered by Disqus