社区讨论

关于辗转相除法的一道纯数学题

学术版参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lui8wkpw
此快照首次捕获于
2024/04/02 18:37
2 年前
此快照最后确认于
2024/04/02 20:38
2 年前
查看原帖
题目:
定义C(a,b)(ab)C(a,b) (a\geq b)为使用辗转相除法求解gcd(a,b)gcd(a,b)所需要的次数(从(a,b)(a,b)一直到(t,0)(t,0)的每一次均要计算,例如C(10,7)=4C(10,7)=4
定义W(a)=lg(a)+1W(a)=\lfloor lg(a) \rfloor+1为正整数aa在十进制下的位数
定义N(a,b)=C(a,b)W(a)+W(b)N(a,b)=\frac{C(a,b)}{W(a)+W(b)},求N(a,b)N(a,b)的最大值
一些说明或思路:
1.1.对于1ba2×1051\leq b \leq a\leq 2\times 10^5,有N(a,b)N(a,b)的最大值为2.502.50,其中(a,b)=(8,5),(89,55),(610,987)(a,b)=(8,5),(89,55),(610,987)
2.N(a,b)2.N(a,b)有界,证明如下:
N(a,b)=C(a,b)W(a)+W(b)<log2a+log2blga+lgb<log2alga<log210N(a,b)=\frac{C(a,b)}{W(a)+W(b)}<\frac{log_2a+{log_2b}}{lga+lgb}<\frac{log_2a}{lga}<log_2{10}
3.3.根据参考文献 https://www.cnki.com.cn/Article/CJFDTotal-NJSF198203006.htm在本题中的C(a,b)lgblg1+52+2C(a,b)\leq \lfloor\frac{lgb}{lg{\frac{1+\sqrt{5}}{2}}}\rfloor+2

回复

4 条回复,欢迎继续交流。

正在加载回复...