プログラムの依頼

 投稿者:GAI  投稿日:2013年12月26日(木)20時48分11秒
  プロジェクトオイラーのProblem303にある
f(n)をnの倍数であり、10進数で表すと2以下の数字のみが用いられる最小の数と定義されており
即ち
f(2)=2
f(3)=12
f(4)=12
f(5)=10
f(6)=12
f(7)=21
f(8)=112
となる。
そこでf(9)がなにかを探せるプログラムを作ってもらいたいんですが・・・
さらに任意のnについてf(n)を求められるようにできますか?
 

Re: プログラムの依頼

 投稿者:nagram  投稿日:2013年12月27日(金)10時34分38秒
  > No.3259[元記事へ]

GAIさんへのお返事です。

根本的に再修正しました(2013/12/27 11:56)
● n=9に特化したプログラム
LET n=9
DIM k(40)
LET c=1
FOR i=1 TO 99
   LET f=n*i
   LET check=0
   FOR j=0 TO 1
      IF MOD(f/10^j,10)>=3 THEN ! 倍数の下(j+1)桁目
         LET check=1
         EXIT FOR
      END IF
   NEXT j
   IF check=0 AND i/10<>INT(i/10) THEN ! 末位の0を回避
      LET k(c)=i
      PRINT k(c); ! k(c)=58,68,69,78,79,89  下2桁
      LET c=c+1
   END IF
NEXT i
PRINT " 下2桁"
LET c=c-1
LET d=100
DO WHILE d<100000
   FOR p=0 TO 2*d-1 STEP 100 ! 上1桁は1か2
      FOR i=1 TO c
         LET s=d+p+k(i)
         LET f=n*s
         LET check=0
         FOR j=2 TO LOG10(f)
            IF MOD(f/10^j,10)>=3 THEN ! 倍数の下(j+1)桁目
               LET check=1
               EXIT FOR
            END IF
         NEXT j
         IF check=0 THEN PRINT n;s;f ! s=1358,f(9)=12222
      NEXT i
   NEXT p
   LET d=10*d
LOOP
END
出力したリストは、sの末位が0の場合を除いてます。


● nを一般化したプログラム
LET n=6502463 ! n>=10とする。(n=10^7ぐらいが実質的な上限か?)
LET mx=100000000 ! 調査するsの上限
PRINT " n"," s","f(n)=n*s"
PRINT n,
LET dd=INT(LOG10(n))
IF mx<10^(dd+1) THEN LET mx=10^(dd+2)
LET n0=0
FOR i=1 TO dd
   IF MOD(n,10^i)=0 THEN LET n0=i ! nが10の倍数
NEXT i
LET n=n/10^n0
LET file$="C:delete_this_file_no_problem.TXT"
OPEN #1: NAME file$
ERASE #1
DIM kk(40)
LET c,cc=1
FOR i=1 TO 99
   LET f=n*i
   LET check=0
   CALL d_check(0,1)
   IF check=0 AND i/10<>INT(i/10) THEN
      LET kk(cc)=i
      LET cc=cc+1
      CALL d_check(2,INT(LOG10(f)))
      CALL s_check(i)
   END IF
NEXT i
LET cc=cc-1
!
FOR s1=100 TO 10^(dd+1) STEP 100
   FOR s2=1 TO cc
      LET f=n*(s1+kk(s2))
      LET check=0
      CALL d_check(0,dd)
      IF check=0 THEN
         LET k0=s1+kk(s2)
         PRINT #1: k0
         LET c=c+1
         CALL d_check(dd+1,INT(LOG10(f)))
         CALL s_check(k0)
      END IF
   NEXT s2
NEXT s1
!
SUB d_check(a,b)
   FOR j=a TO b
      IF MOD(f/10^j,10)>=3 THEN ! 倍数の下(j+1)桁目
         LET check=1
         EXIT SUB
      END IF
   NEXT j
END SUB
SUB s_check(s)
   IF check=0 THEN
      PRINT s,f*10^n0
      CLOSE #1
      FILE DELETE file$
      STOP
   END IF
END SUB
!
LET c=c-1
IF c=0 THEN
   PRINT "f(n)は存在しない"
   CLOSE #1
   FILE DELETE file$
   STOP
END IF
!
SET #1: POINTER BEGIN
DIM k(c)
FOR i=1 TO c
   INPUT #1: k(i)
NEXT i
CLOSE #1
FILE DELETE file$
!PRINT c
!MAT PRINT k;
LET d=10^(dd+1)
DO WHILE d<mx
   FOR p=0 TO 10*d-1 STEP 10^(dd+1)
      FOR i=1 TO c
         LET s=d+p+k(i)
         LET f=n*s
         LET check=0
         CALL d_check(dd+1,LOG10(f))
         IF check=0 THEN
            PRINT s,f*10^n0
            STOP
         END IF
      NEXT i
   NEXT p
   LET d=10*d
LOOP
PRINT "発見できませんでした。mxの値を大きくして再調査して下さい。"
END
 

戻る