素因数分解したら小町数となる最大の自然数
久しぶりの小町数の問題というか、過去問をもう一度考え直してみる。『素因数分解したら小町算となる最小の自然数』午後のひとときに、数学の問題を解いてみる。問題ある自然数Nを素因数分解したところ、素因数分解した式が小町算となる最小の自然数Nを求めよ。小町算とは、1から9ま…ameblo.jp問題ある自然数nを素因数分解すると、右辺がp・q・r・…のようなすべての指数が1の素数の積となった。指数は1なので表記しないとして、右辺が小町数となった。小町数は、1から9までを1つづつ被らずに使った数です。最小のnは、2・3・5・41・67・89＝7334490であることは手計算でも求まることは出来るだろう。最大のnを、プログラミングで求めよ。シンキングタ～イムさて、久々のプログラミング問題。一つのプログラムで求めるのは、ちょっと面倒だなと思ってしまった。なので、作業を分担させることとする。まずは、0を含まないn桁の各桁数が被らない素数を列挙するプログラムを書いてみる。prime_digit.c#include <stdio.h>#include <stdlib.h>#include <math.h>int main(int argc, char *argv[]){ unsigned long long s,e; unsigned long long i,j,k; int n,num[10]; n = atoi(argv[1]); if ( n < 1 || n > 9 ) return EXIT_SUCCESS; i = powl(10,n)+0.5; s = (i-1)/9; e = (i*10-i)/9; if ( n == 1 ) { printf("2\n3\n"); s = 5; } for (i=s; i<e; i+=2) { j = sqrtl(i)+0.5; for (k=3; k<=j; k+=2) { if ( i%k == 0 ) break; } if ( k > j ) { for (n=0; n<10; n++) num[n] = 0; k = i; while ( k > 0 ) { num[k%10]++; k /= 10; } for (n=0; n<10; n++) { if ( num[n] > 1 ) break; } if ( num[0] == 0 && n == 10 ) printf("%llu\n",i); } } return EXIT_SUCCESS;}50行にも満たないコードだ。自分がプログラミングのバイトをしていたころは1行10円だったから、500円といったところだろうか。まぁ、慣れていれば5分でコーディング、テストも含めても10分ってところだろうか。prime_digit.exeを桁数をパラメータに実行したものをリダイレクトでファイル化する。prime_digit 1 > prime_digit_1.txt2357prime_digit 2 > prime_digit_2.txt1317192329313741434753596167717379838997prime_digit 3 > prime_digit_3.txt127137139149157163167173179193197239241251257263269271281283293317347349359367379389397419421431439457461463467479487491521523541547563569571587593613617619631641643647653659673683691719739743751761769821823827829839853857859863937941947953967971983prime_digit 4 > prime_digit_4.txt12371249125912791283128912971327136714231427142914391453145914831487148914931523154315491567157915831597162716371657169316971723175317591783178918231847186718731879197319872137214321532179234123472351235723712381238924172437245924672473253125392543254925792591259326172647265726592671268326872689269327132719273127412749275327892791281928372843285128572861287928972917295329572963297131673169318732173251325732593271345734613467346934913517352735293541354735713581361736593671369136973719376137693821384738513917394739674127412941394153415741594217421942314253425942614271427342834289429743274357439143974513451745194523456145674583459145974621463746394651465746734679469147214723472947514759478347894793481348174831486148714931493749514957496749734987514751675179518951975231523752615273527952815297534753815387541354175419543154375471547954835623563956415647568356895693574157435749578357915813582158275839584358495861586758695879589759235927598159876143617361976217624762576271628763176329635963796389639764216427645164736481649165216529654765716581671967816791679368236827682968416857687169176947697169837129715971937213721972437253728373217349735173697451745974817489752375297541754975617583758975917621763976437649768176917823782978417853795179638123814781678179821982318237824382638269827382918293829783178329836984198423842984318461846785138521852785378539854385638573859786238627862986418647869387138719873187418753876189238941895189638971912791379157917391879241925792819283934193719413942194319437946194639467947395219547958796139623963196439721974397819817985198579871こんな感じで8まで作る。9を作る必要がないのは、1＋2＋3＋4＋5＋6＋7＋8＋9＝45ということなので、3の倍数であり、9の倍数であるので、9桁の小町数の素数は存在しないのだ。これらリダイレクトで作ったテキストファイルを複数開いて、照合するプログラムを作れば、容易に見つけることが出来るだろう。prime_digit_2p.c#include <stdio.h>#include <stdlib.h>#include <math.h>int main(){ FILE *f1,*f2; char n1[30],n2[30]; int rec[9] = {0,4,20,83,395,1610,5045,12850,23082}; int num[10]; int i,j,k,l,m; unsigned long long x,y,t,mx; mx = 0L; for (i=8; i>4; i--) { j = 9-i; sprintf(n1,"prime_digit_%d.txt",i); sprintf(n2,"prime_digit_%d.txt",j); f1 = fopen(n1,"ra"); f2 = fopen(n2,"ra"); for (k=0; k<rec[i]; k++) { fscanf(f1,"%llu",&x); for (l=0; l<rec[j]; l++) { fscanf(f2,"%llu",&y); for (t=0; t<10; t++) num[t] = 0; t = x; while ( t > 0 ) { num[t%10] ++; t /= 10; } t = y; while ( t > 0 ) { num[t%10] ++; t /= 10; } for (t=1; t<10; t++) if ( num[t] != 1 ) break; if ( t == 10 ) { t = x*y; if ( t > mx ) printf("%llu\t%llu\t%llu\n",mx=t,x,y); } } fseek(f2, 0L, SEEK_SET); } fclose(f1); fclose(f2); } return EXIT_SUCCESS;}2つの素数の積の導き出した答えは、842696243 97523 8641842696243＝8641×97523同様に3つの素数の積のプログラムでは、575176021 8521 9643 7575176021=7×8521×9643同様に4つの素数の積のプログラムでは、284561305 9421 863 5 7284561305＝5×7×863×9421もうこの辺でいいだろう。842696243＝8641×97523これが最大ということになる。ちなみに指数もありにすると、798654321ということになるだろうことは解るだろうが、問題の趣旨では指数は1で、表記しないということでしたね。今回は教材用として、出力はリダイレクトにしたが、探索用プログラムのように、内部で開いて書き込むことも出来るし、高速化するならば、アスキーテキストではなくて、バイナリで書き込んでも良いだろう。まぁ、そこまで膨大なデータにならないのと、目視出来るという意味でアスキーテキストにしてみました。50過ぎのコマンド系のプログラマって、今どきのプログラミングではないので、やる必要あるのか？ってのはある。時流に乗るならば、Pythonとかになるんだろうけど、どうなんだろうね。自分はGUIよりも、コマンド叩いてきた人間なんで、いや、もうGUIの方が長いというか、今どきコマンド叩いている人間がどれくらいいるのだろうか。ただ、毎回図形問題で描いている図は、htmlとjavascriptで書いているというか描いているのと、エディタはメモ帳だからね。既にあるもので、どうにかこうにかしなければいけなかったので、未だにメモ帳で済んでしまっているのも、なんだかなって思ってしまう。逆に、統合化環境とか言われると、また一から覚えないとならないんだろうな。さて、現代はAIの時代だ。AIにどのように質問したら、上記のような解を得られるのだろうか。geminiととことん会話しながら最小、最大の解を求めさせてみましたが、いつまでたっても最小も最大も求められませんでした。AIも、この手のような問題はまだまだなようです。結局、信じられるのは自分のスキルってことですかね。ではではa img { background-color: lightgray;}table.renbun td { border: 0px; padding: 2px 2px 2px 2px; vertical-align: middle; white-space: nowrap; }table.renbun td.ul { border-style: solid; border-width: 0px 0px 1px 0px; }table.renbun td.ol { border-style: solid; border-width: 1px 0px 0px 0px; }table.ans td:nth-child(1) { text-align: center; }table.ans td div { width: 265px; overflow-x: scroll; }table.ans td div span { white-space: nowrap; }table.test td {white-space: nowrap;padding: 0 5px;text-align: right;} .u {border-bottom-style: solid;border-bottom-width: 1px;text-align: center;}table#list td { padding: 0 2px; font-family: monospace; }.no { display:inline-block; text-align:center; vertical-align:middle;}.ni { display:inline-block; text-align:center; vertical-align:middle; line-height:100%;}.ns { font-family:serif; font-size:250%; line-height:100%;}.io { display:inline-block; white-space:nowrap;}.io sub { vertical-align:bottom; white-space:nowrap;}.io sup { vertical-align:top; white-space:nowrap;}.ii { display:inline-block; vertical-align:middle;}.is { vertical-align:middle; font-family:arial;// font-family: sans-serif; font-size:300%; line-height:70%; font-weight: 5;// margin: 0 -15px 0 -10px;}.ii2{ display:inline-block; line-height:100%; vertical-align:middle;}.is2{ line-height:155%;// line-height:109%; font-family:sans-serif;}.mo { display:inline-block; vertical-align:middle;}.mi { display:inline-block; white-space:nowrap; vertical-align:middle; line-height:100%;}html:not([lang]) .mp { display:inline-block; line-height:100%; font-size:120%; font-family:sans-serif; margin: 0; padding: 0;}.mp{ display:inline-block; line-height:100%; font-size:120%; font-family:serif; margin: 0; padding: 0;}.md{ display:inline-block; line-height:120%; text-align:right; margin: 0 5px;}.lo { display:inline-block; text-align:center; vertical-align:middle;}.li { display:inline-block; text-align:center; vertical-align:middle; line-height:100%; margin: 0 5px 0 0;}.ls { font-family:serif; font-size:120%; line-height:100%;}.fb {border-style:solid;border-width:1px 0 0 0;margin:1px 0;}.fo {display:inline-block;text-align:center;vertical-align:middle;white-space: nowrap;}.fo span {margin: 0 3px;}.fo span span {margin: 0 0;}.article table {white-space: nowrap;}.ro{display:inline-block;white-space:nowrap;line-height:100%;position:static;}.rt{font-family: 'Meiryo', 'YuGothic', 'Gothic', sans-serif;}.ri{display:inherit;border-style:solid;border-width:1px 0 0 0;padding:0 1px 0 1px;margin:1px 0 0 0;position:relative; left:-1.5px;}article table {margin-bottom: 0 !important;}article table td {white-space: nowrap;text-align: center;}
