多个互素合数之和的猜想(及验证代码)
  • 板块学术版
  • 楼主xxz_xxz
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/10/3 21:57
  • 上次更新2024/10/4 08:45:30
查看原帖
多个互素合数之和的猜想(及验证代码)
594127
xxz_xxz楼主2024/10/3 21:57

如题,这是一个数学证明题。对是我乱想的。

形式化地(我乱学的LaTeX好丑陋): mN,NN,xN,K={k1,...,km},{aK,isprime(a)=false}i=1mki=x{a,bKab,gcd(a,b)=1}\forall m \in \mathbb N , \exists N \in \mathbb N , \forall x \geq N , \exists \mathbb K = \{k_{1}, ..., k_{m}\}, \{\forall a \in \mathbb K, isprime(a) = false\} \land \sum_{i = 1}^{m}k_{i} = x \land \{\forall{a,b} \in \mathbb K\land a \neq b, gcd(a, b) = 1\}

对于 m=2m=2 ,可以证明 N=210N=210 时上述命题成立,且 210 是 N 可取的最小值。具体证明用了 ϕ(n)\phi(n)π(n)\pi(n) 之间的关系,即转化为求证 ϕ(n)>2π(n)\phi(n) > 2\pi(n) 。这个式子可以用一些高级的放缩来整,是我之前求助一个大佬搞的 (orz)。

现在将 mm 拓展到任意3及以上的正整数,这个命题仍成立吗?

下面有一段我用于分析 m=3m=3m=4m=4 的情况的代码(也是为什么我会把这帖发在洛谷上):

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<set>
#include<deque>
using namespace std;

typedef unsigned int UI;

const UI N = 65536;
UI subs[N], ntps[N];
bool ntp[N];
UI l = 0, r = 0, q = 0;

UI gcd(UI a, UI b)
{
	if(!(a && b))
	{
		cerr << "ERROR\n";
		return 0;
	}
	while(a = a % b)swap(a, b);
	return b;
}

void ask(UI m)
{
	for(UI i = 0; ntps[i] <= m - 34; ++i)
	{
		for(UI j = i + 1; ntps[j] <= m - 25 - ntps[i]; ++j)
		{
			UI k = m - ntps[i] - ntps[j];
			if(ntp[k] && gcd(ntps[i], ntps[j]) == 1 && gcd(ntps[i], k) == 1 &&
				gcd(ntps[j], k) == 1)
			{
				if(ntps[i] != 4 && ntps[i] != 9)
				cout << ntps[i] << ' ' << ntps[j] << ' ' << k << ' ' << m << endl;
				goto end;
			}
		}
	}
	cout << "impossible for " << m << endl;
	end:;
}

int main(int argc, char* argv[])
{
	for(UI i = 2; i < sqrt(N); ++i)
	{
		if(ntp[i])continue;
		for(UI j = 2; j != (N + i - 1) / i; ++j)ntp[i * j] = true;
	}
	//for(UI i = 0; i != N; ++i)cout << ntp[i] << ' ';
	for(UI i = 0, j = 0; i != N; ++i)
	{
		if(ntp[i])ntps[j++] = i;
	}
	while(true)
	{
		cin >> l >> r;
		l = max(l, (UI)38);
		for(UI i = l; i <= r; ++i)
		{
			ask(i);
		}
		cout << "next?(+x=next, 0=exit)\n";
		cin >> q;
		if(!q)break;
	}
	return 0;
}
//min possible = 38, max impossible = 175
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<set>
#include<deque>
using namespace std;

typedef unsigned int UI;

const UI N = 65536;
UI subs[N], ntps[N];
bool ntp[N];
UI l = 0, r = 0, q = 0;

UI gcd(UI a, UI b)
{
	if(!(a && b))
	{
		cerr << "ERROR\n";
		return 0;
	}
	while(a = a % b)swap(a, b);
	return b;
}

void ask(UI m)
{
	for(UI i = 0; ntps[i] <= m - 83; ++i)
	{
		for(UI j = i + 1; ntps[j] <= m - 79 - ntps[i]; ++j)
		{
			for(UI k = j + 1; ntps[k] <= m - 70 - ntps[i] - ntps[j]; ++k)
			{
				UI l = m - ntps[i] - ntps[j] - ntps[k];
				if(ntp[l] &&
					gcd(ntps[i], ntps[j]) == 1 &&
					gcd(ntps[i], ntps[k]) == 1 &&
					gcd(ntps[i], l) == 1 &&
					gcd(ntps[j], ntps[k]) == 1 &&
					gcd(ntps[j], l) == 1 &&
					gcd(ntps[k], l) == 1)
				{
					if(ntps[i] != 4 && ntps[i] != 9)
					cout << ntps[i] << ' ' << ntps[j] << ' ' << ntps[k] << ' ' <<
						l << ' ' << m << endl;
					goto end;
				}
			}
		}
	}
	cout << "impossible for " << m << endl;
	end:;
}

int main(int argc, char* argv[])
{
	for(UI i = 2; i < sqrt(N); ++i)
	{
		if(ntp[i])continue;
		for(UI j = 2; j != (N + i - 1) / i; ++j)ntp[i * j] = true;
	}
	//for(UI i = 0; i != N; ++i)cout << ntp[i] << ' ';
	for(UI i = 0, j = 0; i != N; ++i)
	{
		if(ntp[i])ntps[j++] = i;
	}
	while(true)
	{
		cin >> l >> r;
		l = max(l, (UI)38);
		for(UI i = l; i <= r; ++i)
		{
			ask(i);
		}
		cout << "next?(+x=next, 0=exit)\n";
		cin >> q;
		if(!q)break;
	}
	return 0;
}

这两段代码显然是分开的,前面计算 m=3m=3 ,后面是 m=4m=4 ,结果都不大(前者我注释了,后者我没注释但记得是五百多)

第一次发学术版,没怎么深入研究这个问题,请各路大佬多多包涵。如果这个猜想已经在学术界被研究了,还望请指个路;如果本贴某些内容有(非(违法违规或违反相关规定)的问题,请联系我,我会尽快改正。

2024/10/3 21:57
加载中...