Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月21日(土)10時45分20秒
  031
両替問題

考察
5p貨までの使用枚数が決まれば、1p貨の使用枚数は自動的に決まるので、
1p貨を何枚使うかは考える必要がない。
したがって、問題を置き換えて、
5p貨までを使用して、0～200￡を支払う場合の数を求めればよい。
（終り）

!!OPTION ARITHMETIC RATIONAL !多桁の整数
LET M=200
LET S=0
FOR C200=0 TO M STEP 200 !0,200,…
   LET T200=M-C200 !残りの金額について
   FOR C100=0 TO T200 STEP 100
      LET T100=T200-C100
      FOR C50=0 TO T100 STEP 50
         LET T50=T100-C50
         FOR C20=0 TO T50 STEP 20
            LET T20=T50-C20
            FOR C10=0 TO T20 STEP 10
               LET T10=T20-C10
               FOR C5=0 TO T10 STEP 5
                  LET T5=T10-C5
                  LET S=S+INT(T5/2)+1
               NEXT C5
            NEXT C10
         NEXT C20
      NEXT C50
   NEXT C100
NEXT C200
PRINT S;"通り" !73682通り
END


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月21日(土)10時49分26秒
  > No.3244[元記事へ]

046
Christian Goldbachは、全ての奇合成数は平方数の2倍と素数の和で表せると予想した。
参考サイト　http://odz.sakura.ne.jp/projecteuler/


OPTION ARITHMETIC RATIONAL !多桁の整数
FOR N=1 TO 100000 STEP 2
   LET K=1
   LET T=N-2*K^2
   DO WHILE T>1 AND prmdiv(T)<>T
      LET K=K+1
      LET T=N-2*K^2
   LOOP
   IF T<0 THEN PRINT N
NEXT N
END

!UBASICの整数論関連より　UBASIC.LIB抜粋

EXTERNAL FUNCTION prmdiv(n) !１より大きな最小の約数
OPTION ARITHMETIC RATIONAL !多桁の整数
IF n<>INT(n) THEN !整数以外なら
   PRINT "prmdiv関数でパラメータが不適当です。"
   STOP
ELSEIF n=0 THEN
   LET prmdiv=0
ELSE
   LET n=ABS(n) !絶対値をとる

   IF MOD(n,2)=0 THEN !２の倍数
      LET prmdiv=2
   ELSEIF MOD(n,3)=0 THEN !３の倍数
      LET prmdiv=3
   ELSE
      FOR i=5 TO INTSQR(n) STEP 6
         IF MOD(n,i)=0 THEN !5,11,17,23,29,…
            LET prmdiv=i
            EXIT FUNCTION
         ELSEIF MOD(n,i+2)=0 THEN !7,13,19,25,31,…
            LET prmdiv=i+2
            EXIT FUNCTION
         END IF !+1,+3,+5は２の倍数（偶数）、+1,+4は３の倍数、+5は５の倍数
      NEXT i
      LET prmdiv=n !その数自身
   END IF
END IF
END FUNCTION




003
素因数分解


OPTION ARITHMETIC RATIONAL !多桁の整数
LET N=13195
LET N=600851475143
DO
   LET P=prmdiv(N)
   DO WHILE MOD(N,P)=0 !p^k
      LET N=N/P
   LOOP
LOOP WHILE N>1
PRINT P !6857
END




010
素数の和


OPTION ARITHMETIC RATIONAL !多桁の整数
LET S=2
FOR N=3 TO 2000000 STEP 2
   IF prmdiv(N)=N THEN LET S=S+N
NEXT N
PRINT S !142913828922
END


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月21日(土)11時13分35秒
  > No.3245[元記事へ]

024
順列
0～9の10個の数字の順列を辞書順に並べ替えたときに、100万個目の文字列は何か。


LET N=10
DIM A(N) !1～10の並び
CALL Num2PermFactorial(1000000-1, A,N)
FOR i=1 TO N !0相対
   LET A(i)=A(i)-1
NEXT i
MAT PRINT A;
END

!n!の順列パターン ⇔ 0～(n!-1)の番号

EXTERNAL FUNCTION PermFactorial2Num(A(),N) !順列パターンに番号を付ける　※辞書式順序
FOR j=1 TO N-1 !階乗進数の各桁の値＋１　A[1..N]=(N-1)! … 3! 2! 1! 0!
   FOR k=j+1 TO N
      IF A(k)>=A(j) THEN LET A(k)=A(k)-1
   NEXT k
NEXT j
LET v=0
FOR j=N TO 1 STEP -1 !非負の10進数整数へ
   LET v=v*j+A(N-j+1)-1
NEXT j
LET PermFactorial2Num=v
END FUNCTION

EXTERNAL SUB Num2PermFactorial(h, A(),N) !番号から順列パターンを生成する　※辞書式順序
LET v=h !非負の10進数整数を階乗進数へ
FOR j=1 TO N
   LET t=INT(v/j)
   LET A(N-j+1)=v-t*j +1 !階乗進数の各桁の値＋１　A[1..N]=(N-1)! … 3! 2! 1! 0!
   LET v=t
NEXT j
FOR j=N-1 TO 1 STEP -1 !順列パターンへ
   FOR k=j+1 TO N
      IF A(k)>=A(j) THEN LET A(k)=A(k)+1
   NEXT k
NEXT j
END SUB


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月22日(日)11時00分8秒
  > No.3246[元記事へ]

