隣数から1程度の少しだけ大きい数を２つの数の掛け算のまま表現できるプログラム

今回は記事もプログラムも短いです。余分なモジュールも一切要りません。

プログラム例

def nup(a,b,r):
    #a=2*(2*x+1)-x-1
    x=0
    xls=[]
    wls=[]
    w=0
    for i in range(3,100):
        if (r+a*b)%i==0 and a>i:
            #print(i)
            x=(a+(i-a)%i)//i
            w=(-a)%i
            xls+=[x]
            wls+=[w]
    if x==0:
        return []
    y=(a+w)//x
    z=a-x*y
    c,d=y,(x)*b+z
    d-=(c*d-a*b)//c
    print(c,d,c*d,a*b,r)
    print(x,y,z,w,'xyz')
    for i in range(len(xls)):
        y=(a+wls[i])//xls[i]
        z=a-xls[i]*y
        e,f=y,xls[i]*b+z
        f-=(e*f-a*b)//c
        print(e,f,e*f,a*b,r)
        print(xls[i],y,z,wls[i],'xyz')
    return [c,d]
def ndown(a,b,r):
    #a=2*(2*x+1)-x-1
    x=0
    xls=[]
    wls=[]
    w=0
    for i in range(3,100):
        if (-r+a*b)%i==0 and a>i:
            #print(i)
            x=(a+(i-a)%i)//i
            w=(-a)%i
            xls+=[x]
            wls+=[w]
    if x==0:
        return []
    y=(a+w)//x
    z=a-x*y
    c,d=y,(x)*b+z
    d-=(c*d-a*b)//c+1
    print(c,d,c*d,a*b,r)
    print(x,y,z,w,'xyz')
    for i in range(len(xls)):
        y=(a+wls[i])//xls[i]
        z=a-xls[i]*y
        e,f=y,xls[i]*b+z
        f-=(e*f-a*b)//c+1
        print(e,f,e*f,a*b,r)
        print(xls[i],y,z,wls[i],'xyz')
    return [c,d]
print(nup(203,20,3))
print(ndown(31,41,5))

このプログラムではまず隣数の因数分解がわかっている前提で、ある数mを割り切る数aと、aと対になってmを構成する数(つまり、mに対するaの商)をそれぞれ第一因数、第二因数に入れて、mからどれだけ動いた数について求めたいかを示す数(m+rならr)を第三因数に入れると、m+rを割り切る数の組み合わせを1組返します。

理屈は単純で、

$${(ma+n)(mb+n)-(mc+n)(md+n)}$$について、$${c=ma+n,b=md+n}$$ならば、c-bに等しいことを利用して、1組の数のペアの、因数性を保ったまま少しだけ別の数の積を示すように変形しているという話です。

適当なmを指定するのに、総当たりを掛けているので、大きな数にどこまで通用するかはわからないけれど、どうだろう。。

ちなみに、第一因数が大きいほど見つかる確率は高くなります。