论坛 › 小题大作 › 大于n的最小高合成数

zeroieme 发表于 2019-4-17 14:13:45

大于n的最小高合成数

类似问题：小于n的最大高合成数
https://bbs.emath.ac.cn/thread-6248-1-1.html
https://blog.csdn.net/hcbbt/article/details/38580367

$n= 2 \times 10^40$


补充两个高合成数的资料
https://en.wikipedia.org/wiki/Highly_composite_number
http://wwwhomes.uni-bielefeld.de/achim/highly.html

liangbch 发表于 2019-4-17 15:03:38

8*9*25*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97*101 小于 2*10^40,可以作为一个基本值，可在此基础上调整

liangbch 发表于 2019-4-17 15:48:27

64*81*25*49*121*169*289*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83

zeroieme 发表于 2019-4-17 16:04:09

本帖最后由 zeroieme 于 2019-4-17 16:35 编辑

liangbch 发表于 2019-4-17 15:03
8*9*25*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*97*101 小于 2*10^40,可以作为一 ...

有什么好办法“调整”

And
64*81*25*49*121*169*289*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83<2*10^40

liangbch 发表于 2019-4-17 16:50:12

首先，这个数 可表示为 \({p_n}^{e_n} *... *{p_2}^{e_2} * {p_1}^{e_1}\), p1=2, p2=3,p3=5
如100以内的高度合成数中，最大的为 \( 60= 5^1 * 3^1 * 2^2 \),
高度合成数具有这样的性质，我归纳的，如有错，欢迎指正。
1.所有的指数 e1,e2,e3, en等， 必须大于等于1， 即中间的某个素因子的指数不能为0， 或者说，指数必须是连续的。不可能有素因子2，3，7，但没有素因子5的情况。
2.若 j>i,则\( e_j<= e_i \), 即大的素因子，其指数一定不超过小的素因子的指数。
3.最大的素因子的指数是1

知道了这个规律，编程就相对容易了。

zeroieme 发表于 2019-4-17 17:45:48

我用的笨办法是建立高合成数表，查找得。
1024*243*125*49*121*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83

mathe 发表于 2019-4-17 18:41:31

这应该属于凸规划问题。

liangbch 发表于 2019-4-17 19:19:51

编了个程序查了下，最佳答案是 83*79*73*71*67*61*59*53*47*43*41*37*31*29*23*19*17*13*(11^2)*(7^3)*(5^3)*(3^5)*(2^7), 总共 603979776因子
程序的速度非常快，不到1秒。

liangbch 发表于 2019-4-17 19:22:48

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct _node
{
        double logp;        // log(p)
        double logn;        // 高度合成数的对数，是累加的
        int e;                        // 指数
        double fn;                // 因子总数,
}NODE;

#define MAX_D        32                //最大深度为32,最大可查找具有32个素因子的高度合成数

//前32个素数
const int sp=
{
        2, 3, 5, 7, 11, 13, 17, 19,
        23, 29, 31, 37, 41, 43, 47, 53,
        59, 61, 67, 71, 73, 79, 83, 89,
        97, 101, 103, 107, 109, 113, 127, 131
};

// 更新 arr, arr, 直到arr
void init( NODE arr[], int n )
{
        int i;
        for (i=n;i>=1;i--)
        {
                arr.logp= log( (double)sp);         arr.e=1;
                if (i==n)
                {
                        arr.logn=arr.logp * arr.e;
                        arr.fn   = arr.e+1;
                }
                else
                {
                        arr.logn=arr.logn + (arr.logp * arr.e);// arr.logn 就是这个数的对数
                        arr.fn=arr.fn * (arr.e+1);                                //这个累计的，arr.fn就是这个数的所有因子数
                }
        }
}