001
1000未満の3か5の倍数になっている数字の合計を求めよ。


!!OPTION ARITHMETIC RATIONAL !多桁の整数

!その１
LET S=0
FOR N=1 TO 1000-1
   IF MOD(N,3)=0 OR MOD(N,5)=0 THEN LET S=S+N
NEXT N
PRINT S !233168


!その２
DEF F(N)=N*(N+1)/2
LET N=1000-1
PRINT 3*F(INT(N/3))+5*F(INT(N/5))-15*F(INT(N/15))

END


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月22日(日)11時01分34秒
  > No.3247[元記事へ]

002
偶数のフィボナッチ数

考察
奇数+偶数=奇数　1+2=3
偶数+奇数=奇数　2+3=5
奇数+奇数=偶数　3+5=8
（終り）


!!OPTION ARITHMETIC RATIONAL !多桁の整数

LET F1=1
LET F2=2
LET S=0
DO WHILE F2<4000000
   LET S=S+F2
   PRINT F2 !debug
   LET F4=2*F2+F1 !F3=F2+F1、F4=F3+F2、F5=F4+F3より
   LET F5=3*F2+2*F1
   LET F1=F4
   LET F2=F5
LOOP
PRINT S !4613732
END


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月22日(日)11時08分34秒
  > No.3248[元記事へ]

006
2乗和の差


OPTION ARITHMETIC RATIONAL !多桁の整数

!その１
LET N=100
PRINT (N*(N+1)/2)^2 - N*(N+1)*(2*N+1)/6 !(Σk)^2-Σk^2


!その２
LET N=100
LET S=0 !(1+2+3+ … +100)^2-(1^2+2^2+3^2+ … +100^2)
FOR A=1 TO N-1
   FOR B=A+1 TO N
      LET S=S+A*B
   NEXT B
NEXT A
PRINT 2*S !25164150

END


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月23日(月)10時39分43秒
  > No.3249[元記事へ]

005
1から20までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか。


!!OPTION ARITHMETIC RATIONAL !多桁の整数

DEF LCM(a,b)=a*b/GCD(a,b) !最小公倍数

LET L=1 !最小の数
FOR i=2 TO 20
   LET L=LCM(L,i)
NEXT i
PRINT L

PRINT 2^4*3^2*5*7*11*13*17*19 !検算

END

EXTERNAL FUNCTION gcd(a,b) !最大公約数
DO UNTIL b=0
   LET t=b
   LET b=MOD(a,b)
   LET a=t
LOOP
LET gcd=ABS(a)
END FUNCTION


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月23日(月)10時41分28秒
  > No.3250[元記事へ]

015
20×20 のマス目ではいくつのルートがあるか。


!!OPTION ARITHMETIC RATIONAL !多桁の整数

PRINT FACT(20+20)/(FACT(20)*FACT(20))

PRINT COMB(20+20,20)

LET N=20+20
LET R=20
LET C=1
FOR i=1 TO R !nCr=nPr/r!={ n*(n-1)* … *(n-r+1) } / { 1*2* … *r }
   LET C=C*(N-i+1)/i
NEXT i
PRINT C

END


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月23日(月)10時43分29秒
  > No.3251[元記事へ]

040
チャンパーノウン定数

考察
1桁の数（1～9）が、9個
2桁の数（10～99）が、90個
3桁数の数（100～999）が、900個
4桁数の数（1000～9999）が、9000個
　：
ずつ並んでいく。
（終り）


!!OPTION ARITHMETIC RATIONAL !多桁の整数

PRINT f(1)*f(10)*f(100)*f(1000)*f(10000)*f(100000)*f(1000000)
END

EXTERNAL FUNCTION f(N) !小数点以下第n位にある数字を返す
LET T=N
LET K=1 !該当する数の桁数
DO
   LET W=K*9*10^(K-1)
   IF T<=W THEN EXIT DO
   LET T=T-W
   LET K=K+1
LOOP
!!!PRINT K; T !debug

LET Q=CEIL(T/K)
LET A=10^(K-1)+Q-1 !該当する数
LET R=MOD(T,K) !桁位置
IF R=0 THEN LET R=K

LET B=10^(K-R)
LET W=MOD(INT(A/B),10)
!!!PRINT Q;R; A;B ;W !debug

LET f=W
END FUNCTION


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月25日(水)13時59分46秒
  > No.3252[元記事へ]

016
累乗の各桁の和
2^1000の各桁の和を求めよ。


OPTION ARITHMETIC RATIONAL !多桁の整数

LET N=2^1000
!!LET N=2^15
PRINT N !debug
LET S=0
DO WHILE N>0
   LET S=S+MOD(N,10)
   LET N=INT(N/10)
LOOP
PRINT S !1366

END



020
階乗の数字和
100!の各桁の数字の和を求めよ。


OPTION ARITHMETIC RATIONAL !多桁の整数

LET N=FACT(100)
!!LET N=FACT(10)
PRINT N !debug
LET S=0
DO WHILE N>0
   LET S=S+MOD(N,10)
   LET N=INT(N/10)
LOOP
PRINT S !648

END



025
1000桁のフィボナッチ数


OPTION ARITHMETIC RATIONAL !多桁の整数

LET F1=1
LET F2=1
LET K=2 !k項
DO WHILE INT(F2/10^(1000-1))=0
   LET K=K+1
   LET F3=F2+F1
   LET F1=F2
   LET F2=F3
