标签: diophantine

我决定接下来解决Project Euler 问题233,但我遇到了一些重大问题!我做了一些分析并取得了一些相当不错的进展,但我现在已经陷入困境.这是我的工作:

引理1:由于圆圈经过4个角点,因此任何n都至少有4个解.但是对于圆周上的每个点,有7个其他点被发现有反射.因此总有8k + 4个格点.

引理2:圆具有半径(√2)n和中心(n/2,n/2),因此其方程为(xn/2)^ 2 +(yn/2)^ 2 = [n /√2] ^ 2.这减少到x ^ 2 + y ^ 2 = n(x + y).

引理3:如果写入x ^ 2 + y ^ 2 = n(x + y)的解(x,y,z),则另一个解是(kx,ky,kz).证明是:

(x+y)n = x^2+y^2

(kx)^2+(ky)^2 = (kx+ky)m
k(x^2+y^2) = (x+y)m
m = kn

这和我对这个思路的影响一样多 - 我看不到任何地方可以从那里去,但它包括在内,因为它可能很有用.

我的下一个想法是移动圆圈的中心.将有相同数量的解决方案在任何维度上移动整个整数.所以当n/2是整数时,所以n = 2k,x ^ 2 + y ^ 2 = 2*k ^ 2.并且事实证明,对于该等式,存在与等式x ^ 2 + y ^ 2 = k ^ 2一样多的解(参见Sloane A046109). …

我最近对Project Euler非常沉迷,我正在努力做到这一点!我已经开始对它进行一些分析,并且已经大大减少了问题.这是我的工作:

A = pqr和

1/A = 1/p + 1/q + 1/r所以pqr/A = pq + pr + qr

由于第一个等式:

pq + pr + qr = 1

由于p,q和r中只有两个必须是负数,我们可以将方程式简化为:

abc,其中ab = ac + bc + 1

解决问题我们得到:

ab-1 =(a + b)c

c =(ab-1)/(a + b)

---

这意味着我们需要找到a和b:

ab = 1(mod a + b)

那么a和b的A值是:

A = abc = ab(ab-1)/(a + b)

对不起,如果这是很多数学!但现在我们所要处理的只是一个条件和两个方程式.既然我需要找到写成ab(ab-1)/(a + b)且ab = 1(mod a + b)的第150,000个最小整数,理想情况下我想搜索(a,b)其中A是尽可能小.

为了方便起见,我假设<b,我也注意到gcd(a,b)= 1.

我的第一个实现是直接的,甚至可以足够快地找到150,000个解决方案.但是,找到150,000个最小的解决方案需要很长时间.无论如何,这是代码:

n = 150000
seen = set()

a …

如果集合的数字的gcd为1,则存在集合的Frobenius数.给定一组具有最多10个元素的正整数,使得所有元素的gcd为1,我们如何计算集合的Frobenius数？

以下是原始问题的链接:https://icpcarchive.ecs.baylor.edu/external/62/6298.pdf Sylvester的公式可用于查找一组2个元素的Frobenius数.

我试图为给定的H生成以下方程的所有解.

H = 4时:

1) ALL solutions for x_1 + x_2 + x_3 + x_4 =4
2) ALL solutions for x_1 + x_2 + x_3 = 4
3) ALL solutions for x_1 + x_2 = 4
4) ALL solutions for x_1 =4

对于我的问题,总有4个方程要解决(独立于其他方程).总共有2 ^(H-1)个解决方案.对于前一个,这里是解决方案:

1) 1 1 1 1
2) 1 1 2 and 1 2 1 and 2 1 1
3) 1 3 and 3 1 and 2 2
4) 4

这是一个解决问题的R算法.

library(gtools)
H<-4
solutions<-NULL

for(i in seq(H))
{ …

我正在尝试编写一种算法来确定线性方程,特别是ax + by = c的形式,对于给定的a,b,c是否具有正整数解.它需要是有效的,因为数字a,b和c可以在0 <= a,b,c <= 10 ^ 16的范围内.我该如何处理这个问题？

由于它是一个丢番图方程式,我试图检查a和b的GCD是否除以c,但这样我无法区分正,负或零解.

确定线性不定方程的非负值解存在性的算法

我在这里找到了一个解决方案,但我并不太明白.也许有人可以为我简化它？因为这个很通用,我只对2个变量的方程感兴趣.

有类似的问题:检查变量是否是整数,但我看不到我的问题的答案.

我的意思是,最近我和很多人打架,所以我的朋友建议我安装Python.我今天打开它,这样我就可以计算大数字并且具有良好的精度,但是...如何使用这种精度？我的意思是,如果我做了类似的pow(31,123)工作,但如果我想检查数字是否为整数,我得到:

>>> (4.00000000000001).is_integer()
False
>>> (4.000000000000001).is_integer()
False
>>> (4.0000000000000001).is_integer()
True
>>> (4.00000000000000001).is_integer()
True

我想写一个简单的循环来找到一些丢番图方程的解,我需要从非常大的数字取平方根并检查它是否是整数,但现在我处于紧张状态.有人可以帮助我或者给我一个如何获得更好精度的建议吗？

例:

例如:$ 2x ^ 2 = 1 + y ^ 31 $,其中x,y是整数.我的想法是循环,我增加y(从1开始),加1,除以2,取平方根,然后它必须是整数以满足等式.这就是我需要它的原因.