找回密码
 欢迎注册
查看: 13486|回复: 8

[讨论] 根号n小数点后以n开头的数

[复制链接]
发表于 2018-4-19 14:50:43 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
本帖最后由 lsr314 于 2018-4-19 14:54 编辑

数列 http://oeis.org/A272208/list 中的数$n$满足:$sqrt(n)$小数点后以$n$开头,即$\floor(10^k sqrt(n))\equiv n(mod 10^k)$,其中$k$表示十进制下$n$的位数。
已知的有:
$8, 77, 5711, 9797, 997997, 8053139, 60755907, 99979997, 9999799997, 71515443427, 93445113269, 999997999997, 26369408771424, 96872443448748, 99650905131203, 99999979999997, 751273714618266, 3368237924952647, 3493498117381256, 9999999799999997, 35399255736521405, 999999997999999997$

比如$sqrt(5711) = 75.5711\cdots$,所以$5711$在数列中。
数列中有一个子数列是若干个$9$加一个$7$,再重复一遍,比如最后一个$999999997999999997$,不过倒数第二项$35399255736521405$是如何找到的?除了穷举测试以外,不知道有什么更快的算法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-4-19 15:02:00 | 显示全部楼层
想到了一个跳跃性的算法,即当发现$sqrt(n)$小数点后前$k$位和$n$差异较大时,可以跳过一些数,通过跳的幅度,控制算法的效率。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-4-19 18:16:57 | 显示全部楼层
想到了一个很快的方法,应该能得到下一个这样的数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-19 21:06:21 | 显示全部楼层
我们可以穷举$a=\floor(\sqrt(n))$,在$a$确定时,通常$k$也可以直接确定(最多两种)
于是这时我们设$n-a^2=u$,其中$0\lt u\le 2a$
所以有$0\lt e=10^k(\sqrt(a^2+u)-a)-(a^2+u)\lt 1$
于是$0\lt 10^{2k}(a^2+u)-(a^2+u+a*10^k)^2\lt 2(a^2+u+a*10^k)+1$
$0\lt 10^{2k}u-(a^2+u)^2-2(a^2+u)*a*10^k\lt 2(a^2+u+a*10^k)+1$
我们求解两个关于u的二次不等式应该马上可以得出u很精确的范围

第一个为
$u^2-(10^{2k}-2a10^k-2a^2)u+a^4+2a^3 10^k<0$
第二个为
$u^2-(10^{2k}-2a 10^k-2a^2-2)u+a^4+2a^3 10^k+2a^2+2a10^k+1>0$
由于$10^k$远远大于a,根据韦达定理我们可以估算出两二次方程均有一个大解接近$10^{2k}$,一个小解接近$2a$
由于$0\lt u\le 2a$,我们只要小解确定的范围即可,由此可以得出
$u>u_1={(10^{2k}-2a10^k-2a^2)-\sqrt{(10^{2k}-2a10^k-2a^2)^2-4(a^4+2a^3 10^k)}}/2$
$u<u_2={(10^{2k}-2a 10^k-2a^2-2)-\sqrt{(10^{2k}-2a 10^k-2a^2-2)^2-4(a^4+2a^3 10^k+2a^2+2a10^k+1)}}/2$
但是$u_1,u_2$的表达式均不容易计算,我们只知道它们略小于$2a$,于是我们可以根据方程另外表示为
$u_1={a^4+2a^3 10^k+u_1}/{10^{2k}-2a10^k-2a^2}$
$u_2={a^4+2a^3 10^k+2a^2+2a10^k+1+u_2}/{10^{2k}-2a 10^k-2a^2-2}$
我们可以稍微放缩得出
${2a^3 10^k+a^4}/{10^{2k}-2a10^k-2a^2}<u<{2a^3 10^k+a^4+2a^2+2a10^k+1+2a}/{10^{2k}-2a 10^k-2a^2-2}$
也就是要求小区间$({2a^3 10^k+a^4}/{10^{2k}-2a10^k-2a^2}, {2a^3 10^k+a^4+2a10^k+2a^2+1+2a}/{10^{2k}-2a 10^k-2a^2-2})$里面包含整数$u$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-19 21:21:05 来自手机 | 显示全部楼层
进一步,得出u的不等式后,我们是否可以进一步确定a的范围,如果可以,那么就可以迅速求出更大的范围
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-4-19 21:58:17 | 显示全部楼层
mathe 发表于 2018-4-19 21:06
我们可以穷举$a=\floor(\sqrt(n))$,在$a$确定时,通常$k$也可以直接确定(最多两种)
于是这时我们设$n-a^ ...