LOOP
PRINT K !4782

END


十進BASICは、有理数モードで多桁整数が扱えるので上記のように記述すればよい。

多桁整数を実装する場合は次のようにする。

016

LET N=1000 !2^n

DIM A(1000) !10進法k桁の数　a[k]*10^(k-1)+ … +a[2]*10^1+a[1]*10^0、0≦a[j]≦9
MAT A=ZER
LET A(1)=2 !2^1=2とする
FOR i=2 TO N !2^n
   CALL MUL(A,2)
NEXT i

LET S=0 !各桁の数字の和
FOR i=1 TO 1000
   LET S=S+A(i)
NEXT i
PRINT S

END

EXTERNAL SUB MUL(A(),X) !かけ算 A=A*X
LET CY=0 !かけ算の筆算による
FOR J=1 TO 1000 !j桁目を計算する
   LET T=A(J)*X+CY
   LET A(J)=MOD(T,10)
   LET CY=INT(T/10)
NEXT J
IF CY>0 THEN
   PRINT "オーバーフロー"
   STOP
END IF
!!!MAT PRINT A; !debug
END SUB



020

LET N=100 !n!

DIM A(1000) !10進法k桁の数　a[k]*10^(k-1)+ … +a[2]*10^1+a[1]*10^0、0≦a[j]≦9
MAT A=ZER
LET A(1)=1 !0!=1!=1とする
FOR X=2 TO N !2*3*4* … *n
   CALL MUL(A,X)
NEXT X

LET S=0 !各桁の数字の和
FOR i=1 TO 1000
   LET S=S+A(i)
NEXT i
PRINT S

END



025

DIM F1(1000),F2(1000),F3(1000)
MAT F1=ZER
LET F1(1)=1
MAT F2=ZER
LET F2(1)=1

LET K=2 !k項
LET F=F2(1000) !1000桁目の値
DO WHILE F=0
   LET K=K+1

   SELECT CASE MOD(K,3) !F[n+2]=F[n+1]+F[n]
   CASE 0
      CALL ADD(F2,F1, F3)
      LET F=F3(1000)
   CASE 1
      CALL ADD(F3,F2, F1)
      LET F=F1(1000)
   CASE 2
      CALL ADD(F1,F3, F2)
      LET F=F2(1000)
   CASE ELSE
   END SELECT
LOOP
PRINT K !4782

END

EXTERNAL SUB ADD(A(),B(), C()) !足し算 C=A+B
LET CY=0
FOR i=1 TO 1000 !i桁目を計算する
   LET T=A(i)+B(i)+CY
   LET C(i)=MOD(T,10)
   LET CY=INT(T/10)
NEXT i
IF CY>0 THEN
   PRINT "オーバーフロー"
   STOP
END IF
END SUB


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月25日(水)19時55分8秒
  > No.3257[元記事へ]

206
2乗すると「1_2_3_4_5_6_7_8_9_0」の形となるような唯一の正整数を求めよ。
ただし、「_」は1桁の数である。

考察
2乗すると0になるのは、0のみである。
2乗すると9になるのは、3と7のみである。
求める値は、一の位が0で、十の位は3または7である。
よって、2乗すると「1_2_3_4_5_6_7_8_900」の形となる。
これより、「1_2_3_4_5_6_7_8_9」として、
√(10203040506070809)から√(19293949596979899)までの範囲である。
（終り）


OPTION ARITHMETIC RATIONAL !多桁の整数

FOR M=INT(INTSQR(10203040506070809)/10) TO INTSQR(19293949596979899)/10
   LET N=M*10+3
   LET T=N*N
   FOR i=9 TO 1 STEP -1
      IF MOD(T,10)<>i THEN EXIT FOR
      LET T=INT(T/100)
   NEXT i
   IF i<1 THEN PRINT N*10

   LET N=M*10+7
   LET T=N*N
   FOR i=9 TO 1 STEP -1
      IF MOD(T,10)<>i THEN EXIT FOR
      LET T=INT(T/100)
   NEXT i
   IF i<1 THEN PRINT N*10 !1389019170^2=1929374254627488900
NEXT M

END


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月27日(金)09時50分25秒
  > No.3258[元記事へ]

303
小さい桁を持つ倍数
参考サイト　http://oeis.org/A181061


OPTION ARITHMETIC RATIONAL !多桁の整数

LET S=0
FOR N=1 TO 100
   LET T=F(N)
   PRINT N; T !debug
   LET S=S+T/N
NEXT N
PRINT S

END

EXTERNAL FUNCTION F(N) !f(n)
OPTION ARITHMETIC RATIONAL !多桁の整数
LET Y=1
DO
   LET T=Y !3進法を利用する
   LET X=0
   LET K=1 !10^k
   DO WHILE T>0
      LET X=X+MOD(T,3)*K
      LET T=INT(T/3)
      LET K=K*10
   LOOP
   IF MOD(X,N)=0 THEN EXIT DO !題意を満たす
   LET Y=Y+1
LOOP
LET F=X
END FUNCTION


EXTERNAL FUNCTION FF(N) !f(n)
OPTION ARITHMETIC RATIONAL !多桁の整数
LET X=N
DO
   LET T=X !各桁の数字を確認する
   DO WHILE T>0
      IF MOD(T,10)>2 THEN EXIT DO !3以上なら、NG
      LET T=INT(T/10)
   LOOP
   IF T=0 THEN EXIT DO !題意を満たす
   LET X=X+N !次の倍数へ
