python - 【闲来无事，大家都来发表下想法】一道数论题

Question

题目：一个数最后一位是6，移动到首位是原来数的三倍，求这个数
要求：速度最优

大神们快来踊跃探讨~~~

Answer 1

先贴上一版：

x = 6
xs = []
while True:
    xs.append(x // 3)
    x = x % 3 * 10 + x // 3
    if x == 6:
        print ''.join(str(x) for x in xs)
        break

输出：

2068965517241379310344827586

原理是手算，把每次得到的商的末位补到被除数的最后，然后继续除法，直到末位为6，且余数为0停止。

Answer 2

记所求数为x，为一个m+1位数，记为

$$ x = \overline {a6} $$

，其中a为一个m位数。则有：

$$ 3x = \overline {6a} $$

即

$$ 3 \times (10a+6) = 6 \times 10^m + a $$

化简得：

$$ 29a = 6(10^m-3) $$

即：

$${29 \over 6} = {{10^m-3} \over {a}} $$

因为：$$(29, 6) = 1$$，所以必须有：

$$ 10^m \equiv 3 (mod 29) $$

该方程最小解为

$$ m = 27 $$

由费马小定理，所有解为：

$$ m = 28k - 1 $$

代回原式得所有解：

$$ x = (10^{28k-1}-3) \times {6 \over 29} \times 10 + 6 $$

公式app无法显示，请在web端查看

---

Update: 费马小定理那里有些跳步，详细如下：

因为 29 是质数，且

$$ (29, 10) = 1$$

由费马小定理有

$$ 10^{28} \equiv 1 ( mod 29) $$

并且 28 为 10 模 29 的阶

从而形如

$$ 27 + 28k $$

也就是

$$ 28k - 1 $$

的数也是该方程的解，并且为所有解。

Answer 3

下午看到這題的時候就有了個想法, 手邊沒電腦只好等到現在...

後來看到 @citaret 的答案就發現剛好是反向的想法, 下面是我的作法:

x = 6
last_carry = 0
result = 6
radix = 10

while True:
    c1, x = pmod(x * 3, 10)
    c2, x = pmod(x + last_carry, 10)
    last_carry = c1 + c2
    
    if x==6 and last_carry==0:
        return result

    result += (x * radix)
    radix *= 10

想法就剛好是反過來, 我一步一步地乘上去

• 每次把 x 乘 3

  • 把個位數加上 last_carry 就是下次的 x

  • 把十位數的進位留下來當作下次的 last_carry

  • 做到 x==6 且無進位的時候

用圖來思考長這樣:

0 <-- last carry
 \
1 8 = 6 X 3
 \  (0 + 8 = 8)
2 4 = 8 X 3
 \  (1 + 4 = 5) 
1 5 = 5 X 3
...

用 timeit 稍微測了一下時間(各運行 1000000 次), 共測三次:

# first
dokelung: 17.301649590954185
citaret:  18.24915363173932

# second
dokelung: 19.257807812653482
citaret:  17.994877750985324

# third
dokelung: 17.0617663115263
citaret:  18.355605391785502

時間看起來差不多, 不過我自認為代碼沒有很漂亮...

---

我回答過的問題: Python-QA