大于n的最小高合成数

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

类似问题：小于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[MAX_D]=
{
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[n], arr[n-1], 直到arr[1]
void init( NODE arr[], int n )
{
int i;
for (i=n;i>=1;i--)
{
arr[i].logp= log( (double)sp[i-1]); arr[i].e=1;
if (i==n)
{
arr[i].logn= arr[i].logp * arr[i].e;
arr[i].fn = arr[i].e+1;
}
else
{
arr[i].logn= arr[i+1].logn + (arr[i].logp * arr[i].e); // arr[1].logn 就是这个数的对数
arr[i].fn = arr[i+1].fn * (arr[i].e+1); //这个累计的，arr[1].fn就是这个数的所有因子数
}
}
}
// arr[pos].e++;
// arr[j].e= arr[pos].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[pos].e++;
arr[pos].logn = arr[pos+1].logn + (arr[pos].logp * arr[pos].e);
arr[pos].fn = arr[pos+1].fn * (arr[pos].e+1);
for (int i=pos-1;i>=1;i--)
{
arr[i].e = arr[pos].e;
arr[i].logn = arr[i+1].logn + (arr[i].logp * arr[i].e); // arr[1].logn 就是这个数的对数
arr[i].fn = arr[i+1].fn * (arr[i].e+1); //这个累计的，arr[1].fn就是这个数的所有因子数
}
if ( arr[1].logn < maxLogN )
break;
pos++; // 在arr[pos]处做进位失败，继续在更高位上做进位
}
return true;
}
void saveResult(NODE arr[], int eArr[], int m, double *pMaxFac)
{
if ( arr[1].fn > *pMaxFac)
{
for (int j=1;j<=m;j++)
eArr[j]=arr[j].e; //保存结果
*pMaxFac= arr[1].fn;
}
}
void print_factor_list(int eArr[], int m )
{
double fac=1.0; //因子数
printf("\n");
for (int i=m;i>=1;i--)
{
fac *= (eArr[i]+1.0);
if ( eArr[i]==1)
printf("%d",sp[i-1]);
else
printf("(%d^%d)", sp[i-1], eArr[i]);
if ( i>1)
printf("*");
}
printf(",%lf factor\n",fac);
}
// 查找高度合成数
// eArr为各个素因子的指数，m为查找深度,返回最佳搜索结果的因子的个数，eArr[]存放因子
// arr[0]和eArr[0]不使用
double search_HCN( NODE arr[], int eArr[], double maxLogN, int m )
{
double maxFac=0.0; // 最大因子数
init(arr,m);
if ( arr[1].logn<maxLogN) //第一个搜索的组合就超范围，返回0.0
saveResult(arr, eArr, m, &maxFac);
else
{
for (int i=1;i<=m;i++)
eArr[i]=0;
return 0.0;
}
while (1)
{
// 将arr[1].e增加
arr[1].e++;
arr[1].logn = arr[2].logn + (arr[1].logp * arr[1].e); // arr[1].logn 就是这个数的对数
arr[1].fn = arr[2].fn * (arr[1].e+1);
if (arr[1].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[MAX_D+1] ;
int eArr[MAX_D];
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[i]));
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[MAX_D]=
{
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[n], arr[n-1], 直到arr[1]
void init( NODE arr[], int n )
{
int i;
for (i=n;i>=1;i--)
{
arr[i].logp= log( (double)sp[i-1]); arr[i].e=1;
if (i==n)
{
arr[i].logn= arr[i].logp * arr[i].e;
arr[i].fn = arr[i].e+1;
}
else
{
arr[i].logn= arr[i+1].logn + (arr[i].logp * arr[i].e); // arr[1].logn 就是这个数的对数
arr[i].fn = arr[i+1].fn * (arr[i].e+1); //这个累计的，arr[1].fn就是这个数的所有因子数
}
}
}
// arr[pos].e++;
// arr[j].e= arr[pos].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[pos].e++;
if ( pos<m)
{
arr[pos].logn = arr[pos+1].logn + (arr[pos].logp * arr[pos].e);
arr[pos].fn = arr[pos+1].fn * (arr[pos].e+1);
}
else // pos==m
{
arr[pos].logn = (arr[pos].logp * arr[pos].e);
arr[pos].fn = (arr[pos].e+1);
}
for (int i=pos-1;i>=1;i--)
{
arr[i].e = arr[pos].e;
arr[i].logn = arr[i+1].logn + (arr[i].logp * arr[i].e); // arr[1].logn 就是这个数的对数
arr[i].fn = arr[i+1].fn * (arr[i].e+1); //这个累计的，arr[1].fn就是这个数的所有因子数
}
if ( arr[1].logn < maxLogN )
break;
pos++; // 在arr[pos]处做进位失败，继续在更高位上做进位
}
return true;
}
void saveResult(NODE arr[], int eArr[], int m, double *pMaxFac)
{
if ( arr[1].fn > *pMaxFac)
{
for (int j=1;j<=m;j++)
eArr[j]=arr[j].e; //保存结果
*pMaxFac= arr[1].fn;
}
}
void print_factor_list(int eArr[], int m )
{
double fac=1.0; //因子数
printf("\n");
for (int i=m;i>=1;i--)
{
fac *= (eArr[i]+1.0);
if ( eArr[i]==1)
printf("%d",sp[i-1]);
else
printf("(%d^%d)", sp[i-1], eArr[i]);
if ( i>1)
printf("*");
}
printf(",%lf factor\n",fac);
}
// 查找高度合成数
// eArr为各个素因子的指数，m为查找深度,返回最佳搜索结果的因子的个数，eArr[]存放因子
// arr[0]和eArr[0]不使用
double search_HCN( NODE arr[], int eArr[], double maxLogN, int m )
{
double maxFac=0.0; // 最大因子数
init(arr,m);
if ( arr[1].logn<maxLogN) //第一个搜索的组合就超范围，返回0.0
saveResult(arr, eArr, m, &maxFac);
else
{
for (int i=1;i<=m;i++)
eArr[i]=0;
return 0.0;
}
while (1)
{
// 将arr[1].e增加
arr[1].e++;
arr[1].logn = arr[2].logn + (arr[1].logp * arr[1].e); // arr[1].logn 就是这个数的对数
arr[1].fn = arr[2].fn * (arr[1].e+1);
if (arr[1].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[MAX_D+1] ;
int eArr[MAX_D];
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[i]));
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的最小高合成数

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。