LOOP
LET FF=X
END FUNCTION


倍数より、012の数を元に検索した方が速いようだ。
だが、9の倍数は大きな数になるので、N=10000はかなり手強い。



その２

OPTION ARITHMETIC RATIONAL !多桁の整数

LET t0=TIME

!PRINT f(999)
!PRINT USING "#####.##": TIME-T0
!STOP


LET N=100 !Σ

DIM FF(N) !f(n)
MAT FF=ZER

LET S=0

LET R=20 !10,15,20
DIM A(R) !並び　※重複順列を利用して、0,1,2の数を生成する
MAT A=CON !00…01
LET A(R)=2

LET C=N
DO
   LET X=0 !f(n)の候補
   FOR i=1 TO R !10進法の数とみなす
      LET X=X*10+(A(i)-1)
   NEXT i

   FOR J=1 TO N
      IF FF(J)=0 THEN !見つかっていない場合
         IF MOD(X,J)=0 THEN !割り切れる
            LET FF(J)=X
            LET S=S+X/J
            LET C=C-1 !残りの個数
         END IF
      END IF
   NEXT J

   IF C=0 THEN EXIT DO !すべてが見つかったなら

   CALL NextReptPerm(A,3,R, rc) !次へ
   IF rc<>0 THEN
      PRINT "Rの値を大きくしてください。"; R
      STOP
   END IF
LOOP

PRINT S


PRINT USING "#####.##": TIME-T0

END


EXTERNAL FUNCTION F(N) !f(n)
OPTION ARITHMETIC RATIONAL !多桁の整数
LET R=20
DIM A(R) !並び　※重複順列を利用して、0,1,2の数を生成する
MAT A=CON !00…01
LET A(R)=2
DO
!!!MAT PRINT A; !debug
   LET X=0 !f(n)の候補
   FOR i=1 TO R !10進法の数とみなす
      LET X=X*10+(A(i)-1)
   NEXT i
   IF MOD(X,N)=0 THEN EXIT DO !割り切れる
   CALL NextReptPerm(A,3,R, rc) !次へ
   IF rc<>0 THEN
      PRINT "Rの値を大きくしてください。"; R
      STOP
   END IF
LOOP
LET F=X
END FUNCTION


EXTERNAL SUB NextReptPerm(A(),N,R, rc) !辞書式順序で次の順列を返す
OPTION ARITHMETIC RATIONAL !多桁の整数
LET rc=1 !完了
FOR i=R TO 1 STEP -1 !N進法R桁の数として　※インクリメント・カウンタ
   IF A(i)<N THEN !1～Nで更新する
      LET A(i)=A(i)+1
      FOR j=i+1 TO R !A(i)=A(i+1)= … =A(R)　最初の並び
         LET A(j)=1
      NEXT j
      LET rc=0 !未了
      EXIT SUB
   END IF
NEXT i
END SUB


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月28日(土)10時01分33秒
  > No.3260[元記事へ]

291
Panaitopol素数

考察
x＞y＞0として、
p=(x^4-y^4)/(x^3+y^3)=(x-y)(x^2+y^2)/(x^2-xy+y^2)=(x-y)(x^2+y^2)/((x-y)^2+xy)
（終り）


OPTION ARITHMETIC RATIONAL !多桁の整数

LET C=0
FOR X=2 TO 10000 !X＞Y
   FOR Y=1 TO X-1
      LET P=(X-Y)*(X^2+Y^2)/(X^2-X*Y+Y^2)
      IF P=INT(P) THEN
         IF prmdiv(P)=P THEN !素数なら
            LET C=C+1
            PRINT X;Y;P !debug
         END IF
      END IF
   NEXT Y
NEXT X
PRINT C;"通り"

END

!UBASICの整数論関連より　UBASIC.LIB抜粋

EXTERNAL FUNCTION prmdiv(n) !１より大きな最小の約数
OPTION ARITHMETIC RATIONAL !多桁の整数
IF n<>INT(n) THEN !整数以外なら
   PRINT "prmdiv関数でパラメータが不適当です。"
   STOP
ELSEIF n=0 THEN
   LET prmdiv=0
ELSE
   LET n=ABS(n) !絶対値をとる

   IF MOD(n,2)=0 THEN !２の倍数
      LET prmdiv=2
   ELSEIF MOD(n,3)=0 THEN !３の倍数
      LET prmdiv=3
   ELSE
      FOR i=5 TO INTSQR(n) STEP 6
         IF MOD(n,i)=0 THEN !5,11,17,23,29,…
            LET prmdiv=i
            EXIT FUNCTION
         ELSEIF MOD(n,i+2)=0 THEN !7,13,19,25,31,…
            LET prmdiv=i+2
            EXIT FUNCTION
         END IF !+1,+3,+5は２の倍数（偶数）、+1,+4は３の倍数、+5は５の倍数
      NEXT i
      LET prmdiv=n !その数自身
   END IF
END IF
END FUNCTION



その２

考察
nを自然数とする。
x=(n+1)(n^2+n+1)、y=n(n^2+n+1)を与式に代入すると、
p=(x^4-y^4)/(x^3+y^3)=n^2+(n+1)^2
（終り）


OPTION ARITHMETIC RATIONAL !多桁の整数

