数学系の問題について

Question

数学系のプログラミングの問題を解いていて、疑問に思うことがあったので質問させていただきました。
数学系の話になりますので、プログラミングとあまり関係がないかもしれません。

2^x - 3^y （x,yは０以上の整数）

x, yが大きくなるにつれて、この差も0からどんどん離れていくようです。（実験より）
x, yをある数以上に定めたときに、この差の絶対値の最小値は存在するのでしょうか。

言い方を変えると、
2^x - 3^y = nとなる整数(x, y)の組が無限に存在する、整数nは存在するのでしょうか。

追記
差の絶対値が０となるのはx=0,y=0のみ（素因数分解の一意性より）
差の絶対値が１となるのはx=3,y=2のみ（カタラン予想より）
差の絶対値が２となるのはx=0,y=1のみ？（おおまかに調べたところ）
差の絶対値が３となるのはx=2,y=0のみ？
差の絶対値が４となるのはない？
差の絶対値が５となるのはx=2,y=2 or x=3,y=1,x=5,y=3のみ？

このようにある程度まで調べましたが、おそらくそれぞれ有限の組み合わせしかないと思われます。

Comments

[退会済みユーザー]

「アルゴリズム」タグや、ほかのユーザーの多い言語の（見てもらえる範囲が広くなる）タグをつけてはいかがでしょうか？

---
10:54再修正
参考までに、Excelですぐに確認できる範囲(2^49,3^31)では、nを満たすx,yが複数あるnは2組づつしか見つかっていません。
n = -1,1,5,7,13

```
Option Explicit
Sub power()
Dim i_max As Long
Dim j_max As Long
Dim i As Long
Dim j As Long
i_max = 49 '2^i
j_max = 31 '3^j
With ActiveSheet
For i = 0 To i_max
For j = 0 To j_max
If i = 0 Then
.Cells(i + 1, j + 2) = "-3^" & j
End If

If j = 0 Then
.Cells(i + 2, j + 1) = "2^" & i
End If

.Cells(i + 2, j + 2) = "=power(2," & i & ") - power(3," & j & ")"
Next j
Next i
End With
End Sub
```

[kei_10]

アドバイスありがとうございます。

[fuzzball]

どういう理由で言語のタグを付けているのでしょうか？関係のないタグは削除して下さい。

Answer 1

2^x - 3^y = nとなる整数(x, y)の組が無限に存在する、整数nは存在するのでしょうか。

同じ質問がこちらにありました。
https://math.stackexchange.com/questions/1642096/special-case-of-pillais-conjecture
回答によると、整数nを固定したとき、整数解(x,y)は有限個になるとあります。

Comments

[kei_10]

回答ありがとうございます。
ただ証明がないのが残念ですね。

[kei_10]

どうやら私が考えていたのは、ピライの予想（Pillai's conjecture）というもののようですね。
未解決問題です。

Answer 2

2^x - 3^y = nとなる整数(x, y)の組が無限に存在する、整数nは存在するのでしょうか。

なさそうですね。
http://www.wolframalpha.com/input/?dataset=&i=2%5Ex-3%5Ey%3Dn,n%3Dinteger

Comments

[退会済みユーザー]

本筋とずれてしまいますが、このリンクはとても便利祖なのですがどのように使うのでしょうか？

[Lhankor_Mhy]

> slashさん
ほんと便利ですよね。↓などはいかがでしょう。
http://mathtrain.jp/wolalpha

[退会済みユーザー]

Lhankor_Mhy様
ありがとうございます、ブックマークしました。
---
カタラン予想でしたか

[kei_10]

回答ありがとうございます。
n=1の時がカタラン予想ですね。

Answer 3

差の絶対値の最小は0(x=y=0)です。

###証明を試みましたが難解で、すでに定理として確立しているようなので諦めます
2a-3b=n(a,bは整数)という不定方程式を考えます。
2a-3b=1を満たす(a,b)の一つに(2,1)があります。つまり、
22-31=1 です。この両辺をn倍して、
22n-3n=n となります
これと最初の方程式の辺々の差を取って、
2(a-2n)-3(b-n)=0
2(a-2n)=3(b-n)
となります。
2と3は互いに素なので、kを整数として、
(a,b) = (3k + 2n,2k + n)
これが不定方程式の解となります。

問題の式で、x,yを2以上の整数とし(解が無数に存在するものを探すため、こう仮定しても問題ない)、
2*(2^(x-1))-3*(3^(y-1))=n
となるx,yを考えると、先ほどの方程式と比較して、
(a,b) = (2^(x-1),3^(y-1)) = (3k + 2n,2k + n)
ということになります。しかし、2^(x-1)は偶数、3^(y-1)は奇数で、2n、2kが偶数なので、
kは偶数、nは奇数でなければ解が存在しません。

今あるnに対し、解(x1,y1)が存在し、対応するkがあるとして、
それよりもx,yがともに大きい解(x2,y2)の存在を考えます。
まずyについて、適当な正の整数mを使って、
3^(y2-1) = 3^(y1+m-1) = 3^(y1-1)3^m = (2k + n)3^m = (2k * 3^m) + 3^mn
=2(k * 3^m) + (3^mn - n) + n
ここで、3^m*n - nは奇数-奇数なので偶数2pとおけ、
2(k * 3^m) + 2p + n = 2(k * 3^m + p) + n
となるので、k * 3^m + pを新たなkとして方程式の解(の候補)にできます。

同様に、xについても議論していくと(適当な正の整数をhとする)、
2^(x2-1) = 2(x1-1)2^h = (3k * 2^h) + 2n2^h = 3(k * 2^h) + (2n*2^h - 2n) + 2n
= 3(k * 2^h) + (2^h - 1)*2n + 2n
(2^h - 1)*2n が3の倍数3qであれば、
3(k * 2^h) + 3q + 2n = 3(k * 2^h + q) +2n
で、k * 2^h + qを新たなkにして解(の候補)にできます。
このためには、2^h-1かnの少なくとも一方が3の倍数である必要があります。
2^h-1が3の倍数になるのは、2≡-1(mod 3)のため、hが偶数のときです。

ここで、双方で新たにkと置いたk * 2^h + qとk * 3^m + pが等しくなれば、それに対応する(x,y)を方程式の解とできます。

Comments

[kei_10]

差の絶対値の最小値が０というのは、x,y>=0の時のみですよね。
x,y>=10の時の差の絶対値の最小値は求められるのでしょうか。（明らかに０ではありませんよね）

Answer 4

x, yをある数以上に定めたときに、この差の絶対値の最小値は存在するのでしょうか。

こちらだけ。
1です。

Comments

[swordone]

0では？
追記：「ある数以上」の「ある数」が0でなければ1ですね

[退会済みユーザー]

たしかに＾＾；

[kei_10]

たとえば、ある数を100にした時の、差の最小値は求められるのでしょうか。

[退会済みユーザー]

2^x - 3^y = 1 or -1 である組み合わせが確認できればそれがその組み合わせまでの最小になりますが、確認できないですね＾＾；

Answer 5

引用テキストx, yをある数以上に定めたときに、この差の最小値は存在するのでしょうか。

この差に最小値は存在しえません。なぜならばyの値を大きくすれば、いくらでも差は小さくなるからです。（マイナス無限大に発散する）言い換えの方の論理は正しいかはよくわかりません。そもそも言い換えとなっていない気がします。

Comments

[kei_10]

回答ありがとうございます。
質問内容に間違いがあったので編集しました。