6174猜想 ，1955年，卡普耶卡(D.R.Kaprekar)研究了對四位數的一種變換：任給出四位數k0,用它的四個數字由大到小重新排列成一個四位數m,再減去它的反序數rev(m),得出數k1=m-rev(m),然後，繼續對k1重複上述變換，得數k2.如此進行下去，卡普耶卡發現，無論k0是多大的四位數， 只要四個數字不全相同，最多進行7次上述變換，就會出現四位數6174.
基本介紹
循環猜想,編程證明,編程過程,K數變換,如何變換,怎樣達到,
循環猜想
6174
因數分解：2*3^2*7^3，科學家稱這個數為“自我拷貝數”。
例如:
k0=5298,k1=9852-2589=7263,k2=7632-2367=5265,k3=6552-2556=3996,k4=9963-3699=6264,k5=6642-2466=4176,k6=7641-1467=6174.
後來,這個問題就流傳下來,人們稱這個問題為"6174問題",上述變換稱為卡普耶卡變換,簡稱 K 變換.
一般地,只要在0,1,2,...,9中任取四個不全相等的數字組成一個整數k0(不一定是四位數),然後從k0開始不斷地作K變換,得出數k1,k2,k3,...,則必有某個m(m=<7),使得km=6174.
更一般地,從0,1,2,...,9中任取n個不全相同的數字組成一個十進制數k0(不一定是n位數),然後,從k0開始不斷地做K變換,得出k1,k2,...,那么結果會是怎樣的呢?已經知道的是:
n=2,只能形成一個循環:(27,45,09,81,63).例如取兩個數字7與3,連續不斷地做K變換,得出:36,27,45,09,81,27,...出現循環.
n=3,只能形成一個循環:(495).
n=4,只能形成一個循環:(6174).
n=5,已經發現三個循環:(53955,59994),(62964,71973,83952,74943),(63954,61974,82962,75933).
n=6,已經發現三個循環:(642654,...),(631764,...),(549945,...).
n=7,已經發現一個循環:(8719722,8649432,7519743,8429652,7619733,8439552,7509843,9529641...).
n=8,已經發現四個循環:(63317664),(97508421),(83208762,86526432,64308654...),(86308632,...)
n=9,已經發現三個循環:(864197532),(965296431,...),(965296431,...)
容易證明,對於任何自然數n>=2,連續做K變換必定要形成循環.這是因為由n個數字組成的數只有有限個的緣故.但是對於n>=5,循環的個數以及循環的長度(指每個循環中所包含數的個數)尚不清楚,這也是國內一些數學愛好者熱衷於研究的一個課題.
6174是一個非常神奇的數字。乍一看，它可能不這么明顯。但是，正如我們即將看到，任何人都可以通過簡單的減法去發現6174的特別之處。
編程證明
6174猜想：一個任意的四位正整數（全相同的除外，如1111）。將數字重新組合成一個最大的數和最小的數相減，重複這個過程，最多七步，必得6174。下面給出c源碼證明該猜想（1000-9999除去全相同的）：輸出量過於龐大故略去了輸出。
#include <cstdio>
#include <iostream>
using namespace std;
void insertSort(int r[],int len)
{
int i,k,tmp;
for(i=1;i<len;i++)
{
k=i-1;
tmp=r[i];
while(k>=0&&r[k]>tmp)
{
r[k+1]=r[k];
k--;
}
r[k+1]=tmp;
}
}
int main()
{
int u;
cin>>u;
for (int jj=0;jj<u;jj++)
{
int N,count,end,s;
int r[4];
int max,min;
cin>>N;
count=1;
end=0;
s=N;
while(end=6174)
{
r[0]=s%10;
r[1]=s/10%10;
r[2]=s/100%10;
r[3]=s/1000;
insertSort(r,4);
max=1000*r[3]+100*r[2]+10*r[1]+r[0];
min=1000*r[0]+100*r[1]+10*r[2]+r[3];
end=max-min;
count++;
s=end;
}
cout<<count;
}
}
using namespace std;
void insertSort(int r[],int len)
{
int i,k,tmp;
for(i=1;i<len;i++)
{
k=i-1;
tmp=r[i];
while(k>=0&&r[k]>tmp)
{
r[k+1]=r[k];
k--;
}
r[k+1]=tmp;
}
}
int main()
{
int u;
cin>>u;
for (int jj=0;jj<u;jj++)
{
int N,count,end,s;
int r[4];
int max,min;
cin>>N;
count=1;
end=0;
s=N;
while(end=6174)
{
r[0]=s%10;
r[1]=s/10%10;
r[2]=s/100%10;
r[3]=s/1000;
insertSort(r,4);
max=1000*r[3]+100*r[2]+10*r[1]+r[0];
min=1000*r[0]+100*r[1]+10*r[2]+r[3];
end=max-min;
count++;
s=end;
}
cout<<count;
}
}
編程過程
以上給出了6174猜想的c證明。下面用c演示了對任一猜想中的四位數計算過程，並總計了一共操作的步驟。編譯連線後，輸入輸出結果見下圖所示：
輸入：2000
輸出：
第1步：2000-0002=1998
第2步：9981-1899=8082
第3步：8820-0288=8532
第4步：8532-2358=6174
2000一共經過了4步得到了6174
#include<stdio.h>
void insertSort(int r[],int len){
int i,k,tmp;
for(i=1;i<len;i++){
k=i-1;
tmp=r[i];
while(k>=0&&r[k]>tmp){
r[k+1]=r[k];
k--;
}
r[k+1]=tmp;
}
}
void main(){
int N,count,end,s;
int r[4];
int max,min;
printf("請輸入一個任意的四位正整數（全相同的除外，如1111）:");
scanf("%d",&N);
count=0;
end=0;
s=N;
while(end!=6174){
r[0]=s%10;
r[1]=s/10%10;
r[2]=s/100%10;
r[3]=s/1000;
insertSort(r,4);
max=1000*r[3]+100*r[2]+10*r[1]+r[0];
min=1000*r[0]+100*r[1]+10*r[2]+r[3];
end=max-min;
count++;
printf("第%d步：%d%d%d%d-%d%d%d%d=%d%d%d%d\n",count,r[3],r[2],r[1],r[0],r[0],r[1],r[2],r[3],end/1000,end/100%10,end/10%10,end%10);
s=end;
}
printf("%d一共經過了%d步得到了6174\n",N,count);
}
K數變換
1949年，來自印度德伏拉利(Devlali)數學家D.R.Kaprekar設計了一個被稱為Kaprekar變換的操作。首先選擇一個四位不全相同的整數（即不是1111，2222，...），然後重新安排每一位上的數字得到一個最大數和最小數。接著，用最大的數減去最小的數從而獲得一個新的數。重複以上操作以不斷得到新的數。
這是一個簡單的變換，但Kaprekar卻發現它導致了一個令人吃驚的結果。讓我們試試吧，就從2005開始。重排這個數的四個位數得到最大數是5200，最小數是0025，即25（如果有一個以上的0，那就把0放左邊）。接下來的過程如下：
5200 - 0025 = 5175
7551 - 1557 = 5994
9954 - 4599 = 5355
5553 - 3555 = 1998
9981 - 1899 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174
7641 - 1467 = 6174
當我們得到6174這個數後，下一步都會得到6174這個數，以後每一步都不斷重複。我們把6174這個數稱為這個變換的核。所以6174是一個Kaprekar變換的核，但這是不是僅僅由一個數出發而得到6174的特殊例子？接下來我們可以看到6174不僅僅是Kaprekar變換的特例，有更多的驚喜等待著我們。讓我們用不同地點整數再試一次，比如1789。
9871 - 1789 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174
我們又得到了6174！
當我們從2005開始到6174需要7步操作，而1789需要3步。事實上，對於所有四位不全相同的數字通過以上操作都能達到6174這個唯一的數。很神奇，不是嗎？Kaprekar變換是如此的簡單卻從中發現了這個有趣的結果。當我們去思考為什麼會是這個神秘的數字6174時，這個過程會更加有趣。
如何變換
任何四位整數的四個位數都可以通過降序排列得到一個最大的數，而通過升序排列得到一個最小的數。比如有四個整數a,b,c,d他們之間的關係如下：
9 ≥ a ≥ b ≥ c ≥ d ≥ 0
且a,b,c,d不全相同，則最大的數是abcd而最小的數是dcba
我們可以通過標準的豎式減法來得到Kaprekar變換的結果：
a | b | c | d | |
- | d | c | b | a |
A | B | C | D |
而結果各位數存在以下關係：
D = 10 + d - a (因為 a > d) |
C = 10 + c - 1 - b = 9 + c - b (因為 b > c - 1) |
B = b - 1 - c (因為 b > c) |
A = a - d |
因為a>b>c>d。
如果得出的ABCD可以通過4個最初給出的數a,b,c,d表示的話，那么一個數便會通過Kaprekar變換重複出現。所以我們可以通過考慮{a, b, c, d}的所有可能的組合來判斷是否滿足以上條件，若符合的話便找到了Kaprekar變換的核。 每個組合（一共有4！=24種組合）給出一個含有四個未知數的聯立方程組，所以我們能夠解出a,b,c,d。
容易得出只有一種組合得到整數解且滿足9 ≥ a ≥ b ≥ c ≥ d ≥ 0的條件。這個組合便是ABCD=bdac，而這種情況下聯立方程組的解為a=7,b=6,c=4 和d=1，即ABCD=6174。 然而如果a=b=c=d，則方程無解。因此6174是Kaprekar變換下唯一不變的數字-我們的神秘數字的確是獨特的。
而對於三位數，同樣的現象發生了。例如對753進行Kaprekar變換，步驟如下：
753 - 357 = 396
963 - 369 = 594
954 - 459 = 495
954 - 459 = 495
數字495便是三位數在Kaprekar變換下的唯一的核，易驗證所有的三位數通過這個變換都會得到495，有興趣的讀者可以自行驗證。
達到6174最多需要幾步？
我第一次知道6174這個奇特的數是1975年，一個朋友告訴我的，當時給我留下了深刻的印象。我認為弄清楚這個現象為何發生比證明它要難得多。我用計算機去驗證是否所有的四位數（四位不全相同）能否通過有限步達到6174這個核。這個程式是大概50行的Visual Basic語言編寫，驗證了所有8991個符合條件的四位數。
下表顯示了運算結果：每個四位不全相同的四位數通過Kaprekar變換達到6174最多僅需7步。如果你用一個四位數通過Kaprekar變換並未在七步之內達到6174那就是你算錯了！
疊代次數 | 數字數 |
0 | 1 |
1 | 356 |
2 | 519 |
3 | 2124 |
4 | 1124 |
5 | 1379 |
6 | 1508 |
7 | 1980 |
怎樣達到
電腦程式驗證了所有8991個數，不過Malcolm Lines的文章解釋說驗證Kaprekar變換僅需驗證30個數就包含了所有可能的情況。
如前文一樣，設一個四位數abcd，滿足
9 ≥ a ≥ b ≥ c ≥ d ≥ 0
讓我們進行第一次減法。最大的數是1000a+100b+10c+d而最小的數是1000d+100c+10b+a。所以這一步減法過程如下：
1000a + 100b + 10c + d - (1000d + 100c + 10b + a)
= 1000(a-d) + 100(b-c) + 10(c-b) + (d-a)
= 999(a-d) + 90(b-c)
其中1<(a-d)<9，0<(b-c)<9。通過遍歷所有的可能情況，我們可以得到經過一次減法後結果的所有可能。如表1所示
表1：執行一次kaprekar變換後的所有可能結果
我們只需對a,b,c,d不全相等且符合條件a ≥ b ≥ c ≥ d的數進行考察，因此我們只需考慮 (a-d) ≥ (b-c)的情況。所以表中灰色部分(a-d) < (b-c)可以略去。
我們將表中每個數的四位數降序排列，得到新的最大數準備做第二次減法：
表2：準備做第二次減法的最大數
我們可以忽略掉表2中的重複部分（灰色區域），最後剩下30個數去執行後續的步驟。下圖顯示了這些數是如何達到6174的。
這30個數達到6174的路徑
從這個圖可以清楚地看到任何四位數最多僅需7步就可達到6174。即便如此，我仍然認為這是十分神秘的。我猜測這個數的發現者Kaprekar要不絕頂聰明要不就花了很多時間去想這個問題！
兩位數，五位數，六位或者更多...
我們已經看到四位數和三位數可以達到唯一的一個核，不過其他數呢？事實證明這樣得到的結果與上文相比遜色許多。讓我們試一個兩位數，比如28：
82 - 28 = 54
54 - 45 = 9
90 - 09 = 81
81 - 18 = 63
63 - 36 = 27
72 - 27 = 45
54 - 45 = 9
不用花太長時間就可發現兩位數會得到一個循環9→81→63→27→45→9。不像三位數或四位數那樣會得到一個唯一的核。
不過五位數呢？可以找到一個類似6174或495那樣的五位數的核嗎？要回答這個問題我們可以用和前面類似的方法去分析：驗證120種{a,b,c,d,e} 的可能組合符合條件
9 ≥ a ≥ b ≥ c ≥ d ≥ e ≥ 0
且
abcde - edcba = ABCDE
值得慶幸的是這個工作可以由計算機來完成，結果是五位數並不能得到一個唯一的核。不過所有的五位數通過Karprekar變換可以得到以下的三個循環：
71973→83952→74943→62964→71973
75933→63954→61974→82962→75933
59994→53955→59994
就像Malcolm Lines在他的文章中指出的那樣，驗證六位或更多位數需要耗費大量的時間，這項工作變得極其乏味！為了避免你重走舊路，下表列出了兩位數到十位數的驗證結果（更多結果可見Mathews Archive of Recreational Mathematics）。從中我們可以看到只有三位數和四位數得到了唯一的核。