LET C=0
LET N=1
DO
   LET P=N^2+(N+1)^2
   IF P>5E15 THEN EXIT DO
   IF prmdiv(P)=P THEN !素数なら
      LET C=C+1
      PRINT N;P !debug
   END IF
   LET N=N+1
LOOP
PRINT C;"通り"

END

※サブルーチン部分は省略


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月28日(土)10時04分56秒
  > No.3262[元記事へ]

221
アレクサンダー整数（Alexandrian integer）
参考サイト　http://oeis.org/A147811

考察
1/A=1/p-1/q-1/r=(qr-rp-pq)/(pqr)、A=pqrより、1=qr-rp-pq　∴pq+1=(q-p)r
(q-p)を(pq+1)の約数とすると、r=(pq+1)/(q-p)
（終り）


OPTION ARITHMETIC RATIONAL !多桁の整数

LET t0=TIME

!!LET M=100 !A=1195116
LET M=5000 !A=82945319184
!!LET M=150000 !A=1884161251122450

DIM B(0 TO M+1) !※0,m+1は番兵
LET B(0)=0
LET C=0
!!FOR P=1 TO 106 !1195116^(1/3)より
FOR P=1 TO 4361 !82945319184^(1/3)より
!!FOR P=1 TO 123511 !1884161251122450^(1/3)=123511より
   FOR Q=P+1 TO 2*P
      LET R=(P*Q+1)/(Q-P)
      IF R=INT(R) THEN !割り切れるなら
         LET C=C+1 !※順不同
         CALL ranking(P*Q*R, B,M,C) !並べ替える　※A=pqrは一般に増加する
      END IF
   NEXT Q
NEXT P
PRINT C;"通り"

PRINT B(1); B(M)

PRINT USING "#####.##": TIME-t0

END

EXTERNAL SUB ranking(X, A(),M,C) !昇順に並べる　a[1]＜a[2]＜a[3]＜ …＜a[m]
OPTION ARITHMETIC RATIONAL !多桁の整数

LET P=C
IF C>M THEN LET P=M+1  !満タン

IF X<A(P-1) THEN
   FOR i=P-1 TO 1 STEP -1 !右へスライドさせながら、挿入位置を見つける
      IF A(i)<X THEN EXIT FOR
      LET A(i+1)=A(i)
   NEXT i
   LET A(i+1)=X !挿入
ELSE
   LET A(P)=X !最後に挿入する。
END IF

!!!PRINT X !debug
!!!MAT PRINT A;
END SUB



150000は無理みたい!
 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月29日(日)10時15分7秒
  > No.3263[元記事へ]

048
1^1+2^2+3^3+ … +1000^1000の最後の10桁を求めよ。


OPTION ARITHMETIC RATIONAL !多桁整数

LET S=0
FOR N=1 TO 1000
   LET S=MOD(S+N^N,10^10)
NEXT N
PRINT S !9110846700

END



十進モードや2進モードでは、10^10どうしの2数のかけ算がオーバーフローすることを考慮する。


LET S=0
FOR N=1 TO 1000
   LET S=MOD(S+pow(N,N,10^5),10^10)
NEXT N
PRINT S !9110846700

END

EXTERNAL FUNCTION mul(X,Y,B) !かけ算 xy mod b^2
LET X1=INT(X/B) !m進法へ
LET X0=MOD(X,B)
LET Y1=INT(Y/B)
LET Y0=MOD(Y,B)
!xy=(x1*b+x0)(y1*b+y0)=(x1*y1)*b^2+(x1*y0+x0*y1)*b+(x0*y0)より
LET mul=MOD((X1*Y0+X0*Y1)*B+X0*Y0,B*B)
END FUNCTION

EXTERNAL FUNCTION pow(A,K,B) !べき乗の計算 a^k mod b^2
LET P=1
LET X=A
DO WHILE K>0 !べき乗kを2進法展開する
   IF MOD(K,2)=1 THEN LET P=mul(P,X,B) !p=p*x
   LET X=mul(X,X,B) !x=x^2
   LET K=INT(K/2)
LOOP
LET pow=P
END FUNCTION


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2013年12月29日(日)10時17分9秒
  > No.3264[元記事へ]

018
最大経路の和 その1

考察
動的計画法による
　　　　　　 (j-1)列　　　　j列
　(i-1)段　　dp[i-1,j-1]　　dp[i-1,j]
　　　　　　　　　　　　＼　↓
　　　i段 　　　　　　　　　MAX + a[i,j] → dp[i,j]
（終り）


!LET n=4 !最大値 23
!DATA 3
!DATA 7, 4
!DATA 2, 4, 6
!DATA 8, 5, 9, 3

LET n=15 !最大値 1074
DATA 75
DATA 95, 64
DATA 17, 47, 82
DATA 18, 35, 87, 10
DATA 20, 04, 82, 47, 65
DATA 19, 01, 23, 75, 03, 34
DATA 88, 02, 77, 73, 07, 63, 67
DATA 99, 65, 04, 28, 06, 16, 70, 92
DATA 41, 41, 26, 56, 83, 40, 80, 70, 33
DATA 41, 48, 72, 33, 47, 32, 37, 16, 94, 29
DATA 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14
DATA 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57
DATA 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48
DATA 63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31
DATA 04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23

DIM A(0 TO n-1, 0 TO n-1)
FOR i=0 TO n-1 !数値を読み込む
   FOR j=0 TO i
      READ A(i,j)
   NEXT j
NEXT i

