分数化小数，小数部分出现2021，求分母最小值

王守恩

王守恩 发表于 2021-2-23 08:17
(1)，2021太简单了， 把 2021 改成 202122232425262728，看看答案是多少
(2)，2021太简单了， 把 ...

自以为找到了通项公式(?)，看来不对(小数还凑凑，大数不行)。
一个最简分数\(\frac{n}{m}\)化为小数后发现，小数部分出现20212022，则这个分数的分母\(m\)最小是多少？

.·.·.

王守恩 发表于 2021-2-24 09:31
自以为找到了通项公式(?)，看来不对(小数还凑凑，大数不行)。
一个最简分数\(\frac{n}{m}\)化为小数后发 ...

其实小数部分出现10000001比20212022难好多。
用这个栗子就很好
（选用10000001是因为，1/10的小数部分的确是100000000......）
首先找到分母小于10的全部分数，可以发现1/10<0.1000000$1$<0.1000000$2$<1/9
接下来只需要找到一个即约分数x，满足0.1000000$1$<x<0.1000000$2$
Farey数表的性质保证了，我们可以用O(输入长度)的空间复杂度完成计算：
1/10<2/19<1/9
0.10000002<2/19
1/10<3/28<2/19
0.10000002<3/28
...
1/10<0.10000002<500000/4999999（Farey分数表证明了，全部分母小于等于4999999的分数中，比1/10大的就是500000/4999999）
而1/10<0.10000001<500001/5000009<0.10000002<500000/4999999
这直接证明了，5000009是最小的满足小数部分出现10000001的分母

hejoseph

用连分数的缩写形式

20212022/100000000=[0, 4, 1, 18, 15, 6, 3, 1, 1, 7, 1, 1, 5, 1, 1, 1, 2]
20212023/100000000=[0, 4, 1, 18, 15, 5, 1, 1, 3, 4, 3, 8, 1, 13]
[0, 4, 1, 18, 15, 6]=1735/8584

10000001/100000000=[0, 9, 1, 999999, 10]
10000002/100000000=[0, 9, 1, 499999, 10]
[0, 9, 1, 500000]=500001/5000009

王守恩

自以为找到了通项公式(?)，看来不对(小数还凑凑，大数不行)。继续凑热闹。
一个最简分数\(\frac{n}{m}\)化为小数后发现，小数部分出现2021 2022 2023...2047 2048(112位)，则这个分数的分母\(m\)最小是多少？

王守恩

王守恩 发表于 2021-2-24 19:02
自以为找到了通项公式(?)，看来不对(小数还凑凑，大数不行)。继续凑热闹。
一个最简分数\(\frac{n}{m}\)化 ...

一个最简分数\(\frac{n}{m}\)化为小数后发现，小数部分出现 0 0 0 0 0 0 (连续 6 个 0)，则这个分数的分母\(m\)最小是多少？

mathe

如果分数$n/m$是其小数表示中连续k为出现某个模式x,如果这连续k为是从小数后第u位开始的，那么${n 10^u}/m$的小数部分分母相同，其模式x正好出现在小数点之后，所以取这个分数（分子模m取余数)即可，所以总可以只分析模式x紧跟在小数点的情况。
于是这时，我们查看$n/m 10^k$,那么$x\le n/m 10^k \lt x+1$，即$x m \le n 10^k \lt (x+1)m$
也就是我们如果穷举$x, 2x, 3x,...,hx,...$这一系列数据的末k未，如果第一个$h x$在$10^k -h+1$到$10^k-1$之间或者是0，就符合要求。我们找到这样的第一个h就是最小的m.这个方案仅在x=0时不可行。这时我们需要在模式x后面添加一位非0数，依次搜索x1,x2,...,x9等模式即可。
另外还可以优化的一点是，在判断一个$hx$是否满足要求后，通常在x比较小时，我们不一定必须检查$(h+1)x$,而可以利用${10^k}/x$比较大时，直接跳跃一个比较大的步长。
比如x=2021时,k=4,我们第一步可以直接判断$4x=8084$不满足条件，然后后面依次每次h加5，如果发现某次h+5后，(h+5)x满足要求的h
所以x=2021时，只要判断 4x=8084, 9x=8189, 14x=8294,...,...,89x=9869, 94x=9974满足要求

王守恩

王守恩 发表于 2021-2-25 09:47
一个最简分数\(\frac{n}{m}\)化为小数后发现，小数部分出现 0 0 0 0 0 0 (连续 6 个 0)，则这个分数的分 ...

把答案晒一晒。
一个最简分数 \(\frac{n}{m}\) 化为小数后发现，小数部分出现..，则这个分数的分母 \(m\) 最小是多少？
\(\frac{11}{109}=0.1009\)      小数部分出现 1 0 0，
\(\frac{101}{1009}=0.10009\)     小数部分出现 1 0 0 0，
\(\frac{1001}{10009}=0.100009\)    小数部分出现 1 0 0 0 0，
\(\frac{10001}{100009}=0.1000009\)   小数部分出现 1 0 0 0 0 0，
\(\frac{100001}{1000009}=0.10000009\)  小数部分出现 1 0 0 0 0 0 0，
\(\frac{1000000}{1000001}=0.9999990000009\) 小数部分出现 0 0 0 0 0 0，

留一道题。一个最简分数 \(\frac{n}{m}\) 化为小数后发现(23836位)，
小数部分出现 2021 2022 2023 2024...7976 7977 7978 7979，则这个分数的分母 \(m\) 最小是多少？

王守恩

王守恩 发表于 2021-3-1 17:57
把答案晒一晒。
一个最简分数 \(\frac{n}{m}\) 化为小数后发现，小数部分出现..，则这个分数的分母 \( ...

给出答案。一个最简分数 \(\frac{n}{m}\) 化为小数后发现(23836位)，
小数部分出现 2021 2022 2023 2024...7976 7977 7978 7979，则这个分数的分母=99980001
留一道题。一个最简分数  \(\frac{n}{m}\)  化为小数后发现，
小数部分出现 123456789101112131415161718192021，则这个分数的分母  \(m\)  最小是多少？

王守恩

王守恩 发表于 2021-3-9 10:20
给出答案。一个最简分数 \(\frac{n}{m}\) 化为小数后发现(23836位)，
小数部分出现 2021 2022 2023 2024 ...

一个最简分数 \(\frac{n}{m}\) 化为小数后发现，
小数部分出现 1415926535，则这个分数的分母 \(m\) 最小是多少？
一个最简分数 \(\frac{n}{m}\) 化为小数后发现，
小数部分出现 14159265358979，则这个分数的分母 \(m\) 最小是多少？

王守恩

hejoseph 发表于 2021-2-24 16:01
用连分数的缩写形式

20212022/100000000=[0, 4, 1, 18, 15, 6, 3, 1, 1, 7, 1, 1, 5, 1, 1, 1, 2]

\(\pi\) 的连分数。《整数序列在线百科全书(OEIS)》A002486       
7, 106, 113, 33102, 33215, 66317, 99532, 265381, 364913, 1360120,
1725033, 25510582, 52746197, 78256779, 131002976, 340262731,.....

\(\pi\) 的误差分数。《整数序列在线百科全书(OEIS)》找不到
1, 5, 7, 64, 106, 113, 113, 24175, 32085, 33102, 99532, 265381, 1360120,
1725033, 18610450, 25510582, 78256779, 340262731,811528438, ..........