1樓：
如果以下思路沒什麼漏洞的話， 應該是成立的。
設數 的 進製下各位數和為 ，操作一次以後得到的數為 。
我們要估計的就是最少需要 次操作使得 變為0。
那麼有顯然有 ，並且具有
單調性：
個位無貢獻：
對於 ，此時 為Hamming weight, OEIS上有（其他進製下貌似沒有）。
A071542 - OEIS
斷言1：對於 ，有 f_(n) \Leftrightarrow \lfloor n/k \rfloor = k^" eeimg="1"/>，此時 。
斷言1表明，若經過一次操作以後，位數減小，則必減小一位，且經過操作以後一定為 。
推論1：對於任意自然數 ，在經過有限次操作變為0的過程中，必然經過 。
因此我們只需要考慮至少操作多少次使得 變為 ，次數記為 ，（若 ，表示變為0的次數，即 ）。事實上，
顯然那麼
那麼求和以後便有了下界
關於上界，可以試試用bounded integer compositions做更精準的估計，考察
對於 中的數，由於 都足夠大，這部分數「好」，若經過的數多，那麼總次數肯定會較小。
對於 中的數，這部分數「壞」，若經過的數教多，那麼總次數肯定會較大。
最壞情況便是經過了所有 中的數，此時必然有
接下來就要估計 ，如果鬆弛掉首位為正的限制，那麼該問題可以視為 個在 之間的整數求和為 的解的個數。該問題可參考這部分內容（超出了我的能力範圍）。
。如果還要做得更精細一點，提供乙個思路，就是每次運算元值上的變動只會影響到最低的 位上的數值，因此在變化過程中高位會取遍 中的全部數值，這部分做估計可能是有效的，但是應該依然需要bounded integer compositions。
2樓：
突然發現早上迷迷糊糊寫的玩意是偽證，試圖修復但是沒能成功…
所以就先把幾個很平凡，但是大概率著手做這件事的人不容易迴避的小結論丟出來好了…
我們先約定這樣的符號：
為 減去其各位數字和得到的數， 為 通過 變為 需要的運算元。其中， 為非負整數。
於是我們有：
若 ，則當且僅當 時，
若 n_2,n_1\in N,n_2\in N" eeimg="1"/>，則有
由2的條件和結論立即可以得到，
若下面提及的變數都非負，且使得函式有定義，則
對於任意乙個 位數 ，在 的序列中，必定出現了 （其實後半段都是廢話…）
接下來，我們定義一些新的東西…
為 減去其各位數字和再減一得到的數，為 通過 變為 需要的運算元。
特別地，我們定義
於是，與上面類似地，1,2,3,4對 和 也成立
(5）則被改寫為:
7.對於任意乙個 位數 ，在 的序列中，必定出現了 或 中的乙個
進一步，考慮用 描述 的遞推關係，有：
8.若 ，則有
在此基礎上有：
啊，突然覺得我壓出來的上下界太難看了…甚至不想寫出來了…
那就在這打住吧（果然我就是個廢物啦
3樓：Yehowah
乙個n位的k進製數的大小約為 ，其各位和約為 ，估計的次數約為 ，將這個數估計得精確一些，假如這個數為a，所需的次數約為 ，其中
為了更精確一些，可以將其各位和估計為 ，也就是說約為
更更精確一些（也照顧到k比較小的情況），可以將位數減少後的情況考慮進去。約為 ，化簡得
再精確一些，我們注意到最高位不是任意的，而是必定小於等於一開始的最高位。所以 ，化簡得
再精確下去我也不太確定應該怎麼精確了，如果再仔細摳前幾位的數字就太複雜了，不過考慮到在各位數字比較大的時候下降得也比較快，或許較小的數字出現頻率會更高，或許可以給整個式子乘乙個調節係數？
4樓：靈劍
拋個小小的磚，可以發現需要的運算元和這個數字的個位數是無關的，因為個位數總是在減去各位數字和的過程中相互抵消了，所以只考慮十位及以上構成的數字即可；進一步地，減去各位數字和之後的結果的個位數也不再重要，因此遞推式可以寫為：
這裡N為k進製中「十位」及以上構成的數字，即原始數n經過 運算的結果； 表示k進製下各位數字和。一般來說，有：
因此隨著N的增長， 經過不規則的週期性增長和突然下降（從類似9999增長到10000這樣的情況），會比較難處理，但如果我們簡單粗暴地假定 的平均值是
這樣的形式，C是某個和k有關的常數， 也理解為某種平均值意義下的次數，則 的增長速度（導數）約為
則這個對數積分函式的增長量級約為 ，可以猜想可能比較接近這個界。
注意到如果忽略c關於k的變化，猜想c大致是個固定範圍的數，則C隨著k的增加單調遞減，也就是 隨著k單調遞增，比例大約是 。但需要注意到這裡N是 ，所以對於相同的N來說，不同k下面本身N是不同的，考慮到這一點，如果改寫成n的函式，應當是
因為這個除以k的原因看上去反而是下降的。建議直接畫關於N的圖來研究可能比較合適。
當然這些都是純猜想，沒有經過證明。
5樓：Reciprocity
@qzane 給出了乙個下界，我這裡給個上界，k進製下n按照上述操作歸零的步數小於等於(n/k下取整+1)。
假設n的個位數字之和是d(n)，然後f(n)=n-d(n)。顯然，f(n+1)=f(n)當n的個位數字不是k-1的時候。
引理，f(n+1)>f(n)當n的個位數字是k-1的時候。
證明，只需證明d(n+1)<=d(n)即可。假設n的最後乙個不為k-1的數字在倒數第r位，為a。那麼n+1和n的倒數第r位之前數字相同，n+1的倒數r位數字為a+1，之後均為0。因此
d(n+1)-d(n)=a+1-(a+(r-1)(k-1))=-rk+r+k。
由於r和k均大等2，因此d(n+1)≤d(n)。引理得證。
推論，任意x≤y，我們有f(x)≤f(y)。
從而，我們知道f(a)=f(b)當且僅當a和b除了個位數字之外均相同。因此對於每個f(a)，有且僅有k個b使得f(a)=f(b)。
對於任意的n，我們考慮集合
S=設為。
由上面分析，S共有[n/k]個元素。因此j=[n/k]
由推論，我們知道f(n)必然為S中最大元。不放設t1>t2>…>tj=0。則有f(n)=t1。
由S定義，f(t1)屬於S，且f(t1)＜t1。因此f(t1)=某個ti，其中i大等2。繼續操作，至多j次操作必然歸零，因此至多需要j+1次操作可以歸零。
PS，不能給出具體值的主要原因是不知道f(t1)=哪個ti。如果有f(ts)=t(s+1)對所有s恆成立的話，很容易得出所有n的次數都是n/k下取整+1。可惜上面說的並不成立
如果4位數的密碼系統在每次輸入乙個數字後檢查之前的四個數字是否正確，那麼最多嘗試多少次可以得到密碼？
白楊樹 如果要算期望的話，那麼如之前的答主所說，用Markov chain就可以解決，但是從題主的描述來看的話，題主的問題應該是需要按鍵多少次才能遍歷所有的 個密碼組合。既然是這樣的話，我有乙個暴力的證明，就當拋磚引玉吧。以下證明基本不需要任何數學背景 先說結論 遍歷所有組合所需要的按鍵數目是 個。...
2，0，1，9，10這幾個數字組成乙個六位數字有多少種
先暴力排序，共有4 4 96種排序法。可是其中有一些和另一些是重複的，10和10可以交換。如果在一起，那就有C 4 2 2 12種96 12 84 108種，分別為10129,10192,10219,10291,10912,10921,11029,11092,12109,12910,19102,19...
把乙個數x通過數字相錯的方式拆成兩個數 x x ，則 x x 的影象是什麼樣的？
劍拔青雲 如果要構造這樣的函式 和 就需要對實數 做一定的修改 實數按十進位制數字分類的話可以分為整數 有限小數 無限迴圈小數 它們都是有理數 和無限不迴圈小數 無理數 對無限小數不作修改，對有限小數和整數作如下修改 將最後一位有效數字減1，之後的數字全用數字9填充，例如 等 詳細內容參照華東師大第...