DIM DP(0 TO n-1, 0 TO n-1)
LET DP(0,0)=A(0,0)
FOR i=1 TO n-1 !i段目
   LET DP(i,0)=DP(i-1,0) + A(i,0) !左端
   FOR j=1 TO i-1 !j列目
      LET DP(i,j)=MAX(DP(i-1,j-1),DP(i-1,j)) + A(i,j)
   NEXT j
   LET DP(i,i)=DP(i-1,i-1) + A(i,i) !右端
NEXT i

LET ans=0
FOR i=0 TO n-1
   LET ans=MAX(ans,DP(n-1,i))
NEXT i
PRINT ans

END


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2014年 1月 1日(水)10時45分24秒
  > No.3265[元記事へ]

148
パスカルの三角形の最初の10億列の要素で7で割り切れないものの数を答えよ。

考察
COMB(n,m)を直接計算すると、大きな数になっていく。
したがって、7の個数を数えることで、7の倍数を判定する。
n!の中のpの個数は、f(n,p)=[n/p]+[n/p^2]+[n/p^3]+ … である。
COMB(n,m)の中のpの個数は、
COMB(n,m)=n!/(m!(n-m)!)より、f(n,p)-(m,p)-f(n-m,p)
（終り）


OPTION ARITHMETIC RATIONAL !多桁の整数

LET N=100 !10^9

LET S=1 !0段目 C(0,0)
FOR i=1 TO N-1 !i段目
   LET M=i/2 !左端C(i,0)=1を除いた左側を検索する
   LET S=S+2
   FOR J=1 TO M
      IF G(i,J,7)=0 THEN !7の個数が0なら、7で割り切れない
         IF J<M THEN LET S=S+2 ELSE LET S=S+1 !対称性による
      END IF
   NEXT J
NEXT i
PRINT S; N*(N+1)/2-S

END

EXTERNAL FUNCTION F(N,P) !n!の中のpの個数　f(n)=[n/p]+[n/p^2]+[n/p^3]+ …
OPTION ARITHMETIC RATIONAL !多桁の整数
LET W=0
LET T=N
DO
   LET T=INT(T/P)
   LET W=W+T
LOOP WHILE T>0
LET F=W
END FUNCTION

EXTERNAL FUNCTION G(N,M,P) !COMB(n,m)の中のpの個数
OPTION ARITHMETIC RATIONAL !多桁の整数
LET G=F(N,P)-F(M,P)-F(N-M,P)
END FUNCTION


たが、Nが大きな場合は計算が困難である。

実際に、COMB(n,m)の中の7の個数の分布を表すと次のようになる。


　 1: 0
　 2: 0  0
　 3: 0  0  0
　 4: 0  0  0  0
　 5: 0  0  0  0  0
　 6: 0  0  0  0  0  0
　 7: 0  0  0  0  0  0  0
　 8: 0  1  1  1  1  1  1  0
　 9: 0  0  1  1  1  1  1  0  0
　10: 0  0  0  1  1  1  1  0  0  0
　11: 0  0  0  0  1  1  1  0  0  0  0
　12: 0  0  0  0  0  1  1  0  0  0  0  0
　13: 0  0  0  0  0  0  1  0  0  0  0  0  0
　14: 0  0  0  0  0  0  0  0  0  0  0  0  0  0
　15: 0  1  1  1  1  1  1  0  1  1  1  1  1  1  0
　16: 0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0
　17: 0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0
　18: 0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0
　19: 0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0
　20: 0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0
　21: 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
　22: 0  1  1  1  1  1  1  0  1  1  1  1  1  1  0  1  1  1  1  1  1  0
　23: 0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0
　24: 0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0
　25: 0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0
　26: 0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0
　27: 0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0
　28: 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
　29: 0  1  1  1  1  1  1  0  1  1  1  1  1  1  0  1  1  1  1  1  1  0  1  1  1  1  1  1  0
　30: 0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0
　31: 0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0
　32: 0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0
　33: 0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0
　34: 0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0
　35: 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
　36: 0  1  1  1  1  1  1  0  1  1  1  1  1  1  0  1  1  1  1  1  1  0  1  1  1  1  1  1  0  1  1  1  1  1  1  0
　37: 0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0
　38: 0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0
　39: 0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0
　40: 0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0
　41: 0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0
　42: 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
　43: 0  1  1  1  1  1  1  0  1  1  1  1  1  1  0  1  1  1  1  1  1  0  1  1  1  1  1  1  0  1  1  1  1  1  1  0  1  1  1  1  1  1  0
　44: 0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0  1  1  1  1  1  0  0
　45: 0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0  1  1  1  1  0  0  0
　46: 0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0  1  1  1  0  0  0  0
　47: 0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0  1  1  0  0  0  0  0
　48: 0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  0
　49: 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0



三角形の形状で規則正しく分布している。これを利用して、


OPTION ARITHMETIC RATIONAL !多桁整数

DEF T(N)=N*(N+1)/2

LET N=10^9

DIM S(0 TO 7-1)
FOR i=0 TO 7-1
   LET S(i)=T(i)
NEXT i

LET C=0

LET X=1
DO WHILE N>0 !7進法へ
   LET R=MOD(N,7)
   LET C=C*(R+1) + S(R)*X
   LET X=X*28 !X*T(7)
   LET N=INT(N/7)
LOOP

PRINT C !2129970655314432

END


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2014年 1月 1日(水)11時00分46秒
  > No.3274[元記事へ]

