単位分数の和で1/2をつくる

 投稿者：山中和義  投稿日：2013年 1月17日(木)10時10分56秒
  問題
nを、2より大きい整数とする。
互いに素となる正の整数p,qが、p＜q≦n かつ p+q＞n を満たすとき、
Σ1/(pq)=1/2となる。

考察
n=2のとき
　1/(1*2)
n=3のとき
　1/(1*2) +1/(1*3)+1/(2*3)
n=4のとき
　1/(1*3) +1/(2*3) +1/(1*4)+1/(3*4)
n=5のとき
　1/(2*3)+1/(1*4) +1/(3*4) +1/(1*5)+1/(2*5)+1/(3*5)+1/(4*5)
n=6のとき
　1/(1*5) +1/(3*4)+1/(2*5)+1/(3*5)+1/(4*5) +1/(1*6)+1/(5*6)

一般に、
　a,bは正の整数のとき、1/(ab)=1/(a(a+b))+1/(b(a+b))

互いに素とする組(a,b)が、この問題にあてはまる。

a+b=7のとき、(a,b)=(1,6)、(2,5)、(3,4)なので、
1/(1*6)=1/(1*7)+1/(6*7)、1/(2*5)=1/(2*7)+1/(5*7)、1/(3*4)=1/(3*7)+1/(4*7)
これより、
　n=7のとき、
　　n=6、すなわち、1/(3*4)+1/(2*5)+1/(3*5)+1/(4*5)+1/(1*6)+1/(5*6) をもとに、
　　1/(3*4)+1/(2*5)+1/(1*6) +1/(3*5)+1/(4*5)+1/(5*6) +1/(1*7)+1/(2*7)+1/(3*7)+1/(4*7)+1/(5*7)+1/(6*7)
　　とする。
とすることで、機械的に生成できる。
（終り）


OPTION ARITHMETIC RATIONAL !有理数モード
FOR n=2 TO 20
   LET s=0
   FOR p=1 TO n-1 !1≦p＜q≦n
      FOR q=p+1 TO n
         IF gcd(p,q)=1 THEN !互いに素
            IF p+q>n THEN
               PRINT p;q; !debug
               IF p+q=n+1 THEN PRINT "*" ELSE PRINT !debug
               LET s=s+1/(p*q) !Σ1/(pq)
            END IF
         END IF
      NEXT q
   NEXT p
   PRINT "n=";n; s !=1/2
   PRINT
NEXT n
END

EXTERNAL FUNCTION gcd(a,b) !最大公約数
OPTION ARITHMETIC RATIONAL !有理数モード
DO UNTIL b=0
   LET t=b
   LET b=MOD(a,b)
   LET a=t
LOOP
LET gcd=a
END FUNCTION

 		 

単位分数の和で1をつくる

 投稿者：山中和義  投稿日：2013年 2月20日(水)12時24分18秒
  > No.2961[元記事へ]

問題
分母がn以下の相異なる単位分数の和で1をつくる
　1=1/a+1/b+ … +1/c、a＜b＜ … ＜c≦n
例
　1/1　項数= 1
　1/2+1/3+1/6　項数= 3
　1/2+1/3+1/7+1/42　項数= 4
　1/2+1/3+1/7+1/78+1/91　項数= 5
　1/2+1/3+1/8+1/24　項数= 4
　1/2+1/3+1/8+1/32+1/96　項数= 5
　1/2+1/3+1/8+1/33+1/88　項数= 5
　1/2+1/3+1/8+1/36+1/72　項数= 5
　1/2+1/3+1/8+1/40+1/60　項数= 5
　1/2+1/3+1/8+1/42+1/56　項数= 5
　1/2+1/3+1/8+1/56+1/78+1/91　項数= 6
　1/2+1/3+1/8+1/60+1/72+1/90　項数= 6
　1/2+1/3+1/8+1/63+1/72+1/84　項数= 6
　1/2+1/3+1/9+1/18　項数= 4
　1/2+1/3+1/9+1/22+1/99　項数= 5
　1/2+1/3+1/9+1/24+1/72　項数= 5
　1/2+1/3+1/9+1/27+1/54　項数= 5
　1/2+1/3+1/9+1/30+1/45　項数= 5
　1/2+1/3+1/9+1/32+1/72+1/96　項数= 6
　1/2+1/3+1/9+1/33+1/66+1/99　項数= 6
　1/2+1/3+1/9+1/33+1/72+1/88　項数= 6
　1/2+1/3+1/9+1/35+1/63+1/90　項数= 6
　　　　：



OPTION ARITHMETIC RATIONAL !有理数モード
DIM F(100),A(100),B(100)
MAT F=ZER
LET A(100)=1/100 !iの値、i以降の和
LET B(100)=A(100)
FOR i=99 TO 1 STEP -1
   LET A(i)=1/i !減少列 1/1＞1/2＞1/3＞ … ＞1/100
   LET B(i)=A(i)+B(i+1)
NEXT i
LET N=1
CALL try(N,1,A,B,F)
END

EXTERNAL SUB try(N,p,A(),B(),F()) !バックトラック法で検索する
OPTION ARITHMETIC RATIONAL !有理数モード
FOR i=p TO 100 !※cの上限
   LET T=N-A(i) !残り
   IF T>0 THEN
      IF i<100 AND B(i+1)<T THEN EXIT FOR !全部を使って可能性があれば、その部分集合を考える
      LET F(i)=1 !使用中とする
      CALL try(T,i+1,A,B,F) !有理数tを(i+1)以降で表す
      LET F(i)=0 !元に戻す
   ELSEIF T=0 THEN !題意を満たすなら
      LET k=0
      FOR j=1 TO p-1 !式を表示する
         IF F(j)=1 THEN
            PRINT "1/";STR$(j);"+";
            LET k=k+1
         END IF
      NEXT j
      PRINT  "1/";STR$(i);"　項数=";k+1
   END IF
NEXT i
END SUB

 		 

戻る