我的思路类似,但是想找到下一个数还是有点困难
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-19 22:35:23 | 显示全部楼层
由于对于$0<x<1/2$有$1+x<1/{1-x}<1+x+2x^2$
我们可以继续放缩上面区间为
$((2a^3 10^{-k}+a^4*10^{-2k})(1+2a10^{-k}+2a^2 10^{-2k}), (2a^3 10^{-k}+a^4 10^{-2k}+2a10^{-k}+2a^2 10^{-2k}+10^{-2k}+2a 10^{-2k})(1+(2a10^{-k}+2a^2 10^{-2k}+2 10^{-2k})+2(2a10^{-k}+2a^2 10^{-2k}+2 10^{-2k})^2))$
其中$a^2$和$10^k$同阶,谁来整理一下,看它们差多少,这个就代表了第二部分和一个整数的差也不能差过这个距离,可以确定的是这个差必然是一个低阶无穷小,这也说明了这两个数据都非常接近一个整数,第一个略小,第二个略大,如果我们抛弃各种低阶无穷小,意味着$2a^3 10^{-k} +5a^4 10^{-2k}$非常接近整数
$({2a^3 10^k+a^4}/{10^{2k}-2a10^k-2a^2}, {2a^3 10^k+a^4+2a10^k+2a^2+1+2a}/{10^{2k}-2a 10^k-2a^2-2})$
我们记$U=2a^3 10^k+a^4, v=2a10^k+2a^2+1+2a, X=10^{2k}-2a 10^k-2a^2$,于是这个区间是$(U/X, {U+v}/{X-2})$
区间长度为${U+v}/{X-2}-U/X={vX+2U}/{X(X-2)}~=2a10^{-k}<2*10^{-k/2}$
${2a^3 10^k+a^4+2a10^k+2a^2+1+2a}/{10^{2k}-2a 10^k-2a^2-2} - (2a^3 10^{-k} +5a^4 10^{-2k})={2a10^k+2a^2+1+2a+4a^4 10^{-k}+4a^3 10^{-k}+10a^5 10^{-k}+10a^6 10^{-2k}+10a^4 10^{-2k}}/{10^{2k}-2a 10^k-2a^2-2}~=12a 10^{-k}<=12*10^{-k/2}$
由此我们知道对于稍微大一点的k,$2a^3 10^{-k} +5a^4 10^{-2k}$和整数的差别不超过$12*10^{-k/2}$
比如以n=8053139为例子,a=2837,k=7,$2a^3 10^{-k} +5a^4 10^{-2k}=4569.99702374738805$,
$12*10^{-k/2}=0.0037947331922020551983986722533192622404$
不过由此缩小a的搜索范围还有困难
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-4-20 08:28:18 | 显示全部楼层
本帖最后由 lsr314 于 2018-4-20 08:33 编辑


我是通过对$sqrt(1-4x)$泰勒展开得到上下界和差异的渐进式的,Mathematica计算有点慢,pari/gp溢出了,应该可以用2楼的思路,跳过一些a来优化计算速度
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-4-22 20:47:48 | 显示全部楼层
本帖最后由 王守恩 于 2018-4-23 05:31 编辑

基础资料:答案是在下面这群数里面。渴望大家还有更精细的方法!

\(\D 1^2+\frac{2×2^3}{1×10^1}-1=1\)

\(\D 2^2+\frac{2×3^3}{1×10^1}-1=8\)

\(\D 3^2+\frac{2×4^3}{1×10^2}-1=9\)

\(\D 4^2+\frac{2×5^3}{1×10^2}-1=17\)

\(\D 5^2+\frac{2×6^3}{1×10^2}-1=28\)

\(\D 6^2+\frac{2×7^3}{1×10^2}-1=41\)

\(\D 7^2+\frac{2×8^3}{1×10^2}-1=58\)

\(\D 8^2+\frac{2×9^3}{1×10^2}-1=77\)

\(\D 9^2+\frac{2×10^3}{1×10^3}-1=82\)

