[代數] 質數與排列組合

[songhome (爽轟)]

最近實務上遇到一個問題想請問一下數學上有沒有相關理論可以應用

假設現在有4家店(1 2 3 4號)，有一百個人，每個人可以任意去這四家店
因此對於這一百個人來說，都有可能會有2^4種組合

我想要用一個數字紀錄每個人去這4家店的狀況，

舉例來說
A去了1、2號，B去了3號，C去了1、4號
最簡單的紀錄方式是

A:1100
B:0010
C:1001

可是這種紀錄法當我要驗證每個人有沒有去過某家店的時候實務上不好驗證
(例如要看A有沒有去過第三家店，我要想辦法取出第三位數，在判斷是不是1)
所以後來想到可以利用質數，四家店代表2 3 5 7
則記錄方式變成去過的店家的數字相乘

A:2*3=6
B:5
C:2*7=14

所以在驗證的時候，我只要計算A除以某家店代表的數字後餘數是不是0就可以了
==============================================

但這個方法的問題在當我店家數很多的時候，儲存的數字膨脹太快
(其實也不用太多，20家就膨脹得很可怕了)
系統沒辦法儲存這麼大的數字，最大只能存到2^52

試算了一下，前33大質數相乘(2~137)就會超過2^52了(也就是店家數最多只能32家)
但理論上1~2^52應該會存在一個函數可以1對1對應到52家店的進入狀況才對
(也就是最多應可到52家)

可是這個函數不知道要怎麼找，不曉得有沒有相關理論可以套用呢?
謝謝






--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.249.20.43
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1494523885.A.5A2.html
推 Desperato   : 二進位 然後直接取對應bit
推 Desperato   : 即使不是電腦 我還是覺得A比較簡單又快..
抱歉內文沒有講清楚，不用第一個方法的原因有兩個

1.該系統沒有迴圈可以用，只能進行簡單的運算，因此要將N進位轉換為2進位不可行
(還是說有辦法不透過迴圈的方式轉換@@?)

2.如果直接存2近位的形式的話，儲存空間會太大
(文字長度1所占空間遠比數字長度1大)

所以才想說找找看有沒有其他數值的方法可以套用
※ 編輯: songhome (223.140.109.81), 05/12/2017 09:36:00
→ wohtp       : 這世上沒有數值方法不奠基於迴圈吧
→ wohtp       : 至少看來你可以lookup...那把二進位轉換表整個先在
→ wohtp       : 其他不是廢物的機器上面產生出來，轉換就直接查表
→ songhome    : 好像也只有這個方法了 感謝幫忙
推 LPH66       : 這樣說吧, 你要轉成質數乘積也是需要迴圈
→ LPH66       : 然後二進位法驗證的方式是 bitwise and
→ LPH66       : 我覺得除非是陽春到不的手持計算機不然都有這個吧?
→ LPH66       : (連 Windows 的小算盤都有了)
→ songhome    : 那套系統本身不是拿來計算的(計算乘積和除質數在不
→ songhome    : 同系統上)，上面的計算功能確實和小算盤差不多
→ wohtp       : Lookup其實也要用到迴圈，所以應該是OS甚至app的問
→ wohtp       : 題，機器本身實在不可能沒有迴圈
→ songhome    : 大概等於小算盤工程型的等級而已
→ songhome    : 是app的問題沒錯，但已經寫死無法更改
推 LPH66       : 打回去 app 作者要他改...
→ wohtp       : 所以你或許可以想一下，你的系統只是不准你明著做迴
→ wohtp       : 圈，它背後自己都在偷偷做
→ wohtp       : 所以可能有方法你自己不明著寫但是讓它做？