数学の粘度のやつ
はじめに
学校でS先生からマーティン・ガードナーの最難問というものを紹介された。問題の概要は次の通り。
ある数の粘度は、すべての桁を掛けて出る答えが1桁になるまでにかかる積算の回数で表す。それぞれの桁の数を掛け算して出るのが2番目の数で、そのまた全桁の数を掛けて出るのが3番目の数…こうして1桁の数が出るまでやり、出るまでに重ねた掛け算の回数を数えるのだ。
例えば、77は粘度4だ。なぜなら1桁になるまで4回掛け算しなきゃならないからね（77-49-36-18-8）。粘度1で一番小さい数は10、粘度2で一番小さい数は25、粘度3で一番小さい数は39、粘度4の最小数は77だ。では、粘度5で一番小さい数は何？
※Marthin Gardner(1914-2010)はアメリカの数学者兼科学記者。多くの数学パズルを残した。
今回はこの問題をプログラムを使って解いた。言語はCとPython
整数nの粘度を求めるプログラム
この問題を解く前段階として整数nが入力として与えられたとき整数nの粘度を求めるプログラムを書いた。
#-*- coding: utf-8 -*- def mul(a): b = 1 while True: b *= a%10 a /= 10 if a == 0: return b def nend(a): nend = 0 while True: if len(str(a)) == 1 and nend == 0: return 0 elif len(str(a)) >= 2: a = mul(a) nend += 1 elif len(str(a)) == 1: return nend n = int(raw_input("整数nを入力してください:")) print "整数nの粘度は%dです。" % nend(n)
- C
#include <stdio.h> int mul(long long int a) { int b = 1; while(1){ b *= a%10; a /= 10; if(a == 0) return b; } } int nend(long long int a) { int nend = 0; while(1){ if(a/10 < 1 && nend == 0) return 0; else if(a/10 >= 1){ a = mul(a); nend++; } else if(a/10 < 1) return nend; } } int main() { long long int n; printf("整数nを入力してください:"); scanf("%lld",&n); printf("整数nの粘度は%ldです。",nend(n)); return 0; }
粘度nの最小値を求めるプログラム
#-*- coding: utf-8 -*- def mul(a): b = 1 while True: b *= a%10 a /= 10 if a == 0: return b def nend(a): nend = 0 while True: if len(str(a)) == 1 and nend == 0: return 0 elif len(str(a)) >= 2: a = mul(a) nend += 1 elif len(str(a)) == 1: return nend n = 1 i = 1 while True: if nend(n) == i: print "粘度%dの最小値は%dです" % (i,n) i += 1 if i==8: break n += 1
- C
#include <stdio.h> int mul(long long int a) { int b = 1; while(1){ b *= a%10; a /= 10; if(a == 0) return b; } } int nend(long long int a) { int nend = 0; while(1){ if(a/10 < 1 && nend == 0) return 0; else if(a/10 >= 1){ a = mul(a); nend++; } else if(a/10 < 1) return nend; } } int main() { long long int n=1; int i=1; while(1){ if(nend(n) == i){ printf("粘度%dの最小値は%ld\n",i,n); i++; } if(i==10) break; n++; } return 0; }
このプログラム実は少し手を抜いています。というのは粘度nの最小値 < 粘度n+1の最小値という条件を勝手つけてしまっています。(実際にはそれでも問題ないのかもしれませんが証明してないので手抜き)
実行すると問題の答えの粘度5の最小値は679だとわかります。
分ったところまで粘度nの最小値を貼っておきます。(あってるかはわからない)
ちなみに粘度9はそこそこの性能のPCでも1分近く(もしくはそれ以上)かかりました。(Pythonの場合)
粘度10はCで書いてかつ、そこそこの性能のPCでも5分～10分くらいかかりました。
粘度1の最小値は10 粘度2の最小値は25 粘度3の最小値は39 粘度4の最小値は77 粘度5の最小値は679 粘度6の最小値は6788 粘度7の最小値は68889 粘度8の最小値は2677889 粘度9の最小値は26888999 粘度10の最小値は3778888999