// arr.e++;
// arr.e= arr.e(1<=j<pos）
// 进位不溢出，返回true, 否则返回false
// m 为最大查找深度
bool carry( NODE arr[], int pos , int m, double maxLogN)
{
        while (1)
        {
                if ( pos==m)   //不能在最高位做进位，因为最高位的指数必须是1，若超过1，则搜索结束
                        return false;

                arr.e++;
                arr.logn = arr.logn + (arr.logp * arr.e);
                arr.fn   = arr.fn * (arr.e+1);

                for (int i=pos-1;i>=1;i--)
                {
                        arr.e    = arr.e;
                        arr.logn = arr.logn + (arr.logp * arr.e);        // arr.logn 就是这个数的对数
                        arr.fn   = arr.fn * (arr.e+1);                                //这个累计的，arr.fn就是这个数的所有因子数
                }
               
                if ( arr.logn < maxLogN )
                        break;
                pos++;// 在arr处做进位失败，继续在更高位上做进位
        }
        return true;
}


void saveResult(NODE arr[], int eArr[], int m, double *pMaxFac)
{
        if ( arr.fn > *pMaxFac)
        {
                for (int j=1;j<=m;j++)
                        eArr=arr.e;//保存结果
                *pMaxFac= arr.fn;
        }
}

void print_factor_list(int eArr[], int m )
{
        double fac=1.0; //因子数
        printf("\n");
        for (int i=m;i>=1;i--)
        {
                fac *= (eArr+1.0);
                if (eArr==1)
                        printf("%d",sp);
                else
                        printf("(%d^%d)", sp, eArr);
                if ( i>1)
                        printf("*");
        }
        printf(",%lf factor\n",fac);
}

// 查找高度合成数
// eArr为各个素因子的指数，m为查找深度,返回最佳搜索结果的因子的个数，eArr[]存放因子
// arr和eArr不使用
double search_HCN( NODE arr[], int eArr[], double maxLogN, int m )
{
        double maxFac=0.0;        // 最大因子数

        init(arr,m);
        if ( arr.logn<maxLogN)//第一个搜索的组合就超范围，返回0.0
                saveResult(arr, eArr, m, &maxFac);                       
        else
        {
                for (int i=1;i<=m;i++)
                        eArr=0;
                return 0.0;
        }


        while (1)
        {
                // 将arr.e增加
                arr.e++;
                arr.logn = arr.logn + (arr.logp * arr.e);        // arr.logn 就是这个数的对数
                arr.fn   = arr.fn * (arr.e+1);       
               
                if (arr.logn <maxLogN)
                        saveResult(arr, eArr, m, &maxFac);        //保存结果
                else
                {
                        if ( carry( arr, 2, m, maxLogN) )//进位成功
                                saveResult(arr, eArr, m, &maxFac);       
                        else
                                break;        //进位失败，所有搜索完成
                }
        }
        return maxFac; //返回最大因子个数
}

void test_search_hcn()
{
        NODE arr ;
        int eArr;

        double logMaxN= log(2.0) + log(10.0)*40;//高度合查成数的对数不能超过max
        double sum;
        int i,maxDeep;//最大查找深度
       
        for (sum=0.0,i=0;i<MAX_D;i++)
        {
                sum += log( (double)(sp));
                if (sum<logMaxN)
                        maxDeep=i+1;
                else
                        break;
        }

        for (int m=maxDeep; m>=2;m--)        //查找素因子个数为m,m-1,..,3,2的情况下的高度合成数
        {
                search_HCN( arr, eArr, logMaxN, m );
                print_factor_list(eArr,m);
        }
}

int main(int argc, char* argv[])
{
        test_search_hcn();
        return 0;
}

liangbch 发表于 2019-4-17 20:07:00

5#的第三个条件，理由不充分。去掉。
修改后的代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct _node
{
        double logp;        // log(p)
        double logn;        // 高度合成数的对数，是累加的
        int e;                        // 指数
        double fn;                // 因子总数,
}NODE;

#define MAX_D        32                //最大深度为32,最大可查找具有32个素因子的高度合成数

//前32个素数
const int sp=
{
        2, 3, 5, 7, 11, 13, 17, 19,
        23, 29, 31, 37, 41, 43, 47, 53,
        59, 61, 67, 71, 73, 79, 83, 89,
        97, 101, 103, 107, 109, 113, 127, 131
};

