您了解質數嗎?

[曾阿牛 10]

這裡提供一個關於質數的問題

讓咱們先看看 9731 這個四位數　它有個性質　任意相臨的兩個位數都形成質數

也就是說　97, 73, 31 都是質數　　同樣的　3179 也具有相同的性質

但是呢 9731 是所有具有此性質的四位數中 最大的

問題來了　請找12位數中 具有此性質 的最大數　( 書上說有點難 )

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

更正一下問題　題目應該有限制 相臨兩位數所形成的質數要不同

否則 979797979797 就是最大的12位數了

此內容已被編輯, January 14, 2010 ,由 曾阿牛

[arthurduh1 10]

好題目~~~

因為兩位數的質數末碼必定為1,3,7,9，所以這個十二位數的後十一碼必定都是1,3,7,9

而個、十位都是1,3,7,9的質數有：11,13,17,19,31,37,71,73,79,97

而在十位是1的有4個；是3的有2個；是7的有3個；是9的有1個；

　在個位是1的有3個；是3的有2個；是7的有3個；是9的有2個；

所以這十一個數字第一個一定是1，最後一個是9。

最後一個是9，那倒數第二個一定是7。(←謝謝曾阿牛大大的提醒，這裡邏輯有問題)

接下來從最高位開始盡可能地配最大數字，

會得到1973717**79，接著就沒得填了。

因此捨而求其次19737131179

然後在最高位補上最大可能數6就得到結果

619737131179

(希望沒想錯......)

此內容已被編輯, January 16, 2010 ,由 arthurduh1

[曾阿牛 10]

為什麼說：『最後一個是9，那倒數第二個一定是7。』？

[arthurduh1 10]

喔

Sorry

順序沒有弄清楚，跳躍性思考了......

應該是：

「所以這十一個數字第一個一定是1，最後一個是9。

接下來從最高位開始盡可能地配最大數字，

第二位配九時(19********9)，

因為已經有19，剩下個位數為9的質數只有79，因此倒數第二位為7

依次配最大位數會得到1973717**79，接著就沒得填了。

因此捨而求其次19737131179」

其實填到19737****79時，

也可以觀察出剩下的個位數為7之質數只有17，

得到19737***179，

再填下去就解決了。

適時地使用此步驟可以省去一些配位數的時間。

此內容已被編輯, January 16, 2010 ,由 arthurduh1

[曾阿牛 10]

感謝 arthurduh1 大大的回答　　方便的話　可否請 arthurduh1 大大說說為什麼覺得這是個好題目

[arthurduh1 10]

就是有用到一些數學概念才能迅速找到答案呀！

硬湊要湊很久~~~

而且這題似乎是要找這種性質的最大可能數，

其實可以不用說是十二位數啦！

如果不限定這種數的話，

可以想想：「給你一組兩位數字的集合A，

請找出一個最大數目x，

使得x的每兩相鄰位數都在A裡面並不重複。」

這就是一種演算法了~~~

此內容已被編輯, January 18, 2010 ,由 arthurduh1

[曾阿牛 10]

原來如此　　個人認為　12 位數恰好是要運用那10個不重複的兩位數質數的最大的數量　

因為 再多就必發生重複　　所以 12 變成是個界線(限)

您提到的這推廣問題「給你一組兩位數字的集合A，請找出一個最大數目x，

使得x的每兩相鄰位數都在A裡面並不重複。」

雖然以 size 而言　A 最多只有100個元素　

但此問題的精神與圖論裡找漢米爾頓路徑的問題以及最佳化問題可說是大同小異

感謝您的回覆　　話說回來　質數的性質在本題裡扮演的角色 並非主角

此內容已被編輯, January 18, 2010 ,由 曾阿牛

[arthurduh1 10]

對呀！因為所有條件都到極限了。所以我說不用限定十二位數。

把它改成n進位就好啦！size不是問題。

沒錯，質數只是個包裝，而且是個性質不錯的包裝。

謝謝你囉！

(我好久po意見了說......)

[曾阿牛 10]

Re #8 arthurduh1　改成 n 進位！！！　　這又是我沒想到的！　真是個好的推廣