本文代码是我为了解决
Project Euler上的问题而写的数学工具,之前的见:
按字典顺序生成所有的排列
筛法求素数
所谓一个实数的
连分数表示,是指将一个实数x写成以下形式:
其中a0,a1,...,b1,b2,..都是自然数。
当其中b1,b2,..都取为1时,我们称之为
简单连分数表示(Simple Continued Fraction)
可以证明:每一个不是完全平方数的自然数N,其平方根可以写成
简单连分数表示,并且其中a1,a2,..呈周期出现。
比如23的平方根的连分数表示为:
并且其中
[1,3,1,8]就是其一个周期,就是接下来的表示是由[1,3,1,8]循环出现。
下面是得到一个自然数平方根的简单连分数表示的Scala代码:
/**
&#Util.scala
utils for mathematical algorithm,include:
# get all primes below bound in order
# generate all permutations in lexicographical order
# get simple continued fraction representation of the sqrt of n
@author Eastsun
*/
package eastsun.math
object Util {
/**
Get simple continued fraction representation of the sqrt of n
*/
def continuedFractionOfSqrt(n: Int,buf: Array[Int]):Int = {
val sq = Math.sqrt(n)
var (p,q) = (sq,n - sq*sq)
if(q == 0) 0
else{
var idx = 0
var an = 0
do {
an = (sq + p)/q
if(buf != null) buf(idx) = an
idx += 1
p = an*q - p
q = (n - p*p)/q
}while(an != 2*sq)
idx
}
}
}
简单解释一下函数
def continuedFractionOfSqrt(n: Int,buf: Array[Int]):Int的功能:该函数有两个参数,其中n表示要求其平方根连分数表示的自然数n;buf用来保存其连分数表示中a1,a2,...的一个周期(注意,没有包括a0),该参数可以为null。函数返回一个Int,表示a1,a2,..周期的大小,也就是buf中保存数据的长度。
下面是对使用该函数的一个演示:
引用
scala> var buf = new Array[Int](4)
buf: Array[Int] = Array(0, 0, 0, 0)
scala> continuedFractionOfSqrt(23,buf)
res8: Int = 4
scala> buf.mkString(",")
res9: String = 1,3,1,8
scala>
OK,现在我们可以来看看Project Euler上的
第64题了:
引用
64 How many continued fractions for N ≤ 10000 have an odd period?
题目很简单:
求10000以内的自然数中,平方根的连分数表示的周期长度为奇数的有多少个。
下面是该题的Scala解法(使用了上面的函数):
import eastsun.math.Util._
object Euler064 extends Application {
val res = 1.to(10000).filter{ continuedFractionOfSqrt(_,null) % 2 ==1 }.length
println(res)
}
在将Project Euler66题前,先介绍一个数学名词:
佩尔方程:形如 x^2 - D×y^2 = 1的不定方程称为佩尔方程。其中D为非完全平方数的自然数。并且称其所有正整数解(x,y)中使得x最小的那个解为
最小解。
佩尔方程求解与平方根的连分数表示有着很大的关联,这里我就不细说了,对数学细节干兴趣的可以参考Math World上的
Pell Equation。下面我直接给出
Project Euler66题的叙述及其Scala代码:
引用
Find the value of D ≤1000 in minimal solutions of x for which the largest value of x is obtained.
就是说对D≤1000,求D使得佩尔方程x^2 - D×y^2 = 1的最小解中x的值最大。
下面上代码:
import eastsun.math.Util._
object Euler066 extends Application {
val buf = new Array[Int](1000)
var (res,max,d) = (2,3:BigInt,1)
while(d <= 1000){
val pd = continuedFractionOfSqrt(d,buf)
if(pd > 0){
val sq = Math.sqrt(d)
var (x0,y0) = (sq:BigInt,1:BigInt)
var (x1,y1) = ((buf(0)*sq+1):BigInt,buf(0):BigInt)
val cnt = if(pd%2 == 1) 2*pd-1 else pd-1
var idx = 1
while(idx < cnt){
var t = x1
var a = buf(idx%pd)
x1 = x1*a + x0
x0 = t
t = y1
y1 = y1*a + y0
y0 = t
idx += 1
}
if(x1 > max){
max = x1
res = d
}
}
d += 1
}
println(res)
}
分享到:
相关推荐
讲述连分数的一些性质、定理和pell方程的解法;分数与连分数的互化;
pell方程的基本解的性质、定理、解法; 给出实例x^2-94*y^2=1的解法。
pell方程的几个公式pell方程的几个公式pell方程的几个公式pell方程的几个公式pell方程的几个公式pell方程的几个公式pell方程的几个公式pell方程的几个公式
Pell方程ax2-by2=±1(a,b∈Z+,ab不是完全平方数)可解性的判别是一个非常有意义的问题。本文运用Legendre符号和同余的性质给出了形如ax2-mqy2=±1(m∈Z+,3|a,q≡±1(mod6)是素数,amq是非完全平方数)型Pell方程无正...
给出2种新的特殊类型的 Pell方程的最小解计算公式。
一般二元二次丢番图方程的解法 Pell的 很好的英文资料哦
主要运用Lucas数的奇偶性,讨论了当A,B是适合A>1,2 f AB且AB非平方数的正整数时,广义Pell方程的整数解(x,y),即给出了方程Ax2-By2=4适合gcd(x,y)=1的整数解(x,y)的通解公式.
p2,…,直至pi(i≥2)(其中pi(i≥2)与1对模6同余,且pi(i≥2)为互异的奇素数)与y的平方之积的整数解问题至今仍未解决的问题,主要利用同余式、平方剩余、递归序列、Pell方程的解的性质得出了Diophantine方程x的立方加减1...
对于整数 d 和 s,其中 d 为非平方和正数,Pell(d,s,n) 将前 n 个正整数解 (x,y) 返回到修正的 Pell 方程 x^2-dy^2=(-1)^s ,如果存在这样的解决方案。 如果 s 是偶数,即如果右侧等于 1,则这样的解总是存在,尽管...
数论应用选讲 1.求解二元一次不定方程 2.佩尔方程 3.Fibonacci数列
Pell方程x2-Dy2=-1可解性的一个判别,是一个非常有意义的问题。本文运用Pell方程x2-Dy2=1的解的基本性质,给出了Pell方程x2-Dy2=-1可解性的一个判别条件,并给出了一些有用的推论。
设n是正奇数,Un = (αn+βn) /2,Vn = (αn-βn) /22,其中α=1 + 2,β=1-2.运用Pell数的算术性质讨论了方程x2 + Uyn = Vzn的正整数解(x,y,z),证明了当n≡±3( mod8)时,该方程仅有正整数解(x,y,z) =( V2n-1,2,4) .
struts2+pell文件上传struts2+pell文件上传
struts2-pell-multipart-plugin-2.1.6.jar
pell 是最简单最小(5kB)的所见即所得的WYSIWYG文本编辑器
主要运用Pell方程、递归数列、同余式及(非)平方剩余等一些初等的证明方法,证明了不定方程x(x+1)(x+2)・(x+3)=13y(y+1)(y+2)(y+3)无正整数解。在证明该结论的过程中,对不定方程进行变形和整理,将其化为Pell方程...
vue-pell-editor所见即所得文本编辑器的Vue包装器安装通过NPM或Yarn进行安装:$ npm install --save vue-pell-editor#或$ yarn add vu vue-pell-editor所见即所得文本编辑器的Vue包装器安装安装通过NPM或Yarn:$ ...
还在为找不到jar文件烦心吗,不用了到我空间来有你想要的,持续更新。。。 struts2-pell-multipart-plugin-2.2.1.jar
辗转相除法求两个数的最大公约数是最早被数学家研究的算法之一,并且和数论中如连分数,丢番图方程有着紧密的联系。本文从基本的欧几里得算法谈起,涉及了几个数论问题的解法,并受其思想的启发,研究并解决了了几个...
Pell编辑器的最小包装器,没有内置任何附加功能。 安装 npm i react-pell2 用法 import ReactPell from 'react-pell2' ; < ReactPell xss=removed><u><i>Initial content!</i></u></b>" onChange = { } classes...