// 更新 arr, arr, 直到arr
void init( NODE arr[], int n )
{
        int i;
        for (i=n;i>=1;i--)
        {
                arr.logp= log( (double)sp);         arr.e=1;
                if (i==n)
                {
                        arr.logn=arr.logp * arr.e;
                        arr.fn   = arr.e+1;
                }
                else
                {
                        arr.logn=arr.logn + (arr.logp * arr.e);// arr.logn 就是这个数的对数
                        arr.fn=arr.fn * (arr.e+1);                                //这个累计的，arr.fn就是这个数的所有因子数
                }
        }
}


// arr.e++;
// arr.e= arr.e(1<=j<pos）
// 进位不溢出，返回true, 否则返回false
// m 为最大查找深度
bool carry( NODE arr[], int pos , int m, double maxLogN)
{
        while (1)
        {
                if ( pos>m)               
                        return false;

                arr.e++;
                if ( pos<m)
                {
                        arr.logn = arr.logn + (arr.logp * arr.e);
                        arr.fn   = arr.fn * (arr.e+1);
                }
                else // pos==m
                {
                        arr.logn =(arr.logp * arr.e);
                        arr.fn   =(arr.e+1);
                }

                for (int i=pos-1;i>=1;i--)
                {
                        arr.e    = arr.e;
                        arr.logn = arr.logn + (arr.logp * arr.e);        // arr.logn 就是这个数的对数
                        arr.fn   = arr.fn * (arr.e+1);                                //这个累计的，arr.fn就是这个数的所有因子数
                }
               
                if ( arr.logn < maxLogN )
                        break;
                pos++;// 在arr处做进位失败，继续在更高位上做进位
        }
        return true;
}


void saveResult(NODE arr[], int eArr[], int m, double *pMaxFac)
{
        if ( arr.fn > *pMaxFac)
        {
                for (int j=1;j<=m;j++)
                        eArr=arr.e;//保存结果
                *pMaxFac= arr.fn;
        }
}

void print_factor_list(int eArr[], int m )
{
        double fac=1.0; //因子数
        printf("\n");
        for (int i=m;i>=1;i--)
        {
                fac *= (eArr+1.0);
                if (eArr==1)
                        printf("%d",sp);
                else
                        printf("(%d^%d)", sp, eArr);
                if ( i>1)
                        printf("*");
        }
        printf(",%lf factor\n",fac);
}

// 查找高度合成数
// eArr为各个素因子的指数，m为查找深度,返回最佳搜索结果的因子的个数，eArr[]存放因子
// arr和eArr不使用
double search_HCN( NODE arr[], int eArr[], double maxLogN, int m )
{
        double maxFac=0.0;        // 最大因子数

        init(arr,m);
        if ( arr.logn<maxLogN)//第一个搜索的组合就超范围，返回0.0
                saveResult(arr, eArr, m, &maxFac);                       
        else
        {
                for (int i=1;i<=m;i++)
                        eArr=0;
                return 0.0;
        }


        while (1)
        {
                // 将arr.e增加
                arr.e++;
                arr.logn = arr.logn + (arr.logp * arr.e);        // arr.logn 就是这个数的对数
                arr.fn   = arr.fn * (arr.e+1);       
               
                if (arr.logn <maxLogN)
                        saveResult(arr, eArr, m, &maxFac);        //保存结果
                else
                {
                        if ( carry( arr, 2, m, maxLogN) )//进位成功
                                saveResult(arr, eArr, m, &maxFac);       
                        else
                                break;        //进位失败，所有搜索完成
                }
        }
        return maxFac; //返回最大因子个数
}

void test_search_hcn()
{
        NODE arr ;
        int eArr;

        double logMaxN= log(2.0) + log(10.0)*40;//高度合查成数的对数不能超过max
        double sum;
        int i,maxDeep;//最大查找深度
       
        for (sum=0.0,i=0;i<MAX_D;i++)
        {
                sum += log( (double)(sp));
                if (sum<logMaxN)
                        maxDeep=i+1;
                else
                        break;
        }

        for (int m=maxDeep; m>=2;m--)        //查找素因子个数为m,m-1,..,3,2的情况下的高度合成数
        {
                search_HCN( arr, eArr, logMaxN, m );
                print_factor_list(eArr,m);
        }
}

int main(int argc, char* argv[])
{
        test_search_hcn();
        return 0;
}

查看完整版本: 大于n的最小高合成数