160
任意のNに対して、f(N)をN!の末尾の0の前にある最後の5桁とする。
f(1,000,000,000,000)を求めよ。


LET S=1
FOR N=2 TO 10^12
   LET T=N
   DO WHILE MOD(T,5)=0 !2*5=10で割る
      LET S=S/2
      LET T=INT(T/5)
   LOOP
   LET S=MOD(S*T,10^5)
NEXT N
PRINT S

END


これが処理可能なら良いのだが、、、

最後の5桁、すなわち10^5での数理があるようだ。


考察
g(n)は、nまでの5で割り切れる数を除いて、かつ 2の因子を5つまで取り除いた積とする。
g(n*10^5)=g(10^5)^n≡9376 mod 10^5
9376^k≡9376 mod 10^5
（終り）


!!OPTION ARITHMETIC RATIONAL !多桁の整数

LET N=10^12 !n!

LET M=10^5
!PRINT G(2*10^5), modpow(G(10^5),2,M) !debug

PUBLIC NUMERIC E !2^e
LET E=0

LET W=1

LET T=N
DO WHILE T>0
   IF MOD(T,M)=0 THEN !g(n*10^5)の場合
      PRINT T;"+" !debug
      LET W=MOD(W*9376,M)
   ELSE
      PRINT T !debug
      IF N0=0 THEN LET N0=T
      LET W=MOD(W*G(T),M)
   END IF
   LET T=INT(T/5)
LOOP

PRINT MOD(W*modpow(2,E-F(N0,5),M), M) !16576

END


EXTERNAL FUNCTION F(N,P) !n!の中のpの個数　f(n)=[n/p]+[n/p^2]+[n/p^3]+ …
!!OPTION ARITHMETIC RATIONAL !多桁の整数
LET W=0
LET T=N
DO
   LET T=INT(T/P)
   LET W=W+T
LOOP WHILE T>0
LET F=W
END FUNCTION


EXTERNAL FUNCTION G(N) !nまでの5で割り切れる数を除いて、かつ 2の因子を5つまで取り除いた積
!!OPTION ARITHMETIC RATIONAL !多桁の整数
LET T=1
FOR i=2 TO N
   IF MOD(i,5)=0 THEN !55で割り切れる数を除く
   ELSE
      LET W=i
      FOR J=1 TO 5 !2の因子を5つまで取り除く
         IF MOD(W,2)=0 THEN !2^e
            LET W=W/2
            LET E=E+1
         END IF
      NEXT J
      LET T=MOD(T*W,10^5) !積
   END IF
NEXT i
LET G=T
END FUNCTION


!UBASICの整数論関連より　UBASIC.LIB抜粋

EXTERNAL FUNCTION modpow(a,n,b) !a^n≡x mod b のxを返す　※nは非負整数
!!OPTION ARITHMETIC RATIONAL !多桁の整数
IF n<0 OR n<>INT(n) THEN !非負整数以外なら
   PRINT "modpow関数でパラメータが不適当です。"; a;n;b
   STOP
ELSE
   LET S=MOD(1,b)
   DO WHILE n>0 !べき乗nを２進展開する
      IF MOD(n,2)=1 THEN LET S=MOD(S*a,b) !ビットが１なら計算する
      LET a=MOD(a*a,b)
      LET n=INT(n/2)
   LOOP
   LET modpow=S
END IF
END FUNCTION


 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2014年 3月19日(水)19時13分50秒
  > No.3275[元記事へ]

029
2≦a≦100と2≦b≦100を満たす整数a,bについて、a^bを全て考えてみよう。
いくつの異なる値が存在するか。


考察
2≦a≦A、2≦b≦Bとして、kはa^k≦Aを満たす最大の整数とする。
k個の数からなる組{a, a^2, a^3, …, a^k}を考える。
例
　A=B=10のとき
　{2, 2^2=4, 2^3=8}、{3, 3^2=9}、{5}、{6}、{7}、{10}

a=2,3,5,6,7,10,11,12,13,…,[√A] のとき、k≧2
a＞[√A] のとき、k=1

各要素のべき乗は、重複する数を生成する。
例
　a=2のとき
　　　|　　2　　　　3　　　　4　　　　5 　　　…　　　B
　----+-----------------------------------------------------
　2^1 | 　　2^2　　　2^3　　　2^4　　　2^5　　…　　　　2^B
　2^2 | (2^2)^2　(2^2)^3　(2^2)^4　(2^2)^5　　…　　(2^2)^B
　2^3 | (2^3)^2　(2^3)^3　(2^3)^4　(2^3)^5　　…　　(2^3)^B
　　　　　　　　　　　　：
　2^k | (2^k)^2　(2^k)^3　(2^k)^4　(2^k)^5　　…　　(2^k)^B

　べき乗の部分に着目すると、

　　　|　2　　3　　4　　5 　…　B
　----+-------------------------------
　2^1 |　2　　3　　4　　5 　…　B
　2^2 |　4　　6　　8　　10　…　2B
　2^3 |　6　　9　　12　 15　…　3B
　　　　　　　　　：
　2^k |　2k　 3k　 4k　 5k　…　kB

　同じ数字の箇所は同じ数になるので、重複する数となる。

また、重複する個数はkとBに依存する。
（終り）


