数学之美-无限状态遇上质因数

    文章起名叫数学之美,并不是想蹭吴军博士《数学之美》的名气,当然这篇也不是书中的选段,只是能想到的只有“数学之美”才能描述对于数学的心情和赞美,因此借用“数学之美”这个词作为文章的标题的一部分。

    问题:
    曾经遇到过这样的一个需求,把业务数据根据对应的要求进行统计后,并用图表的方式展出。比如:
    需求描述
    过程如上图所示:
    1、业务数据根据不同的维度和要求进行统计
    2、基于统计数据进行展示或者再加工后展示

    这个需求有几个比较重要的要求:
    1、准确性:不能有遗漏和重复统计的情况。
    2、相同的业务数据要支持增量的统计项。
    3、无序性:所有的统计项对业务数据进行统计的顺序任意。

    为了满足准确性,我们可以为业务数据增加标记状态,用于表示数据已经被处理情况的描述,因为统计项的无限(在一个比较大的范围有限)增加,所以怎么用有限的字段表示无限的状态的标记;并且因为无序性,业务数据的状态不能限定统计项处理的次序。

    问题假设

     

    思路:
    暂时放下上面的具体问题,我们回想一下关于质数相关的一些知识。
    质因数的定义:质因数在数论里是指能整除给定正整数的质数。除了1以外,两个没有其他共同质因子的正整数称为互质。因为1没有质因子,1与任何正整数(包括1本身)都是互质。正整数的因数分解可将正整数表示为一连串的质因子相乘,质因子如重复可以指数表示。根据算术基本定理,任何正整数皆有独一无二的质因子分解式。

    比如:
    6=2*3 所以6的质因数为2和3
    12=2*2*3 = 2^2*3 所以12的质因数也是2和3。其中2^2为2的2次方。

    使用公式表示为:M = P1 * P2 * … * Pr,P1,P2…Pr位质数。

    下面我们证明质因数的唯一性:
    设:M = P1 * P2 * … * Pr = Q1 * Q2 * … * Qs,且P1 <= P2 <= … <= Pr, Q1 <= Q2 <= … <= Qs。
    显然,P1是不等于Q1的,不然两边同时约掉它,我们就得到一个更小的有两种分解方法的数。
    所以我们假设P1<Q1,那么我们用P1替换掉等式最右边中的Q1,得到一个比M更小的数T = P1 * Q2 * Q3 * … * Qs。
    令M’ = M –T,我们得到M’的两种表达:
    M’ = (P1 * P2 * … * Pr) – (P1 * Q2 * … * Qs) = P1 * (P2 * .. * Pr – Q2 * … * Qs) (1)
    M’ = (Q1 * Q2 * … * Qs) – (P1 * Q2 * … * Qs) = (Q1 – P1) * Q2 * … * Qs (2)
    因为Q1-P1为正整数,并且Q2…Qs为质数,因此M’也为正整数。
    从(1)可以看出P1是M’的质因数,所以P1是Q1-P1或者Q2 * … * Qs的质因数。这里引入一个推论:如果一个质数p是ab的因子,则p必须或是a的因子,或是b的因子。
    又Q2….Qs为素数,不可分解,因此P1是Q1-P1的因子。
    这样有某个整数h使P1*h=Q1-P1,移项得到Q1=P1h+P1=P1(h+1),这表明P1是Q1的一个因子,与Q1是一个质数的相矛盾。
    所以正整数皆有独一无二的质因子分解式。

    解题:
    回到我们的问题,我们可以使用质数作为每个统计项的编码,统计项编码的乘积合数作为业务数据的标记状态,如下图所示:

    理论解描述

    此时表示业务数据a分别被统计项A,统计项B和统计项C统计。
    代码如下:

    public static boolean isMatch(long status, long code) {
    	return status % code == 0;
    }
    

    但在实际应用中,质数的乘积非常大,100以内的素数乘积已经超出了64位长整型表示的范围,因此我们做一个折中,用一个预估的最大值值表示无限的状态为,这里我们取最大值为10000。
    30以内的质数分别为2,3,5,7,11,13,17,19,23,29,其乘积为6469693230没有超出64位长整型的表示范围,我们选择这10个质数做排列组合,并用”_”作为分割符,比如2_2_2_2,2_2_2_3等,如下图所示:

    真实解描述
    代码实现如下:

    public static boolean isMatch(String status, String code) {
    	if (StringUtils.isBlank(status) || StringUtils.isBlank(code)) {
    		return false;
    	}
    
    	String[] codeArray = code.split("_");
    	String[] statusArray = status.split("_");
    	if (codeArray.length > statusArray.length) {
    		return false;
    	}
    
    	for (int i = 0; i < codeArray.length; i++) {
    		if (Long.valueOf(statusArray[i]) % Long.valueOf(codeArray[i]) != 0) {
    			return false;
    		}
    	}
    
    	return true;
    }
    

    后记:
    针对以上问题,仍然可以找出另外的解法,但这里使用质数的方式表示状态位,更简洁,直观,更能体现数学之美。

    爱因斯坦:“美,本质上终究是简单性;”

    转载请注明:孙豪杰的博客 » 数学之美-无限状态遇上质因数

    喜欢 0
上一篇: 已是最新文章