\(\D 10^2+\frac{2×11^3}{1×10^3}-1=101\)

\(\D 11^2+\frac{2×12^3}{1×10^3}-1=123\)

\(\D 12^2+\frac{2×13^3}{1×10^3}-1=147\)

\(\D 13^2+\frac{2×14^3}{1×10^3}-1=173\)

\(\D 14^2+\frac{2×15^3}{1×10^3}-1=201\)

\(\D 15^2+\frac{2×16^3}{1×10^3}-1=232\)

\(\D 16^2+\frac{2×17^3}{1×10^3}-1=264\)

\(\D 17^2+\frac{2×18^3}{1×10^3}-1=299\)

\(\D 18^2+\frac{2×19^3}{1×10^3}-1=336\)

\(\D 19^2+\frac{2×20^3}{1×10^3}-1=376\)

\(\D 20^2+\frac{2×21^3}{1×10^3}-1=417\)

\(\D 21^2+\frac{2×22^3}{1×10^3}-1=461\)

\(\D 22^2+\frac{2×23^3}{1×10^3}-1=507\)

\(\D 23^2+\frac{2×24^3}{1×10^3}-1=555\)

\(\D 24^2+\frac{2×25^3}{1×10^3}-1=606\)

\(\D 25^2+\frac{2×26^3}{1×10^3}-1=659\)

\(\D 26^2+\frac{2×27^3}{1×10^3}-1=714\)

\(\D 27^2+\frac{2×28^3}{1×10^3}-1=771\)

\(\D 28^2+\frac{2×29^3}{1×10^3}-1=831\)

\(\D 29^2+\frac{2×30^3}{1×10^3}-1=894\)

\(\D 30^2+\frac{2×31^3}{1×10^3}-1=958\)

\(\D 31^2+\frac{2×32^3}{1×10^4}-1=966\)

\(\D 32^2+\frac{2×33^3}{1×10^4}-1=1030\)

\(\D 33^2+\frac{2×34^3}{1×10^4}-1=1095\)

\(\D 34^2+\frac{2×35^3}{1×10^4}-1=1163\)

\(\D 35^2+\frac{2×36^3}{1×10^4}-1=1233\)

\(\D 36^2+\frac{2×37^3}{1×10^4}-1=1305\)

\(\D 37^2+\frac{2×38^3}{1×10^4}-1=1378\)

\(\D 38^2+\frac{2×39^3}{1×10^4}-1=1454\)

\(\D 75^2+\frac{2×76^3}{1×10^4}-1=5711\)

\(\D 98^2+\frac{2×99^3}{1×10^4}-1=9797\)

\(\D 998^2+\frac{2×999^3}{1×10^6}-1=997997\)

\(\D 2837^2+\frac{2×2838^3}{1×10^7}-1=8053139\)

\(\D 7794^2+\frac{2×7795^3}{1×10^8}-1=60755907\)

\(\D 9998^2+\frac{2×9999^3}{1×10^8}-1=99979997\)

\(\D 99998^2+\frac{2×99999^3}{1×10^{10}}-1=9999799997\)

\(\D 267423^2+\frac{2×267424^3}{1×10^{11}}-1=71515443427\)

\(\D 305687^2+\frac{2×305688^3}{1×10^{11}}-1=93445113269\)

\(\D 999998^2+\frac{2×999999^3}{1×10^{12}}-1=999997999997\)

\(\D 5135115^2+\frac{2×5135116^3}{1×10^{14}}-1=26369408771424\)

\(\D 9842379^2+\frac{2×9842380^3}{1×10^{14}}-1=96872443448748\)

\(\D 9982529^2+\frac{2×9982530^3}{1×10^{14}}-1=99650905131203\)

\(\D 9999998^2+\frac{2×9999999^3}{1×10^{14}}-1=99999979999997\)

\(\D 27409372^2+\frac{2×27409373^3}{1×10^{15}}-1=751273714618266\)

\(\D 58036522^2+\frac{2×58036523^3}{1×10^{16}}-1=3368237924952647\)

\(\D 59105821^2+\frac{2×59105822^3}{1×10^{16}}-1=3493498117381256\)

\(\D 99999998^2+\frac{2×99999999^3}{1×10^{16}}-1=9999999799999997\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 23:57 , Processed in 0.047107 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表