例
2≦a≦10、2≦b≦10のとき、2^k≦10から、k=1,2,3
積算表
　k＼b |  2  3  4  5  6  7  8  9 10
　-----+-----------------------------
　   1 |  2  3  4  5  6  7  8  9 10
　   2 |  4  6  8 10 12 14 16 18 20
　   3 |  6  9 12 15 18 21 24 27 30
より、
重複を除いた個数をG(k)とすると、
G(1)=9通り、G(2)=14通り、G(3)=19通り

a={2,2^2,2^4},{3,3^2},5,6,7,10より、
　a=2のとき、G(3)通り
　a=3のとき、G(2)通り
　a=5,6,7,10のとき、G(1)通り
なので、
　19*1+14*1+9*4=69通り
（終り）



!Project Euler Problem（プロジェクトオイラー） 029

LET A=100
LET B=100


LET M=0 !組のなかで数の個数が最大のもの
LET T=A
DO WHILE T>0
   LET M=M+1
   LET T=INT(T/2) !{2, 2^2, 2^3, …, 2^m}
LOOP
LET M=M-1
PRINT "M="; M !debug

!乗算表
!　     2 3 4  …  x  …  q    …  B
!　  1:
!　  2:
!　           ：
!　  p:                   pq=n
!　           ：
!　k-1:                           (k-1)B
!　  k:  → →    kx=n   → →
!　           ：
!　  m:
!をつくって、G(k)を求める。

DIM G(M) !重複を除いた個数をG(k)とする
LET G(1)=B-1 !1段目
LET C=G(1)
FOR K=2 TO M !k段目
   LET T=INT((K-1)*B/K) !kxが(k-1)Bより大きな数はすべて重複しない
   FOR X=2 TO T !b列目
      LET N=K*X
      FOR P=1 TO K-1 !nをpqに分解する
         LET Q=N/P
         IF Q=INT(Q) AND (Q>=2 AND Q<=B) THEN EXIT FOR !重複する
      NEXT P
      IF P>K-1 THEN LET C=C+1 !重複しないなら
   NEXT X
   LET C=C+(B-T)

   LET G(K)=C
NEXT K
MAT PRINT G; !debug


!組（A=2,3,5,6,7,10,11,12,13,…）に応じて計算していく。

LET C=0

LET AA=INT(SQR(A))
DIM F(AA) !2～[√A]までの数（篩いに用いる）
MAT F=ZER

LET S=0 !組にすることで除外された数の個数
FOR J=2 TO AA !素因数分解して、因数の組み合わせで組に分ける
   IF F(J)=0 THEN !新しい組なら
      PRINT "A="; J !debug

      LET K=0
      LET T=J !{j^1, j^2, j^3, …, j^k}の要素は、k個
      DO WHILE T<=A
         IF T<=AA THEN LET F(T)=1 !同じ組である
         LET S=S+1
         LET K=K+1

         LET T=T*J !次へ
      LOOP
      PRINT K !debug

      LET C=C+G(K)

   END IF
NEXT J

LET C=C+(A-1-S)*G(1) !√Aより大きいものは、(B-1)通り

PRINT C; "通り" !9183

END


実行結果

M= 6
99  149  199  240  291  328

A= 2
6
A= 3
4
A= 5
2
A= 6
2
A= 7
2
A= 10
2
9183 通り

 		 

Re: Project Euler Problem（プロジェクトオイラー）

 投稿者：山中和義  投稿日：2014年 3月22日(土)09時30分5秒
  > No.3340[元記事へ]

045
40755は、三角数かつ五角数かつ六角数である。
次の三角数かつ五角数かつ六角数となる数を求めよ。

3つの数を競い合わせる方法


!!OPTION ARITHMETIC RATIONAL !多桁の整数

DEF T(N)=N*(N+1)/2 !三角数
DEF P(N)=N*(3*N-1)/2 !五角数
DEF H(N)=N*(2*N-1) !六角数

LET N1=1
LET N2=1
LET N3=1

FOR K=1 TO 3 !1番目、2番目、3番目
   LET A=T(N1)
   LET B=P(N2)
   LET C=H(N3)

   DO UNTIL A=B AND B=C
      LET M=MAX(MAX(A,B),C) !一番大きな数に揃える
      DO WHILE A<M
         LET N1=N1+1
         LET A=T(N1)
      LOOP
      DO WHILE B<M
         LET N2=N2+1
         LET B=P(N2)
      LOOP
      DO WHILE C<M
         LET N3=N3+1
         LET C=H(N3)
      LOOP
   LOOP

   PRINT STR$(K);":"; A; N1;N2;N3 !1533776805

   LET N1=N1+1 !次へ
   LET N2=N2+1
   LET N3=N3+1
NEXT K

END



2次方程式を解く方法


!!OPTION ARITHMETIC RATIONAL !多桁の整数

LET N=1
FOR K=1 TO 3 !1番目、2番目、3番目

   DO
      LET X=N*(2*N-1) !六角数

      LET D=SQR(1+24*X) !五角数X=N(3N-1)/2より
      IF D=INT(D) THEN
         LET M=(1+D)/6
         IF M=INT(M) THEN

            LET D=SQR(1+8*X) !三角数X=N(N+1)/2より
            IF D=INT(D) THEN
               LET M=(1+D)/2
               IF M=INT(M) THEN EXIT DO
            END IF

         END IF
      END IF
      LET N=N+1
   LOOP
   PRINT STR$(K);":"; X ;N !1533776805

   LET N=N+1
NEXT K

END

 		 

戻る